# A nice duality problem

In the recent Qualifying Exam, there was a very nice (I mean, tough) problem in the Linear Optimization paper that nobody could solve. I was able to crack it two days later. Here it is:

Problem

A matrix $A \; (n \times n)$ is positive semidefinite if $x^\intercal A x \geq 0 \; \forall x \in \mathbb{R}^n$. Prove that if $A$ is positive semidefinte then the following system has a solution: $\{x^\intercal A \geq 0; \ x \geq 0; x \neq 0 \}$.

Solution

$\begin{cases} x^\intercal A \geq 0 \\ x \geq 0 \\ x \neq 0 \end{cases} \Leftrightarrow \begin{cases} x^\intercal A \geq 0 \\ x \geq 0 \\ \mathbf{1}\cdot x > 0 \end{cases} \Leftrightarrow \begin{cases} x^\intercal A \geq 0 \\ x \geq 0 \\ -\mathbf{1}\cdot x < 0 \end{cases}$

where $\mathbf{1}$ is a vector in $\mathbb{R}^n$ whose entries are all 1.

Consider the following linear program

$\min \ -\mathbf{1}\cdot x$

subject to

$x^\intercal A \geq 0$

$x \geq 0$

Its dual is

$\max \ \mathbf{0}\cdot y$

subject to

$Ay \leq -1$

$y \geq 0$

Observe that the dual is infeasible, because if there exists a solution $y$ such that $Ay \leq -1 < 0$ and $y \geq 0$ then this implies $y^\intercal Ay < 0$, contradicting the fact that A is positive semidefinite.

Since the dual is infeasible, the primal is either infeasible or unbounded. But $x = 0$ is a solution to the primal, so it is unbounded. Thus there exists a solution $x$ such that $\{-\mathbf{1}\cdot x < 0; x^\intercal A \geq 0; x \geq 0\}$ Q.E.D.

Now that the math is done, it’s time for some story. All of us were taught that the Farkas lemma is extremely important, and thus all of us tried to use it to solve this problem, to no avail. I was particularly bugged by the condition $x \neq 0$, which we had never seen in all our exercises. The exam was on a Wednesday. Two days later, on a Friday evening, on a bus ride from school home, I was determined to solve it. Perhaps it was the motion and the rumbling sound of the bus, perhaps it was my subconscious mind having spent enough time on the problem, or perhaps it was just my shining moment, but I finally realized that $x \neq 0$ means $\mathbf{1}\cdot x > 0$, given that $x \geq 0$. Now the next question is how do I use that in an LP? Well, I can’t use it in the constraints, so it must be in the objective function. Let’s try to $\max \; \mathbf{1}\cdot x$. But wait, I have a $\geq$ constraint, so I must $\min \; -\mathbf{1}\cdot x$. And the rest is easy. That was probably one of my proudest moments in the PhD program so far.