Convex and Nonsmooth Optimization

Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method)

  • Pavel Dvurechensky
  • Alexander Gasnikov
  • Alexander Tiurin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , ,

    In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. … Read more

    Convergence of first-order methods via the convex conjugate

  • Javier F. Peña
    • Categories Convex Optimization Tags ,

    This paper gives a unified and succinct approach to the $O(1/\sqrt{k}), O(1/k),$ and $O(1/k^2)$ convergence rates of the subgradient, gradient, and accelerated gradient methods for unconstrained convex minimization. In the three cases the proof of convergence follows from a generic bound defined by the convex conjugate of the objective function. Citation Working Paper, Carnegie Mellon … Read more

    A Robust Multi-Batch L-BFGS Method for Machine Learning

  • Albert S. Berahas
  • Martin Takac
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper describes an implementation of the L-BFGS method designed to deal with two adversarial situations. The first occurs in distributed computing environments where some of the computational nodes devoted to the evaluation of the function and gradient are unable to return results on time. A similar challenge occurs in a multi-batch approach in which … Read more

    Self-concordant inclusions: A unified framework for path-following generalized Newton-type algorithms

  • Shu Lu
  • Tianxiao Sun
  • Quoc Tran-Dinh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    We study a class of monotone inclusions called “self-concordant inclusion” which covers three fundamental convex optimization formulations as special cases. We develop a new generalized Newton-type framework to solve this inclusion. Our framework subsumes three schemes: full-step, damped-step and path-following methods as specific instances, while allows one to use inexact computation to form generalized Newton … Read more

    Measuring axial symmetry in convex cones

  • Alberto Seeger
  • Mounir Torki
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The problem of measuring the degree of central symmetry of a convex body has been treated by various authors since the early twentieth century. This work addresses the issue of measuring the degree of axial symmetry of a convex cone. Passing from central symmetry in convex bodies to axial symmetry in convex cones is not … Read more

    Dynamic Stochastic Approximation for Multi-stage Stochastic Optimization

  • Guanghui Lan
  • Zhiqiang Zhou
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal ${\cal O}(1/\epsilon^4)$ rate of convergence in terms … Read more

    Non-smooth Non-convex Bregman Minimization: Unification and new Algorithms

  • Thomas Brox
  • Jalal Fadili
  • Peter Ochs
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose a unifying algorithm for non-smooth non-convex optimization. The algorithm approximates the objective function by a convex model function and finds an approximate (Bregman) proximal point of the convex model. This approximate minimizer of the model function yields a descent direction, along which the next iterate is found. Complemented with an Armijo-like line search … Read more

    Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming

  • Sun Hongchun
  • Min Sun
    • Categories Convex Optimization

    For a type of multi-block separable convex programming raised in machine learning and statistical inference, we propose a proximal alternating direction method of multiplier (PADMM) with partially parallel splitting, which has the following nice properties: (1) To alleviate the weight of the proximal terms, the restrictions imposed on the proximal parameters are relaxed substantively; (2) … Read more

    Iteration complexity on the Generalized Peaceman-Rachford splitting method for separable convex programming

  • Peng Jian-Wen
  • Xue-Qing Zhang
    • Categories Convex Optimization

    Recently, a generalized version of Peaceman-Rachford splitting method (GPRSM) for solving a convex minmization model with a general separable structure has been proposed by \textbf{Sun} et al and its global convergence has been proved. In this paper, we further study theoretical aspects of the generalized Peaceman-Rachford splitting method. We first establish the worst-case $\mathcal{O}(1/t)$ convergence … Read more

    Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems

  • Vincent Guigues
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming

    We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation … Read more