高速最適化

Question

私はのソリューションをスピードアップしようとしていますシンプルな凸状の問題を抱えています。私はシータとRTがNx1のある

のargmin（シータ）を解くいます。

私はcvxpy

import numpy as np 
from scipy.optimize import minimize 
import cvxpy 

np.random.seed(123) 

T = 50 
N = 5 
R = np.random.uniform(-1, 1, size=(T, N)) 

cvtheta = cvxpy.Variable(N) 
fn = -sum([cvxpy.log(1 + cvtheta.T * rt) for rt in R]) 

prob = cvxpy.Problem(cvxpy.Minimize(fn)) 
prob.solve() 

prob.status 
#'optimal' 

prob.value 
# -5.658335088091929 

cvtheta.value 
# matrix([[-0.82105079], 
#   [-0.35475695], 
#   [-0.41984643], 
#   [ 0.66117397], 
#   [ 0.46065358]]) 

しかし、これはあまりにも遅くなるので、私はscipyさんfmin_cgで勾配ベースの方法をしようとしていますR大きなためで簡単にこの問題を解決することができます。

goalfunです関数値とグラデーションを返すフレンドリ関数。

機能やグラデーションが正しいかを確認すること

def goalfun(theta, *args): 
    R = args[0] 
    N = R.shape[1] 
    common = (1 + np.sum(theta * R, axis=1))**-1 

    if np.any(common < 0): 
     return 1e2, 1e2 * np.ones(N) 

    fun = np.sum(np.log(common)) 

    thetaprime = np.tile(theta, (N, 1)).T 
    np.fill_diagonal(thetaprime, np.ones(N)) 
    grad = np.sum(np.dot(R, thetaprime) * common[:, None], axis=0) 

    return fun, grad 

：

goalfun(np.squeeze(np.asarray(cvtheta.value)), R) 
# (-5.6583350819293603, 
# array([ -9.12423065e-09, -3.36854633e-09, -1.00983679e-08, 
#   -1.49619901e-08, -1.22987872e-08])) 

しかし、これだけでゴミをもたらし、関係なく、methodの、反復回数などを解く（x0が実質的である場合Optimization terminated successfullyを生み出す唯一のものがあります最適シータ）

x0 = np.random.rand(R.shape[1]) 

minimize(fun=goalfun, x0=x0, args=R, jac=True, method='CG') 
# fun: 3.3690101669818775 
#  jac: array([-11.07449021, -14.04017873, -13.38560561, -5.60375334, -2.89210078]) 
# message: 'Desired error not necessarily achieved due to precision loss.' 
#  nfev: 25 
#  nit: 1 
#  njev: 13 
# status: 2 
# success: False 
#  x: array([ 0.00892177, 0.24404118, 0.51627475, 0.21119326, -0.00831957]) 

すなわちに等しいですcvxpyが扱いやすい、このように見えない無害な問題は、非凸型ソルバにとって完全に病理的であることが分かります。この問題は本当に厄介ですか、何か不足していますか？これをスピードアップするための代替手段は何ですか？

Answer 1

私は問題がthetaがlog引数が負になるようにすることは可能であるということであると信じています。あなたがこの問題を特定しているようだ、とこの「溶液」望ましいではないことをソルバーを提案するヒューリスティック試みとして、明らかに、この場合にはタプル(100,100*ones(N))を返すgoalfun持っています。しかし、より強力な条件はつまり、この「溶液」可能はないが、課されなければなりません。もちろん、これは適切な制約を設けることによって行うことができます。 （興味深いことに、cvxpyは自動的にこの問題を処理するために表示されます。）ここで

は、デリバティブを提供して悩まずに、サンプルの実行です。実現可能な初期見積り x0の使用に注意してください。

np.random.seed(123) 

T = 50 
N = 5 
R = np.random.uniform(-1, 1, size=(T, N)) 

def goalfun(theta, *args): 
    R = args[0] 
    N = R.shape[1] 
    common = (1 + np.sum(theta * R, axis=1))**-1 

    return np.sum(np.log(common)) 

def con_fun(theta, *args): 
    R = args[0] 

    return 1+np.sum(theta * R, axis=1) 


cons = ({'type': 'ineq', 'fun': lambda x: con_fun(x, R)}) 

x0 = np.zeros(R.shape[1]) 
minimize(fun=goalfun, x0=x0, args=R, constraints=cons) 

fun: -5.658334806882614 
jac: array([ 0.0019, -0.0004, -0.0003, 0.0005, -0.0015, 0. ]) message: 'Optimization terminated successfully.' 
nfev: 92 
nit: 12 
njev: 12 status: 0 success: True 
    x: array([-0.8209, -0.3547, -0.4198, 0.6612, 0.4605]) 

私はこれを実行すると、私は検索の中でいくつかの点でthetaの値はほとんど制約を満たすチェックされていることを示す、invalid value encountered in log警告を受けることに注意してください。しかし、その結果はcvxpyのそれにかなり近いです。 cvxpy.Problem公式で制約が明示的に課されたときにcvxpy解が変化するかどうかを調べることは興味深いでしょう。