Exercise 4.6* (Duality in Chebychev approximation)

Question

Let $\mathbf{A}$ be an $m 	imes n$ matrix and let $\mathbf{b}$ be a vector in $\Re^{m}$. We consider the problem of minimizing $\|\mathbf{A} \mathbf{x}-\mathbf{b}\|_{\infty}$ over all $\mathbf{x} \in \Re^{n}$. Here $\|\cdot\|_{\infty}$ is the vector norm defined by $\|\mathbf{y}\|_{\infty}=$ $\max _{i}\left|y_{i}ight|$. Let $v$ be the value of the optimal cost.
\begin{enumerate}[label=(\alph*)]
\item Let $\mathbf{p}$ be any vector in $\Re^{m}$ that satisfies $\sum_{i=1}^{m}\left|p_{i}ight|=1$ and $\mathbf{p}^{\prime} \mathbf{A}=\mathbf{0}^{\prime}$. Show that $\mathbf{p}^{\prime} \mathbf{b} \leq v$.

\item In order to obtain the best possible lower bound of the form considered in part (a), we form the linear programming problem

$$
\begin{aligned}
	ext{maximize} \quad & \mathbf{p}^{\prime} \mathbf{b} \
	ext { subject to } \quad & \mathbf{p}^{\prime} \mathbf{A}=\mathbf{0}^{\prime} \
& \sum_{i=1}^{m}\left|p_{i}ight| \leq 1
\end{aligned}
$$

Show that the optimal cost in this problem is equal to $v$.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{proof}
Unfolding the definition of the maximum norm, we rewrite our optimization problem as follows:
\begin{equation}
\begin{array}{ll}
  \text{minimize}   \quad & \underset{i=1,\ldots,m}{\operatorname{max}} \left|\mathbf{a}_{i}^{\prime}\mathbf{x} - b_i\right|\[5pt]
  \text{subject to} \quad & \mathbf{x} \text{ free.}
\end{array}
\end{equation}

Recall from Section 1.3 (Piecewise linear convex objective functions), that the problems involving maximums and absolute values can be rewritten as linear optimization problems by introducing a dummy variable to the system and restricting it from below:
\begin{equation}
\begin{array}{lll}
  \text{minimize}   \quad & z\
  \text{subject to} \quad & z \geq b_1 - \mathbf{a}_{1}^{\prime}\mathbf{x}, & z \geq \mathbf{a}_{1}^{\prime}\mathbf{x} - b_1\
                          & \vdots & \vdots\
                          & z \geq b_m - \mathbf{a}_{m}^{\prime}\mathbf{x}, & z \geq \mathbf{a}_{m}^{\prime}\mathbf{x} - b_m\
                          & \text{$\mathbf{x}$ free, $z$ free.}
\end{array}
\label{y:linopt2}
\end{equation}

For the sake of completeness, we rewrite \eqref{y:linopt2} in a more canonical way:
\begin{equation}
\begin{array}{lll}
  \text{minimize}   \quad & \begin{bmatrix}\mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \ z \end{bmatrix}\[15pt]
  \text{subject to} \quad & \begin{bmatrix} | & 1 \ \mathbf{A} & \vdots \ \mid & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \ z \end{bmatrix} \geq \mathbf{b}, \ &\begin{bmatrix} | & 1 \ -\mathbf{A} & \vdots \ \mid & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \ z \end{bmatrix} \geq - \mathbf{b}\[10pt]
                          & \text{$\mathbf{x}$ free, $z$ free.}
\end{array}
\label{y:linopt3}
\end{equation}

Using the definition on page 142, the linear optimization problem in \eqref{y:linopt3} results in the following $2m$-dimensional dual problem:
\begin{equation}
\begin{array}{lll}
  \text{maximize}   \quad & \begin{bmatrix} \mathbf{p}_1^{\prime} &\mathbf{p}_2^{\prime}\end{bmatrix} \begin{bmatrix} \mathbf{b} \ - \mathbf{b} \end{bmatrix}\[10pt]
  \text{subject to} \quad & \mathbf{p}_1^{\prime}\mathbf{A} = \mathbf{0}^{\prime} \quad &-\mathbf{p}_2^{\prime}\mathbf{A} = \mathbf{0}^{\prime}\
                          & \sum_{i=1}^{m}\left(p_{1,i}+p_{2,i}\right) = 1\
                          & \mathbf{p}_1 \geq \mathbf{0} &\mathbf{p}_2 \geq \mathbf{0}.
\end{array}
\end{equation}

We introduce the following variable change. Set $\mathbf{p} := \mathbf{p}_1 - \mathbf{p_2}$. The trick is to notice that $\left|\mathbf{p}\right| = \mathbf{p}_1 + \mathbf{p_2}$. (This follows from the complementary slackness as two components $p_{1,j}$ and $p_{2,j}$, $j=1,\ldots,m$, cannot be positive at the same time.). Thus, the above optimization problem is equivalent to

\begin{equation}
\begin{array}{lll}
  \text{maximize}   \quad & \mathbf{p}^{\prime} \mathbf{b}\
  \text{subject to} \quad & \mathbf{p}^{\prime}\mathbf{A} = \mathbf{0}^{\prime}\
                          & \sum_{i=1}^{m}\left|p_{i}\right| = 1.
\end{array}
\end{equation}

By weak duality (Theorem 4.3), a feasible solution $\mathbf{p}$ of the dual problem \eqref{y:linopt3} results in an objective value $-\mathbf{p}^{\prime}\mathbf{b}$ less than or equal to the optimal cost $v$ of the primal problem. This is exactly the exercise assertion in (a). By the strong duality, the optimal values of both optimization problems must be equal. This is the assertion in (b).
\end{proof}

Exercise 4.6* (Duality in Chebychev approximation)

Answers

Comments

Exercise 4.6* (Duality in Chebychev approximation)

Answers

Comments

Add answer