The Quadratic Programming Solver

Example 11.1 Linear Least Squares Problem

The linear least squares problem arises in the context of determining a solution to an overdetermined set of linear equations. In practice, these equations could arise in data fitting and estimation problems. An overdetermined system of linear equations can be defined as

$\mathbf{Ax} = \mathbf{b}$

where $\mathbf{A} \in \mathbb {R}^{m \times n}$ , $\mathbf{x}\in \mathbb {R}^ n$ , $\mathbf{b} \in \mathbb {R}^ m$ , and $m > n$ . Since this system usually does not have a solution, you need to be satisfied with some sort of approximate solution. The most widely used approximation is the least squares solution, which minimizes $\| \mathbf{Ax} - \mathbf{b}\| _2^2$ .

This problem is called a least squares problem for the following reason. Let $\mathbf{A}$ , $\mathbf{x}$ , and $\mathbf{b}$ be defined as previously. Let $k_ i(x)$ be the kth component of the vector $\mathbf{Ax} - \mathbf{b}$ :

$k_ i(x) = a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_ n - b_ i,\; i = 1,2,\ldots , m$

By definition of the Euclidean norm, the objective function can be expressed as follows:

$\| \mathbf{Ax} - \mathbf{b}\| _2^2 = \sum \limits _{i = 1}^ m k_ i(x)^2$

Therefore, the function you minimize is the sum of squares of m terms $k_ i(x)$ ; hence the term least squares. The following example is an illustration of the linear least squares problem; that is, each of the terms $k_ i$ is a linear function of x .

Consider the following least squares problem defined by

$\mathbf{A} = \left[\begin{array}{rc} 4 & 0 \\ -1 & 1 \\ 3 & 2 \end{array}\right],\quad \mathbf{b} = \left[\begin{array}{c} 1 \\ 0 \\ 1 \end{array}\right]$

This translates to the following set of linear equations:

$4x_1 = 1, \quad -x_1 + x_2 = 0, \quad 3x_1 + 2x_2 = 1$

The corresponding least squares problem is:

$\mbox{minimize} \quad (4x_1 -1)^2 + (-x_1 + x_2)^2 + (3x_1 + 2x_2 -1)^2$

The preceding objective function can be expanded to:

$\mbox{minimize} \quad 26x_1^2 + 5x_2^2 + 10 x_1x_2 - 14 x_1 -4x_2 + 2$

In addition, you impose the following constraint so that the equation $3x_1 + 2x_2 = 1$ is satisfied within a tolerance of 0.1:

$0.9 \leq 3x_1 + 2x_2 \leq 1.1$

You can use the following SAS statements to solve the least squares problem:

/* example 1: linear least-squares problem */
proc optmodel;
   var x1; /* declare free (no explicit bounds) variable x1 */
   var x2; /* declare free (no explicit bounds) variable x2 */
   /* declare slack variable for ranged constraint */
   var w >= 0 <= 0.2;

   /* objective function: minimize is the sum of squares */
   minimize f = 26 * x1 * x1 + 5 * x2 * x2 + 10 * x1 * x2
       - 14 * x1 - 4 * x2 + 2;

   /* subject to the following constraint */
   con L: 3 * x1 + 2 * x2 - w = 0.9;

   solve with qp;

   /* print the optimal solution */
   print x1 x2;
quit;

The output is shown in Output 11.1.1.

Output 11.1.1: Summaries and Optimal Solution

The OPTMODEL Procedure

Problem Summary
Objective Sense	Minimization
Objective Function	f
Objective Type	Quadratic

Number of Variables	3
Bounded Above	0
Bounded Below	0
Bounded Below and Above	1
Free	2
Fixed	0

Number of Constraints	1
Linear LE (<=)	0
Linear EQ (=)	1
Linear GE (>=)	0
Linear Range	0

Constraint Coefficients	3

Performance Information
Execution Mode	Single-Machine
Number of Threads	4

Solution Summary
Solver	QP
Algorithm	Interior Point
Objective Function	f
Solution Status	Optimal
Objective Value	0.0095238095

Primal Infeasibility	1.926295E-12
Dual Infeasibility	1.3056209E-9
Bound Infeasibility	0
Duality Gap	4.3533121E-8
Complementarity	1.3603398E-7

Iterations	3
Presolve Time	0.00
Solution Time	0.01

x1	x2
0.2381	0.1619