Minimize a convex function over a sphere

Question

Problem description

Let $\mathcal{C} = \{X \in \mathbb{R}^n \mid g(X) \leq 0\}$ with $g(X)$ a convex function. Suppose I need to solve the feasibility problem, for a given $r>0$ $$ \exists ^?X \in \mathcal{C} \cap \{ X\in \mathbb{R}^n \mid X^T \cdot X \geq r^2\}$$

My attempt

I need to solve the following optimization problem \begin{align} \min_{x \in \mathbb{R}^n} &\quad g(x) \\\text{s.t}&\quad x^T\cdot x \geq r^2 \end{align} This unfortunately is a minimization of a convex function over a concave domain. However, consider the following matrix: $$ Q = \begin{bmatrix} A &B\\ B^T &C\end{bmatrix} \in \mathbb{R}^{(n+m)\times(n+m)}$$ with $C \in \mathbb{R}^{m\times m}$, $B \in \mathbb{R}^{n\times m}$ and $A \in \mathbb{R}^{n\times n}$. Then according to Schur's complement theorem one has: $$ C \succeq 0 \implies \left( Q \succeq0 \iff A - B \cdot C^{-1} \cdot B^T \succeq 0\right)$$ Therefore, because $\mathcal{I} \succeq 0$ \begin{align} r^2 - X^T\cdot X \geq 0 \iff X^T\cdot X \leq r^2 \iff \begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \succeq 0 \end{align} Therefore $$ \begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \nsucceq 0 \Rightarrow r^2 - X^T\cdot X < 0 $$ Hence a sufficient (but not necessary) condition for $X^T\cdot X \geq r^2$ is $\begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \preceq 0$, which is convex in $X$. It is obtained: \begin{align} \min_{x \in \mathbb{R}^n} &\quad g(x) \\ \text{s.t} &\quad \begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \preceq 0 \end{align}

Question

Is this correct? I am afraid while the necessary condition being the matrix not to be positive definite, asking for it to be negative definite is too much! Are there any better solution?

Answer 1

You are trying to minimize a convex function outside (including on) a sphere. That is a non-convex constraint region, and hence a non-convex optimization problem.

The statement

Hence a sufficient condition for $X^T\cdot X \geq r^2$ is $\begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \preceq 0$, which is convex in $X$ is obtained:

is convex alchemy, and is just flat out wrong. If it were correct, you would have discovered a way of turning the non-convex optimization problem into a convex SDP.

I suggest you try using a global optimization solver if you want the globally optimal solution. And if the dimension is not too large, it may succeed.

Or you can use a local non-convex nonlinear optimization solver.

If you are really wedded to convex optimization, and want to spin the dice with your own crude optimization solver, which might not converge to anything, and if it does converge to something, may not even converge to a local optimum, let alone the global optimum, you can try the convex-concave procedure, as outlined in Stephen Boyd's answer at http://ask.cvxr.com/t/how-to-handle-nonlinear-equality-constraints/22/4

Edit to address your edit subsequent to my original answer. $\begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \preceq 0$ is INFEASIBLE. Even if $r^2 = 0$ it is infeasible due to $\mathcal{I}$ having positive diagonal elements. You are attempting convex alchemy, and it is wrong.