I have been given the primal quadratic program with a single quadratic constraint as given below:

$$\begin{array}{ll} \min\limits_{x \in \mathbb{R}^n} & \frac12 x^{T} Q x \\ \text{subject to} & \frac12 x^{T} x \leq \frac12 \end{array}$$

where $$Q$$ is an indefinite, symmetric, rational matrix of size $$n$$. The task is to show that the optimal values of the primal problem as given and its dual agree. That is, there is no duality gap.

I have (perhaps incorrectly) determined the Lagrangian of this program to be $$L(x,u) = \frac{1}{2}x^{T}Qx+\frac{1}{2}u(x^{T}x-1) = \frac{1}{2}x^{T}(Q+uI)x-\frac{1}{2}u.$$

At this point, after chasing through some circular algebra attempting to solve the dual problem to maximize (over $$u$$) the infimum (over $$x \in \mathbb{R}^n$$) of $$L(x,u)$$ and doing some KKT analysis on the primal problem as given, I can't seem to arrive at the desired result. Further, I understand there is a theorem which says that if there exists a saddle point of the Lagrangian function, then there is no duality gap (Bazaraa, Sherali, and Shetty), yet I can't seem to reconcile any sort of "mathematically tight" guarantee that there exists a saddle point for $$L$$ (although I have a hunch that there ought to be since $$Q$$ is indefinite, that is, $$Q$$ is not PD, not PSD, not ND, not NSD).

If anyone happens to see something particularly insightful in all of this, I would really appreciate the input.

• The minimum should be the eigenvector corresponding to the most negative eigenvalue of $Q$, scaled so it lies on constraint hypersphere. Commented Nov 20, 2014 at 8:20

Let $\lambda_{\min}$ be the minimum eigenvalue of $Q$.

The dual function is \begin{align} g(u) &= \inf_x L(x,u) \\ &= \begin{cases} -\infty \quad \text{if } u < -\lambda_{\min} , \\ -\frac12 u \quad \text{otherwise}. \end{cases} \end{align} The dual problem is \begin{align} \operatorname*{maximize}_{u} & \quad -\frac12 u \\ \text{subject to} & \quad u \geq -\lambda_{\min}. \end{align} The optimal value for the dual problem is \begin{equation*} d^\star = \frac12 \lambda_{\min}. \end{equation*}

And this is equal to the primal optimal value, according to the standard variational characterization of the eigenvalues of $Q$.

Note: To derive the dual function, I used the following facts.

1. The minimum eigenvalue of $Q + u I$ is $\lambda_\min + u$.
2. Let $M \in \mathbb R^{n \times n}$ be symmetric. The quadratic function $h(x) = \frac12 x^T M x$ is unbounded below if the minimum eigenvalue of $M$ is negative. Otherwise, the minimum value of $M$ is $0$.