1

tl;dr 在具有大约 25,000 个变量的凸优化问题上，ECOS 运行到 max_iters 并以以下错误终止：

SolverError: Solver 'ECOS' failed. Try another solver, or solve with verbose=True for more information.

这是什么意思？

我正在尝试解决cvxpy中的凸优化问题，其中设置如下：

# <table> is a contingency table with 3 columns where the first two columns are unique item ids, and the third column describes the frequency of co-occurrence

import numpy as np
import cvxpy as cp

theta = cp.Variable([196, 10], nonneg=True)
phi = cp.Variable([10], nonneg=True) 
Q = cp.Parameter([2548, 10], nonneg=True) 
Q.value = np.ones([196, 10])/10

obj_func = 0
for m, row in enumerate(table):
    i, j, freq = row
    obj_func += freq * Q[m,:] * (cp.log(theta[i,:]) + cp.log(theta[j,:]) + cp.log(phi)- cp.log(Q[m,:]))

objective = cp.Maximize(obj_func)
constraints = [
    cp.sum(phi) == 1,
    cp.sum(theta, axis=0) == 1,
]

problem = cp.Problem(objective, constraints)
opt_val = problem.solve()

使用 and 运行时verbose=True，max_iters=500输出如下所示：

ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -1.108e+05  +1e+06  1e+00  1e+00  1e+00  1e+00    ---    ---    0  0  - |  -  - 
 1  -1.571e+04  -1.265e+05  +1e+06  7e-01  1e+00  1e+00  9e-01  0.2387  5e-01   2  2  2 |  0  2
 2  -7.070e+04  -1.814e+05  +8e+05  8e-01  1e+00  2e+00  7e-01  0.3791  3e-01   1  2  2 |  1  0
 3  -1.869e+05  -2.975e+05  +5e+05  9e-01  1e+00  2e+00  4e-01  0.6988  5e-01   2  3  2 |  4  1
...
497  +4.782e+08  +4.782e+08  +4e-07  2e-03  5e-12  3e-04  3e-13  0.3208  9e-01   1  1  0 | 16  5
498  +4.782e+08  +4.782e+08  +4e-07  2e-03  5e-12  3e-04  3e-13  0.9791  1e+00   2  1  0 | 27  0
499  +4.782e+08  +4.782e+08  +4e-07  2e-03  5e-12  3e-04  3e-13  0.5013  1e+00   1  1  0 | 21  3
500  +4.782e+08  +4.782e+08  +4e-07  2e-03  5e-12  3e-04  3e-13  0.9791  1e+00   1  1  0 | 30  0
Maximum number of iterations reached, recovering best iterate (497) and stopping.

RAN OUT OF ITERATIONS (reached feastol=1.6e-03, reltol=8.3e-16, abstol=4.0e-07).
Runtime: 314.146930 seconds.

据我所知，这是一个完美标准的凸优化问题。然而，当我在它上面运行 ECOS 时，我达到了 max_iters 却没有收敛。重复max_iters = 500（与默认值 67 相比）并没有解决问题。

我的问题是，为什么会发生这种情况？ECOS 想告诉我什么？我的问题不可行吗？只是有太多变数需要处理吗？

4

1 回答 1

0

进行猜测，我怀疑这归结为缩放。原始成本和对偶成本非常接近，差距很小。也许对于这种情况，求解器公差设置得太紧了？

要尝试的事情：

  • 尝试重新调整您的公式，以使所有涉及的常数具有相似的大小。
  • 看看 ECOS 计算的解。很可能没问题 - 在这种情况下，您只需要调整求解器的终止标准。
于 2020-01-24T13:20:26.893 回答