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

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}$.

• What are the constraints? Equality constraints? Inequality constraints? – Rodrigo de Azevedo Feb 19 '17 at 18:03
• needless to say, arbitrary quadratic constraints can be used to model 0-1 optimisation, and thus it's certainly hopeless to hope for even an approximation result---in this generality. – Dima Pasechnik Feb 19 '17 at 18:43
• Let's assume that the constraints are linear inequalities. – ght Feb 20 '17 at 3:57
• The quadratic part $- x^T \Lambda x$ in itself is already causing the problem to be non-convex. – F_G Feb 20 '17 at 17:28
• you wrote "subject to Linear and Quadratic constraints". If you have arbitrary quadratic constraints you can have $x_i(x_i-1)=0$, forcing $x_i\in\{0,1\}$. Using this you can encode your favourite NP-hard (or even APX-hard) combinatorial optimisation problem, e.g. MAX-CLIQUE. – Dima Pasechnik Feb 22 '17 at 15:46

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…

• How do you show that the diagonal p=1 case is SOCP? – ght Feb 25 '17 at 11:19

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