Linear, Cone and Semidefinite Programming

Welfare-Maximizing Correlated Equilibria using Kantorovich Polynomials with Sparsity

  • Fook Wai Kong
  • Berc Rustem
    • Categories Game Theory, Global Optimization, Semi-definite Programming Tags , , , , ,

    We propose an algorithm that computes the epsilon-correlated equilibria with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive an infinite-dimensional formulation of epsilon-correlated equilibria using Kantorovich polynomials and re-express it as a polynomial positivity constraint. In addition, we exploit polynomial sparsity to achieve a leaner problem formulation involving Sum-Of-Squares … Read more

    Curvature Integrals and Iteration Complexities in SDP and Symmetric Cone Programs

  • Satoshi Kakihara
  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. The idea to exploit the curvature of the central path for the analysis of iteration … Read more

    Information Geometry and Interior-Point Algorithms in SDP and Symmetric Cone Programs

  • Satoshi Kakihara
  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    This paper is a continuation of the paper Kakihara, Ohara and Tsuchiya by the authors where they demonstrated that the number of iterations of Mizuno-Todd-Ye predictor-corrector primal-dual interior-point methods for SDP and more generally symmetric cone programs is (asymptotically) expressed with an integral over the central trajectory called “curvature integral.” It was shown that the … Read more

    PuLP: A Linear Programming Toolkit for Python

  • Iain Dunning
  • Stuart Mitchell
  • Michael O'Sullivan
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Modeling Languages and Systems

    This paper introduces the PuLP library, an open source package that allows mathematical programs to be described in the Python computer programming language. PuLP is a high-level modelling library that leverages the power of the Python language and allows the user to create programs using expressions that are natural to the Python language, avoiding special … Read more

    A smooth perceptron algorithm

  • Javier F. Peña
  • Negar Soheili
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , ,

    The perceptron algorithm, introduced in the late fifties in the machine learning community, is a simple greedy algorithm for finding a solution to a finite set of linear inequalities. The algorithm’s main advantages are its simplicity and noise tolerance. The algorithm’s main disadvantage is its slow convergence rate. We propose a modified version of the … Read more

    Properties of a Cutting Plane Method for Semidefinite Programming

  • John E. Mitchell
  • Kartik Krishnan Sivaramakrishnan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that … Read more

    An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP

  • K.F. Jiang
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    The accelerated proximal gradient (APG) method, first proposed by Nesterov, and later refined by Beck and Teboulle, and studied in a unifying manner by Tseng has proven to be highly efficient in solving some classes of large scale structured convex optimization (possibly nonsmooth) problems, including nuclear norm minimization problems in matrix completion and $l_1$ minimization … Read more

    An exact duality theory for semidefinite programming based on sums of squares

  • Igor Klep
  • Markus Schweighofer
    • Categories Semi-definite Programming Tags , , , , , , , ,

    Farkas’ lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality … Read more

    Sampling with respect to a class of measures arising in second-order cone optimization with rank constraints

  • Leonid Faybusovich
    • Categories Second-Order Cone Programming Tags , ,

    We describe a classof measures on second-order cones as a push-forward of the Cartesian product of a probabilistic measure on positive semi-line corresponding to Gamma distribution and the uniform measure on the sphere Citation report, Department of Mathematics, University of Notre Dame, July, 2011 Article Download View Sampling with respect to a class of measures … Read more