5
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ What are the constraints? Equality constraints? Inequality constraints? $\endgroup$ – Rodrigo de Azevedo Feb 19 '17 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Feb 19 '17 at 18:43
  • $\begingroup$ Let's assume that the constraints are linear inequalities. $\endgroup$ – ght Feb 20 '17 at 3:57
  • 1
    $\begingroup$ The quadratic part $- x^T \Lambda x$ in itself is already causing the problem to be non-convex. $\endgroup$ – F_G Feb 20 '17 at 17:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Feb 22 '17 at 15:46
5
+75
$\begingroup$

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…

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

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

$\endgroup$

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.