Quadratic Programming – Optimization Online

Sparsity-Preserving Integration of Convex Curvature Information into Linear Relaxations for Quadratic Unconstrained Binary Optimization

Published: 2026/08/24

Sven Mallach

We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly … Read more

Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

Published: 2026/08/03

Alberto Del Pia

(Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming approximation algorithm, computational complexity, Jacobi rotations, mixed-integer quadratic programming, Simultaneous diagonalization

We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective … Read more

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Published: 2026/08/02

(Mixed) Integer Nonlinear Programming, Quadratic Programming disjunctive optimization, indicator constraints, mixed-integer convex programming

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the Coordinate Optimality Reformulation (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable … Read more

Convexlikeness and Supportedness in Quadratic Multiobjective Optimization

Published: 2026/07/19

Multi-Criteria Optimization, Quadratic Programming convexlikeness, hidden convexity, multiobjective optimization, nonconvex optimization, nonconvex quadratic programming, s-lemma, supportedness, Weighted sum scalarization

This paper studies geometric and structural properties of quadratic multiobjective optimization problems. Thereby, a multiobjective optimization problem is called convexlike if the upper image, i.e., the image set plus the nonnegative orthant, is a convex set. Moreover, we say that a feasible point is supported in case it is a minimal solution of a weighted … Read more

Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion

Published: 2026/07/18

Cone Programming, Global Optimization Applications, Quadratic Programming quadratically constrained quadratic programming, Rank-one doubly nonnegative matrix completions, Rank-one solutions, Sparsity pattern of mathematical optimization problem., Tight conic relaxations

We study tight conic relaxations for a quadratically constrained quadratic programming (QCQP) formulation of rank-one doubly nonnegative (DNN) matrix completion. Motivated by sparse QCQPs whose lifted matrix variables include elements not directly specified by the objective or constraints, we interpret tightness as a rank-one completion property for the unspecified elements. For sparsity patterns whose blocks … Read more

Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

Published: 2026/06/19

Global Optimization Theory, Quadratic Programming, Semi-definite Programming block-clique sparsity, chordal graph, clique-wise formulation, exact SDP relaxation, local-to-global exactness, quadratically constrained quadratic program, rank-at-most-one optimal solution., semidefinite programming relaxation, sparse optimization

We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more

A unified framework for inexact adaptive stepsizes in the gradient methods, the conjugate gradient methods and the quasi-Newton methods for strictly convex quadratic optimization

Published: 2026/04/23

Zexian Liu

Convex Optimization, Quadratic Programming, Unconstrained Optimization Approximately optimal stepsize, conjugate gradient method, gradient method, Quasi-Newton method, Unified framework

The inexact adaptive stepsizes for the conjugate gradient method and the quasi-Newton method are very rare. The exact stepsizes in the gradient method, the conjugate gradient method and the quasi-Newton method for strictly convex quadratic optimization have a unified framework, while the unified framework for inexact adaptive stepsizes in the gradient method, the conjugate gradient … Read more

Separable QCQPs and Their Exact SDP Relaxations

Published: 2026/04/03

Global Optimization Theory, Quadratic Programming, Semi-definite Programming exact relaxation, horizontal connection, new rank-based exactness results, semidefinite programming relaxation, Separable QCQP, structured bilevel optimization.

This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters … Read more

Beyond binarity: Semidefinite programming for ternary quadratic problems

Published: 2026/03/30

(Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Branch-and-Bound, integer semidefinite programming, quadratic ratio problems, ternary optimization problem

We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation … Read more