病态凸函数的快速优化

Question

我有一个简单的凸问题，我试图加快解决。我正在解的是

其中θ和rt是Nx1。在

我可以用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]])

对于cd2{cd2>

goalfun是一个scipy.minimize友好函数，返回函数值和渐变。在

^{pr2}$

确保功能和坡度正确：

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、迭代等等（产生Optimization terminated successfully的唯一条件是x0实际上等于最优θ）

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变为负。似乎您已经发现了这个问题，并让goalfun返回元组(100,100*ones(N))，显然，这是一个启发性的尝试，建议解算器这个“解决方案”不是更可取的。然而，必须施加一个更强大的条件，即这个“解决方案”是不可行的。当然，这可以通过提供适当的约束来实现。（有趣的是，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])

请注意，当我运行这个时，我得到一个invalid value encountered in log警告，表示在搜索的某个时刻，theta的值被选中，它几乎不满足约束条件。然而，结果与cvxpy的结果相当接近。如果在cvxpy.Problem公式中显式地施加约束，检查cvxpy解决方案是否会发生变化。在