Month: February 2026

Modeling Binary Relations in Piecewise-Linear Approximations

  • Kristin Braun
  • Robert Burlacu
  • Tobias Kuen
  • kristinarolsing
    • Categories Combinatorial Optimization, Global Optimization Theory, Nonlinear Optimization Tags , , , , ,

    Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs. Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial. We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane … Read more

    Dantzig-Wolfe and Arc-Flow Reformulations: A Systematic Comparison

  • Daniel Yamin
  • Willem-Jan van Hoeve
  • Ted K. Ralphs
    • Categories Combinatorial Optimization, Integer Programming

    Dantzig-Wolfe reformulation is a widely used technique for obtaining stronger relaxations in the context of branch-and-bound methods for solving integer optimization problems. Arc-Flow reformulations are a lesser known technique related to dynamic programming that has experienced a resurgence as result of the recent popularization of decision diagrams as a tool for solving integer programs. Although … Read more

    Separating Hyperplanes for Mixed-Integer Polynomial Optimization Problems

  • Carl Eggen
  • Jan Kronqvist
  • Andreas Lundell
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Tags , , ,

    Algorithms based on polyhedral outer approximations provide a powerful approach to solving mixed-integer nonlinear optimization problems. An initial relaxation of the feasible set is strengthened by iteratively adding linear inequalities and separating infeasible points. However, when the constraints are nonconvex, computing such separating hyperplanes becomes challenging. In this article, the moment-/sums-of-squares hierarchy is used in … Read more

    Convergence Analysis of an Inertial Dynamical System with Hessian-Driven Damping under θ-Parametrized Implicit–Explicit Discretization

  • Milan Barik
  • Suvendu Ranjan Pattanaik
    • Categories Other Topics Tags

    In this paper, we consider an unconstrained composite convex optimisation problem. We propose an inertial forward–backward algorithm derived from an implicit– explicit discretisation of a second-order dynamical system with Hessian-driven damping. For α ≥ 3, we establish an O(1/d^2) convergence rate for the objective value gap. Furthermore, when α > 3, we prove that the … Read more

    A Projected Stochastic Gradient Method for Finite-Sum Problems with Linear Equality Constraints

  • Nataša Krklec Jerinkić
  • Benedetta Morini
  • Mahsa Yousefi
    • Categories Nonlinear Optimization, Optimization in Data Science Tags , ,

    A stochastic gradient method for finite-sum minimization subject to deterministic linear constraints is proposed and analyzed. The procedure presented adapts the projected gradient method on a convex set to the use of both a stochastic gradient and a possibly inexact projection map. Under standard assumptions in the field of stochastic gradient methods, we provide theoretical … Read more

    Improved Analysis of Restarted Accelerated Gradient and Augmented Lagrangian Methods via Inexact Proximal Point Frameworks

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    This paper studies a class of double-loop (inner-outer) algorithms for convex composite optimization. For unconstrained problems, we develop a restarted accelerated composite gradient method that attains the optimal first-order complexity in both the convex and strongly convex settings. For linearly constrained problems, we introduce inexact augmented Lagrangian methods, including a basic method and an outer-accelerated … Read more

    Modelling and Analysis of an Inverse Parameter Identification Problem in Piezoelectricity

  • Raphael Kuess
  • Daniel Walter
  • Andrea Walther
    • Categories Infinite Dimensional Optimization, Nonlinear Systems and Least-Squares, Systems governed by Differential Equations Optimization Tags , , , , ,

    Piezoelectric material behavior is mathematically described by coupled hyperbolic-elliptic partial differential equations (PDEs) governing mechanical displacement and electrical potential. This paper presents advancements in the theory of identifying material parameters in piezoelectric PDEs. We focus on modeling and analyzing the inverse problem assuming matrix-valued Sobolev-Bochner parameters to encompass a time and space-dependent setting and thus … Read more

    A General Penalty-Method and a General Regularization-Method for Cardinality-Constrained Optimization Problems

  • Felix P. Broesamle
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    We consider cardinality-constrained optimization problems (CCOPs), which are general nonlinear programs with an additional constraint limiting the number of nonzero continuous variables. The continuous reformulation of CCOPs involves complementarity constraints, which pose significant theoretical and computational challenges. To address these difficulties, we propose and analyze two numerical solution approaches: a general penalty method and a … Read more

    Tight semidefinite programming relaxations for sparse box-constrained quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , , ,

    We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more