Constraint $x'Ax = 0$, where $x$ and $A$ are both optimization variables

Question

I'm trying to solve the following optimization problem: $$ \min_{x, \phi} x \quad \text{s.t.} \quad \sum_{s,t = 1}^n \left(m_{s,t} x -v_{s,t} \right)\phi_s \phi_t = 0 , \quad \lVert \phi \rVert = 1$$ where $x$ is scalar and $\phi$ is in the unit sphere on $\mathbb{R}^n$.

After defining some slack variables $r_{s,t} = m_{s,t} x -v_{s,t}$, I can rewrite the first constraint as $\phi'R\phi = 0$, where we are optimizing over both $R$ and $\phi$. This version of the problem looks potentially standard. If it is, I would appreciate it if anyone could point me to good references.

The problem also looks closely related to robust least squares, but I haven't quite managed to make the connection work.

Would also appreciate perspectives on whether I should just throw the problem into a nonlinear optimizer and not worry too much.

Thanks!

Answer 1

If you know some additional things on your problem parameters $m$ and $v$ you might find better (or closed-form) solutions. For clarity, we can express the constraint $\sum_{s,t = 1}^n \left(m_{s,t} x -v_{s,t} \right)\phi_s \phi_t = 0$ in matrix form as $\phi^T (Mx-V)\phi = 0$ where $M$ and $V$ are symmetric matrices of the form $M(s,t) = \frac{m_{s,t}+m_{t,s}}{2}$ and likewise for $V$.

Once you have that, if either $M$ or $V$ happens to be positive or negative definite, you can get a closed-form solution by doing the following. Assuming it is $M$ the one that is positive definite:

1. Find the Cholesky factors of $M$: $M = R^T R$.

2. Rewrite the constraint as $\phi^T (Mx-V)\phi = \phi^T R^T\left(Ix - R^{-T}VR^{-1}\right)R\phi$

3. Compute the eigendecomposition of the symmetric matrix $R^{-T}VR^{-1} = U^T \Sigma U$.

4. Factor out the eigenvectors: $\phi^T R^T U^T\left(Ix - \Sigma\right)UR\phi = 0$.

5. Take $x$ to be the minimum entry in $\Sigma$, i.e. $x = min(\sigma_i)$.

And you can follow similar approaches for $V$ being the positive definite one, and flipping signs if they are negative definite.

A second approach, if the positive definite assumption doesn't apply, but if one of the matrices is positive or negative semi-definite, you can try to take advantage of the fact that, for example, $\phi^TV\phi$ is always non-negative if $V$ is positive semidefinite, and thus $x \phi^TM\phi$ must be non-negative too for the constraint to hold, and study the spectrum of $M$ to derive some bounds. For example, if you know the highest value that $\phi^T V \phi$ can take (using the highest eigenvalue of $V$), and the smallest negative value that $\phi^T M \phi$ (using some knowledge of the spectrum), you can find the most negative value of $x$ such that these numbers match, and thus derive a lower bound on $x$.

A complementary approach to this one would be to find good feasible solutions to your optimization problem. A way to do so is to assume something stronger than what your problem requires, for example, find a value of $x$ such that $(Mx-V)\phi = 0$. This a sufficient condition for a feasible solution, as any pair of $x,\phi$ satisfying this will satisfy your original constraint, but is not necessary, as even if $(Mx-V)\phi \neq 0$, your constraint can be satisfied if $\phi$ is orthogonal to $(Mx-V)\phi$. But the condition $(Mx-V)\phi = 0$ can be posed as a generalized eigenvalue problem and you can solve it in closed form (see this this, but beware that the notation $(A-\lambda B)x=0$ is used instead of yours) and you can take $x$ to be the smallest (most negative) eigenvalue of the appropriate generalized eigenvalue problem.

So even if you cannot compute closed-form solutions for all cases, you can get good suboptimal solutions and lower bounds, and from there get some suboptimality bounds to know how far you are from being optimal. Hope this helps!

Answer 2

A first option would be to write the problem as a (non-convex) QCQP and feed that to, e.g., Gurobi. To obtain a QCQP formulation, create a variable $z_{s, t} = \phi_{s} \phi_{t}$ and re-write the constraint with $z_{s, t}$ instead of $\phi$ (so all the terms are quadratic).

However, since you are minimizing $x$, you can try a bisection approach. For given $x$, you are solving a feasibility problem with quadratic terms which, once again, you can feed to a non-convex solver. There may be a more efficient approach using clever linear algebra, since the problem essentially asks whether there exists $\phi$ such that $\phi^{T}R(x)\phi = 0$ (and $R(x)$ is a constant when $x$ is fixed).