Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Princeton University Press eBooks

On approximation algorithms for concave quadratic programming

Stephen A. Vavasis

Published Dec 31, 1991• 18 citations
Publisher

Abstract

We consider $\epsilon$-approximation schemes for concave quadratic programming. Because the existing definition of $\epsilon$-approximation for combinatorial optimization problems is inappropriate for nonlinear optimization, we propose a new definition for $\epsilon$-approximation. We argue that such an approximation can be found in polynomial time for fixed $\epsilon$ and $k$, where $k$ denotes the number of negative eigenvalues. Our algorithm is polynomial in 1/$\epsilon$ for fixed $k$, and superexponential in $k$ for fixed $\epsilon$.

DOI
10.1515/9781400862528.3

Related papers

Subdeterminants and Concave Integer Quadratic Programming

Alberto Del Pia

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by $\Delta$ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an $\epsilon$-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by $\Delta$ in absolute value. The number of these integer linear programs is polynomial in the dimension $n$, in $\Delta$, and in $1/\epsilon$, provided that the number $k$ of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with $\Delta \le 2$ and $k$ fixed. In the totally unimodular case $\Delta = 1$, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in $1/\epsilon$ and is independent of $n$, provided that $k$ is fixed.

arXiv:1810.02763•SIAM Journal on Optimization•Jan 1, 2019•8 citations

Polynomial Time Weak Approximation Algorithms for Quadratic Programming

Stephen A. Vavasis

We consider the problem of computing an approximate solution to quadratic programming problems. We focus on algorithms whose running time is polynomial. We show that a solution satisfying weak bounds with resped to optimality can be computed in polynomial time. We also show that for a special case, choosing a random feasible point satisfies the same bound. Recent complexity theory suggests that computing solutions with much stronger bounds cannot be done in polynomial time.

WORLD SCIENTIFIC eBooks•Jul 1, 1993•18 citations

New approximation methods for solving binary quadratic programming problem

Rui Yang

In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.

•Jun 22, 2010•2 citations

A Polynomial-Time Recursive Algorithm for some Unconstrained Quadratic Optimization Problems.

Walid Ben‐Ameur, José Neto

Consider a quadratic function q : Rn -> R given by: q(x) = xtQx, with Q E Rn×n. An unconstrained (−1, 1)-quadratic optimization problem can be expressed as follows: (QP) Z* = min{q(x) | x E {−1, 1}*}, where {−1, 1}n denotes the set of n-dimensional vectors with entries either equal to 1 or −1.We consider here that the matrix Q is symmetric and given by its spectrum, i.e. the set of its eigenvalues and associated unit pairwise orthogonal eigenvectors. Problem (QP) is a classical combinatorial optimization problem with many applications, e.g. in statistical physics and circuit design [2; 8; 10]. It is well-known that any (0,1)-quadratic problem expressed as: min{xt Ax + ctx | x E {0, 1}n}, A E Rn×n, c E Rn, can be formulated in the form of problem (QP) and conversely [9; 4]. The contribution of this work is 3-fold: (i) We slightly extend the known polynomially solvable cases of (QP) to when the matrix Q has fixed rank and the number of positive diagonal entries is O(log(n)). (ii) We introduce a new (to our knowledge) polynomial-time algorithmfor solving problem (QP) when it corresponds to such a polynomially solvable case. (iii) Preliminary experiments indicate that the proposed method may be computationally efficient

Cologne Twente Workshop on Graphs and Combinatorial Optimization•Jan 1, 2009•0 citations

Concave Quadratic Cuts for Mixed-Integer Quadratic Problems

Jaehyun Park, Stephen Boyd

The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice ${\bf Z}^n$, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.

arXiv:1510.06421•Oct 21, 2015•5 citations

Approximate maximum-likelihood estimation using semidefinite programming

J. Dahl, Bernard H. Fleury, Lieven Vandenberghe

We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 22, 2004•9 citations
We consider ϵ\epsilonϵ-approximation schemes for concave quadratic programming. Because the existing definition of ϵ\epsilonϵ-approximation for combinatorial optimization problems is inappropriate for nonlinear optimization, we propose a new definition for ϵ\epsilonϵ-approximation. We argue that such an approximation can be found in polynomial time for fixed ϵ\epsilonϵ and kkk, where kkk denotes the number of negative eigenvalues. Our algorithm is polynomial in 1/ϵ\epsilonϵ for fixed kkk, and superexponential in kkk for fixed ϵ\epsilonϵ.
We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by Δ\DeltaΔ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an ϵ\epsilonϵ-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by Δ\DeltaΔ in absolute value. The number of these integer linear programs is polynomial in the dimension nnn, in Δ\DeltaΔ, and in 1/ϵ1/\epsilon1/ϵ, provided that the number kkk of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with Δ≤2\Delta \le 2Δ≤2 and kkk fixed. In the totally unimodular case Δ=1\Delta = 1Δ=1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/ϵ1/\epsilon1/ϵ and is independent of nnn, provided that kkk is fixed.
In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.
Consider a quadratic function q : Rn -> R given by: q(x) = xtQx, with Q E Rn×n. An unconstrained (−1, 1)-quadratic optimization problem can be expressed as follows: (QP) Z* = min{q(x) | x E {−1, 1}*}, where {−1, 1}n denotes the set of n-dimensional vectors with entries either equal to 1 or −1.We consider here that the matrix Q is symmetric and given by its spectrum, i.e. the set of its eigenvalues and associated unit pairwise orthogonal eigenvectors. Problem (QP) is a classical combinatorial optimization problem with many applications, e.g. in statistical physics and circuit design [2; 8; 10]. It is well-known that any (0,1)-quadratic problem expressed as: min{xt Ax + ctx | x E {0, 1}n}, A E Rn×n, c E Rn, can be formulated in the form of problem (QP) and conversely [9; 4]. The contribution of this work is 3-fold: (i) We slightly extend the known polynomially solvable cases of (QP) to when the matrix Q has fixed rank and the number of positive diagonal entries is O(log(n)). (ii) We introduce a new (to our knowledge) polynomial-time algorithmfor solving problem (QP) when it corresponds to such a polynomially solvable case. (iii) Preliminary experiments indicate that the proposed method may be computationally efficient
The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice Zn{\bf Z}^nZn, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.
We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.