4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, I do not think is wrong, but it may not be necessary. It is based on the logic: if $A \rightarrow B$ then $\neg B \rightarrow \neg A$ $\endgroup$ – C Marius Mar 25 at 8:01
  • $\begingroup$ The question is how much is distorts the original problem, like replacing the sphere with some linear approximation ... or worse. $\endgroup$ – C Marius Mar 25 at 8:16
  • $\begingroup$ See the edit of my answer to address your question edit. Also, you could, but I would not recommend, use binary variables and linear approximation of the sphere to produce a horrible beast. Better to let a global optimization solver do that kind of thing for you. $\endgroup$ – Mark L. Stone Mar 25 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.