Example 19.1 Linear Least Squares Problem

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

where , , , and . Since this system usually does not have a solution, we need to be satisfied with some sort of approximate solution. The most widely used approximation is the least squares solution, which minimizes .

This problem is called a least squares problem for the following reason. Let , , and be defined as previously. Let be the th component of the vector :

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

Therefore, the function we minimize is the sum of squares of terms ; hence the term least squares. The following example is an illustration of the linear least squares problem; i.e., each of the terms is a linear function of .

Consider the following least squares problem defined by

This translates to the following set of linear equations:

The corresponding least squares problem is

The preceding objective function can be expanded to

In addition, we impose the following constraint so that the equation is satisfied within a tolerance of :

You can create the QPS-format input data set by using the following SAS code:

data lsdata;
   input field1 $ field2 $ field3$ field4 field5 $ field6 @;
datalines;
NAME   .      LEASTSQ     .            .         .
ROWS   .      .           .            .         .
N      OBJ    .           .            .         .
G      EQ3    .           .            .         .
COLUMNS .     .           .            .         .
.      X1     OBJ       -14            EQ3       3
.      X2     OBJ        -4            EQ3       2
RHS    .      .           .            .         .
.      RHS    OBJ        -2            EQ3     0.9
RANGES .      .           .            .         .
.      RNG    EQ3       0.2            .         .
BOUNDS .      .           .            .         .
FR    BND1    X1          .            .         .
FR    BND1    X2          .            .         .
QUADOBJ .     .           .            .         .
.      X1     X1         52            .         .
.      X1     X2         10            .         .
.      X2     X2         10            .         .
ENDATA .      .           .            .         .
;

The decision variables and are free, so they have bound type FR in the BOUNDS section of the QPS-format data set.

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

proc optqp data=lsdata 
   printlevel = 0
   primalout = lspout; 
run; 

The optimal solution is displayed in Output 19.1.1.

The iteration log is shown in Output 19.1.2.