Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. 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. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.