Interior-Point Algorithms, Penalty Methods and Equilibrium Problems

  • Hande Benson
  • Arun Sen
  • David F. Shanno
  • Robert J. Vanderbei
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Game Theory Tags , , , ,

    In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC’s)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example … Read more

    A Homogeneous Model for $ and *$ Nonlinear Complementarity Problems

  • Akiko Yoshise
    • Categories Complementarity and Variational Inequalities Tags , , ,

    The homogeneous model for linear programs is an elegant means of obtaining the solution or certificate of infeasibility and has importance regardless of the method used for solving the problem, interior-point methods or other methods. In 1999, Andersen and Ye generalized this model to monotone complementarity problems (CPs) and showed that most of the desirable … Read more

    On-Line Scheduling to Minimize Average Completion Time Revisited

  • Nicole Megow
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Combinatorial Optimization, Scheduling Tags , , ,

    We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith’s ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. CitationWorking Paper 4435-03, Sloan School … Read more

    Sparsity in Sums of Squares of Polynomials

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
    • Categories Linear, Cone and Semidefinite Programming, Polyhedra Tags , , ,

    Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and SDP (semidefinite programming) relaxation of polynomial optimization problems. We disscuss effective methods to obtain a simpler representation of a “sparse” polynomial as a sum of … Read more

    Valid inequalities based on simple mixed-integer sets

  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    In this paper we use facets of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known … Read more

    Local Minima and Convergence in Low-Rank Semidefinite Programming

  • Samuel Burer
  • Renato D.C. Monteiro
    • Categories Combinatorial Optimization, Semi-definite Programming

    The low-rank semidefinite programming problem (LRSDP_r) is a restriction of the semidefinite programming problem (SDP) in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and … Read more

    Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , , , , ,

    Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the … Read more

    A robust SQP method for mathematical programs with linear complementarity constraints

  • Xinwei Liu
  • Georgia Perakis
  • Jie Sun
    • Categories Complementarity and Variational Inequalities Tags , , , ,

    The relationship between the mathematical program with linear complementarity constraints (MPCC) and its inequality relaxation is studied. A new sequential quadratic programming (SQP) method is presented for solving the MPCC based on this relationship. A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global convergence results are derived … Read more

    Network Reinforcement

  • Francisco Barahona
    • Categories Graphs and Matroids Tags

    We give an algorithm for the following problem: given a graph $G=(V,E)$ with edge-weights and a nonnegative integer $k$, find a minimum cost set of edges that contains $k$ disjoint spanning trees. This also solves the following {\it reinforcement problem}: given a network, a number $k$ and a set of candidate edges, each of them … Read more

    A Pivotting Procedure for a Class of Second-Order Cone Programming

  • Masakazu Muramatsu
    • Categories Convex Optimization, Second-Order Cone Programming Tags , , ,

    We propose a pivotting procedure for a class of Second-Order Cone Programming (SOCP) having one second-order cone. We introduce a dictionary, basic variables, nonbasic variables, and other necessary notions to define a pivot for the class of SOCP. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering to or … Read more