Nonlinear Optimization

Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization Tags

    This paper investigates the convergence properties of the hypergradient descent method (HDM), a 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first-order methods. We provide the first rigorous convergence analysis of HDM using the online learning framework of [Gao24] and apply this analysis to develop new state-of-the-art adaptive gradient methods with empirical and … Read more

    An Augmented Lagrangian Approach to Bi-Level Optimization via an Equilibrium Constrained Problem

  • Nadav Hallak
    • Categories Bilevel Optimization, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    Optimization problems involving equilibrium constraints capture diverse optimization settings such as bi-level optimization, min-max problems and games, and the minimization over non-linear constraints. This paper introduces an Augmented Lagrangian approach with Hessian-vector product approximation to address an equilibrium constrained nonconvex nonsmooth optimization problem. The underlying model in particular captures various settings of bi-level optimization problems, … Read more

    Convergence of Descent Optimization Algorithms under Polyak-Lojasiewicz-Kurdyka Conditions

  • Glaydston Bento
  • Boris S. Mordukhovich
  • Yurii Nesterov
  • Tiago Sousa Mota
    • Categories Nonsmooth Optimization, Unconstrained Optimization

    This paper develops a comprehensive convergence analysis for generic classes of descent algorithms in nonsmooth and nonconvex optimization under several conditions of the Polyak-Lojasiewicz-Kurdyka (PLK) type. Along other results, we prove the finite termination of generic algorithms under the PLK conditions with lower exponents. Specifications are given to establish new convergence rates for inexact reduced … Read more

    prunAdag: an adaptive pruning-aware gradient method

  • Margherita Porcelli
  • Giovanni Seraghiti
  • Philippe L. Toint
    • Categories Data Science Algorithms, Nonlinear Optimization Tags , , ,

    A pruning-aware adaptive gradient method is proposed which classifies the variables in two sets before updating them using different strategies. This technique extends the “relevant/irrelevant” approach of Ding (2019) and Zimmer et al. (2022) and allows a posteriori sparsification of the solution of model parameter fitting problems. The new method is proved to be convergent … Read more

    A necessary condition for the guarantee of the superiorization method

  • Kay Barshad
  • Yair Censor
  • Walaa M. Moursi
  • Tyler Weames
  • Henry Wolkowicz
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Convex Optimization Tags , , , , ,

    We study a method that involves principally convex feasibility-seeking and makes secondary efforts of objective function value reduction. This is the well-known superiorization method (SM), where the iterates of an asymptotically convergent iterative feasibility-seeking algorithm are perturbed by objective function nonascent steps. We investigate the question under what conditions a sequence generated by an SM … Read more

    Newtonian Methods with Wolfe Linesearch in Nonsmooth Optimization and Machine Learning

  • Miantao Chao
  • Boris S. Mordukhovich
  • Zijian Shi
  • Jin Zhang
    • Categories Nonlinear Optimization Tags , , , , , ,

    This paper introduces and develops coderivative-based Newton methods with Wolfe linesearch conditions to solve various classes of problems in nonsmooth optimization and machine learning. We first propose a generalized regularized Newton method with Wolfe linesearch (GRNM-W) for unconstrained $C^{1,1}$ minimization problems (which are second-order nonsmooth) and establish global as well as local superlinear convergence of … Read more

    A Decomposition Framework for Nonlinear Nonconvex Two-Stage Optimization

  • Yuchen Lou
  • Andreas Wächter
  • Xinyi Luo
  • Ermin Wei
    • Categories Nonlinear Optimization

    We propose a new decomposition framework for continuous nonlinear constrained two-stage optimization, where both first- and second-stage problems can be nonconvex. A smoothing technique based on an interior-point formulation renders the optimal solution of the second-stage problem differentiable with respect to the first-stage parameters. As a consequence, efficient off-the-shelf optimization packages can be utilized. We … Read more

    Fully Adaptive Zeroth-Order Method for Minimizing Functions with Compressible Gradients

  • Geovani Nunes Grapiglia
  • Daniel McKenzie
    • Categories Unconstrained Optimization Tags , ,

    We propose an adaptive zeroth-order method for minimizing differentiable functions with L-Lipschitz continuous gradients. The method is designed to take advantage of the eventual compressibility of the gradient of the objective function, but it does not require knowledge of the approximate sparsity level s or the Lipschitz constant L of the gradient. We show that … Read more

    Descent Scheme for a Class of Bilevel Programming Problems

  • Bhuvnesh Khatana
    • Categories Approximation Algorithms, Combinatorial Optimization, Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    In this paper, a class of bilevel programming problems is studied, in which the lower level is a quadratic programming problem, and the upper level problem consists of a nonlinear objective function with coupling constraints. An iterative process is developed to generate a sequence of points, which converges to the solution of this problem. In … Read more

    A stochastic Lagrangian-based method for nonconvex optimization with nonlinear constraints

  • Dimitri Papadimitriou
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    The Augmented Lagrangian Method (ALM) is one of the most common approaches for solving linear and nonlinear constrained problems. However, for non-convex objectives, handling non-linear inequality constraints remains challenging. In this paper, we propose a stochastic ALM with Backtracking Line Search that performs on a subset (mini-batch) of randomly selected points for the solving of … Read more