A Feasible Sequential Linear Equation Method for Inequality Constrained Optimization
A Feasible Sequential Linear Equation Method for Inequality Constrained Optimization
复制标题
DOI：
10.1137/s1052623401383881
复制
发表时间：
2002-10
期刊：
影响因子：
--
通讯作者：
Yu-Fei Yang;Donghui Li;L. Qi
中科院分区：
文献类型：
--
作者：
Yu-Fei Yang;Donghui Li;L. Qi
本文利用有效集的一种估计&工作集的概念，提出了一种求解不等式约束优化问题的可行序列线性方程算法。在算法的每次迭代中，我们首先求解一个系数矩阵为m × m（其中m为约束个数）的线性方程组来计算工作集，然后求解一个子问题，该子问题由四个具有公共系数矩阵的简化线性方程组组成.与现有的无QP算法不同，该子问题只涉及与工作集对应的约束。不在工作集中的约束被忽略。因此，每个子问题的维数不是全维数。在不假设平稳点孤立的情况下，我们证明了该算法产生的序列的每一个聚点都是问题的KKT点。此外，在多次迭代之后，工作集变得独立于迭代，并且本质上与KKT点的活动集相同。换句话说，经过许多步骤后，只有那些在解中起作用的约束将被涉及到子问题中。在一定的条件下，证明了该方法的收敛速度是两步超线性的，甚至是Q-超线性的。我们还报告了一些初步的数值实验，以表明所提出的算法是可行的和有效的测试问题。
In this paper, by means of the concept of the working set, which is an estimate of the active set, we propose a feasible sequential linear equation algorithm for solving inequality constrained optimization problems. At each iteration of the proposed algorithm, we first solve one system of linear equations with a coefficient matrix of size m × m (where m is the number of constraints) to compute the working set; we then solve a subproblem which consists of four reduced systems of linear equations with a common coefficient matrix. Unlike existing QP-free algorithms, the subproblem is concerned with only the constraints corresponding to the working set. The constraints not in the working set are neglected. Consequently, the dimension of each subproblem is not of full dimension. Without assuming the isolatedness of the stationary points, we prove that every accumulation point of the sequence generated by the proposed algorithm is a KKT point of the problem. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. In other words, after finitely many steps, only those constraints which are active at the solution will be involved in the subproblem. Under some additional conditions, we show that the convergence rate is two-step superlinear or even Q-superlinear. We also report some preliminary numerical experiments to show that the proposed algorithm is practicable and effective for the test problems.