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

A new chapter

A new chapter of my PhD journey has started. I passed my Qualifying Exam. Now is the time for full-time research. Now that I think about it, this part is even harder than the previous one. Passing the Quals is just the start. So far, I was taught techniques and given problems to solve using those techniques. Now I have to find my own problems. My advisor said, very truly, that being good at research means knowing how to ask the right questions. I’ve collected of lot of techniques so far, and I will continue to do so. But that just mean knowing how to answer questions. Now I need to ask questions.

I feel excited. A bit scared, but good scared.