A Sequential Quadratically Constrained Quadratic Programming Method of Feasible Directions

In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect, an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported. Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001), and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China.     

Stabilized Sequential Quadratic Programming

Recently, Wright proposed a stabilized sequential quadratic programming algorithm for inequality constrained optimization. Assuming the Mangasarian-Fromovitz constraint qualification and the existence of a strictly positive multiplier (but possibly dependent constraint gradients), he proved a local quadratic convergence result. In this paper, we establish quadratic convergence in cases where both strict complementarity and the Mangasarian-Fromovitz constraint qualification do not hold. The constraints on the stabilization parameter are relaxed, and linear convergence is demonstrated when the parameter is kept fixed. We show that the analysis of this method can be carried out using recent results for the stability of variational problems.     

Minimizing Quadratic Functions Subject to Bound Constraints with the Rate of Convergence and Finite Termination

A new active set based algorithm is proposed that uses the conjugate gradient method to explore the face of the feasible region defined by the current iterate and the reduced gradient projection with the fixed steplength to expand the active set. The precision of approximate solutions of the auxiliary unconstrained problems is controlled by the norm of violation of the Karush-Kuhn-Tucker conditions at active constraints and the scalar product of the reduced gradient with the reduced gradient projection. The modifications were exploited to find the rate of convergence in terms of the spectral condition number of the Hessian matrix, to prove its finite termination property even for problems whose solution does not satisfy the strict complementarity condition, and to avoid any backtracking at the cost of evaluation of an upper bound for the spectral radius of the Hessian matrix. The performance of the algorithm is illustrated on solution of the inner obstacle problems. The result is an important ingredient in development of scalable algorithms for numerical solution of elliptic variational inequalities.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

A New Superlinearly Convergent Strongly Subfeasible Sequential Quadratic Programming Algorithm for Inequality-Constrained Optimization

Combining the ideas of generalized projection and the strongly subfeasible sequential quadratic programming (SQP) method, we present a new strongly subfeasible SQP algorithm for nonlinearly inequality-constrained optimization problems. The algorithm, in which a new unified step-length search of Armijo type is introduced, starting from an arbitrary initial point, produces a feasible point after a finite number of iterations and from then on becomes a feasible descent SQP algorithm. At each iteration, only one quadratic program needs to be solved, and two correctional directions are obtained simply by explicit formulas that contain the same inverse matrix. Furthermore, the global and superlinear convergence results are proved under mild assumptions without strict complementarity conditions. Finally, some preliminary numerical results show that the proposed algorithm is stable and promising.     

一类0-1二次规划最优解的新算法

从矩阵的基础知识出发,给出了当目标函数矩阵是严格对角占优阵时,快速地获得0-1二次规划最优解的一个新算法;该方法具有很强的实用性,是此类问题的一个高效求解算法.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

Robust Recursive Quadratic Programming Algorithm Model with Global and Superlinear Convergence Properties

A new, robust recursive quadratic programming algorithm model based on a continuously differentiable merit function is introduced. The algorithm is globally and superlinearly convergent, uses automatic rules for choosing the penalty parameter, and can efficiently cope with the possible inconsistency of the quadratic search subproblem. The properties of the algorithm are studied under weak a priori assumptions; in particular, the superlinear convergence rate is established without requiring strict complementarity. The behavior of the algorithm is also investigated in the case where not all of the assumptions are met. The focus of the paper is on theoretical issues; nevertheless, the analysis carried out and the solutions proposed pave the way to new and more robust RQP codes than those presently available.     

Nonlinear Model Predictive Control via Feasibility-Perturbed Sequential Quadratic Programming

Model predictive control requires the solution of a sequence of continuous optimization problems that are nonlinear if a nonlinear model is used for the plant. We describe briefly a trust-region feasibility-perturbed sequential quadratic programming algorithm (developed in a companion report), then discuss its adaptation to the problems arising in nonlinear model predictive control. Computational experience with several representative sample problems is described, demonstrating the effectiveness of the proposed approach.     

A Structured Reduced Sequential Quadratic Programming and Its Application to a Shape Design Problem

The objective of this work is to solve a model one dimensional duct design problem using a particular optimization method. The design problem is formulated as an equality constrained optimization, called all at once method, so that the analysis problem is not solved until the optimal design is reached. Furthermore, the sparsity structure in the Jacobian of the linearized constraints is exploited by decomposing the variables into the design and flow parts. To achieve this, sequential quadratic programming with BFGS update for the reduced Hessian of the Lagrangian function is used with the variable reduction method which preserves the structure of the Jacobian in representing the null space basis matrix. By updating the reduced Hessians of which the dimension is the number of design variables, the storage requirement for the Hessians is reduced by a large amount. In addition, the flow part of the Jacobian can be computed analytically.The algorithm with a line search globalization is described. A global and local analysis is provided with a modification of the paper by Byrd and Nocedal [Mathematical Programming 49(1991) pp 285-323] in which they analyzed a similar algorithm with the orthogonal factorization method which assumes the orthogonality of the null space basis matrix. Numerical results are obtained and compared favorably with results from the black box method, unconstrained optimization formulation.