线性无关假设如何影响非线性约束最优化算法

How does the linear independence assumption affect algorithms of nonlinear constrained optimization

首先综述非线性约束最优化最近的一些进展.首次定义了约束最优化算法的全局收敛性.注意到最优性条件的精确性和算法近似性之间的差异,并回顾等式约束最优化的原始的Newton型算法框架,即可理解为什么约束梯度的线性无关假设应该而且可以被弱化.这些讨论被扩展到不等式约束最优化问题.然后在没有线性无关假设条件下,证明了一个使用精确罚函数和二阶校正技术的算法可具有超线性收敛性.这些认知有助于接下来开发求解包括非线性半定规划和锥规划等约束最优化问题的更加有效的新算法.

t Firstly, some recent progress in nonlinear constrained optimization is surveyed in this paper. The terminology on the global convergence of algorithms for constrained optimization is officially defined for the first time. By noticing the gap between the exactness of optimality conditions and the approximation of algorithms, and looking into the initial Newton-type algorithmic framework for equality constrained optimization, one will understand why the assumption on the linear independence of gradients of the constraints should be and can be weakened. The discussions are also extended to the optimization with inequality constraints. Without the linear independence assumption, the local convergence of an algorithm using the exact penalty function and the second-order correction is then proved. These recognitions may help to develop more efficient new algorithms for constrained optimization including nonlinear semidefinite and conic programming in the future.