complexity

A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , , ,

    In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for … Read more

    Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper we study new stochastic approximation (SA) type algorithms, namely, the accelerated SA (AC-SA), for solving strongly convex stochastic composite optimization (SCO) problems. Specifically, by introducing a domain shrinking procedure, we significantly improve the large-deviation results associated with the convergence rate of a nearly optimal AC-SA algorithm presented by the authors. Moreover, we … Read more

    On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators

  • Cong D. Dang
  • Guanghui Lan
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    In this paper, we study a class of generalized monotone variational inequality (GMVI) problems whose operators are not necessarily monotone (e.g., pseudo-monotone). We present non-Euclidean extragradient (N-EG) methods for computing an approximate strong solution of these problems, and demonstrate how their iteration complexities depend on the global Lipschitz or H\”{o}lder continuity properties for their operators … Read more

    Complexity of Bilevel Coherent Risk Programming

  • Jonathan Eckstein
    • Categories Stochastic Programming Tags , ,

    This paper considers a bilevel programming approach to applying coherent risk measures to extended two-stage stochastic programming problems. This formulation technique avoids the time-inconsistency issues plaguing naive models and the incomposability issues which cause time-consistent formulations to have complicated, hard-to-explain objective functions. Unfortunately, the analysis here shows that such bilevel formulations, when using the standard … Read more

    Bilevel Programming and the Separation Problem

  • Andrea Lodi
  • Ted K. Ralphs
  • Gerhard J. Woeginger
    • Categories Cutting Plane Approaches, Integer Programming Tags , , ,

    In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more

    Smoothing SQP Algorithm for Non-Lipschitz Optimization with Complexity Analysis

  • Wei Bian
  • Xiaojun Chen
    • Categories Nonsmooth Optimization, Statistics, Unconstrained Optimization Tags , ,

    In this paper, we propose a smoothing sequential quadratic programming (SSQP) algorithm for solving a class of nonsmooth nonconvex, perhaps even non-Lipschitz minimization problems, which has wide applications in statistics and sparse reconstruction. At each step, the SSQP algorithm solves a strongly convex quadratic minimization problem with a diagonal Hessian matrix, which has a simple … Read more

    Subgradient methods for huge-scale optimization problems

  • Yurii Nesterov
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider a new class of huge-scale problems, the problems with {\em sparse subgradients}. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends {\em logarithmically} in the dimension. This technique is … Read more

    Stochastic first order methods in smooth convex optimization.

  • Olivier Devolder
    • Categories Convex Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we are interested in the development of efficient first-order methods for convex optimization problems in the simultaneous presence of smoothness of the objective function and stochasticity in the first-order information. First, we consider the Stochastic Primal Gradient method, which is nothing else but the Mirror Descent SA method applied to a smooth … Read more

    Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis

  • Amir Ali Ahmadi
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , , ,

    The contributions of the first half of this thesis are on the computational and algebraic aspects of convexity in polynomial optimization. We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves … Read more

    On the Difficulty of Deciding Asymptotic Stability of Cubic Homogeneous Vector Fields

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

    It is well-known that asymptotic stability (AS) of homogeneous polynomial vector fields of degree one (i.e., linear systems) can be decided in polynomial time e.g. by searching for a quadratic Lyapunov function. Since homogeneous vector fields of even degree can never be AS, the next interesting degree to consider is equal to three. In this … Read more