Linear, Cone and Semidefinite Programming

On the identification of optimal partition for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, from a central solution sufficiently close to the optimal set, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial … Read more

    Convergence rates of moment-sum-of-squares hierarchies for optimal control problems

  • Didier Henrion
  • Colin N. Jones
  • Milan Korda
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We study the convergence rate of moment-sum-of-squares hierarchies of semidefinite programs for optimal control problems with polynomial data. It is known that these hierarchies generate polynomial under-approximations to the value function of the optimal control problem and that these under-approximations converge in the $L^1$ norm to the value function as their degree $d$ tends to … Read more

    A generalized simplex method for integer problems given by verification oracles

  • Sergei Chubanov
    • Categories Integer Programming, Linear Programming Tags , , ,

    We consider a linear problem over a finite set of integer vectors and assume that there is a verification oracle, which is an algorithm being able to verify whether a given vector optimizes a given linear function over the feasible set. Given an initial solution, the algorithm proposed in this paper finds an optimal solution … Read more

    A Riemannian conjugate gradient method for optimization on the Stiefel manifold

  • Xiaojing Zhu
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    In this paper we propose a new Riemannian conjugate gradient method for optimization on the Stiefel manifold. We introduce two novel vector transports associated with the retraction constructed by the Cayley transform. Both of them satisfy the Ring-Wirth nonexpansive condition, which is fundamental for convergence analysis of Riemannian conjugate gradient methods, and one of them … Read more

    On max-k-sums

  • Michael J. Todd
    • Categories Basic Sciences Applications, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The max-$k$-sum of a set of real scalars is the maximum sum of a subset of size $k$, or alternatively the sum of the $k$ largest elements. We study two extensions: First, we show how to obtain smooth approximations to functions that are pointwise max-$k$-sums of smooth functions. Second, we discuss how the max-$k$-sum can … Read more

    Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

    Low-Rank Matrix Completion using Nuclear Norm with Facial Reduction

  • Shimeng Huang
  • Henry Wolkowicz
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Systems and Least-Squares Tags , , , , , , ,

    Minimization of the nuclear norm is often used as a surrogate, convex relaxation, for finding the minimum rank completion (recovery) of a partial matrix. The minimum nuclear norm problem can be solved as a trace minimization semidefinite programming problem (\SDP). The \SDP and its dual are regular in the sense that they both satisfy strict … Read more

    A simple preprocessing algorithm for semidefinite programming

  • Preston Faulk
  • Gabor Pataki
  • Quoc Tran-Dinh
    • Categories Convex Optimization, Optimization Software Benchmark, Semi-definite Programming

    We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, … Read more

    An inexact dual logarithmic barrier method for solving sparse semidefinite programs

  • Stefania Bellavia
  • Jacek Gondzio
  • Margherita Porcelli
    • Categories Nonlinear Optimization, Semi-definite Programming

    A dual logarithmic barrier method for solving large, sparse semidefinite programs is proposed in this paper. The method avoids any explicit use of the primal variable X and therefore is well-suited to problems with a sparse dual matrix S. It relies on inexact Newton steps in dual space which are computed by the conjugate gradient … Read more