The Quadratic Programming Solver -- Experimental


The OPTMODEL procedure provides a framework for specifying and solving quadratic programs.

Mathematically, a quadratic programming (QP) problem can be stated as follows:

\min & \frac{1}2\, \mathbf{x}^{\rm t} \mathbf{qx} + \mathbf{c}^{\rm t} \mathbf{x...   ...} \;\{\ge, =, \le\}\; \mathbf{b} \    & \mathbf{l} \le \mathbf{x} \le \mathbf{u}

 \mathbf{q} \in\mathbb{r}^{nx n}is the quadratic (also known as Hessian) matrix
 \mathbf{a} \in\mathbb{r}^{mx n}is the constraints matrix
 \mathbf{x} \in\mathbb{r}^nis the vector of decision variables
 \mathbf{c} \in\mathbb{r}^nis the vector of linear objective function coefficients
 \mathbf{b} \in\mathbb{r}^mis the vector of constraints right-hand sides (RHS)
 \mathbf{l} \in\mathbb{r}^nis the vector of lower bounds on the decision variables
 \mathbf{u} \in\mathbb{r}^nis the vector of upper bounds on the decision variables

The quadratic matrix \mathbf{q} is assumed to be symmetric; i.e.,

q_{ij} = q_{ji}, \forall i,j = 1,  ... , n
Indeed, it is easy to show that even if \mathbf{q} \not= \mathbf{q}^{\rm t}, then the simple modification
\tilde \mathbf{q} = \frac{1}2(\mathbf{q} + \mathbf{q}^{\rm t})
produces an equivalent formulation \mathbf{x}^{\rm t}\mathbf{qx} \equiv \mathbf{x}^{\rm t}{\tilde   \mathbf{q}}\mathbf{x}; hence symmetry is assumed. When specifying a quadratic matrix it suffices to list only lower triangular coefficients.

In addition to being symmetric, \mathbf{q} is also required to be positive semidefinite:

\mathbf{x}^{\rm t}\mathbf{qx} \ge 0, \forall \mathbf{x}\in\mathbb{r}^n
for minimization type of models; it is required to be negative semidefinite for maximization type of models. Convexity can come as a result of a matrix-matrix multiplication
\mathbf{q} = \mathbf{l}\mathbf{l}^{\rm t}
or as a consequence of physical laws, etc. See Figure 12.1 for examples of convex, concave, and nonconvex objective functions.

optqpconvex.gif (228647 bytes)

Figure 12.1: Examples of Convex, Concave, and Nonconvex Objective Functions

The order of constraints is insignificant. Some or all components of \mathbf{l} or \mathbf{u} (lower/upper bounds) can be omitted.

Previous Page | Next Page | Top of Page