Convex Optimization

On the Resolution of Ties in Fair Convex Allocation Problems

  • Bismark Singh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    We study the emergence of indistinguishable, but structurally distinct, allocation outcomes in convex resource allocation models. Such outcomes occur when different users receive proportionally identical allocations despite differences in initial conditions, eligibility sets, or priority weights. We formalize this behavior and analyze the structural conditions under which it arises, with a focus on fairness-oriented objectives. … Read more

    A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems

  • Hao Hu
    • Categories (Mixed) Integer Linear Programming, Convex Optimization

    We propose a novel facial reduction algorithm tailored to semidefinite programming relaxations of combinatorial optimization problems with quadratic objective functions. Our method leverages the specific structure of these relaxations, particularly the availability of feasible solutions that can often be generated efficiently in practice. By incorporating such solutions into the facial reduction process, we substantially simplify … Read more

    Cooperative vs Noncooperative Scenarios in multi-objective Potential games: the multi-portfolio context

  • Valerio Giuseppe Sasso
  • Lorenzo Lampariello
  • Simone Sagratella
    • Categories Convex Optimization, Game Theory Tags , , ,

    We focus on multi-agent, multi-objective problems, particularly on those where the objectives admit a potential structure. We show that the solution to the potential multi-objective problem is always a noncooperative optimum for the multi-agent setting. Furthermore, we identify a class of problems for which every noncooperative solution can be computed via the potential problem. We … Read more

    General Perturbation Resilient Dynamic String-Averaging for Inconsistent Problems with Superiorization

  • Kay Barshad
  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , , , , , , , ,

    In this paper we introduce a General Dynamic String-Averaging (GDSA) iterative scheme and investigate its convergence properties in the inconsistent case, that is, when the input operators don’t have a common fixed point. The Dynamic String-Averaging Projection (DSAP) algorithm itself was introduced in an 2013 paper, where its strong convergence and bounded perturbation resilience were … Read more

    Swapping objectives accelerates Davis-Yin splitting

  • Jaewook J. Suh
  • Xin Jiang
  • Shiqian Ma
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    In this work, we investigate the application of Davis–Yin splitting (DYS) to convex optimization problems and demonstrate that swapping the roles of the two nonsmooth convex functions can result in a faster convergence rate. Such a swap typically yields a different sequence of iterates, but its impact on convergence behavior has been largely understudied or … Read more

    Optimized methods for composite optimization: a reduction perspective

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

    Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimized method is specially tailored for a particular problem setting, and it is a well-documented challenge to extend optimized methods to other settings due to their highly bespoke design and analysis. We provide a general … Read more

    First-order methods for stochastic and finite-sum convex optimization with deterministic constraints

  • Zhaosong Lu
  • Yifeng Xiao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an \(\epsilon\)-expectedly feasible stochastic optimal solution, in which the expected constraint violation and expected optimality gap are both within a prescribed tolerance ϵ. However, in many practical applications, constraints must be nearly … Read more

    Dual certificates of primal cone membership

  • Joonyeob Lee
  • Dávid Papp
  • Anita Varga
    • Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , ,

    We discuss easily verifiable cone membership certificates, that is, certificates proving relations of the form \( b\in K \) for convex cones \(K\) that consist of vectors in the dual cone \(K^*\). Vectors in the dual cone are usually associated with separating hyperplanes, and so they are interpreted as certificates of non-membership in the standard … Read more

    Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems

  • Bowen Yuan
    • Categories Convex Optimization, Nonsmooth Optimization Tags , ,

    The part of the analysis of the convergence rate of the mirror descent method that is connected with the adaptive time-varying step size rules due to Alkousa et al. (MOTOR 2024, pp. 3-18) is corrected. Moreover, a Lipschitz-free mirror descent method that achieves weak ergodic convergence is presented, generalizing the convergence results of the mirror … Read more

    Gradient Methods with Online Scaling Part I. Theoretical Foundations

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , ,

    This paper establishes the theoretical foundations of the online scaled gradient methods (OSGM), a framework that utilizes online learning to adapt stepsizes and provably accelerate first-order methods. OSGM quantifies the effectiveness of a stepsize by a feedback function motivated from a convergence measure and uses the feedback to adjust the stepsize through an online learning … Read more