A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Logarithmic SUMT limits in convex programming

The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique (SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary, and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]), primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability. That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions, one of which suffices for strict complementarity. Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001     

A Lipschitzian error bound for monotone symmetric cone linear complementarity problem

We first discuss some properties of the solution set of a monotone symmetric cone linear complementarity problem (SCLCP), and then consider the limiting behaviour of a sequence of strictly feasible solutions within a wide neighbourhood of central trajectory for the monotone SCLCP. Under assumptions of strict complementarity and Slater’s condition, we provide four different characterizations of a Lipschitzian error bound for the monotone SCLCP in general Euclidean Jordan algebras. Thanks to the observation that a pair of primal-dual convex quadratic symmetric cone programming (CQSCP) problems can be exactly formulated as the monotone SCLCP, thus we obtain the same error bound results for CQSCP as a by-product.     

Error bounds for infinite systems of convex inequalities without Slater’s condition

The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints. We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do not assume that the Slater condition holds which has been required in almost all earlier papers. Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000     

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     

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     

On the volumetric path

We consider the logarithmic and the volumetric barrier functions used in interior point methods. In the case of the logarithmic barrier function, the analytic center of a level set is the point at which the central path intersects that level set. We prove that this also holds for the volumetric path. For the central path, it is also true that the analytic center of the optimal level set is the limit point of the central path. The only known case where this last property for the logarithmic barrier function fails occurs in case of semidefinite optimization in the absence of strict complementarity. For the volumetric path, we show with an example that this property does not hold even for a linear optimization problem in canonical form.     

Analyticity of weighted central paths and error bounds for semidefinite programming

The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual solutions to converge linearly with their duality gaps. This research was supported by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC.     

On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization

The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained.     

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.     

Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming

We prove the superlinear convergence of the primal-dual infeasible interior-point path-following algorithm proposed recently by Kojima, Shida, and Shindoh and by the present authors, under two conditions: (i) the semidefinite programming problem has a strictly complementary solution; (ii) the size of the central path neighborhood approaches zero. The nondegeneracy condition suggested by Kojima, Shida, and Shindoh is not used in our analysis. Our result implies that the modified algorithm of Kojima, Shida, and Shindoh, which enforces condition (ii) by using additional corrector steps, has superlinear convergence under the standard assumption of strict complementarity. Finally, we point out that condition (ii) can be made weaker and show the superlinear convergence under the strict complementarity assumption and a weaker condition than (ii).     

Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications

We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative, and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem, our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty method for solving irregular problems. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A spectral bundle method with bounds

Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. In addition, we introduce inexact null steps. This abolishes the need of computing exact eigenvectors for subgradients, which brings along significant advantages in theory and in practice. Encouraging preliminary computational results are reported. Received: February 1, 2000 / Accepted: September 26, 2001?Published online August 27, 2002 RID="*" ID="*"A preliminary version of this paper appeared in the proceedings of IPCO ’98 [12].     

On Implicit Active Constraints in Linear Semi-Infinite Programs with Unbounded Coefficients

The concept of implicit active constraints at a given point provides useful local information about the solution set of linear semi-infinite systems and about the optimal set in linear semi-infinite programming provided the set of gradient vectors of the constraints is bounded, commonly under the additional assumption that there exists some strong Slater point. This paper shows that the mentioned global boundedness condition can be replaced by a weaker local condition (LUB) based on locally active constraints (active in a ball of small radius whose center is some nominal point), providing geometric information about the solution set and Karush-Kuhn-Tucker type conditions for the optimal solution to be strongly unique. The maintaining of the latter property under sufficiently small perturbations of all the data is also analyzed, giving a characterization of its stability with respect to these perturbations in terms of the strong Slater condition, the so-called Extended-Nürnberger condition, and the LUB condition.     

On the generic properties of convex optimization problems in conic form

We prove that strict complementarity, primal and dual nondegeneracy of optimal solutions of convex optimization problems in conic form are generic properties. In this paper, we say generic to mean that the set of data possessing the desired property (or properties) has strictly larger Hausdorff dimension than the set of data that does not. Our proof is elementary and it employs an important result due to Larman [7] on the boundary structure of convex bodies. Received: September 1997 / Accepted: May 2000?Published online November 17, 2000     

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     

Smooth methods of multipliers for complementarity problems

This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows that this class of algorithms is effective at solving many of the standard complementarity test problems. Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999     

Generating and measuring instances of hard semidefinite programs

Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal–dual strictly complementary optimal solution pair. On the other hand, there exist Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification, e.g., Slater’s condition (strict feasibility) holds. Measures of strict feasibility, also called distance to infeasibility, have been used in complexity analysis, and, it is known that (near) loss of strict feasibility results in numerical difficulties. In addition, there exist SDP problems which have a zero duality gap but no strict complementary primal–dual optimal solution. We refer to these problems as hard instances of SDP. The assumption of strict complementarity is essential for asymptotic superlinear and quadratic rate convergence proofs. In this paper, we introduce a procedure for generating hard instances of SDP with a specified complementarity nullity (the dimension of the common nullspace of primal–dual optimal pairs). We then show, empirically, that the complementarity nullity correlates well with the observed local convergence rate and the number of iterations required to obtain optimal solutions to a specified accuracy, i.e., we show, even when Slater’s condition holds, that the loss of strict complementarity results in numerical difficulties. We include two new measures of hardness that correlate well with the complementarity nullity.     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

Primal-Dual Relationship Between Levenberg–Marquardt and Central Trajectories for Linearly Constrained Convex Optimization

We consider the minimization of a convex function on a bounded polyhedron (polytope) represented by linear equality constraints and non-negative variables. We define the Levenberg–Marquardt and central trajectories starting at the analytic center using the same parameter, and show that they satisfy a primal-dual relationship, being close to each other for large values of the parameter. Based on this, we develop an algorithm that starts computing primal-dual feasible points on the Levenberg–Marquardt trajectory and eventually moves to the central path. Our main theorem is particularly relevant in quadratic programming, where points on the primal-dual Levenberg–Marquardt trajectory can be calculated by means of a system of linear equations. We present some computational tests related to box constrained trust region subproblems.