最小化球面上的凸函數


4

問題描述

$ \ mathcal {C} = \ {X \ in \ mathbb {R} ^ n \ mid g(X)\ leq 0 \} $ $ g(X)$ 凸函數。假設對於給定的 $ r> 0 $ ,我需要解決可行性問題 $$ \存在^?X \ in \ mathcal {C} \ cap \ {X \ in \ mathbb {R} ^ n \ mid X ^ T \ cdot X \ geq r ^2 \} $$

我的嘗試

我需要解決以下優化問題 \開始{align}\ min_ {x \ in \ mathbb {R} ^ n}&\ quad g(x)\\\ text {s.t}&\ quad x ^ T \ cdot x \ geq r ^ 2\ end {align} 不幸的是,這是使凹域上的凸函數最小化。但是,請考慮以下矩陣: $$ Q = \ begin {bmatrix} A&B \\ B ^ T&C \ end {bmatrix} \ in \ mathbb {R} ^ {(n + m)\ times(n+ m)} $$ $ C \ in \ mathbb {R} ^ {m \ times m} $ $ B \ in \ mathbb {R} ^ {n \ times m} $ $ A \ in \ mathbb {R} ^ {n \ times n} $ 。然後根據舒爾補定理,一個具有: $$ C \ succeq 0 \ implies \ left(Q \ succeq0 \ iff A-B \ cdot C ^ {-1} \ cdot B ^ T \ succeq 0 \ right)$$因此,因為 $ \ mathcal {I} \ succeq 0 $ \開始{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} 因此 $$ \開始{bmatrix} r ^ 2&X ^ T \\ X&\ mathcal {I} \ end {bmatrix} \ nsucceq 0 \ Rightarrow r ^ 2-X ^ T \cdot X <0 $$ 因此, $ X ^ T \ cdot X \ geq r ^ 2 $ 的充分(但不是必需)條件是 $ \begin {bmatrix} r ^ 2&X ^ T \\ X&\ mathcal {I} \ end {bmatrix} \ preceq 0 $ ,在 $ X $。獲得: \開始{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}

問題

這是正確的嗎?恐怕當矩陣不是正定的必要條件時,要求它為負定太多!有沒有更好的解決方案?

3

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.