Exercise 4.28

Question

Let $\mathbf{a}$ and $\mathbf{a}_{1}, \ldots, \mathbf{a}_{m}$ be given vectors in $\Re^{n}$. Prove that the following two statements are equivalent:
\begin{enumerate}[label=(\alph*)]
\item For all $\mathbf{x} \geq \mathbf{0}$, we have $\mathbf{a}^{\prime} \mathbf{x} \leq \max_{i} \ \mathbf{a}_{i}^{\prime} \mathbf{x}$.
\item There exist nonnegative coefficients $\lambda_{i}$ that sum to $1$ and such that $\mathbf{a} \leq$ $\sum_{i=1}^{m} \lambda_{i} \mathbf{a}_{i}$.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{proof}
\begin{description}
\item[$(a) \implies (b)$] It is obvious that condition in (a) is equivalent to the following optimization problem having a non-negative optimal value:
\begin{equation}
  \begin{array}{ll}
    	ext{minimize}   \quad & \max_{i=1,\ldots,m}\mathbf{a}^{\prime}_i\mathbf{x} - \mathbf{a}^{\prime}\mathbf{x}\
    	ext{subject to} \quad & \mathbf{x} \geq \mathbf{0}.
  \end{array}
  \label{y:linopt}
\end{equation}

Following the procedure from Section 1.3, we can rewrite the piecewise linear optimization problem in form of a usual linear optimization problem:
\begin{equation}
  \begin{array}{ll}
    	ext{minimize}   \quad & z - \mathbf{a}^{\prime}\mathbf{x}\
    	ext{subject to} \quad & z \geq \mathbf{a}^{\prime}_1\mathbf{x}\
                            & \vdots\
                            & z \geq \mathbf{a}^{\prime}_m\mathbf{x}\
                            & \mathbf{x} \geq \mathbf{0}, z 	ext{ free.}
  \end{array}
  \quad \iff \quad
    \begin{array}{ll}
    	ext{minimize}   \quad & \begin{bmatrix} -\mathbf{a}^{\prime} & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \ z \end{bmatrix}\
    	ext{subject to} \quad & \begin{bmatrix} -\mathbf{A} & \mathbf{e} \end{bmatrix}  \begin{bmatrix} \mathbf{x} \ z \end{bmatrix} \geq \mathbf{0}\
                            & \mathbf{x} \geq \mathbf{0}, z 	ext{ free.}\&
  \end{array}
  \label{y:linopt2}
\end{equation}

The dual of \eqref{y:linopt2} is

\begin{equation}
  \begin{array}{ll}
    	ext{maximize}   \quad & \mathbf{p}^{\prime}\mathbf{0}\
    	ext{subject to} \quad & -\mathbf{p}^{\prime}\mathbf{A} \leq - \mathbf{a}\
                            & \sum_{i=1}^{m} p_i = 1\
                            & \mathbf{p} \geq \mathbf{0}.
  \end{array}
  \label{y:linoptdual}
\end{equation}

Since the primal problem is feasible (e.g, for $\mathbf{0}$) and bounded (by $0$), the dual problem must be feasible as well. But a feasible point $\mathbf{p}$ of \eqref{y:linoptdual} satisfies all of the required properties in (b), and we are done.
  
\item[$(b) \implies (a)$] Suppose (b) is true. For all $\mathbf{x}\geq\mathbf{0}$, due to the fact that $\lambda_i \leq 1$ and $\sum \lambda_i = 1$, we have
  $$\mathbf{a}^{\prime}\mathbf{x} \stackrel{b}{\leq} \sum_{i=1}^{m}\lambda_i \mathbf{a}^{\prime}_i\mathbf{x} \leq \sum_{i=1}^{m}\lambda_i \max_{j=1,\ldots,m}\mathbf{a}^{\prime}_j\mathbf{x} = \max_{j=1,\ldots,m}\mathbf{a}^{\prime}_j\mathbf{x}.$$
\end{description}
\end{proof}

Exercise 4.28

Answers

Comments

Exercise 4.28

Answers

Comments

Add answer