Quadratically constrained convex quadratic programs: Faulty feasible regions

We are concerned with the problem of minimizing a convex quadratic function subject to convex quadratic constraints. In particular, we are concerned with the application of the method of analytic centres to problems having a faulty feasible region, i.e. a region that is either unbounded or not full dimensional. Each iteration of a method of centres must determine an analytic centre of a truncated feasible region. If the feasible region is faulty, then the truncated region may have no interior, it may have no analytic centre, it may have an infinity of centres, or it may have a unique centre. Thus, the difficulty caused by faulty feasible regions is that, even when the problem has a solution, the method of centres may fail. Typically, faulty regions have been dealt with by the direct method of adding more constraints and variables, often involving a ‘Big M’ constant. Our method is unique in that it results in a reduction in the number of constraints and, effectively, in the number of variables.