Example 17.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
![\mathbf{ax} = \mathbf{b}](images/optqp_optqpeq74.gif)
where
![\mathbf{a} \in \mathbb{r}^{m x n}](images/optqp_optqpeq75.gif)
,
![\mathbf{x}\in \mathbb{r}^n](images/optqp_optqpeq76.gif)
,
![\mathbf{b} \in \mathbb{r}^m](images/optqp_optqpeq77.gif)
, and
![m \gt n](images/optqp_optqpeq78.gif)
. 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
![\vert \mathbf{ax} - \mathbf{b}\vert _2^2](images/optqp_optqpeq79.gif)
.
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
:
![k_i(x) = a_{i1}x_1 + a_{i2}x_2 + ... + a_{in}x_n - b_i,\; i = 1,2, ... , m](images/optqp_optqpeq82.gif)
By definition of the Euclidean norm, the objective function can be expressed as follows:
![\vert \mathbf{ax} - \mathbf{b}\vert _2^2 = \sum \limits_{i = 1}^m k_i(x)^2](images/optqp_optqpeq83.gif)
Therefore, the function we minimize is the sum of squares of
![m](images/optqp_optqpeq84.gif)
terms
![k_i(x)](images/optqp_optqpeq80.gif)
; hence the term least-squares. The following example is an illustration of the
linear least-squares problem; i.e., each of the terms
![k_i](images/optqp_optqpeq85.gif)
is a linear function of
![x](images/optqp_optqpeq86.gif)
.Consider the following least-squares problem defined by
![\mathbf{a} = [4 & 0 \ -1 & 1 \ 3 & 2 ], \mathbf{b} = [1 \ 0 \ 1 ]](images/optqp_optqpeq87.gif)
This translates to the following set of linear equations:
![4x_1 = 1, -x_1 + x_2 = 0, 3x_1 + 2x_2 = 1](images/optqp_optqpeq88.gif)
The corresponding least-squares problem is
![{minimize} (4x_1 -1)^2 + (-x_1 + x_2)^2 + (3x_1 + 2x_2 -1)^2](images/optqp_optqpeq89.gif)
The preceding objective function can be expanded to
![{minimize} 26x_1^2 + 5x_2^2 + 10 x_1x_2 - 14 x_1 -4x_2 + 2](images/optqp_optqpeq90.gif)
In addition, we impose the following constraint so that the equation
![3x_1 + 2x_2 = 1](images/optqp_optqpeq91.gif)
is satisfied within a tolerance of 0.1:
![0.9 \leq 3x_1 + 2x_2 \leq 1.1](images/optqp_optqpeq92.gif)
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
primalout = lspout;
run;
The optimal solution is displayed in Output 17.1.1.
Output 17.1.1: Solution to the Least-Squares Problem
OBJ |
RHS |
X1 |
F |
-14 |
-1.7977E308 |
1.7977E308 |
0.23809 |
O |
OBJ |
RHS |
X2 |
F |
-4 |
-1.7977E308 |
1.7977E308 |
0.16190 |
O |
|
The iteration log is shown in Output 17.1.2.
Output 17.1.2: Iteration Log
NOTE: The problem LEASTSQ has 2 variables (2 free, 0 fixed). |
NOTE: The problem has 1 constraints (0 LE, 0 EQ, 0 GE, 1 range). |
NOTE: The problem has 2 constraint coefficients. |
NOTE: The objective function has 2 Hessian diagonal elements and 1 Hessian |
elements above the diagonal. |
NOTE: The OPTQP presolver value AUTOMATIC is applied. |
NOTE: The OPTQP presolver removed 0 variables and 0 constraints. |
NOTE: The OPTQP presolver removed 0 constraint coefficients. |
NOTE: The QUADRATIC ITERATIVE solver is called. |
Primal Bound Dual |
Iter Complement Duality Gap Infeas Infeas Infeas |
0 10001805 2.001029 1052.607895 416.588001 0 |
1 501893 2.094827 52.630395 20.750266 0 |
2 26887 34.114879 2.631520 0.958349 0 |
3 2997.321110 600.993085 0.131576 0 0 |
4 734.867262 111.975745 0.006579 0 0 |
5 26.413788 5.701869 0.000329 0 0 |
6 0.877292 0.287945 0.000016608 0 0 |
7 0.051222 0.017041 0.000000983 0 0 |
8 0.007624 0.001934 0.000000103 0 0 |
9 0.001232 0.000171 5.7776383E-9 0 0 |
10 0.000047950 0.000008773 2.898554E-10 0 0 |
11 0.000001381 0.000000438 1.449273E-11 0 0 |
NOTE: Optimal. |
NOTE: Objective = 0.0095238096. |
|