Best ellipsoidal relaxation to solve a nonconvex problem.
type: Item
instance of: scholarly article
title: Best ellipsoidal relaxation to solve a nonconvex problem.
zbMATH Open document ID: 1053.65044
author: S. El Bernoussi
published in: Journal of Computational and Applied Mathematics
publication date: 2004-01-26T00:00:00Z
review text: The author presents an ellipsoidal relaxation of the problem \[ (P)\quad\min\{\frac{1}{2}x^{T}Ax+b^{T}x\mid x\in\{0,1\}^{n}\} \] where \(A\) is an \(n\times n\) symmetric matrix. He shows that the problem \((P)\) and its dual are strictly feasible; so strong duality holds. The numerical results presented indicate the fact that the discribed relaxation is efficient.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 2032620
zbMATH Keywords: quadratic Boolean programming
zbMATH Keywords: quadratic programming
zbMATH Keywords: ellipsoidal relaxation
zbMATH Keywords: semidefinite programming
zbMATH Keywords: numerical results
reviewed by: Dorel I. Duca
MaRDI profile type: Publication
full work available at URL: j.cam.2003.08.012
OpenAlex ID: W2008762851
cites work: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
cites work: Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
cites work: Laplacian eigenvalues and the maximum cut problem
cites work: Lower Bounds for the Partitioning of Graphs
cites work: Q4198056
cites work: A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm1
cites work: A branch and bound method via d. c. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems
cites work: On the Shannon capacity of a graph
cites work: Q4324980
cites work: Computational aspects of a branch and bound algorithm for quadratic zero- one programming
cites work: Constrained global optimization: algorithms and applications
cites work: A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
cites work: Convex Relaxations of (0, 1)-Quadratic Programming
cites work: Strong Duality for Semidefinite Programming
cites work: Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
cites work: A projection technique for partitioning the nodes of a graph
cites work: Some new search directions for primal-dual interior point methods in semidefinite programming
cites work: Semidefinite Programming
cites work: Handbook of semidefinite programming. Theory, algorithms, and applications
DOI: 10.1016/J.CAM.2003.08.012
Recommended article: An improved ellipsoid method for solving convex differentiable optimization problems
Recommended article: Q3033572
Recommended article: Subgradient ellipsoid method for nonsmooth convex problems
Recommended article: An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations
Recommended article: Q3142885
Recommended article: Relaxation and regularization of nonconvex variational problems
Recommended article: Exact relaxations of non-convex variational problems
Recommended article: Q4240202
Recommended article: An Ellipsoid Trust Region Bundle Method for Nonsmooth Convex Minimization
Recommended article: Q3811603
description: scientific article; zbMATH DE number 2032620