QUADRATICALLY CONSTRAINED CONVEX QUADRATIC PROGRAMS - FAULTY FEASIBLEREGIONS

We are concerned with the problem of minimizing a convex quadratic fun ction subject to convex quadratic constraints. In particular, we are c oncerned with the application of the method of analytic centres to pro blems having a faulty feasible region, i.e. a region that is either un bounded 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 i nterior, it may have no analytic centre, it may have an infinity of ce ntres, 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 d ealt with by the direct method of adding more constraints and variable s, often involving a ''Big M'' constant. Our method is unique in that it results in a reduction in the number of constraints and, effectivel y, in the number of variables.