Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point

For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence. To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above. Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China.     

A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations （SSLE） algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.     

AN EFFECTIVE SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS

In this paper,a new globally convergent algorithm for nonlinear optimization prablems with equality and inequality constraints is presented. The new algorithm is of SQP type which determines a search direction by solving a quadratic programming subproblem per itera-tion. Some revisions on the quadratic programming subproblem have been made in such a way that the associated constraint region is nonempty for each point x generated by the algorithm, i. e. , the subproblems always have optimal solutions. The new algorithm has two important properties. The computation of revision parameter for guaranteeing the consistency of quadratic sub-problem and the computation of the second order correction step for superlinear convergence use the same inverse of a matrix per iteration, so the computation amount of the new algorithm will not be increased much more than other SQP type algorithms; Another is that the new algorithm can give automatically a feasible point as a starting point for the quadratic subproblems pe     

无严格互补松驰条件的序列线性方程组新算法

该文通过构造特殊形式的有效集来逼近KKT点处的有效集，给出了一个任意初始点下的序列线性方程组新算法，并证明了该算法在没有严格互补松驰条件的情况下具有全局收敛性和一步超线性收敛性。      

A SSLE-Type Algorithm of Quasi-Strongly Sub-Feasible Directions for Inequality Constrained Minimax Problems

In this paper, we discuss the nonlinear minimax problems with inequality constraints. Based on the stationary conditions of the discussed problems, we propose a sequential systems of linear equations (SSLE)-type algorithm of quasi-strongly sub-feasible directions with an arbitrary initial iteration point. By means of the new working set, we develop a new technique for constructing the sub-matrix in the lower right corner of the coefficient matrix of the system of linear equations (SLE). At each iteration, two systems of linear equations (SLEs) with the same uniformly nonsingular coefficient matrix are solved. Under mild conditions, the proposed algorithm possesses global and strong convergence. Finally, some preliminary numerical experiments are reported.     

不等式约束最优化无严格互补条件下的快速收敛序列线性方程组算法

本文讨论无严格互补性的非线性不等式约束最优化问题,建立了一个新的序列线性方程组算法。算法每次迭代只需解一个线性方程组或计算一次广义梯度投影,并不要求Lagrange函数的近似Hessian阵正定。在较弱的假设下,证明了算法的整体收敛性、强收敛性、超线性收敛性及二次收敛速度。还对算法进行了有效的数值试验。     

超线性与二次收敛序列线性方程组算法

本文,在无严格互补条件下,对非线性不等式约束最优化问题提出了一个新的序列线性方程组(简称SSLE)算法．算法有两个重要特征:首先,每次迭代,只须求解一个线性方程组或一个广义梯度投影阵,且线性方程组可以无解．其次,初始点可以任意选取．在无严格互补条件下,算法仍有全局收敛性、强收敛性、超线性收敛性及二次收敛性．文章的最后,还对算法进行了初步的数值实验．     

A Superlinearly Convergent SSLE Algorithm for Optimization Problems with Linear Complementarity Constraints

In this paper we study a special kind of optimization problems with linear complementarity constraints. First, by a generalized complementarity function and perturbed technique, the discussed problem is transformed into a family of general nonlinear optimization problems containing parameters. And then, using a special penalty function as a merit function, we establish a sequential systems of linear equations (SSLE) algorithm. Three systems of equations solved at each iteration have the same coefficients. Under some suitable conditions, the algorithm is proved to possess not only global convergence, but also strong and superlinear convergence. At the end of the paper, some preliminary numerical experiments are reported.     

基于有效约束识别技术的一个SSLE算法及其收敛性分析

基于一个有效约束识别技术, 给出了具有不等式约束的非线性最优化问题的一个可行SSLE算法. 为获得搜索方向算法的每步迭代只需解两个或三个具有相同系数矩阵的线性方程组. 在一定的条件下, 算法全局收敛到问题的一个KKT点. 没有严格互补条件, 在比强二阶充分条件弱的条件下算法具有超线性收敛速度.     

解不等式约束优化的新的序列线性方程组方法

提出一种新的序列线性方程组(SSLE)算法解非线性不等式约束优化问题.在算法的每步迭代,子问题只需解四个简化的有相同的系数矩阵的线性方程组.证明算法是可行的,并且不需假定聚点的孤立性、严格互补条件和积极约束函数的梯度的线性独立性得到算法的全局收敛性.在一定条件下,证明算法的超线性收敛率.     

最优化两个拓广的SQP和SSLE算法模型及其超线性和二次收敛性

给出一般约束最优化的序列二次规划（SQP）和序列线性方程组（SSLE）算法两个拓广的模型,详细分析和论证两个模型的局部超线性收敛性及二次收敛性条件,其中并不需要严格互补条件,拓广的模型及其收敛速度结果具有更广泛的适用性,为SQP和SSLE算法收敛速度的研究提供了更为完善和便利的理论基础。     

A sequential equality constrained quadratic programming algorithm for inequality constrained optimization

In this paper, the feasible type SQP method is improved. A new SQP algorithm is presented to solve the nonlinear inequality constrained optimization. As compared with the existing SQP methods, per single iteration, in order to obtain the search direction, it is only necessary to solve equality constrained quadratic programming subproblems and systems of linear equations. Under some suitable conditions, the global and superlinear convergence can be induced.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. 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. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

一般约束优化基于识别函数的模松弛算法

借助于半罚函数和产生工作集的识别函数以及模松弛SQP算法思想, 本文建立了求解带等式及不等式约束优化的一个新算法. 每次迭代中, 算法的搜索方向由一个简化的二次规划子问题及一个简化的线性方程组产生. 算法在不包含严格互补性的温和条件下具有全局收敛性和超线性收敛性. 最后给出了算法初步的数值试验报告.     

A type of efficient feasible SQP algorithms for inequality constrained optimization

In this paper, motivated by Zhu et al. methods [Z.B. Zhu, K.C. Zhang, J.B. Jian, An improved SQP algorithm for inequality constrained optimization, Math. Meth. Oper. Res. 58 (2003) 271-282; Zhibin Zhu, Jinbao Jian, An efficient feasible SQP algorithm for inequality constrained optimization, Nonlinear Anal. Real World Appl. 10(2) (2009) 1220-1228], we propose a type of efficient feasible SQP algorithms to solve nonlinear inequality constrained optimization problems. By solving only one QP subproblem with a subset of the constraints estimated as active, a class of revised feasible descent directions are generated per single iteration. These methods are implementable and globally convergent. We also prove that the algorithms have superlinear convergence rate under some mild conditions.     

A TRULY GLOBALLY CONVERGENT FEASIBLE NEWTON-TYPE METHOD FOR MIXED COMPLEMENTARITY PROBLEMS

Typical solution methods for solving mixed complementarity problems either generatefeasible iterates but have to solve relatively complicated subproblems such as quadraticprograms or linear complementarity problems,or(those methods)have relatively simplesubproblems such as system of linear equations but possibly generate infeasible iterates.In this paper,we propose a new Newton-type method for solving monotone mixed com-plementarity problems,which ensures to generate feasible iterates,and only has to solve asystem of well-conditioned linear equations with reduced dimension per iteration.Withoutany regularity assumption,we prove that the whole sequence of iterates converges to a so-lution of the problem(truly globally convergent).Furthermore,under suitable conditions,the local superlinear rate of convergence is also established.     

不等式约束优化一个新型可行QP-free算法

本文对非线性不等式约束优化问题提出了一个新的可行 QP-free 算法. 新算法保存了现有算法的优点, 并具有以下特性: (1) 算法每次迭代只需求解三个具有相同系数矩阵的线性方程组, 计算量小; (2) 可行下降方向只需通过求解一个线性方程组即可获得, 克服了以往分别求解两个线性方程组获得下降方向和可行方向, 然后再做凸组合的困难;(3) 迭代点均为可行点, 并不要求是严格内点; (4) 算法中采用了试探性线搜索,可以进一步减少计算量; (5) 算法中参数很少,数值试验表明算法具有较好的数值效果和较强的稳定性.     

A SUPERLINEARLY CONVERGENT TRUST REGION ALGORITHM FOR LC^1 CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.     

Smoothing SQP algorithm for semismooth equations with box constraints

In this paper, in order to solve semismooth equations with box constraints, we present a class of smoothing SQP algorithms using the regularized-smooth techniques. The main difference of our algorithm from some related literature is that the correspondent objective function arising from the equation system is not required to be continuously differentiable. Under the appropriate conditions, we prove the global convergence theorem, in other words, any accumulation point of the iteration point sequence generated by the proposed algorithm is a KKT point of the corresponding optimization problem with box constraints. Particularly, if an accumulation point of the iteration sequence is a vertex of box constraints and additionally, its corresponding KKT multipliers satisfy strictly complementary conditions, the gradient projection of the iteration sequence finitely terminates at this vertex. Furthermore, under local error bound conditions which are weaker than BD-regular conditions, we show that the proposed algorithm converges superlinearly. Finally, the promising numerical results demonstrate that the proposed smoothing SQP algorithm is an effective method.