Nonlinear Optimization

New Nonlinear Conjugate Gradient Methods with Guaranteed Descent for Multi-Objective Optimization

  • Manuel Berkemeier
  • sonntagk
    • Categories Multi-Criteria Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    In this article, we present several examples of special nonlinear conjugate gradient directions for nonlinear (non-convex) multi-objective optimization. These directions provide a descent direction for the objectives, independent of the line-search. This way, we can provide an algorithm with simple, Armijo-like backtracking and prove convergence to first-order critical points. In contrast to other popular conjugate … Read more

    Some Unified Theory for Variance Reduced Prox-Linear Methods

  • Yue Wu
  • Benjamin Grimmer
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form $f(g(x))+h(x)$ where the inner mapping $g$ is a smooth finite summation or expectation amenable to variance reduction. In such settings, prox-linear methods can enjoy variance-reduced speed-ups despite the existence of nonsmoothness. We provide a unified convergence theory applicable to a … Read more

    Computing Weak Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method

  • Henri Lefebvre
  • Martin Schmidt
    • Categories Energy, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    In recent years, significant attention has been devoted to the issue of explainability in automated decision-making tools. The idea is to explain the outcome of a model by presenting a certain change in the input of the model so that the outcome changes significantly. In this paper, we study this question for linear optimization problems … Read more

    Stochastic first-order methods with multi-extrapolated momentum for highly smooth unconstrained optimization

  • Chuan He
    • Categories Optimization in Data Science, Unconstrained Optimization Tags , , , , ,

    In this paper we consider an unconstrained stochastic optimization problem where the objective function exhibits a high order of smoothness. In particular, we propose a stochastic first-order method (SFOM) with multi-extrapolated momentum, in which multiple extrapolations are performed in each iteration, followed by a momentum step based on these extrapolations. We show that our proposed … Read more

    Randomized Subspace Derivative-Free Optimization with Quadratic Models and Second-Order Convergence

  • Lindon Roberts
  • Coralia Cartis
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    We consider model-based derivative-free optimization (DFO) for large-scale problems, based on iterative minimization in random subspaces. We provide the first worst-case complexity bound for such methods for convergence to approximate second-order critical points, and show that these bounds have significantly improved dimension dependence compared to standard full-space methods, provided low accuracy solutions are desired and/or … Read more

    Addressing Estimation Errors through Robust Portfolio Optimization

  • Gérard Cornuéjols
  • Ozgun Elci
  • Vrishabh Patil
    • Categories Convex Optimization, Quadratic Programming, Robust Optimization Tags , ,

    It is well known that the performance of the classical Markowitz model for portfolio optimization is extremely sensitive to estimation errors on the expected asset returns. Robust optimization mitigates this issue. We focus on ellipsoidal uncertainty sets around a point estimate of the expected asset returns. An important issue is the choice of the parameters … Read more

    A multilevel stochastic regularized first-order method with application to finite sum minimization

  • Margherita Porcelli
  • Elisa Riccietti
  • Filippo Marini
    • Categories Nonlinear Optimization, Stochastic Programming

    In this paper, we propose a multilevel stochastic framework for the solution of nonconvex unconstrained optimization problems. The proposed approach uses random regularized first-order models that exploit an available hierarchical description of the problem, being either in the classical variable space or in the function space, meaning that different levels of accuracy for the objective … Read more

    Gradient-Driven Solution Based on Indifference Analysis (GIA) for Scenario Modelling Optimization Problem

  • Vincent Yuansang Zha
    • Categories Applications - OR and Management Sciences, Finance and Economics, Nonlinear Optimization Tags , , ,

    This paper introduces an optimization technique for scenario modeling in uncertain business situations, termed the Gradient-Driven Solution Based on Indifference Analysis (GIA). GIA evolves the conventional methods of scenario planning by applying a reverse-strategy approach, where future financial goals are specified, and the path to attain these targets are engineered backward. It adopts economic concepts … Read more

    A general merit function-based global convergent framework for nonlinear optimization

  • Luís Felipe Bueno
  • Ernesto G. Birgin
  • Tiara Martini
  • Dimary Moreno López
  • Thadeu Senne
  • Thiago Siqueira Santos
    • Categories Nonlinear Optimization Tags , , , , ,

    In this paper, we revisit the convergence theory of the inexact restoration paradigm for non-linear optimization. The paper first identifies the basic elements of a globally convergent method based on merit functions. Then, the inexact restoration method that employs a two-phase iteration is introduced as a special case. A specific implementation is presented that is … Read more

    The Proximal Bundle Algorithm Under a Frank-Wolfe Perspective: an Improved Complexity Analysis

  • David Fersztand
  • Xu Andy Sun
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    The proximal bundle algorithm (PBA) is a fundamental and computationally effective algorithm for solving optimization problems with nonsmooth components. We investigate its convergence rate, focusing on composite settings where one function is smooth and the other is piecewise linear. We interpret a sequence of null steps of the PBA as a Frank-Wolfe algorithm on the … Read more