Equivalence of Two Statements (Duality Theory, Optimization)

Question

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!

Answer 1

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$

Answer 2

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$.