COMPUTATIONAL COMPLEXITY OF INEXACT GRADIENT AUGMENTED LAGRANGIAN METHODS: APPLICATION TO CONSTRAINED MPC

  • Ion Necoara
  • Quoc Tran-Dinh
  • Valentin Nedelcu
    • Categories Control Applications, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    We study the computational complexity certification of inexact gradient augmented Lagrangian methods for solving convex optimization problems with complicated constraints. We solve the augmented Lagrangian dual problem that arises from the relaxation of complicating constraints with gradient and fast gradient methods based on inexact first order information. Moreover, since the exact solution of the augmented … Read more

    A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

  • Ion Necoara
  • Andrei Patrascu
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Network Optimization Tags , , , ,

    In this paper we present a variant of random coordinate descent method for solving linearly constrained convex optimization problems with composite objective function. If the smooth part has Lipschitz continuous gradient, then the method terminates with an ϵ-optimal solution in O(N2/ϵ) iterations, where N is the number of blocks. For the class of problems with … Read more

    Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: application to distributed MPC

  • Dragos Clipici
  • Ion Necoara
    • Categories Control Applications, Convex Optimization, Parallel Algorithms Tags , , , ,

    In this paper we propose a parallel coordinate descent algorithm for solving smooth convex optimization problems with separable constraints that may arise e.g. in distributed model predictive control (MPC) for linear network systems. Our algorithm is based on block coordinate descent updates in parallel and has a very simple iteration. We prove (sub)linear rate of … Read more

    Hardness and Approximation Results for hBcBall Constrained Homogeneous Polynomial Optimization Problems

  • Ke Hou
  • Anthony Man-Cho So
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    In this paper, we establish hardness and approximation results for various $L_p$-ball constrained homogeneous polynomial optimization problems, where $p \in [2,\infty]$. Specifically, we prove that for any given $d \ge 3$ and $p \in [2,\infty]$, both the problem of optimizing a degree-$d$ homogeneous polynomial over the $L_p$-ball and the problem of optimizing a degree-$d$ multilinear … Read more

    A Semidefinite Approach to the $ Cover Problem

  • João Gouveia
  • James Pfeiffer
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    We apply theta body relaxations to the $K_i$ cover problem and use this to show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all $K_i$-$p$-hole facets are valid, addressing an open question of Conforti et al \cite{conforti}. For the triangle free problem, we show for $K_n$ that … Read more

    Worst-case-expectation approach to optimization under uncertainty

  • Joari Paulo da Costa
  • Alexander Shapiro
  • Murilo Pereira Soares
  • Wajdi Tekaya
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , , , , , ,

    In this paper we discuss multistage programming with the data process subject to uncertainty. We consider a situation were the data process can be naturally separated into two components, one can be modeled as a random process, with a specified probability distribution, and the other one can be treated from a robust (worst case) point … Read more

    Iterative Hard Thresholding Methods for $ Regularized Convex Cone Programming

  • Zhaosong Lu
    • Categories Combinatorial Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the … Read more

    Complexity of Ten Decision Problems in Continuous Time Dynamical Systems

  • Amir Ali Ahmadi
  • Anirudha Majumdar
  • Russ Tedrake
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags ,

    We show that for continuous time dynamical systems described by polynomial differential equations of modest degree (typically equal to three), the following decision problems which arise in numerous areas of systems and control theory cannot have a polynomial time (or even pseudo-polynomial time) algorithm unless P=NP: local attractivity of an equilibrium point, stability of an … Read more

    Modified Orbital Branching with Applications to Orbitopes and to Unit Commitment

  • Miguel F. Anjos
  • James Ostrowski
  • Anthony Vannelli
    • Categories Applications - Science and Engineering, Integer Programming

    The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of MILP problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In … Read more

    Minimal Representation of Insurance Prices

  • Alois Pichler
  • Alexander Shapiro
    • Categories Convex Optimization, Finance and Economics, Statistics Tags , , ,

    This paper addresses law invariant coherent risk measures and their Kusuoka representations. By elaborating the existence of a minimal representation we show that every Kusuoka representation can be reduced to its minimal representation. Uniqueness — in a sense specified in the paper — of the risk measure’s Kusuoka representation is derived from this initial result. … Read more