Unconstrained Optimization

Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm

  • Albert S. Berahas
  • Raghu Bollapragada
  • Wanping Dong
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic and stochastic inexact settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees … Read more

    Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods

  • Thomas O'Leary-Roseberry
  • Raghu Bollapragada
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    \(\) We consider minimizing finite-sum and expectation objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast \(\mathcal{O}\left(\sqrt{\frac{\log k}{k}}\right)\) local superlinear convergence for strongly convex functions in … Read more

    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

    An optimally fast objective-function-free minimization algorithm using random subspaces

  • Stefania Bellavia
  • Serge Gratton
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , ,

    Article Download View An optimally fast objective-function-free minimization algorithm using random subspaces