nondegeneracy

Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Various conic relaxations of quadratic optimization problems in nonnega- tive variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combi- natorial optimization problems can be expressed in several ways, each … 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

    Differentiability properties of metric projections onto convex sets

  • Alexander Shapiro
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    It is known that directional differentiability of metric projection onto a closed convex set in a finite dimensional space is not guaranteed. In this paper we discuss sufficient conditions ensuring directional differentiability of such metric projections. The approach is based on a general theory of sensitivity analysis of parameterized optimization problems. ArticleDownload View PDF

    Full stability of locally optimal solutions in second-order cone programming

  • Boris S. Mordukhovich
  • Jiri V. Outrata
  • Ebrahim Sarabi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    The paper presents complete characterizations of Lipschitzian full stability of locally optimal solutions to problems of second-order cone programming (SOCP) expressed entirely in terms of their initial data. These characterizations are obtained via appropriate versions of the quadratic growth and strong second-order sucient conditions under the corresponding constraint quali cations. We also establish close relationships between … Read more

    Positive Semidefinite Matrix Completion, Universal Rigidity and the Strong Arnold Property

  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Semi-definite Programming Tags , , , , ,

    This paper addresses the following three topics: positive semidefinite (psd) matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidefinite programming as unifying theme. Our main contribution is a sufficient condition for constructing partial psd matrices which admit a unique completion to a … Read more

    Semi-algebraic functions have small subdifferentials

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Nonsmooth Optimization Tags , , ,

    We prove that the subdifferential of any semi-algebraic extended-real-valued function on $\R^n$ has $n$-dimensional graph. We discuss consequences for generic semi-algebraic optimization problems. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. April 2010.ArticleDownload View PDF

    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