Global Optimization Theory – Page 23

Solving standard quadratic optimization problems via linear, semidefinite and copositive programming

Published: 2001/05/23, Updated: 2007/05/14

Combinatorial Optimization, Global Optimization Theory, Semi-definite Programming approximation algorithms, copositive programming, semidefinite programming, stability number, standard quadratic optimization

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities … Read more

Generating Convex Polynomial Inequalities for Mixed 0-1 Programs

Published: 2001/01/05

Sanjay Mehrotra

Robert Stubbs

(Mixed) Integer Nonlinear Programming, Convex Optimization, Global Optimization Theory convex polynomial inequalities, disjunctive programming, lift-and-project, linearization relaxation techniques, mixed-integer programming

We develop a method for generating valid convex polynomial inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities. Article Download View Generating Convex … Read more