complexity

Partially separable convexly-constrained optimization with non-Lipschitz singularities and its complexity

  • Xiaojun Chen
  • Philippe L. Toint
  • Hong Wang
    • Categories Nonsmooth Optimization Tags , ,

    An adaptive regularization algorithm using high-order models is proposed for partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian $\ell_q$-norm regularization terms for $q\in (0,1)$. It is shown that the algorithm using an $p$-th order Taylor model for $p$ odd needs in general at most $O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and … Read more

    On High-order Model Regularization for Constrained Optimization

  • José Mario Martínez
    • Categories Nonlinear Optimization Tags , ,

    In two recent papers regularization methods based on Taylor polynomial models for minimization were proposed that only rely on H\”older conditions on the higher order employed derivatives. Grapiglia and Nesterov considered cubic regularization with a sufficient descent condition that uses the current gradient and resembles the classical Armijo’s criterion. Cartis, Gould, and Toint used Taylor … Read more

    Communication-Efficient Algorithms for Decentralized and Stochastic Optimization

  • Guanghui Lan
  • Soomin Lee
  • Yi Zhou
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , , , ,

    We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. We first propose a decentralized primal-dual … Read more

    Efficiency of minimizing compositions of convex functions and smooth maps

  • Dmitriy Drusvyatskiy
  • Courtney Paquette
    • Categories Nonsmooth Optimization Tags , , , , , ,

    We consider the problem of minimizing a sum of a convex function and a composition of a convex function with a smooth map. Important examples include exact penalty formulations of nonlinear programs and nonlinear least squares problems with side constraints. The basic algorithm we rely on is the well-known prox-linear method, which in each iteration … Read more

    Generalized Symmetric ADMM for Separable Convex Optimization

  • Jianchao Bai
  • Jicheng Li
  • Fengmin Xu
  • Hongchao Zhang
    • Categories Convex Optimization, Global Optimization Theory Tags , , , , , ,

    The Alternating Direction Method of Multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a Generalized Symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two … Read more

    A proximal-Newton method for unconstrained convex optimization in Hilbert spaces

  • M. Marques Alves
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    We propose and study the iteration-complexity of a proximal-Newton method for finding approximate solutions of the problem of minimizing a twice continuously differentiable convex function on a (possibly infinite dimensional) Hilbert space. We prove global convergence rates for obtaining approximate solutions in terms of function/gradient values. Our main results follow from an iteration-complexity study of … Read more

    Dynamic Spectrum Management: A Complete Complexity Characterization

  • Ya-Feng Liu
    • Categories Applications - OR and Management Sciences, Global Optimization Theory, Telecommunications Tags , , ,

    Consider a multi-user multi-carrier communication system where multiple users share multiple discrete subcarriers. To achieve high spectrum efficiency, the users in the system must choose their transmit power dynamically in response to fast channel fluctuations. Assuming perfect channel state information, two formulations for the spectrum management (power control) problem are considered in this paper: the … Read more

    Quadratic regularization with cubic descent for unconstrained optimization

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Unconstrained Optimization Tags , , , ,

    Cubic-regularization and trust-region methods with worst case first-order complexity $O(\varepsilon^{-3/2})$ and worst-case second-order complexity $O(\varepsilon^{-3})$ have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. … Read more

    Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

  • Robert M. Freund
  • Haihao Lu
  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some Lipschitz constant L. However, in many settings the differentiable convex function f(.) is not uniformly smooth — for example in D-optimal design where f(x):=-ln det(HXH^T), or even the univariate … Read more

    Accelerated gradient sliding for structured convex optimization

  • Guanghui Lan
  • Yuyuan Ouyang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Our main goal in this paper is to show that one can skip gradient computations for gradient descent type methods applied to certain structured convex programming (CP) problems. To this end, we first present an accelerated gradient sliding (AGS) method for minimizing the summation of two smooth convex functions with different Lipschitz constants. We show … Read more