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     

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     

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 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     

Robust optimization – methodology and applications

Robust Optimization (RO) is a modeling methodology, combined with computational tools, to process optimization problems in which the data are uncertain and is only known to belong to some uncertainty set. The paper surveys the main results of RO as applied to uncertain linear, conic quadratic and semidefinite programming. For these cases, computationally tractable robust counterparts of uncertain problems are explicitly obtained, or good approximations of these counterparts are proposed, making RO a useful tool for real-world applications. We discuss some of these applications, specifically: antenna design, truss topology design and stability analysis/synthesis in uncertain dynamic systems. We also describe a case study of 90 LPs from the NETLIB collection. The study reveals that the feasibility properties of the usual solutions of real world LPs can be severely affected by small perturbations of the data and that the RO methodology can be successfully used to overcome this phenomenon. Received: May 24, 2000 / Accepted: September 12, 2001?Published online February 14, 2002     

Box-inequalities for quadratic assignment polytopes

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope. Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001     

A branch-and-cut algorithm for capacitated network design problems

We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities, are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report on our computational experience using real-life data. Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999     

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     

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     

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     

Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming

One way of solving multiple objective mathematical programming problems is finding discrete representations of the efficient set. A modified goal of finding good discrete representations of the efficient set would contribute to the practicality of vector maximization algorithms. We define coverage, uniformity and cardinality as the three attributes of quality of discrete representations and introduce a framework that includes these attributes in which discrete representations can be evaluated, compared to each other, and judged satisfactory or unsatisfactory by a Decision Maker. We provide simple mathematical programming formulations that can be used to compute the coverage error of a given discrete representation. Our formulations are practically implementable when the problem under study is a multiobjective linear programming problem. We believe that the interactive algorithms along with the vector maximization methods can make use of our framework and its tools. Received April 7, 1998 / Revised version received March 1999?Published online November 9, 1999     

The many facets of linear programming

We examine the history of linear programming from computational, geometric, and complexity points of view, looking at simplex, ellipsoid, interior-point, and other methods. Received: June 22, 2000 / Accepted: April 4, 2001?Published online October 2, 2001     

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     

An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints

In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids. The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems. Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA and the combined DCA-branch-and-bound algorithm. Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000     

Objective-derivative-free methods for constrained optimization

We propose feasible descent methods for constrained minimization that do not make explicit use of the derivative of the objective function. The methods iteratively sample the objective function value along a finite set of feasible search arcs and decrease the sampling stepsize if an improved objective function value is not sampled. The search arcs are obtained by projecting search direction rays onto the feasible set and the search directions are chosen such that a subset approximately generates the cone of first-order feasible variations at the current iterate. We show that these methods have desirable convergence properties under certain regularity assumptions on the constraints. In the case of linear constraints, the projections are redundant and the regularity assumptions hold automatically. Numerical experience with the methods in the linearly constrained case is reported. Received: November 12, 1999 / Accepted: April 6, 2001?Published online October 26, 2001     

On reduced convex QP formulations of monotone LCPs

Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice versa are well known. We describe a class of LCPs for which a reduced QP formulation – one that has fewer constraints than the “standard” QP formulation – is available. We mention several instances of this class, including the known case in which the coefficient matrix in the LCP is symmetric. Received: May 2000 / Accepted: February 22, 2001?Published online April 12, 2001     

Mixing mixed-integer inequalities

Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure. Received: April 1998 / Accepted: January 2001?Published online April 12, 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].     

Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut

Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real–world application we aim at is the control of a stacker crane in a warehouse.?We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered – at least for our special application – and that the heuristics provide acceptable solutions. Received: August 1999 / Accepted: September 2000?Published online April 12, 2001