scipy.optimize.minimize(method='trust-constr') 不会在 xtol 条件下终止
scipy.optimize.minimize(method=’trust-constr’) doesn't terminate on xtol condition
我已经建立了一个具有线性等式约束的优化问题如下
sol0 = minimize(objective, x0, args=mock_df, method='trust-constr',
bounds=bnds, constraints=cons,
options={'maxiter': 250, 'verbose': 3})
objective是一个加权求和函数，coefficients/weights要优化使其最小化。由于我在系数和约束上有界限，所以我在 scipy.optimize.minimize.
中使用了 trust-constr 方法
最小化成功了，但我不明白终止条件。根据 trust-constr documentation 它应该在 xtol
终止
The algorithm will terminate when tr_radius < xtol, where tr_radius is the radius of the trust region used in the algorithm. Default is 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
When inequality constraints are present the algorithm will terminate only when the barrier parameter is less than barrier_tol.
这将解释不等式约束情况下的行为，但我所有的约束都是定义为字典的等式约束
con0 = {'type': 'eq', 'fun': constraint0}
有没有人深入 trust-constr 给我解释一下？
你有上限的变量吗？也许求解器将这些实现为约束，例如 var < UPPER_BOUND.
（如果我有这样的声誉分数，我会把它作为评论）
它通过PreparedConstraintsclass和函数_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 作为 PreparedConstraint 附加到已在 prepared_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），returns 因此额外的约束数量是边界数量的两倍。
_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 的提示，他的回答获得了赏金。
我已经建立了一个具有线性等式约束的优化问题如下
sol0 = minimize(objective, x0, args=mock_df, method='trust-constr',
bounds=bnds, constraints=cons,
options={'maxiter': 250, 'verbose': 3})
objective是一个加权求和函数，coefficients/weights要优化使其最小化。由于我在系数和约束上有界限，所以我在 scipy.optimize.minimize.
trust-constr 方法
最小化成功了，但我不明白终止条件。根据 trust-constr documentation 它应该在 xtol
The algorithm will terminate when
tr_radius < xtol, wheretr_radiusis the radius of the trust region used in the algorithm. Default is 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
When inequality constraints are present the algorithm will terminate only when the barrier parameter is less than
barrier_tol.
这将解释不等式约束情况下的行为，但我所有的约束都是定义为字典的等式约束
con0 = {'type': 'eq', 'fun': constraint0}
有没有人深入 trust-constr 给我解释一下？
你有上限的变量吗？也许求解器将这些实现为约束，例如 var < UPPER_BOUND.
（如果我有这样的声誉分数，我会把它作为评论）
它通过PreparedConstraintsclass和函数_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 作为 PreparedConstraint 附加到已在 prepared_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），returns 因此额外的约束数量是边界数量的两倍。
_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 的提示，他的回答获得了赏金。