convex optimization

An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and its Implications to Second-Order Methods

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

    This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) method. Iteration-complexity results are established for the A-HPE method, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE method are … Read more

    Hierarchical Classification via Orthogonal Transfer

  • Mingrui Wu
  • Lin Xiao
  • Dengyong Zhou
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , ,

    We consider multiclass classification problems where the set of labels are organized hierarchically as a category tree. We associate each node in the tree with a classifier and classify the examples recursively from the root to the leaves. We propose a hierarchical Support Vector Machine (SVM) that encourages the classifier at each node of the … Read more

    An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections

  • Dirk A. Lorenz
  • Marc E. Pfetsch
  • Andreas M. Tillmann
    • Categories Convex Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , , , ,

    We propose a new subgradient method for the minimization of convex functions over a convex set. Common subgradient algorithms require an exact projection onto the feasible region in every iteration, which can be efficient only for problems that admit a fast projection. In our method we use inexact adaptive projections requiring to move within a … Read more

    FAST FIRST-ORDER METHODS FOR COMPOSITE CONVEX OPTIMIZATION WITH BACKTRACKING

  • Xi Bai
  • Donald Goldfarb
  • Katya Scheinberg
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose new versions of accelerated first order methods for convex composite optimization, where the prox parameter is allowed to increase from one iteration to the next. In particular we show that a full backtracking strategy can be used within the FISTA \cite{Beck-Teboulle-2009} and FALM algorithms \cite{Goldfarb-Ma-Scheinberg-2010} while preserving their worst-case iteration complexities of $O(\sqrt{L(f)/\epsilon})$. … Read more

    Level methods uniformly optimal for composite and structured nonsmooth convex optimization

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more

    Level methods uniformly optimal for composite and structured nonsmooth convex optimization

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more

    A Double Smoothing Technique for Constrained Convex Optimization Problems and Applications to Optimal Control

  • Olivier Devolder
  • François Glineur
  • Yurii Nesterov
    • Categories Convex Optimization, Infinite Dimensional Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper, we propose an efficient approach for solving a class of convex optimization problems in Hilbert spaces. Our feasible region is a (possibly infinite-dimensional) simple convex set, i.e. we assume that projections on this set are computationally easy to compute. The problem we consider is the minimization of a convex function over this … Read more

    Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming

  • Bingsheng He
  • Tao Min
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , ,

    We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, … Read more

    Inexact Dynamic Bundle Methods

  • Krzysztof C. Kiwiel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    We give a proximal bundle method for minimizing a convex function $f$ over $\mathbb{R}_+^n$. It requires evaluating $f$ and its subgradients with a possibly unknown accuracy $\epsilon\ge0$, and maintains a set of free variables $I$ to simplify its prox subproblems. The method asymptotically finds points that are $\epsilon$-optimal. In Lagrangian relaxation of convex programs, it … Read more

    A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality

  • Luis M. Briceno-Arias
  • Patrick L. Combettes
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    The principle underlying this paper is the basic observation that the problem of simultaneously solving a large class of composite monotone inclusions and their duals can be reduced to that of finding a zero of the sum of a maximally monotone operator and a linear skew-adjoint operator. An algorithmic framework is developed for solving this … Read more