Linear, Cone and Semidefinite Programming

Quadratic Convergence of a Squared Smoothing Newton Method for Nonsmooth Matrix Equations and Its Applications in Semidefinite Optimization Problems

  • Liqun Qi
  • Jie Sun
  • Defeng Sun
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Semi-definite Programming Tags ,

    We study a smoothing Newton method for solving a nonsmooth matrix equation that includes semidefinite programming and the semidefinte complementarity problem as special cases. This method, if specialized for solving semidefinite programs, needs to solve only one linear system per iteration and achieves quadratic convergence under strict complementarity. We also establish quadratic convergence of this … Read more

    A semidefinite programming heuristic for quadratic programming problems with complementarity constraints

  • Stephen E. Braun
  • John E. Mitchell
    • Categories Complementarity and Variational Inequalities, Finance and Economics, Semi-definite Programming Tags , ,

    The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these … Read more

    A unifying framework for several cutting plane algorithms for semidefinite programming

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Nonsmooth Optimization, Semi-definite Programming, Semi-infinite Programming Tags , , ,

    Cutting plane methods provide the means to solve large scale semidefinite programs (SDP) cheaply and quickly. They can also conceivably be employed for the purposes of re-optimization after branching, or the addition of cutting planes. We give a survey of various cutting plane approaches for SDP in this paper. These cutting plane approaches arise from … Read more

    Optimal Magnetic Shield Design with Second-Order Cone Programming

  • Takashi Sasakawa
  • Takashi Tsuchiya
    • Categories Multidisciplinary Design Optimization, Second-Order Cone Programming Tags , , ,

    In this paper, we consider a continuous version of the convex network flow problem which involves the integral of the Euclidean norm of the flow and its square in the objective function. A discretized version of this problem can be cast as a second-order cone program, for which efficient primal-dual interior-point algorithms have been developed … Read more

    A new iteration-complexity bound for the MTY predictor-corrector algorithm

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program $\min\{c^Tx : Ax=b, \, x \ge 0\}$ with decision … Read more

    A Conic Programming Approach to Generalized Tchebycheff Inequalities

  • Javier F. Peña
  • Luis F. Zuluaga
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    Consider the problem of finding optimal bounds on the expected value of piece-wise polynomials over all measures with a given set of moments. We show that this problem can be studied within the framework of conic programming. Relying on a key approximation result for conic programming, we show that these bounds can be numerically computed … Read more

    Optimal Portfolios using Linear Programming Models

  • Christos Papahristodoulou
    • Categories Applications - OR and Management Sciences, Finance and Economics, Linear Programming

    The classical Quadratic Programming formulation of the well known portfolio selection problem, is cumbersome, time consuming and relies on two important assumptions: (a) the expected return is multivariate normally distributed; (b) the investor is risk averter. This paper formulates two alternative models, (i) maximin, and (ii) minimization of absolute deviation. Data from a very simple … Read more

    SDPARA : SemiDefinite Programming Algorithm PARAllel Version

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , , ,

    Abstract: The SDPA (SemiDefinite Programming Algorithm) is known as efficient computer software based on primal-dual interior-point method for solving SDPs (Semidefinite Programs). In many applications, however, some SDPs become larger and larger, too large for the SDPA to solve on a single processor. In execution of the SDPA applied to large scale SDPs, the computation … Read more

    Semidefinite optimization, a spectral approach

  • M.A. van Bossum
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , , , , ,

    This thesis is about mathematical optimization. Mathematical optimization involves the construction of methods to solve optimization problems, which can arise from real-life problems in applied science, when they are mathematically modeled. Examples come from electrical design, engineering, control theory, telecommunication, environment, finance, and logistics. This thesis deals especially with semidefinite optimization problems. Semidefinite programming is … Read more