Exercise 4.7 (Duality in piecewise linear convex optimization)

Question

Consider the problem of minimizing $\max _{i=1, \ldots, m}\left(\mathbf{a}_{i}^{\prime} \mathbf{x}-b_{i}ight)$ over all $\mathbf{x} \in \Re^{n}$. Let $v$ be the value of the optimal cost, assumed finite. Let $\mathbf{A}$ be the matrix with rows $\mathbf{a}_{1}, \ldots, \mathbf{a}_{m}$, and let $\mathbf{b}$ be the vector with components $b_{1}, \ldots, b_{m}$.
\begin{enumerate}[label=(\alph*)]
\item Consider any vector $\mathbf{p} \in \Re^{m}$ that satisfies $\mathbf{p}^{\prime} \mathbf{A}=\mathbf{0}^{\prime}, \mathbf{p} \geq \mathbf{0}$, and $\sum_{i=1}^{m} p_{i}=$ 1. 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{equation*}
  \begin{array}{ll}
    	ext{maximize}   \quad & -\mathbf{p}^{\prime}\mathbf{b}\
    	ext{subject to} \quad & \mathbf{p}^{\prime}\mathbf{A} = \mathbf{0}^{\prime}\
                            & \mathbf{p}^{\prime}\mathbf{e} = 1\
                            & \mathbf{p} \geq \mathbf{0},
  \end{array}
\end{equation*}

where $\mathbf{e}$ is the vector with all components equal to 1. Show that the optimal cost in this problem is equal to $v$.
\end{enumerate}

Elu Thingol · Accepted Answer

Recall from Section 1.3 (Piecewise linear convex objective functions), that we can rewrite the piecewise linear optimization problem
\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)\
  \text{subject to} \quad & \mathbf{x} \text{ free.}
\end{array}
  \label{y:primal}
\end{equation}

in the following equivalent form as a linear optimization problem:
\begin{equation}
\begin{array}{lll}
  \text{minimize}   \quad & z\
  \text{subject to} \quad & z \geq \mathbf{a}_{1}^{\prime}\mathbf{x} - b_1\
                          & \vdots\
                          & 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}\[5pt]
  \text{subject to} \quad & \begin{bmatrix} \mathbf{-A} & \mathbf{e} \end{bmatrix} \begin{bmatrix} \mathbf{x} \ z \end{bmatrix} \geq -\mathbf{b}\[5pt]
                          & \text{$\mathbf{x}$ free, $z$ free.}
\end{array}
  \label{y:linopt3}
\end{equation}

Following the definition on page 142, the linear optimization problem in \eqref{y:linopt3} results in the following dual problem:
\begin{equation}
  \begin{array}{ll}
    \text{maximize}   \quad & -\mathbf{p}^{\prime}\mathbf{b}\
    \text{subject to} \quad & -\mathbf{p}^{\prime}\begin{bmatrix} \mathbf{-A} & \mathbf{e} \end{bmatrix} = \begin{bmatrix}\mathbf{0} & 1 \end{bmatrix}\
                            & \mathbf{p} \geq \mathbf{0},
  \end{array}
\end{equation}

or, in a more reader-friendly form,
\begin{equation}
  \begin{array}{ll}
    \text{maximize}   \quad & -\mathbf{p}^{\prime}\mathbf{b}\
    \text{subject to} \quad & \mathbf{p}^{\prime}\mathbf{A} = \mathbf{0}^{\prime}\
                            & \mathbf{p}^{\prime}\mathbf{e} = 1\
                            & \mathbf{p} \geq \mathbf{0}.
  \end{array}
  \label{y:dual}
\end{equation}

\begin{enumerate}[label=(\alph*)]
\item Any vector $\mathbf{p}$ satisfying the conditions given in the exercise is feasible for the dual problem \eqref{y:dual}. By weak duality, its objective value $\mathbf{p}^{\prime}\mathbf{b}$ cannot exceed that of the optimum $v$ of the primal problem.
\item We have shown that \eqref{y:dual} is the dual problem for the primal \eqref{y:primal}. By strong duality (Theorem 4.4), optimal values of both problems must coincide.
\end{enumerate}

Exercise 4.7 (Duality in piecewise linear convex optimization)

Answers

Comments

Exercise 4.7 (Duality in piecewise linear convex optimization)

Answers

Comments

Add answer