Can this optimization problem be transformed into or approximated by a SOCP?

Question

We would like to know if the following optimization problem can be transformed into an SOCP problem or maybe approximated by a SOCP problem. The objective function is defined as $$ \mathrm{Obj}(x) = \big({\alpha^{T}x -x^{T}\Lambda x -{x^{\beta}}^{T}\Omega x^{\beta} }\big) $$ and we would like to solve $$ \max_{x} \mathrm{Obj}(x) $$ subject to Linear and Quadratic constraints for the $n$-dimensional vector $x=(x_1,x_2,\ldots,x_n)$. The vector $x^{\beta}$ is defined such that its $i$-th entry is equal to $x_{i}^{\beta}$ and $$ \frac{1}{2}\leq\beta<1. $$ Both matrices $\Lambda$ and $\Omega$ are positive definite.

Especially important is the case $\beta=\frac{1}{2}$.

Answer 1

First, you should restrict $x$ to be positive or use $|x|^\beta$ instead.

Then I think that the answer is no:

For $\beta\neq 1/2$ you can argue as follows:

The special case of diagonal $\Omega = \mathrm{diag}(w_1,\dots,w_n)$ ($w_i>0$) is simpler as in this case you problem is $$ \min_x x^T\Lambda x - \alpha^T x + \sum_i w_i |x_i|^{2\beta}\quad\text{s.t. convex constraints} $$ i.e. is is a convex quadratic problem with a weighted $\ell^{p}$ regularizer with $1\leq p=2\beta <2$. As such it is a fairly simple convex problem.

I am fairly sure that even this special case can not be cast as SOCP (if found this claim in "Mixed norm FIR filter optimization using second-order cone programming" by Dan P. Scholnik (ICASSP 2002) and the report "Second-Order Cone Formulations of Mixed-Norm Error Constraints for FIR Filter Optimization" by Dan P. Scholnik and Jeffrey O. Coleman but no reference is given).

For $\beta=1/2$, i.e. $p=1$ one has to argue differently as the above case can be cast as an SOCP. The case including the spd matrices is equivalent to (neglecting the constraints) $$ \min_x \|Ax-b\|_2^2 + \|Lx^{1/2}\|_2^2 $$ with some $A$, $b$ and $L$.

Here the penalty looks like $$ \|Lx^{1/2}\|_2^2 = \sum_i (\sum_j l_{i,j}x_j^{1/2})^2. $$ With $n=2$, and $L=\begin{bmatrix}1 & 0\\1 & 1\end{bmatrix}$ lead to $$ \|Lx^{1/2}\|_2^2 = |x_1| + (\sqrt{x_1}+\sqrt{x_2})^2 $$ which is not a convex function (simply check that the level sets are not convex), so also here, the answer is no.

There is still a possibility that there may be a clever reformulation/substitution, but I doubt that. A prove that there is no such a reformulation seems very hard…

Answer 2

Probably not. But this looks similar to sparse recovery optimization. You could probably solve this with techniques similar to the ones in:

G. Haeser, H. Liu, Y. Ye - Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary, 2017. https://arxiv.org/pdf/1702.04300

Bian, W., Chen, X.: Linearly constrained non-lipschitz optimization for image restoration. SIAM Journal on Imaging Sciences, 8(4):2294–2322 (2015)

Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algo- rithms for non-Lipschitz and nonconvex minimization. Mathematical Pro- gramming, 149(1):301–327 (2015)

Ge, D., He, R. & He, S. pp 1–28 An improved algorithm for the L2–Lp minimization problem (2017). Mathematical Programming, doi:10.1007/s10107-016-1107-2