Month: December 2024

A proximal alternating direction method of multipliers with a proximal-perturbed Lagrangian function for nonconvex and nonsmooth structured optimization

  • Pengjie Liu
    • Categories Nonsmooth Optimization Tags , , ,

    Building on [J. Glob. Optim. 89 (2024) 899–926], we continue to focus on solving a nonconvex and nonsmooth structured optimization problem with linear and closed convex set constraints, where its objective function is the sum of a convex (possibly nonsmooth) function and a smooth (possibly nonconvex) function. Based on the traditional augmented Lagrangian construction, we … 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

    Accelerating Proximal Gradient Descent via Silver Stepsizes

  • Jinho Bok
  • Jason M. Altschuler
    • Categories Convex Optimization

    Surprisingly, recent work has shown that gradient descent can be accelerated without using momentum–just by judiciously choosing stepsizes. An open question raised by several papers is whether this phenomenon of stepsize-based acceleration holds more generally for constrained and/or composite convex optimization via projected and/or proximal versions of gradient descent. We answer this in the affirmative … Read more

    Faces of homogeneous cones and applications to homogeneous chordality

  • João Gouveia
  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    A convex cone K is said to be homogeneous if its group of automorphisms acts transitively on its relative interior. Important examples of homogeneous cones include symmetric cones and cones of positive semidefinite (PSD) matrices that follow a sparsity pattern given by a homogeneous chordal graph. Our goal in this paper is to elucidate the … Read more

    Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule

  • Jason M. Altschuler
  • Pablo A. Parrilo
    • Categories Convex Optimization

    We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution improves the iteration complexity from $O(k)$ to $O(k^{1/2})$, where $k$ is the condition number. No momentum or other algorithmic modifications are required. This result is incomparable to the (deterministic) Silver Stepsize Schedule which … Read more

    Neural Embedded Mixed-Integer Optimization for Location-Routing Problems

  • Waquar Kaleem
  • Anirudh Subramanyam
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , ,

    We present a novel framework that combines machine learning with mixed-integer optimization to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is a classical yet NP-hard problem that integrates strategic facility location with operational vehicle routing decisions, aiming to simultaneously minimize both fixed and variable costs. The proposed method first trains a permutationally invariant neural … Read more

    Effective Scenarios in Distributionally Robust Optimization with Wasserstein Distance

  • Chennan Zhou
  • Güzin Bayraksan
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    This paper studies effective scenarios in Distributionally Robust Optimization (DRO) problems defined on a finite number of realizations (also called scenarios) of the uncertain parameters. Effective scenarios are critical scenarios in DRO in the sense that their removal from the support of the considered distributions alters the optimal value. Ineffective scenarios are those whose removal … 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

    A Generalized Voting Game for Categorical Network Choices

  • Lin Yueh
  • Stefano Nasini
  • Martine Labbé
    • Categories Combinatorial Optimization, Data Science Algorithms, Game Theory Tags , , ,

    This paper presents a game-theoretical framework for data classification and network discovery, focusing on pairwise influences in multivariate choices. The framework consists of two complementary games in which individuals, connected through a signed weighted graph, exhibit network similarity. A voting rule captures the influence of an individual’s neighbors, categorized as attractive (friend-like) or repulsive (enemy-like), … Read more

    A proximal-perturbed Bregman ADMM for solving nonsmooth and nonconvex optimization problems

  • Jianchao Bai
    • Categories Nonsmooth Optimization Tags , , ,

    In this paper, we focus on a linearly constrained composite minimization problem whose objective function is possibly nonsmooth and nonconvex. Unlike the traditional construction of augmented Lagrangian function, we provide a proximal-perturbed augmented Lagrangian and then develop a new Bregman Alternating Direction Method of Multipliers (ADMM). Under mild assumptions, we show that the novel augmented … Read more