Month: January 2026

An adaptive line-search-free multiobjective gradient method and its iteration-complexity analysis

  • Max L. N. Gonçalves
  • Geovani Nunes Grapiglia
  • Jefferson Gonçalves Melo
    • Categories Multi-Criteria Optimization, Unconstrained Optimization Tags , , ,

    This work introduces an Adaptive Line-Search-Free Multiobjective Gradient (AMG) method for solving smooth multiobjective optimization problems. The proposed approach automatically adjusts stepsizes based on steepest descent directions, promoting robustness with respect to stepsize choice while maintaining low computational cost. The method is specifically tailored to the multiobjective setting and does not rely on function evaluations, … Read more

    On Approximate Computation of Critical Points

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Unconstrained Optimization Tags , ,

    We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in \(n\) variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm … Read more

    Potential-Based Flows – An Overview

  • Marc E. Pfetsch
  • Martin Schmidt
  • Martin Skutella
  • Johannes Thürauf
    • Categories Energy, Network Optimization

    Potential-based flows provide an algebraic way to model static physical flows in networks, for example, in gas, water, and lossless DC power networks. The flow on an arc in the network depends on the difference of the potentials at its end-nodes, possibly in a nonlinear way. Potential-based flows have several nice properties like uniqueness and … Read more

    Asymptotically tight Lagrangian dual of smooth nonconvex problems via improved error bound of Shapley-Folkman Lemma

  • Jingye Xu
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    In convex geometry, the Shapley–Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$-dimensional bounded nonconvex sets does not accumulate once the number of summands exceeds the dimension $n$, and thus the sum becomes approximately convex. Originally published by Starr in the context of quasi-equilibrium in nonconvex market models in economics, the lemma … Read more

    Riemannian optimization with finite-difference gradient approximations

  • Timothé Taminiau
  • Estelle Massart
  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization Tags , ,

    Derivative-free Riemannian optimization (DFRO) aims to minimize an objective function using only function evaluations, under the constraint that the decision variables lie on a Riemannian manifold. The rapid increase in problem dimensions over the years calls for computationally cheap DFRO algorithms, that is, algorithms requiring as few function evaluations and retractions as possible. We propose … Read more

    A Marginal Reliability Impact Based Accreditation Framework for Capacity Markets

  • Feng Zhao
    • Categories Energy Tags , , , , , , ,

    This paper presents a Marginal Reliability Impact (MRI) based resource accreditation framework in the context of capacity market design. Under this framework, a resource is accredited based on its marginal impact on system reliability, thus aligning the resource’s capacity market value with its reliability contribution. A salient feature of the MRI-based accreditation is that each … Read more

    Non-Convex Self-Concordant Functions: Practical Algorithms and Complexity Analysis

  • Donald Goldfarb
    • Categories Convex Optimization Tags

    We extend the standard notion of self-concordance to non-convex optimization and develop a family of second-order algorithms with global convergence guarantees. In particular, two function classes – weakly self-concordant functions and F-based self-concordant functions – generalize the self-concordant framework beyond convexity, without assuming the Lipschitz continuity of the gradient or Hessian. For these function classes, … Read more

    Infeasibility Certificates from Superadditive Functions for Mixed-Integer Programs

  • Natasha Patnaik
  • Tu Anh-Nguyen
  • Akshay Gupte
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present a constructive procedure for certifying the infeasibility of a mixed-integer program (MIP) using recursion on a sequence of sets that describe the sets of barely feasible right-hand sides. Each of these sets corresponds to a monotonic superadditive function, and the pointwise limit of this sequence is a functional certificate for MIP infeasibility. Our … Read more

    A first approximation algorithm for the Bin Packing Problem with Setups

  • Fabio Ciccarelli
  • Roberto Baldacci
  • Stefano Coniglio
  • Valerio Dose
  • Fabio Furini
    • Categories Approximation Algorithms, Combinatorial Optimization

    We study constant-factor approximation algorithms for the Bin Packing Problem with Setups (BPPS). First, we show that adaptations of classical BPP heuristics can have arbitrarily poor worst-case performance on BPPS instances. Then, we propose a two-phase heuristic for the BPPS that applies an α-approximation algorithm for the BPP to the items of each class and … Read more