求解不等式约束优化问题无严格互补松弛条件的QP-Free新算法

A New QP-Free Algorithm for Inequality Constrained Optimization without Strict Complementarity

本文针对不等式约束优化问题,结合Facchinei-Fischer-Kanzow精确有效集识别技术,给出一个新的线性方程组与辅助方向相结合的可行下降算法.算法每步迭代只需求解一个降维的线性方程组或计算一次辅助方向,且获取辅助方向的投影矩阵只涉及近似有效约束集中的元素,问题规模大为减少,且当迭代次数充分大时,只需求解一个降维的线性方程组.无需严格互补松弛条件,算法全局且一步超线性收敛.

In this paper, based on the Facchinei-Fischer-Kanzow active set identification technique, a new QP-Free Mgorithm is proposed for solving inequality constrained optimiza- tion problem. At each iteration, an auxiliary direction or a system of linear equations is computed to obtain a search direction. When the iteration is sufficiently large, only a sys- tem of linear equations is solved. In particular, the auxiliary direction is obtained by using a reduced matrix, the scale of which is much smaller than that of the Generalized Projec- tion Gradient matrix. Without strict complementarity, the new algorithm is proved to be globally convergent with a superlinear convergence rate under assumptions milder than the strong second order sufficient condition.