Month: June 2001

A comparison of the Sherali-Adams, Lov\’asz-Schrijver and Lasserre relaxations for sh-1$ programming

  • Monique Laurent
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Sherali and Adams \cite{SA90}, Lov\’asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre’s approach uses results about representations of positive polynomials as sums of squares and the dual … Read more

    On the convergence of the central path in semidefinite optimization

  • Etienne de Klerk
  • Margaréta Halická
  • Cornelis Roos
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    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

    On Solving The Progressive Party Problem as a MIP

  • Erwin Kalvelagen
    • Categories Applications - OR and Management Sciences Tags ,

    The `Progressive Party Problem’ [smith1995] has long been considered a problem intractable for branch-and-bound mixed integer solvers. Quite impressive results have been reported with constraint programming systems for this problem. As a result the problem has become a standard example in texts on constraint programming. Fortunately, there has been progress in the mixed integer programming … Read more

    A GRASP with path-relinking for private virtual circuit routing

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , , , , , ,

    A frame relay service offers virtual private networks to customers by provisioning a set of long-term private virtual circuits (PVCs) between customer endpoints on a large backbone network. During the provisioning of a PVC, routing decisions are made without any knowledge of future requests. Over time, these decisions can cause inefficiencies in the network and … Read more

    Improved complexity for maximum volume inscribed ellipsoids

  • Kurt M. Anstreicher
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    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

    Geometry of Semidefinite Max-Cut Relaxations via Ranks

  • Miguel F. Anjos
  • Henry Wolkowicz
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and … Read more

    Augmented self-concordant barriers and nonlinear optimization problems with finite complexity.

  • Yurii Nesterov
  • Jean-Philippe Vial
    • Categories Integer Programming Tags , ,

    In this paper we study special barrier functions for the convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center … Read more

    Componentwise fast convergence in the solution of full-rank systems of nonlinear equations

  • Nicholas I. M. Gould
  • Dominique Orban
  • Annick Sartenaer
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , ,

    The asymptotic convergence of parameterized variants of Newton’s method for the solution of nonlinear systems of equations is considered. The original system is perturbed by a term involving the variables and a scalar parameter which is driven to zero as the iteration proceeds. The exact local solutions to the perturbed systems then form a differentiable … Read more

    An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming

  • E. Alper Yildirim
    • Categories Semi-definite Programming Tags , ,

    We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. For perturbations of the right-hand side vector and the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang … Read more