Optimizing QPs

INDEX

Gray bullet

ILOG CPLEX allows you to solve your QP models through a simple interface, by calling the default optimizer as follows:

In the Interactive Optimizer, use the command optimize.
From the Callable Library, use the routine CPXqpopt.
In Concert applications, use the solve method of IloCplex.

With default settings, this will result in the barrier optimizer being called to solve a continuous QP.

For users who wish to tune the performance of their applications, there are two Simplex optimizers to try for solving QPs. They are Dual Simplex and Primal Simplex. You can also use the Network Simplex optimizer; this solves the model as an LP network (temporarily ignoring the quadratic term in the objective function) and takes this solution as a starting point for the Primal Simplex QP optimizer. This choice of QP optimizer is controlled by the RootAlg parameter (QPMETHOD in the Interactive Optimizer and in the Callable Library). Table 12.1 shows you the possible settings.

Table 12.1 RootAlg Parameter Settings

RootAlg Value

Optimizer

Automatic (default)

Primal Simplex

Dual Simplex

Network Simplex

Barrier

Sifting

Concurrent

Many of the optimizer tuning decisions for LP apply in the QP case; and parameters that control Barrier and Simplex optimizers in the LP case can be set for the QP case, although in some instances to differing effect. Most models are solved fastest by default parameter settings. See the LP chapter for tuning advice.

Just as for the LP case, each of the available QP optimizers automatically preprocesses your model, conducting presolution problem analysis and reductions appropriate for a QP.

The Barrier optimizer for QP supports crossover, but unlike other LP optimizers, its crossover step is off by default for QPs. The QP Simplex optimizers return basic solutions, and these bases can be used for purposes of restarting sequences of optimizations, for example. As a result, application writers who wish to allow end users control over the choice of QP optimizer need to be aware of this fundamental difference and to program carefully. For most purposes, the nonbasic barrier solution is entirely satisfactory, in that all such solutions fully satisfy the standard optimality and feasibility conditions of optimization theory.