Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.     

Global and local convergence of a nonmonotone SQP method for constrained nonlinear optimization

In this paper, we propose a robust sequential quadratic programming (SQP) method for nonlinear programming without using any explicit penalty function and filter. The method embeds the modified QP subproblem proposed by Burke and Han (Math Program 43:277–303, 1989) for the search direction, which overcomes the common difficulty in the traditional SQP methods, namely the inconsistency of the quadratic programming subproblems. A non-monotonic technique is employed further in a framework in which the trial point is accepted whenever there is a sufficient relaxed reduction of the objective function or the constraint violation function. A forcing sequence possibly tending to zero is introduced to control the constraint violation dynamically, which is able to prevent the constraint violation from over-relaxing and plays a crucial role in global convergence and the local fast convergence as well. We prove that the method converges globally without the Mangasarian–Fromovitz constraint qualification (MFCQ). In particular, we show that any feasible limit point that satisfies the relaxed constant positive linear dependence constraint qualification is also a Karush–Kuhn–Tucker point. Under the strict MFCQ and the second order sufficient condition, furthermore, we establish the superlinear convergence. Preliminary numerical results show the efficiency of our method.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

Global convergence of a robust filter SQP algorithm

We present a robust filter SQP algorithm for solving constrained optimization problems. This algorithm is based on the modified quadratic programming proposed by Burke to avoid the infeasibility of the quadratic programming subproblem at each iteration. Compared with other filter SQP algorithms, our algorithm does not require any restoration phase procedure which may spend a large amount of computation. The main advantage of our algorithm is that it is globally convergent without requiring strong constraint qualifications, such as Mangasarian–Fromovitz constraint qualification (MFCQ) and the constant rank constraint qualification (CRCQ). Furthermore, the feasible limit points of the sequence generated by our algorithm are proven to be the KKT points if some weaker conditions are satisfied. Numerical results are also presented to show the efficiency of the algorithm.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem

This paper is mainly concerned with the classical KKT reformulation and the primal KKT reformulation (also known as an optimization problem with generalized equation constraint (OPEC)) of the optimistic bilevel optimization problem. A generalization of the MFCQ to an optimization problem with operator constraint is applied to each of these reformulations, hence leading to new constraint qualifications (CQs) for the bilevel optimization problem. M- and S-type stationarity conditions tailored for the problem are derived as well. Considering the close link between the aforementioned reformulations, similarities and relationships between the corresponding CQs and optimality conditions are highlighted. In this paper, a concept of partial calmness known for the optimal value reformulation is also introduced for the primal KKT reformulation and used to recover the M-stationarity conditions.     

A special complementarity function revisited

ABSTRACT

Recently, a local framework of Newton-type methods for constrained systems of equations has been developed. Applied to the solution of Karush–Kuhn–Tucker (KKT) systems, the framework enables local quadratic convergence under conditions that allow nonisolated and degenerate KKT points. This result is based on a reformulation of the KKT conditions as a constrained piecewise smooth system of equations. It is an open question whether a comparable result can be achieved for other (not piecewise smooth) reformulations. It will be shown that this is possible if the KKT system is reformulated by means of the Fischer–Burmeister complementarity function under conditions that allow degenerate KKT points and nonisolated Lagrange multipliers. To this end, novel constrained Levenberg–Marquardt subproblems are introduced. They allow significantly longer steps for updating the multipliers. Based on this, a convergence rate of at least 1.5 is shown.     

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 efficient gradient method with approximate optimal stepsize for the strictly convex quadratic minimization problem

In this paper, a new type of stepsize, approximate optimal stepsize, for gradient method is introduced to interpret the Barzilai–Borwein (BB) method, and an efficient gradient method with an approximate optimal stepsize for the strictly convex quadratic minimization problem is presented. Based on a multi-step quasi-Newton condition, we construct a new quadratic approximation model to generate an approximate optimal stepsize. We then use the two well-known BB stepsizes to truncate it for improving numerical effects and treat the resulted approximate optimal stepsize as the new stepsize for gradient method. We establish the global convergence and R-linear convergence of the proposed method. Numerical results show that the proposed method outperforms some well-known gradient methods.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

A TRUST—REGION ALGORITHM FOR NONLINEAR INEQUALITY CONSTRAINED OPTIMIZATION

This paper presents a new trust-region algorithm for n-dimension nonlinear optimiza-tion subject to m nonlinear inequality constraints.Equivalent KKT conditions are derived,which is the basis for constructing the new algorithm.Global convergence of the algorithun to a first-order KKT point is eatablished under mild conditions on the trial steps.local quadratic convergence theorem is provcd for nondegenerate minimizer point.Numerical expcriment is prcsented to show the effectiveness of our approach.     

A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING

We propose a multidimensional filter SQP algorithm. The multidimensional filter technique proposed by Gould et al. [SIAM J. Optim., 2005] is extended to solve constrained optimization problems. In our proposed algorithm, the constraints are partitioned into several parts, and the entry of our filter consists of these different parts. Not only the criteria for accepting a trial step would be relaxed, but the individual behavior of each part of constraints is considered. One feature is that the undesirable link between the objective function and the constraint violation in the filter acceptance criteria disappears. The other is that feasibility restoration phases are unnecessary because a consistent quadratic programming subproblem is used. We prove that our algorithm is globally convergent to KKT points under the constant positive generators (CPG) condition which is weaker than the well-known Mangasarian-Fromovitz constraint qualification (MFCQ) and the constant positive linear dependence (CPLD). Numerical results are presented to show the efficiency of the algorithm.     

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.     

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.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

Projected Hessian algorithm with backtracking interior point technique for linear constrained optimization

In this paper, we propose a new trust-region-projected Hessian algorithm with nonmonotonic backtracking interior point technique for linear constrained optimization. By performing the QR decomposition of an affine scaling equality constraint matrix, the conducted subproblem in the algorithm is changed into the general trust-region subproblem defined by minimizing a quadratic function subject only to an ellipsoidal constraint. By using both the trust-region strategy and the line-search technique, each iteration switches to a backtracking interior point step generated by the trustregion subproblem. The global convergence and fast local convergence rates for the proposed algorithm are established under some reasonable assumptions. A nonmonotonic criterion is used to speed up the convergence in some ill-conditioned cases. Selected from Journal of Shanghai Normal University (Natural Science), 2003, 32(4): 7–13     

A superlinearly convergent method of quasi-strongly sub-feasible directions with active set identifying for constrained optimization

Combining the norm-relaxed sequential quadratic programming (SQP) method and the idea of method of quasi-strongly sub-feasible directions (MQSSFD) with active set identification technique, a new SQP algorithm for solving nonlinear inequality constrained optimization is proposed. Unlike the previous work, at each iteration of the proposed algorithm, the norm-relaxed quadratic programming (QP) subproblem only consists of the constraints corresponding to an active identification set. Moreover, the high-order correction direction (used to avoid the Maratos effect) is yielded by solving a system of linear equations (SLE) which also includes only the constraints and their gradients corresponding to the active identification set, therefore, the scale and the computation cost of the high-order correction directions are further decreased. The arc search in our algorithm can effectively combine the initialization processes with the optimization processes, and the iteration points can get into the feasible set after a finite number of iterations. Furthermore, the arc search conditions are weaker than the previous work, and the computation cost is further reduced. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ). If the strong second-order sufficient conditions are satisfied, then the active constraints are exactly identified by the identification set. Without the strict complementarity, superlinear convergence can be obtained. Finally, some elementary numerical results are reported.     

Properties of equation reformulation of the Karush–Kuhn–Tucker condition for nonlinear second order cone optimization problems

We give an equation reformulation of the Karush–Kuhn–Tucker (KKT) condition for the second order cone optimization problem. The equation is strongly semismooth and its Clarke subdifferential at the KKT point is proved to be nonsingular under the constraint nondegeneracy condition and a strong second order sufficient optimality condition. This property is used in an implicit function theorem of semismooth functions to analyze the convergence properties of a local sequential quadratic programming type (for short, SQP-type) method by Kato and Fukushima (Optim Lett 1:129–144, 2007). Moreover, we prove that, a local solution x* to the second order cone optimization problem is a strict minimizer of the Han penalty merit function when the constraint nondegeneracy condition and the strong second order optimality condition are satisfied at x*.     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.