Equivalence of Two Statements (Duality Theory, Optimization) Let $a$ and $a_{1}, ...  , a_{m}$ be given vectors in $\mathbb{R^{n}}$. Prove that the following two statements are equivalent.
$a)$ For all $x \geq 0$ we have $a^tx \leq\max\limits_{i}(a_{i}^tx)$.
$b)$ There exists nonnegative coefficients $\lambda_{i}$ that sum to $1$ and such that $a \leq \sum_{i=1}^{m} \lambda_{i}a_{i}$.
The problem arised while I was studying duality theory for my optimization course. I think that an appropriate LP formulation directly kills the problem but I really could not see this. Any help is appreciated. Thank you!
 A: You can easily define your LP as
$$
\min \sum 0\times y_i \\
     \sum_i y_i a_i \geq a\\
      \sum_i y_i = 1 \\
       y_i\geq 0
$$
The dual of this LP is
$$
\max_{x\geq 0} a^T x -\gamma \\
a_i^T x -\gamma \leq 0 \ \ \ \mbox{         for all i}
$$
The primal is feasible if and only if the dual is bounded and
$$
0 \geq \max_{x\geq 0, \gamma} a^T x -\gamma\\
\max_i a_i^T x  \leq \gamma.
$$
Since, $\gamma^{opt} = \max_i a_i^T x$, we have
$$
\max_i a_i^T x = \gamma \geq  a^T x\\
$$
for all $x\geq 0$
A: I originally answered this here duality or Farkas lemma but there seems to be a rush to close, so I am copying the answer here as I am a bit tired of effort that gets closed out.
The key result is that for a non empty closed convex set $C \subset \mathbb{R}^n$, then
$x \in C$ iff $\sigma_C(h) \ge h^T x$ for all $h$, where $\sigma_C$ is the support function of the convex set $C$ defined by $\sigma_C(h) = \sup_{x \in C} h^T x$ (it may take the value $\infty$). At some level this is the essence of duality.
Unfortunately the following answer is a little terse and requires some general familiarity with convex analysis, but elaboration would take a good deal more effort.
Let $Q = \{ x | x \ge 0 \}$ denote the first quadrant.
Let $A = \operatorname{co} \{ a_k \}_k$, the convex hull of the points $a_k$. Note that $A$ is compact, and $\sigma_A(h) = \max_{\sum_k \mu_k =1, \mu_k \ge 0} h^T (\sum_k \mu_k a_k) = \max_k h^T a_k$
Let $C = \{ x | h^T x \le \sigma_A(h), \text{ for all } h \in Q \}$.
Now a little magic (sorry). Consider the closed convex set $-Q$ (that is all points of the form $x \le 0$) and note that the set $A+(-Q)$ (Minkowski sum) is convex and closed (since $A$ is compact and $-Q$ is closed). Note that
$\sigma_{A+(-Q)} (h) = \sigma_A(h)$ for $h \in Q$ and $\sigma_{A+(-Q)} (h) = +\infty$ otherwise.
In particular, $C= \{ x | h^T x \le \sigma_{A+(-Q)} (h), \text{ for all } h \}$ from which we get $C = A+(-Q)$.
Hence $x$ satisfies $h^T x \le \max_k h^T a_k $ for all $h \ge 0$ iff $x \in C$ iff $x \in A+(-Q)$ iff $x = \sum_k \mu_k a_k - q$ where $\sum_k \mu_k =1$, $\mu_k \ge 0$ and $q \in Q$ iff $x \le \sum_k \mu_k a_k$ where $\sum_k \mu_k =1$, $\mu_k \ge 0$.
