Quadratic optimization problem with quadratic constraint

Question

Given $A = A^T \in \mathbb{R}^{n \times n}, X = \begin{bmatrix}x & \eta\end{bmatrix} \text{with} \ x, \eta \in \mathbb{R}^n$ and $||x|| = ||\eta|| = 1$ (vectors in $\mathbb{R}^n$ are treated as columns) solve

$$ \min_{v \in \mathbb{R}^2} f(v):= v^TX^TAXv$$ such that $$ h(v):=v^TX^TXv-1 = 0 $$

First attempt: Construct the Lagrangian, $L := f(v) + \lambda h(v)$

$$\frac{\partial L}{\partial v} = 2(X^TAX)v + 2\lambda(X^TX)v = 0$$ Premultiply by $v^T$ to get

$$\lambda = -v^TX^TAXv $$

Substituting this back yields a very complicated equation in $v$ which I'm unable to solve.

Second attempt: Since $X^TAX$ is symmetric, $v^TX^TAXv \ge ||v_m||^2 \lambda_{\min}(X^TAX)$ where $v_m$ is the eigenvector corresponding to the least eigenvalue $\lambda_{\min}(X^TAX)$ of $X^TAX$. Therefore the minimizer of the original problem is $v = \alpha v_m$ with $\alpha \in \mathbb{R}$ such that $h(v) = 0$.

My second attempt is still a hunch, and I'm not being able to prove the correctness of my hunch.

Question : I'm looking for a complete solution or hints to any of my approaches in order to get an analytical solution to the minimization problem.

The solution to this has been given in the book, but without proof, and I am unsuccessful at getting the same solution. The given minimizer for $v$ is the eigenvector of the smaller eigenvalue of $X^TAX$ scaled appropriately such that the norm is 1.

Answer 1

I am not sure if I understand the problem correctly.

Let:

• 2 by 2 matrix $B = X^{T}AX$,
• 2 by 2 matrix $C = X^{T}X$

Then:

• Objective: $f(x) = \vec{v} B \vec{v} $
• Constraint: $g(x) = \vec{v} C \vec{v} - 1 = 0$

$f(x) = (b_{11}v_{1} + b_{21}v_{2})v_{1} + (b_{12}v_{1} + b_{22}v_{2})v_{2}$

$f(x) = b_{11}v_{1}^{2} + b_{21}v_{2}v_{1} + b_{12}v_{1}v_{2} + b_{22}v_{2}^{2}$

$g(x) = c_{11}v_{1}^{2} + c_{21}v_{2}v_{1} + c_{12}v_{1}v_{2} + c_{22}v_{2}^{2} - 1$

Lagrange:

$L = f(x) + \lambda g(x)$

$0 = \frac{\partial L}{\partial v_{1}} = 2b_{11}v_{1} + b_{21}v_{2} + b_{12}v_{2} + \lambda (2c_{11}v_{1} + c_{21}v_{2} + c_{12}v_{2})$

$0 = \frac{\partial L}{\partial v_{2}} = 2b_{22}v_{2} + b_{12}v_{1} + b_{21}v_{1} + \lambda (2c_{22}v_{2} + c_{12}v_{1} + c_{21}v_{1})$

$0 = c_{11}v_{1}^{2} + c_{21}v_{2}v_{1} + c_{12}v_{1}v_{2} + c_{22}v_{2}^{2} - 1 $

Answer 2

This is the definition of generalized eigenvalues, i.e. you are looking for the minimum generalized eigenvalue of the pair $(X^TAX, X^TX)$.