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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s