Indefinite symmetric quadratic form with inequality constraint

Question

I have a scalar quantity $\Phi =u^TAu$ that I am tracking as part of a greater optimization problem. $A=I-(1+\mu^2)nn^T$, where $u$ is a 3 x 1 vector, $I$ is the 3 x 3 identity matrix, $\mu$ is a non-negative scalar, and $n$ is a normalized 3 x 1 vector ($n^Tn=1$). The eigenvalues of $A$ are $(1,1,-\mu^2)$. Therefore, $A$ is an indefinite, symmetric matrix. Everything is real-valued.

I wish to constrain my choice of $u$ such that $\Phi\leq0$. Because $A$ is indefinite, this condition is dependent on $u$. How can I enforce this constraint? I was hoping there was a way to define a matrix $X$ such that $u=Xv$, to transform this into an unconstrained optimization problem (similar to a subspace method) but I will appreciate any advice. Thank you!

Answer 1

If you project $u$ onto the eigenspace of $A$ corresponding to eigenvalue $1$, the feasible region is a circle whose radius depends on the remaining component of $u$. So, you can either solve a problem with a quadratic constraint, or do a polar transformation.

An eigenvector of $A$ corresponding to eigenvalue $-\mu^2$ is $n$. You can write $u = Xw$ where $X$ is $3 \times 3$ whose first column is $n$ and the other two columns an orthogonal basis for the space orthogonal to $n$, and $w$ is $3 \times 1$.

The condition $u^TAu \leq 0$ is equivalent with $w_2^2 + w_3^2 \leq w_1^2 \mu^2$. Writing $w_1 = r \cos \theta$ and $w_2 = r \sin \theta$, this becomes $0 \leq r \leq w_1 \mu$.

So now we have three options:

1. use $u^T A u \leq 0$ as a constraint
2. use $w_2^2 + w_3^2 \leq w_1^2 \mu^2$ and $u = Xw$ as constraints
3. reformulate the entire problem with polar coordinates and add the linear constraint $0 \leq r \leq w_1 \mu$

The constraint $w_2^2 + w_3^2 \leq w_1^2 \mu^2$ is convex (second order cone) only if $w_1 \geq 0$ or if $w_1 \leq 0$, but not for $w_1 \in \mathbb{R}$. So, if you can solve two constrained convex optimization problems (one for $w_1 \geq 0$, one for $w_1 \leq 0$), option 2 probably has the best numerical performance.

Answer 2

Let $\frac{1}{\sqrt{1+\mu^2}}=\cos\phi$ where $\phi\in[0,\frac{\pi}{2}]$. Then $\mathbf u^TA\mathbf u\le0$ if and only if $\mathbf u=0$ or $\left|\left\langle\frac{\mathbf u}{\|\mathbf u\|},\mathbf n\right\rangle\right|\ge\cos\phi$. Therefore $$ \mathbf u=x\left(\cos(\theta)\mathbf n+\sin(\theta)\mathbf t\right) $$ for some $\theta\in[-\phi,\phi]$ and some unit vector $\mathbf t\perp\mathbf n$. Let $P\in\mathbb R^{3\times2}$ be any matrix whose two columns together with $\mathbf n$ form an orthonormal basis of $\mathbb R^3$. Then we can write $$ \mathbf u=x\left( \cos\left(\phi\cos\alpha\right)\mathbf n +\sin\left(\phi\cos\alpha\right)P\pmatrix{\cos\beta\\ \sin\beta} \right) $$ where $x,\alpha$ and $\beta$ are unconstrained.