| Prev | Next | Top | Quiz0803 |
k
as
\[
P_k = x_1 * P_{k-1} + x_2 * P_{k-2} + e_k
\]
where the coefficient vector
x \in \R^2
is unknown.
Our goal is to determine the coefficient vector that minimizes
the sum of the absolute errors; i.e.,
\[
\sum_{k=3}^5 | e_k |
= \sum_{k=3}^5 | P_k - x_1 * P_{k-1} - x_2 * P_{k-2} |
\]
where the vector
P
is given by
\[
\begin{array}{rrrrrrr}
k & 1 & 2 & 3 & 4 & 5 \\
P_k & 11 & 11 & 13 & 14 & 16
\end{array}
\]
Determine a matrix
A \in \R^{6 \times 2}
,
a vector
b \in \R^6
, and
a vector
c \in \R^3
such that we can satisfy our goal
by finding the solution of the problem
\[
\begin{array}{lcr}
{\rm minimize}
& c_1 * z_1 + c_2 * z_2 + c_3 * z_3
& {\rm w.r.t.} \; z \in \R^3 , x \in \R^2 \\
{\rm subject \; to}
& A_{1,1} * x_1 + A_{1,2} * x_2 - z_1 \leq b_1 \\
& A_{2,1} * x_1 + A_{2,2} * x_2 - z_1 \leq b_2 \\
& A_{3,1} * x_1 + A_{3,2} * x_2 - z_2 \leq b_3 \\
& A_{4,1} * x_1 + A_{4,2} * x_2 - z_2 \leq b_4 \\
& A_{5,1} * x_1 + A_{5,2} * x_2 - z_3 \leq b_5 \\
& A_{6,1} * x_1 + A_{6,2} * x_2 - z_3 \leq b_6
\end{array}
\]
z_1
subject to
z_1 \geq e_3
and
z_1 \geq - e_3
the optimal value is
z_1 = | e_3 |
z_{k-2}
to be
| e_k |
for
k = 3, 4, 5
; i.e.,
\[
\begin{array}{rcl}
z_{k-2} & \geq & P_k - x_1 * P_{k-1} - x_2 * P_{k-2} \\
z_{k-2} & \geq & - P_k + x_1 * P_{k-1} + x_2 * P_{k-2}
\end{array}
\]
Which is equivalent to the following set of inequalities:
\[
\begin{array}{rcl}
- P_3 & \geq & - x_1 * P_2 - x_2 * P_1 - z_1 \\
P_3 & \geq & + x_1 * P_2 + x_2 * P_1 - z_1 \\
- P_4 & \geq & - x_1 * P_3 - x_2 * P_2 - z_2 \\
P_4 & \geq & + x_1 * P_3 + x_2 * P_2 - z_2 \\
- P_5 & \geq & - x_1 * P_4 - x_2 * P_3 - z_3 \\
P_5 & \geq & + x_1 * P_4 + x_2 * P_3 - z_3
\end{array}
\]
Thus we obtain the problem above where
\[
b =
\left(
\begin{array}{r}
- P_3 \\ P_3 \\ - P_4 \\ P_4 \\ - P_5 \\ P_5
\end{array}
\right)
=
\left(
\begin{array}{r}
- 13 \\ 13 \\ -14 \\ 14 \\ -16 \\ 16
\end{array}
\right)
\; , \;
A =
\left(
\begin{array}{rr}
- P_2 & - P_1 \\
P_2 & P_1 \\
- P_3 & - P_2 \\
P_3 & P_2 \\
- P_4 & - P_3 \\
P_4 & P_3
\end{array}
\right)
=
\left(
\begin{array}{rr}
- 11 & - 11 \\
11 & 11 \\
- 13 & - 11 \\
13 & 11 \\
- 14 & - 13 \\
14 & 13
\end{array}
\right)
\; , \;
c = \left(
\begin{array}{r}
1 \\ 1 \\ 1
\end{array}
\right)
\]
Note that if
c
is any vector in
\R^3
with
all positive coefficients, the optimal
z
satisfies
z_{k-2} = | e_k |
for
k = 3, 4, 5
.
With all the coefficients of
c
equal to one,
the optimal objective is equal to
\[
\sum_{k=3}^5 | e_k |
= \sum_{k=3}^5 | P_k - x_1 * P_{k-1} - x_2 * P_{k-2} |
\]