Linear, Cone and Semidefinite Programming

Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

  • Mengdi Wang
    • Categories Dynamic Programming, Linear Programming Tags , , , , , ,

    We propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality, the algorithm adaptively samples state transitions and makes exponentiated primal-dual updates. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that … Read more

    Plea for a semidefinite optimization solver in complex numbers

  • Jean Charles Gilbert
  • Cedric Josz
    • Categories Semi-definite Programming Tags , , ,

    Numerical optimization in complex numbers has drawn much less attention than in real numbers. A widespread opinion is that, since a complex number is a pair of real numbers, the best strategy to solve a complex optimization problem is to transform it into real numbers and to solve the latter by a real number solver. … Read more

    D-OPTIMAL DESIGN FOR MULTIVARIATE POLYNOMIAL REGRESSION VIA THE CHRISTOFFEL FUNCTION AND SEMIDEFINITE RELAXATIONS

  • Yohann De Castro
  • Didier Henrion
  • Jean-Bernard Lasserre
  • Fabrice Gamboa
  • Roxana Hess
    • Categories Semi-definite Programming, Statistics

    We present a new approach to the design of D-optimal experiments with multivariate polynomial regressions on compact semi-algebraic design spaces. We apply the moment-sum-of-squares hierarchy of semidefinite programming problems to solve numerically and approximately the optimal design problem. The geometry of the design is recovered with semidefinite programming duality theory and the Christoffel polynomial. ArticleDownload … Read more

    Lyapunov rank of polyhedral positive operators

  • Michael Orlitzky
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    If K is a closed convex cone and if L is a linear operator having L(K) a subset of K, then L is a positive operator on K and L preserves inequality with respect to K. The set of all positive operators on K is denoted by pi(K). If J is the dual of K, … Read more

    Conic relaxation approaches for equal deployment problems

  • Safia Kedad-Sidhoum
  • Tim J. Mullin
  • Satoko Moriguchi
  • Makoto Yamashita
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming

    An important problem in the breeding of livestock, crops, and forest trees is the optimum of selection of genotypes that maximizes genetic gain. The key constraint in the optimal selection is a convex quadratic constraint that ensures genetic diversity, therefore, the optimal selection can be cast as a second-order cone programming (SOCP) problem. Yamashita et … Read more

    Solving sparse polynomial optimization problems with chordal structure using the sparse, bounded-degree sum-of-squares hierarchy

  • Joachim Dahl
  • Etienne de Klerk
  • Ahmadreza Marandi
    • Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser, Lasserre and Toh [arXiv:1607.01151,2016] constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proven by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality … Read more

    A semi-analytical approach for the positive semidefinite Procrustes problem

  • Nicolas Gillis
  • Punit Sharma
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    The positive semidefinite Procrustes (PSDP) problem is the following: given rectangular matrices $X$ and $B$, find the symmetric positive semidefinite matrix $A$ that minimizes the Frobenius norm of $AX-B$. No general procedure is known that gives an exact solution. In this paper, we present a semi-analytical approach to solve the PSDP problem. First, we characterize … Read more

    Comparison of Lasserre’s measure–based bounds for polynomial optimization to bounds obtained by simulated annealing

  • Etienne de Klerk
  • Monique Laurent
    • Categories Global Optimization, Nonlinear Optimization, Semi-definite Programming

    We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, … Read more

    Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method

  • Shafiu Jibrin
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming Tags , ,

    We study the problem of computing weighted analytic center for system of linear matrix inequality constraints. The problem can be solved using the Standard Newton’s method. However, this approach requires that a starting point in the interior point of the feasible region be given or a Phase I problem be solved. We address the problem … Read more

    Statistical Inference of Semidefinite Programming

  • Alexander Shapiro
    • Categories Semi-definite Programming, Stochastic Programming Tags , , , , , ,

    In this paper we consider covariance structural models with which we associate semidefinite programming problems. We discuss statistical properties of estimates of the respective optimal value and optimal solutions when the `true’ covariance matrix is estimated by its sample counterpart. The analysis is based on perturbation theory of semidefinite programming. As an example we consider … Read more