Nonlinear Optimization

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

    Sparse Polynomial Matrix Optimization

  • Jie Wang
  • Feng Guo
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , ,

    A polynomial matrix inequality is a statement that a symmetric polynomial matrix is positive semidefinite over a given constraint set. Polynomial matrix optimization concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of polynomial matrix inequalities. This work explores the use of sparsity methods in reducing the complexity of sum-of-squares … Read more

    Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms

  • Victor Bucarey
  • Sophia Calderón
  • Gonzalo Muñoz
  • Frédéric Semet
    • Categories Constrained Nonlinear Optimization, Data Science Applications, Other Topics Tags ,

    Dealing with uncertainty in optimization parameters is an important and longstanding challenge. Typically, uncertain parameters are predicted accurately, and then a deterministic optimization problem is solved. However, the decisions produced by this so-called {\it predict-then-optimize} procedure can be highly sensitive to uncertain parameters. In this work, we contribute to recent efforts in producing {\it decision-focused} … Read more

    Unboundedness in Bilevel Optimization

  • Bárbara Rodrigues
  • Margarida Carvalho
  • Miguel F. Anjos
  • nsugishita
    • Categories Bilevel Optimization, Nonlinear Optimization Tags , , ,

    Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel and multilevel optimization by studying its computational complexity. We show that deciding whether an … Read more