Year: 2025

On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems

  • Samuel Burer
  • Karthik Natarajan
    • Categories Quadratic Programming, Robust Optimization, Semi-definite Programming Tags , ,

    We study continuous quadratic submodular minimization with bounds and propose a polynomially sized semidefinite relaxation, which is provably tight for dimension n ≤ 3 and empirically tight for larger n. We apply the relaxation to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing … Read more

    On regularized structure exploiting Quasi-Newton methods for inverse problems

  • Raphael Kuess
  • Andrea Walther
    • Categories Infinite Dimensional Optimization, Nonlinear Systems and Least-Squares Tags , , , ,

    This paper introduces a regularized, structure-exploiting Powell-Symmetric-Broyden (RSE-PSB) method under modified secant conditions for solving ill-posed inverse problems in both infinite dimensional and finite dimensional settings. The approximation of the symmetric, yet potentially indefinite, second-order term, which is neglected by standard Levenberg-Marquardt (LM) approaches, integrates regularization and structure exploitation directly within the Quasi-Newton (QN) framework, … Read more

    Extending Exact Convex Relaxations of Quadratically Constrained Quadratic Programs

  • Masakazu Kojima
  • Sunyoung Kim
  • Naohiko Arima
    • Categories Convex Optimization, Global Optimization, Semi-definite Programming Tags , , , ,

    A convex relaxation of a quadratically constrained quadratic program (QCQP) is called exact if it has a rank-$1$ optimal solution that corresponds to an optimal solution of the  QCQP. Given a QCQP whose convex relaxation is exact,  this paper investigates the incorporation of additional quadratic inequality constraints under a non-intersecting quadratic constraint condition while maintaining … Read more

    Efficient search strategies for constrained multiobjective blackbox optimization

  • Sébastien Le Digabel
  • Antoine Lesage-Landry
  • Ludovic Salomon
  • Christophe Tribes
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags ,

    Multiobjective blackbox optimization deals with problems where the objective and constraint functions are the outputs of a numerical simulation. In this context, no derivatives are available, nor can they be approximated by finite differences, which precludes the use of classical gradient-based techniques. The DMulti-MADS algorithm implements a state-of-the-art direct search procedure for multiobjective blackbox optimization … Read more

    New Algorithms for maximizing the difference of convex functions

  • Aharon Ben-Tal
  • Luba Tetruashvili
    • Categories Global Optimization, Global Optimization Applications, Nonlinear Optimization

    Maximizing the difference of 2 convex functions over a convex feasible set (the so called DCA problem) is a hard problem. There is a large number of publications addressing this problem. Many of them are variations of widely used DCA algorithm [20]. The success of this algorithm to reach a good approximation of a global … Read more

    Cost allocation in maintenance clustering

  • Andries van Beek
  • Loe Schlicher
    • Categories Applications - OR and Management Sciences, Game Theory Tags , , , ,

    Inspired by collaborative initiatives in the military domain, we analyze a setting in which multiple different players (e.g., Ministries of Defence) have to carry out preventive maintenance jobs. Each player is responsible for one job, with a job-specific minimal frequency and with maintenance costs, consisting of a job-specific variable component and a fixed component, which … Read more

    Optimistic Noise-Aware Sequential Quadratic Programming for Equality Constrained Optimization with Rank-Deficient Jacobians

  • Jiahao Shi
  • Baoyu Zhou
  • Albert S. Berahas
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    We propose and analyze a sequential quadratic programming algorithm for minimizing a noisy nonlinear smooth function subject to noisy nonlinear smooth equality constraints. The algorithm uses a step decomposition strategy and, as a result, is robust to potential rank-deficiency in the constraints, allows for two different step size strategies, and has an early stopping mechanism. … Read more

    Facial approach for constructing stationary points for mathematical programs with cone complementarity constraints

  • Javier I. Madariaga
  • Héctor Ramírez
    • Categories Complementarity and Variational Inequalities, Cone Programming Tags , , ,

    This paper studies stationary points in mathematical programs with cone complementarity constraints (CMPCC). We begin by reviewing various formulations of CMPCC and revisiting definitions for Bouligand, proximal strong, regular strong, Wachsmuth’s strong, L-strong, weak, as well as Mordukhovich and Clarke stationary points, establishing a comprehensive framework for CMPCC. Building on key principles related to cone … Read more

    qpBAMM: a parallelizable ADMM approach for block-structured quadratic programs

  • Michel Lahmann
  • Christian Kirches
  • Martin T. Köhler
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    Block-structured quadratic programs (QPs) frequently arise in the context of the direct approach to solving optimal control problems. For successful application of direct optimal control algorithms to many real-world problems it is paramount that these QPs can be solved efficiently and reliably. Besides interior-point methods and active-set methods, ADMM-based quadratic programming approaches have gained popularity. … Read more

    A note on asynchronous Projective Splitting in Julia

  • Utkarsh Sharma
  • Kashish Goel
  • Aryan Dua
  • Sebastian Pokutta
  • Zev Woodstock
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Parallel Algorithms

    While it has been mathematically proven that Projective Splitting (PS) algorithms can converge in parallel and distributed computing settings, to-date, it appears there were no open-source implementations of the full algorithm with asynchronous computing capabilities. This note fills this gap by providing a Julia implementation of the asynchronous PS algorithm of Eckstein and Combettes for … Read more