Minimum of a quadratic function with mixed nonlinear constraints on a non-convex set.

Question

In my research I've got a following quadratic form \begin{equation*} \begin{pmatrix} C_1^T & C_2^T \end{pmatrix} \begin{bmatrix} S_{1,1} & S_{1,2} \\ S^T_{1,2} & S_{2,2} \\ \end{bmatrix}\begin{pmatrix} C_1 \\ C_2 \\ \end{pmatrix} \end{equation*}where $S \in \mathbb{R}^{2n \times 2n}$ is a symmetric matrix and I am trying to find its global minimum on the set $\{C_1,C_2 \in \mathbb{R}^n\mid \left\lVert C_1 \right\rVert = 1, \left\lVert C_2 \right \rVert \leq 1\}$.

I am looking for any ways to solve this problem: either analytical or via software. Any numerical method will do, I just need it to guarantee that it finds the global minimum of the problem.

If it makes the problem any easier, I can change the set $\{C_1,C_2 \in \mathbb{R}^n\mid \left\lVert C_1 \right\rVert = 1, \left\lVert C_2 \right \rVert \leq 1\}$ to $\{C_1,C_2 \in \mathbb{R}^n\mid \left\lVert C_1 \right\rVert \leq 1, \left\lVert C_2 \right \rVert \leq 1\}$.

Answer 1

I am not aware of any closed-form solution of this, so unless I have missed something you have to solve a nonconvex quadratically constrained problem.

The obvious approach would then be a global solver, but this particular problem also allows a strategy based on semidefinite relaxations. Semidefinite relaxation compute lower bounds to the problem, and if the lower bound happens to be tight, a solution can sometimes be extracted too. I tested on random problems, and a correct lower bound was always computed in the first level relaxation but no solution could be detected (could be the implementation) but in the second level of relaxation a solution (actually two of them) could always be extracted.

Implementation with Matlab toolbox YALMIP with Mosek as SDP solver

n = 5;
S = randn(2*n);
c1 = sdpvar(n,1);
c2 = sdpvar(n,1);
c = [c1;c2];

Model = [c1'*c1 == 1, c2'*c2 <= 1]
objective = c'*S*c;

%% Semidefinite relaxation (lower bound appears tight but no solution extracted)
sol = optimize(Model, objective,sdpsettings('solver','moment','moment.order',1))
relaxvalue(c'*S*c)

%% 2nd level semidefinite relaxation
sol = optimize(Model, objective,sdpsettings('solver','moment','moment.order',2))
assign(c,sol.xoptimal{1})
value(c'*S*c)

%% Global solver for comparison
optimize(Model,objective,sdpsettings('solver','bmibnb'))
value(c'*S*c)

A semidefinite relaxation of first level is pretty much what also is called the S-procedure, and it is known that the S-procedure always computes the correct solution when you only have 1 quadratic (in)/equality (as it then essentially solves the generalized eigenvalue problem) but there are some special cases where it is tight also with more constraints. I am not sure if this is such a case.