Linear, Cone and Semidefinite Programming

A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

  • Sergei Chubanov
    • Categories Linear Programming Tags , ,

    This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of … Read more

    Generalized Dual Face Algorithm for Linear Programming

  • Ping-Qi Pan
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , ,

    As a natural extension of the dual simplex algorithm, the dual face algorithm performed remarkably in computational experiments with a set of Netlib standard problems. In this paper, we generalize it to bounded-variable LP problems via local duality. Citation Department of Mathematics, Southeast University, Nanjing, 210096, China, 12/2014 Article Download View Generalized Dual Face Algorithm … Read more

    Constrained trace-optimization of polynomials in freely noncommuting variables

  • Igor Klep
  • Janez Povh
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , , , , , ,

    The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation … Read more

    Clustering-Based Preconditioning for Stochastic Programs

  • Yankai Cao
  • Carl D. Laird
  • Victor M. Zavala
    • Categories Linear Programming, Quadratic Programming, Stochastic Programming

    We present a clustering-based preconditioning strategy for KKT systems arising in stochastic programming within an interior-point framework. The key idea is to perform adaptive clustering of scenarios (inside-the-solver) based on their influence on the problem as opposed to cluster scenarios based on problem data alone, as is done in existing (outside-thesolver) approaches. We derive spectral … Read more

    An Axiomatic Duality Framework for the Theta Body and Related Convex Corners

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are … Read more

    Mathematical Programming Models Based on Hub Covers in Graph Query Processing

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Belma Yelbay
    • Categories 0-1 Programming, Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    The use of graph databases for social networks, images, web links, pathways and so on, has been increasing at a fast pace and promotes the need for efficient graph query processing on such databases. In this study, we discuss graph query processing — referred to as graph matching — and an inherent optimization problem known … Read more

    Interior-point algorithms for convex optimization based on primal-dual metrics

  • Tor G.J. Myklebust
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    We propose and analyse primal-dual interior-point algorithms for convex optimization problems in conic form. The families of algorithms we analyse are so-called short-step algorithms and they match the current best iteration complexity bounds for primal-dual symmetric interior-point algorithm of Nesterov and Todd, for symmetric cone programming problems with given self-scaled barriers. Our results apply to … Read more

    Primal-Dual Entropy Based Interior-Point Algorithms for Linear Optimization

  • Mehdi Karimi
  • Shen Luo
  • Levent Tunçel
    • Categories Linear Programming

    We propose a family of search directions based on primal-dual entropy in the context of interior-point methods for linear optimization. We show that by using entropy based search directions in the predictor step of a predictor-corrector algorithm together with a homogeneous self-dual embedding, we can achieve the current best iteration complexity bound for linear optimization. … Read more

    Convergence analysis for Lasserre’s measure–based hierarchy of upper bounds for polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
    • Categories Global Optimization Theory, Semi-definite Programming Tags

    We consider the problem of minimizing a continuous function f over a compact set K. We analyze a hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-􀀀885], obtained by searching for an optimal probability density function h on K which is a sum of squares of polynomials, so that … Read more

    Lov\'{a}sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

  • S. Bianchi
  • Mariana Escalante
  • Levent Tunçel
  • G. Nasini
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We study the Lov\'{a}sz-Schrijver lift-and-project operator ($\LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $\LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs … Read more