Reduction of indefinite quadratic programs to bilinear programs (Q1187369)

The authors consider the problem of reducing indefinite quadratic programs (Q) to bilinear programs (B) based on a duplication of variables. They propose optimal reduction methods for two criteria: (i) the number of additional variables and (ii) the number of complicating variables (i.e., the number of variables which yield, after fixation, an easy-to-solve problem). These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Finally the reduction of more general global optimization problem than quadratic programs (as example, polynomial programs, hyperbolic programs, problems with variables having fractional exponents, trigonometric and transcendental functions) is discussed.