The central path in linear optimization always converges to the analytic center of the optimal set. This result was extended to semidefinite programming by Goldfarb and Scheinberg (SIAM J. Optim. 8: 871-886, 1998). In this paper we show that this latter result is not correct in the absence of strict complementarity. We provide a counterexample, … Read more
Let $\Pcal=\{x | Ax\le b\}$, where $A$ is an $m\times n$ matrix. We assume that $\Pcal$ contains a ball of radius one centered at the origin, and is contained in a ball of radius $R$ centered at the origin. We consider the problem of approximating the maximum volume ellipsoid inscribed in $\Pcal$. Such ellipsoids have … Read more
This paper analyzes the introduction of multiple central cuts in a conic formulation of the analytic center cutting plane method (in short ACCPM). This work extends earlier work on the homogeneous ACCPM, and parallels the analysis of the multiple cut process in the standard ACCPM. The main issue is the calculation of a direction that … Read more
This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data. CitationRapport de recherche 4179, INRIA, France, 2001ArticleDownload View PDF
The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying dimensions) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard discrete optimization problem; even the restricted version … Read more
Self-scaled barrier functions are fundamental objects in the theory of interior-point methods for linear optimization over symmetric cones, of which linear and semidefinite programming are special cases. We are classifying all self-scaled barriers over irreducible symmetric cones and show that these functions are merely homothetic transformations of the universal barrier function. Together with a decomposition … Read more
This paper proposes a new predictor-corrector interior-point method for a class of semidefinite programs, which numerically traces the central trajectory in a space of Lagrange multipliers. The distinguished features of the method are full use of the BFGS quasi-Newton method in the corrector procedure and an application of the conjugate gradient method with an effective … Read more
Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains … Read more
Lagrangian relaxation is a tool to find upper bounds on a given (arbitrary) maximization problem. Sometimes, the bound is exact and an optimal solution is found. Our aim in this paper is to review this technique, the theory behind it, its numerical aspects, its relation with other techniques such as column generation. Citationin: Computational Combinatorial … Read more
In this paper, we formulate the $l_p$-norm optimization problem as a conic optimization problem, derive its standard duality properties and show it can be solved in polynomial time. We first define an ad hoc closed convex cone, study its properties and derive its dual. This allows us to express the standard $l_p$-norm optimization primal problem … Read more