Semi-definite Programming

Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Arkadi Nemirovski
    • Categories Semi-definite Programming Tags , ,

    In this paper, we first develop “economical” representations for positive semidefinitness of well-structured sparse symmetric matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT … Read more

    The Q Method for Second-order Cone Programming

  • Farid Alizadeh
  • Yu Xia
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    Based on the Q method for SDP, we develop the Q method for SOCP. A modified Q method is also introduced. Properties of the algorithms are discussed. Convergence proofs are given. Finally, we present numerical results. Citation AdvOl-Report#2004/15 McMaster University, Advanced Optimization Laboratory Article Download View The Q Method for Second-order Cone Programming

    On the Behavior of the Homogeneous Self-Dual Model for Conic Convex Optimization

  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model’s behavior are precisely controlled independent of the problem instance: (i) the sizes of epsilon-optimal solutions, and (ii) the maximum distance of epsilon-optimal solutions to the … Read more

    Complex Quadratic Optimization and Semidefinite Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of … Read more

    Recovering Risk-Neutral Probability Density Functions from Options Prices using Cubic Splines

  • Ana M. Monteiro
  • Reha H. Tütüncü
  • Luis Nunes Vicente
    • Categories Finance and Economics, Quadratic Programming, Semi-definite Programming Tags , , , ,

    We present a new approach to estimate the risk-neutral probability density function (pdf) of the future prices of an underlying asset from the prices of options written on the asset. The estimation is carried out in the space of cubic spline functions, yielding appropriate smoothness. The resulting optimization problem, used to invert the data and … Read more

    Computational Enhancements in Low-Rank Semidefinite Programming

  • Samuel Burer
  • Changhui Choi
    • Categories Semi-definite Programming

    We discuss computational enhancements for the low-rank semidefinite programming algorithm, including the extension to block semidefinite programs, an exact linesearch procedure, and a dynamic rank reduction scheme. A truncated Newton method is also introduced, and several preconditioning strategies are proposed. Numerical experiments illustrating these enhancements are provided. Citation Manuscript, Department of Mangagement Sciences, University of … Read more

    A direct formulation for sparse PCA using semidefinite programming

  • Alexandre d'Aspremont
  • Laurent El Ghaoui
  • Michael I. Jordan
  • G. R. G. Lanckriet
    • Categories Finance and Economics, Semi-definite Programming, Statistics Tags , ,

    We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification … Read more

    Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

  • Y.Q. Bai
  • Cornelis Roos
  • G. Q. Wang
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In … Read more

    A semidefinite programming based polyhedral cut and price algorithm for the maxcut problem

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Branch and Cut Algorithms, Semi-definite Programming Tags , , ,

    We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the … Read more

    SDP vs. LP relaxations for the moment approach in some performance evaluation problems

  • Jean-Bernard Lasserre
  • Thomas Prieto-Rumeau
    • Categories Applications - OR and Management Sciences, Finance and Economics, Semi-definite Programming

    Given a Markov process we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence … Read more