A superlinearly convergent norm-relaxed SQP method of strongly sub-feasible directions for constrained optimization without strict complementarity

In this paper, a kind of optimization problems with nonlinear inequality constraints is discussed. Combined the ideas of norm-relaxed SQP method and strongly sub-feasible direction method as well as a pivoting operation, a new fast algorithm with arbitrary initial point for the discussed problem is presented. At each iteration of the algorithm, an improved direction is obtained by solving only one direction finding subproblem which possesses small scale and always has an optimal solution, and to avoid the Maratos effect, another correction direction is yielded by a simple explicit formula. Since the line search technique can automatically combine the initialization and optimization processes, after finite iterations, the iteration points always get into the feasible set. The proposed algorithm is proved to be globally convergent and superlinearly convergent under mild conditions without the strict complementarity. Finally, some numerical tests are reported.     

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

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

Simple Sequential Quadratically Constrained Quadratic Programming Feasible Algorithm with Active Identification Sets for Constrained Minimax Problems

In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

A feasible descent SQP algorithm for general constrained optimization without strict complementarity

In this paper, a class of optimization problems with equality and inequality constraints is discussed. Firstly, the original problem is transformed to an associated simpler problem with only inequality constraints and a parameter. The later problem is shown to be equivalent to the original problem if the parameter is large enough (but finite), then a feasible descent SQP algorithm for the simplified problem is presented. At each iteration of the proposed algorithm, a master direction is obtained by solving a quadratic program (which always has a feasible solution). With two corrections on the master direction by two simple explicit formulas, the algorithm generates a feasible descent direction for the simplified problem and a height-order correction direction which can avoid the Maratos effect without the strict complementarity, then performs a curve search to obtain the next iteration point. Thanks to the new height-order correction technique, under mild conditions without the strict complementarity, the globally and superlinearly convergent properties are obtained. Finally, an efficient implementation of the numerical experiments is reported.     

A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints

This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems

In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems.     

多目标非线性规划的可行方向交互算法

本文提出一个求解多目标非线性规划问题的交互规划算法．在每一轮迭代中,此法仅要求决策者提供目标间权衡比的局部信息．算法中的可行方向是基于求解非线性规划问题的Topkis－Veinott法构千的．我们证明,在一定条件下,此算法收敛于问题的有效解．     

A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

An improved interior-type feasible QP-free algorithm for inequality constrained optimization problems

In this paper, an improved interior-type feasible QP-free algorithm for inequality constrained optimization problems is proposed. At each iteration, by solving three systems of linear equations with the same coefficient matrix, a search direction is generated. The algorithm is proved to be globally and superlinearly convergent under some mild conditions. Preliminary numerical results show that the proposed algorithm may be promising. Advantages of the algorithm include: the uniformly nonsingularity of the coefficient matrices without the strictly complementarity condition is obtained. Moreover, the global convergence is achieved even if the number of the stationary points is infinite.     

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

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

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

基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.     

Multisplitting Iteration Schemes for Solving a Class of Nonlinear Complementarity Problems

We consider several synchronous and asynchronous multisplitting iteration schemes for solving aclass of nonlinear complementarity problems with the system matrix being an H-matrix.We establish theconvergence theorems for the schemes.The numerical experiments show that the schemes are efficient forsolving the class of nonlinear complementarity problems.     

QPCOMP: A quadratic programming based solver for mixed complementarity problems

QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel [14], this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm. This material is based on research supported by National Science Foundation Grant CCR-9157632, Department of Energy Grant DE-FG03-94ER61915, and the Air Force Office of Scientific Research Grant F49620-94-1-0036.     

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

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

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

A New Superlinearly Convergent SQP Algorithm for Nonlinear Minimax Problems

In this paper, the nonlinear minimax problems are discussed. By means of the Sequential Quadratic Programming （SQP）, a new descent algorithm for solving the problems is presented. At each iteration of the proposed algorithm, a main search direction is obtained by solving a Quadratic Programming （QP） which always has a solution. In order to avoid the Maratos effect, a correction direction is obtained by updating the main direction with a simple explicit formula. Under mild conditions without the strict complementarity, the global and superlinear convergence of the algorithm can be obtained. Finally, some numerical experiments are reported.     

A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.