Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming

  • Guanghui Lan
  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more

    A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs

  • Kartik Krishnan Sivaramakrishnan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase … Read more

    Approximation algorithms for metric tree cover and generalized tour and tree covers

  • Viet Hung Nguyen
    • Categories Approximation Algorithms, Network Optimization, Polyhedra Tags , , , ,

    Given a weighted undirected graph $G=(V,E)$, a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of $G$. Arkin, Halld\’orsson … Read more

    SPECTRAL STOCHASTIC FINITE-ELEMENT METHODS FOR PARAMETRIC CONSTRAINED OPTIMIZATION PROBLEMS

  • Mihai Anitescu
    • Categories Constrained Nonlinear Optimization, Mechanical Engineering, Stochastic Programming Tags , , , ,

    We present a method to approximate the solution mapping of parametric constrained optimization problems. The approximation, which is of the spectral stochastic finite element type, is represented as a linear combination of orthogonal polynomials. Its coefficients are determined by solving an appropriate finite-dimensional constrained optimization problem. We show that, under certain conditions, the latter problem … Read more

    A T-algebraic approach to primal-dual interior-point algorithms

  • Chek Beng Chua
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming

    Three primal-dual interior-point algorithms for homogeneous cone programming are presented. They are a short-step algorithm, a large-update algorithm, and a predictor-corrector algorithm. These algorithms are described and analyzed based on a characterization of homogeneous cone via T-algebra. The analysis show that the algorithms have polynomial iteration complexity. CitationDivision of Mathematical Sciences, Nanyang Technological University, December … Read more

    CONVERGENCE OF A CLASS OF SEMI-IMPLICIT TIME-STEPPING SCHEMES FOR NONSMOOTH RIGID MULTIBODY DYNAMICS

  • Mihai Anitescu
  • Florian A. Potra
  • Bogdan Gavrea
    • Categories Complementarity and Variational Inequalities, Mechanical Engineering, Other Topics Tags , , , ,

    In this work we present a framework for the convergence analysis in a measure differential inclusion sense of a class of time-stepping schemes for multibody dynamics with contacts, joints, and friction. This class of methods solves one linear complementarity problem per step and contains the semi-implicit Euler method, as well as trapezoidallike methods for which … Read more

    Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms

  • Vasile L. Basescu
  • John E. Mitchell
    • Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , ,

    It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly … Read more

    Exact regularization of convex programs

  • Michael P. Friedlander
  • Paul Tseng
    • Categories Convex Optimization Tags , , , , , , , ,

    The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more

    A Unified Theorem on SDP Rank Reduction

  • Anthony Man-Cho So
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags ,

    We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X … Read more

    A new adaptive algorithm for linear multiobjective programming problems

  • M.O. Bibi
  • M.S Radjef
  • Sonia Radjef
    • Categories Linear, Cone and Semidefinite Programming, Multi-Criteria Optimization Tags , , , , , ,

    In this paper, we present a new adaptive algorithm for defining the solution set of a multiobjective linear programming problem, where the decision variables are upper and lower bounded, using the direct support method. The principle particularitie of this method is the fact that it handles the bounds of variables such are they are initially … Read more