Unconstrained Optimization

Local Convergence Analysis for Nonisolated Solutions to Derivative-Free Methods of Optimization

  • Dat Tran
    • Categories Approximation Algorithms, Nonlinear Optimization, Unconstrained Optimization

    This paper provides a local convergence analysis for newly developed derivative-free methods in problems of smooth nonconvex optimization. We focus here on local convergence to local minimizers, which might be nonisolated and hence more challenging for convergence analysis. The main results provide efficient conditions for local convergence to arbitrary local minimizers under the fulfillment of … Read more

    Black-box Optimization Algorithms for Regularized Least-squares Problems

  • Yanjun Liu
  • Kevin Lam
  • Lindon Roberts
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , ,

    We consider the problem of optimizing the sum of a smooth, nonconvex function for which derivatives are unavailable, and a convex, nonsmooth function with easy-to-evaluate proximal operator. Of particular focus is the case where the smooth part has a nonlinear least-squares structure. We adapt two existing approaches for derivative-free optimization of nonsmooth compositions of smooth … Read more

    Globally Convergent Derivative-Free Methods in Nonconvex Optimization with and without Noise

  • Dat Tran
    • Categories Approximation Algorithms, Global Optimization Applications, Unconstrained Optimization

    This paper addresses the study of nonconvex derivative-free optimization problems, where only information of either smooth objective functions or their noisy approximations is available. General derivative-free methods are proposed for minimizing differentiable (not necessarily convex) functions with globally Lipschitz continuous gradients, where the accuracy of approximate gradients is interacting with stepsizes and exact gradient values. … Read more

    Doubly stochastic primal dual splitting algorithm with variance reduction for saddle point problems

  • Dimitri Papadimitriou
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    The structured saddle-point problem involving the infimal convolution in real Hilbert spaces finds applicability in many applied mathematics disciplines. For this purpose, we develop a stochastic primal-dual splitting algorithm with loopless variance-reduction for solving this generic problem. We first prove the weak almost sure convergence of the iterates. We then demonstrate that our algorithm achieves … Read more

    Singular value half thresholding algorithm for lp regularized matrix optimization problems

  • Peng Dingtao
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    In this paper, we study the low-rank matrix optimization problem, where the penalty term is the $\ell_p~(0<p<1)$ regularization. Inspired by the good performance of half thresholding function in sparse/low-rank recovery problems, we propose a singular value half thresholding (SVHT) algorithm to solve the $\ell_p$ regularized matrix optimization problem. The main iteration in SVHT algorithm makes … Read more

    Near-optimal closed-loop method via Lyapunov damping for convex optimization

  • Camille Castera
  • Peter Ochs
    • Categories Convex Optimization, Systems governed by Differential Equations Optimization, Unconstrained Optimization Tags , , ,

    We introduce an autonomous system with closed-loop damping for first-order convex optimization. While, to this day, optimal rates of convergence are only achieved by non-autonomous methods via open-loop damping (e.g., Nesterov’s algorithm), we show that our system is the first one featuring a closed-loop damping while exhibiting a rate arbitrarily close to the optimal one. … Read more

    Fixed point continuation algorithm with extrapolation for Schatten p-quasi-norm regularized matrix optimization problems

  • Peng Dingtao
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    In this paper, we consider a general low-rank matrix optimization problem which is modeled by a general Schatten p-quasi-norm (${\rm 0<p<1}$) regularized matrix optimization. For this nonconvex nonsmooth and non-Lipschitz matrix optimization problem, based on the matrix p-thresholding operator, we first propose a fixed point continuation algorithm with extrapolation (FPCAe) for solving it. Secondly, we … Read more

    Continuous exact relaxation and alternating proximal gradient algorithm for partial sparse and partial group sparse optimization problems

  • Peng Dingtao
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags

    In this paper, we consider a partial sparse and partial group sparse optimization problem, where the loss function is a continuously differentiable function (possibly nonconvex), and the penalty term consists of two parts associated with sparsity and group sparsity. The first part is the $\ell_0$ norm of ${\bf x}$, the second part is the $\ell_{2,0}$ … Read more

    Accelerated Gradient Descent via Long Steps

  • Benjamin Grimmer
  • Kevin Shu
  • Alex L. Wang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Unconstrained Optimization Tags , , , , ,

    Recently Grimmer [1] showed for smooth convex optimization by utilizing longer steps periodically, gradient descent’s state-of-the-art O(1/T) convergence guarantees can be improved by constant factors, conjecturing an accelerated rate strictly faster than O(1/T) could be possible. Here we prove such a big-O gain, establishing gradient descent’s first accelerated convergence rate in this setting. Namely, we … Read more