Nonlinear Optimization

A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization

  • Chuan He
  • Zhaosong Lu
    • Categories Cone Programming, Nonlinear Optimization Tags , , , , , ,

    In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. Under … Read more

    Analyzing Inexact Hypergradients for Bilevel Learning

  • Matthias J. Ehrhardt
  • Lindon Roberts
    • Categories Nonlinear Optimization, Optimization in Data Science Tags , ,

    Estimating hyperparameters has been a long-standing problem in machine learning. We consider the case where the task at hand is modeled as the solution to an optimization problem. Here the exact gradient with respect to the hyperparameters cannot be feasibly computed and approximate strategies are required. We introduce a unified framework for computing hypergradients that … Read more

    Splitted Levenberg-Marquardt Method for Large-Scale Sparse Problems

  • Greta Malaspina
  • Nataša Krejić
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , ,

    We consider large-scale nonlinear least squares problems with sparse residuals, each of them depending on a small number of variables. A decoupling procedure which results in a splitting of the original problems into a sequence of independent problems of smaller sizes is proposed and analysed. The smaller size problems are modified in a way that … Read more

    Improved Front Steepest Descent for Multi-objective Optimization

  • Matteo Lapucci
  • Pierluigi Mansueto
    • Categories Nonlinear Optimization Tags , ,

    In this paper, we deal with the Front Steepest Descent algorithm for multi-objective optimization. We point out that the algorithm from the literature is often incapable, by design, of spanning large portions of the Pareto front. We thus introduce some modifications within the algorithm aimed to overcome this significant limitation. We prove that the asymptotic … Read more

    A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

  • Chuan He
  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We … Read more

    Strengthening SONC Relaxations with Constraints Derived from Variable Bounds

  • Ksenia Bestuzheva
  • Ambros Gleixner
    • Categories Constrained Nonlinear Optimization, Global Optimization, Optimization Software Design Principles Tags , , ,

    Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into … Read more

    A Levenberg-Marquardt Method for Nonsmooth Regularized Least Squares

  • Dominique Orban
  • Aleksandr Y. Aravkin
  • Robert Baraldi
    • Categories Data Science Algorithms, Nonlinear Systems and Least-Squares, Nonsmooth Optimization Tags , , , , ,

    We develop a Levenberg-Marquardt method for minimizing the sum of a smooth nonlinear least-squares term \(f(x) = \frac{1}{2} \|F(x)\|_2^2\) and a nonsmooth term \(h\). Both \(f\) and \(h\) may be nonconvex. Steps are computed by minimizing the sum of a regularized linear least-squares model and a model of \(h\) using a first-order method such as … Read more

    A first-order augmented Lagrangian method for constrained minimax optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization, Robust Optimization Tags , , ,

    In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Under some suitable assumptions, an … Read more

    First-order penalty methods for bilevel optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower-level part is a convex optimization problem, while the upper-level part is possibly a nonconvex optimization problem. In particular, we propose penalty methods for solving them, whose subproblems turn out to be a structured minimax problem and are … Read more

    Inexact reduced gradient methods in nonconvex optimization

  • Dat Tran
    • Categories Global Optimization Applications, Unconstrained Optimization

    This paper proposes and develops new linesearch methods with inexact gradient information for finding stationary points of nonconvex continuously differentiable functions on finite-dimensional spaces. Some abstract convergence results for a broad class of linesearch methods are established. A general scheme for inexact reduced gradient (IRG) methods is proposed, where the errors in the gradient approximation … Read more