Global optimization algorithms for linearly constrained indefinite quadratic problems (Q810370): Difference between revisions

One considers the problem of finding a globally optimal solution to nonconvex quadratic problems of the form \[ (1)\quad global\quad \min_{x\in P}f(x)=c^ Tx+{1\over2}x^ TQx, \] where Q is an indefinite symmetric matrix, c, \(x\in R^ n\) and P is a bounded polyhedron in \(R^ n.\) The author shows that the optimal solution of problem (1) occurs at some boundary point of the feasible domain P and that if \(x^*\) solves (1), then \(x^*\) is also optimal for the linear program \(\min_{x\in P}(\nabla f(x^*))^ Tx.\) An overview of the most important methods used, including Benders decomposition, concave programming approaches, enumerative techniques, and bilinear programming, is given.