14

我已经建立了一个线性等式约束的优化问题，如下所示

sol0 = minimize(objective, x0, args=mock_df, method='trust-constr',
                bounds=bnds, constraints=cons,
                options={'maxiter': 250, 'verbose': 3})

是加权和函数，其objective系数/权重将被优化以使其最小化。由于我对系数和约束都有界限，因此我使用trust-constr了scipy.optimize.minimize.

最小化有效，但我不理解终止标准。根据trust-constr文档，它应该终止于xtol

算法将在 时终止tr_radius < xtol，其中tr_radius是算法中使用的信任区域的半径。默认值为 1e-8。

但是，verbose输出显示，终止确实是由barrier_tol参数触发的，如下面的清单所示

| niter |f evals|CG iter|  obj func   |tr radius |   opt    |  c viol  | penalty  |barrier param|CG stop|
|-------|-------|-------|-------------|----------|----------|----------|----------|-------------|-------|
C:\ProgramData\Anaconda3\lib\site-packages\scipy\optimize\_trustregion_constr\projections.py:182: UserWarning: Singular Jacobian matrix. Using SVD decomposition to perform the factorizations.
  warn('Singular Jacobian matrix. Using SVD decomposition to ' +
|   1   |  31   |   0   | -4.4450e+02 | 1.00e+00 | 7.61e+02 | 5.00e-01 | 1.00e+00 |  1.00e-01   |   0   |
C:\ProgramData\Anaconda3\lib\site-packages\scipy\optimize\_hessian_update_strategy.py:187: UserWarning: delta_grad == 0.0. Check if the approximated function is linear. If the function is linear better results can be obtained by defining the Hessian as zero instead of using quasi-Newton approximations.
  'approximations.', UserWarning)
|   2   |  62   |   1   | -2.2830e+03 | 6.99e+00 | 3.64e+02 | 7.28e-01 | 1.00e+00 |  1.00e-01   |   2   |
|   3   |  93   |   2   | -9.7651e+03 | 3.42e+01 | 5.52e+01 | 5.33e+00 | 1.00e+00 |  1.00e-01   |   2   |
|   4   |  124  |  26   | -4.9999e+03 | 3.42e+01 | 8.23e+01 | 9.29e-01 | 3.48e+16 |  1.00e-01   |   1   |
|   5   |  155  |  50   | -4.1486e+03 | 3.42e+01 | 5.04e+01 | 2.08e-01 | 3.48e+16 |  1.00e-01   |   1   |
...
|  56   | 1674  | 1127  | -1.6146e+03 | 1.77e-08 | 4.49e+00 | 3.55e-15 | 3.66e+33 |  1.00e-01   |   1   |
|  57   | 1705  | 1151  | -1.6146e+03 | 1.77e-09 | 4.49e+00 | 3.55e-15 | 3.66e+33 |  1.00e-01   |   1   |
|  58   | 1736  | 1151  | -1.6146e+03 | 1.00e+00 | 4.42e+00 | 3.55e-15 | 1.00e+00 |  2.00e-02   |   0   |
|  59   | 1767  | 1175  | -1.6146e+03 | 1.00e-01 | 4.42e+00 | 3.55e-15 | 1.00e+00 |  2.00e-02   |   1   |
|  60   | 1798  | 1199  | -1.6146e+03 | 1.00e-02 | 4.42e+00 | 3.55e-15 | 1.00e+00 |  2.00e-02   |   1   |
...
|  66   | 1984  | 1343  | -1.6146e+03 | 1.00e-08 | 4.42e+00 | 3.55e-15 | 1.00e+00 |  2.00e-02   |   1   |
|  67   | 2015  | 1367  | -1.6146e+03 | 1.00e-09 | 4.42e+00 | 3.55e-15 | 1.00e+00 |  2.00e-02   |   1   |
|  68   | 2046  | 1367  | -1.6146e+03 | 1.00e+00 | 4.36e+00 | 3.55e-15 | 1.00e+00 |  4.00e-03   |   0   |
|  69   | 2077  | 1391  | -1.6146e+03 | 1.00e-01 | 4.36e+00 | 3.55e-15 | 1.00e+00 |  4.00e-03   |   1   |
...
|  77   | 2325  | 1583  | -1.6146e+03 | 1.00e-09 | 4.36e+00 | 3.55e-15 | 1.00e+00 |  4.00e-03   |   1   |
|  78   | 2356  | 1583  | -1.6146e+03 | 1.00e+00 | 4.35e+00 | 3.55e-15 | 1.00e+00 |  8.00e-04   |   0   |
|  79   | 2387  | 1607  | -1.6146e+03 | 1.00e-01 | 4.35e+00 | 3.55e-15 | 1.00e+00 |  8.00e-04   |   1   |
...
|  87   | 2635  | 1799  | -1.6146e+03 | 1.00e-09 | 4.35e+00 | 3.55e-15 | 1.00e+00 |  8.00e-04   |   1   |
|  88   | 2666  | 1799  | -1.6146e+03 | 1.00e+00 | 4.34e+00 | 3.55e-15 | 1.00e+00 |  1.60e-04   |   0   |
|  89   | 2697  | 1823  | -1.6146e+03 | 1.00e-01 | 4.34e+00 | 3.55e-15 | 1.00e+00 |  1.60e-04   |   1   |
...
|  97   | 2945  | 2015  | -1.6146e+03 | 1.00e-09 | 4.34e+00 | 3.55e-15 | 1.00e+00 |  1.60e-04   |   1   |
|  98   | 2976  | 2015  | -1.6146e+03 | 1.00e+00 | 4.34e+00 | 3.55e-15 | 1.00e+00 |  3.20e-05   |   0   |
|  99   | 3007  | 2039  | -1.6146e+03 | 1.00e-01 | 4.34e+00 | 3.55e-15 | 1.00e+00 |  3.20e-05   |   1   |
...
|  167  | 5053  | 3527  | -1.6146e+03 | 1.00e-07 | 1.35e+01 | 2.12e-11 | 1.00e+00 |  2.05e-09   |   1   |
|  168  | 5084  | 3551  | -1.6146e+03 | 1.00e-08 | 1.35e+01 | 2.12e-11 | 1.00e+00 |  2.05e-09   |   1   |
|  169  | 5115  | 3575  | -1.6146e+03 | 1.00e-09 | 1.35e+01 | 2.12e-11 | 1.00e+00 |  2.05e-09   |   1   |
`xtol` termination condition is satisfied.
Number of iterations: 169, function evaluations: 5115, CG iterations: 3575, optimality: 1.35e+01, constraint violation: 2.12e-11, execution time: 3.8e+02 s.

很明显，一旦 ,tr_radius < xtol被tr_radius重置为其默认值1并且barrier param被减小。一旦barrier param < barrier_tol（即 1e-8） 和tr_radius < xtol，优化成功终止。该文件说关于barrier_tol

当存在不等式约束时，算法将仅在障碍参数小于 时终止barrier_tol。

这将解释在不等式约束的情况下的行为，但我所有的约束都是定义为字典的等式约束

con0 = {'type': 'eq', 'fun': constraint0}

有足够深入的人trust-constr向我解释这个吗？

4

2 回答 2

6

Do you have variables with upper bounds? Perhaps the solver is implementing these as constraints like var < UPPER_BOUND.

(I would put this as a comment if I had the reputation score to do so)

于 2019-07-27T10:25:13.713 回答
5

PreparedConstraints它通过类和initial_constraints_as_canonical函数中的函数与变量边界到不等式约束的内部转换相关_minimize_trustregion_constr联minimize(method='trust-constr')。

定义它的源代码可以在scipy/scipy/optimize/_trustregion_constr/minimize_trustregion_constr.py

负责的代码行是

if bounds is not None:
    if sparse_jacobian is None:
        sparse_jacobian = True
    prepared_constraints.append(PreparedConstraint(bounds, x0,
                                                   sparse_jacobian))

其中算法将定义的变量边界附加到已经准备好的最初定义的约束列表bounds中。后续线路PreparedConstraintprepared_constraints

# Concatenate initial constraints to the canonical form.
c_eq0, c_ineq0, J_eq0, J_ineq0 = initial_constraints_as_canonical(
    n_vars, prepared_constraints, sparse_jacobian)

将每个边界转换为两个不等式约束 (x > lb和x < ub) 并因此返回两倍于边界数量的附加约束。

_minimize_trustregion_constr然后检测那些不等式约束并正确选择算法tr_interior_point

# Choose appropriate method
if canonical.n_ineq == 0:
    method = 'equality_constrained_sqp'
else:
    method = 'tr_interior_point'

在下文中，该问题被视为最初包含不等式约束的问题，因此正确地终止于问题中描述的xtol条件和barrier_parameter条件。

感谢@Dylan Black 的提示，他的回答获得了赏金。

于 2019-07-29T08:25:01.730 回答