Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function

An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported.     

Approximating quadratic programming with bound and quadratic constraints

Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998     

Augmented Lagrangians with Adaptive Precision Control for Quadratic Programming with Equality Constraints: Corrigendum and Addendum

In this paper we give corrections to our paper on an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints.     

Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP). We obtain tight bounds on the perturbations that allow interior-point methods to recover feasible and near-optimal solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present explicit bounds for SDP using the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and NT directions. Received: December 1999 / Accepted: January 2001?Published online March 22, 2001     

Primal and dual convergence of a proximal point exponential penalty method for linear programming

We consider the diagonal inexact proximal point iteration where f(x,r)=c ^T x+r∑exp[(A _i x-b _i )/r] is the exponential penalty approximation of the linear program min{c ^T x:Ax≤b}. We prove that under an appropriate choice of the sequences λ _k , ε _k and with some control on the residual ν ^k , for every r _k →0⁺ the sequence u ^k converges towards an optimal point u ^∞ of the linear program. We also study the convergence of the associated dual sequence μ _i ^k =exp[(A _i u ^k -b _i )/r _k ] towards a dual optimal solution. Received: May 2000 / Accepted: November 2001?Published online June 25, 2002     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A trust region method based on interior point techniques for nonlinear programming

An algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints is described. It applies sequential quadratic programming techniques to a sequence of barrier problems, and uses trust regions to ensure the robustness of the iteration and to allow the direct use of second order derivatives. This framework permits primal and primal-dual steps, but the paper focuses on the primal version of the new algorithm. An analysis of the convergence properties of this method is presented. Received: May 1996 / Accepted: August 18, 2000?Published online October 18, 2000     

Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

On the rate of convergence of sequential quadratic programming with nondifferentiable exact penalty function in the presence of constraint degeneracy

We analyze the convergence of a sequential quadratic programming (SQP) method for nonlinear programming for the case in which the Jacobian of the active constraints is rank deficient at the solution and/or strict complementarity does not hold for some or any feasible Lagrange multipliers. We use a nondifferentiable exact penalty function, and we prove that the sequence generated by an SQP using a line search is locally R-linearly convergent if the matrix of the quadratic program is positive definite and constant over iterations, provided that the Mangasarian-Fromovitz constraint qualification and some second-order sufficiency conditions hold. Received: April 28, 1998 / Accepted: June 28, 2001?Published online April 12, 2002     

A branch and cut algorithm for nonconvex quadratically constrained quadratic programming

We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality. Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods

The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance. Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000     

A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints

A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased. Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity, dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve quadratic convergence. Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000     

Continuity properties of the Karush-Kuhn-Tucker point set in quadratic programming problems

Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998     

Bound constrained quadratic programming via piecewise quadratic functions

1 , the smallest eigenvalue of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The paper describes the algorithm and its implementation including estimation of λ₁, how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive testing and comparison with other methods for constrained QP are given. Received May 1, 1997 / Revised version received March 17, 1998 Published online November 24, 1998     

An interior Newton method for quadratic programming

We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential. Received October 11, 1993 / Revised version received February 20, 1996 Published online July 19, 1999     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

Basis- and partition identification for quadratic programming and linear complementarity problems

Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus. Received April 9, 1996 / Revised version received April 27, 1998? Published online May 12, 1999