# Is there any method that convert a non-convex problem to a convex one?

I have an optimization problem of the form:

minimize $\quad f_0(x)$

subject to $\;\;\;f_1(x)\leq0,\quad\quad\quad(C1)$

$\quad\;\quad\;\quad\quad\;f_2(x)\leq0,\quad\quad\quad(C2)$

where $x=\left[x_1, \cdots, x_K\right]^\mathrm{T}$ is the optimization variable.

• $f_0(\cdot)$ is a convex function.
• $f_1(\cdot)$ is a convex function.
• $f_2(\cdot)$ is a concave function. Explicitly, $f_2(x)$ is of the form:

$f_2(x)=\sum\limits_{k=p}^{p+n-1}\left(\log_2\left(1+\gamma_k x_k\right)-r_k\right)$ for $p\in\{1, \cdots, K-n\}$.

How to convert $f_2(x)$ to a convex function? Is there any method that do such a modification? Is my problem hard to solve because of the concavity of constraint $(C2)$?

Thank you for your time.

• Please add explicitly to the question that you want to transform your problem into an easier to solve version as well. And the answer should point out why the original version is harder to solve than the transformed one. – mvw May 16 '14 at 13:27

## 1 Answer

$\sqrt{x}$ is concave, but notice that if we compose it with $x^2$ we get $x$ which is convex.

One possibility is to find the right function to compose with, i.e. to map your non-convex domain (feasible points) to a convex set.

In your case, maybe taking $g(y)=(g_p(y_p),g_{p+1}(y_{p+1}),...,g_{p+n-1}(y_{p+n-1}))$, i.e. $x_k:=g_k(y_k)=(2^{y_k}-1)/\gamma_k$, gives $f_2\circ g=\sum y_k-r_k$, which is linear.

You will need to see if $f_0\circ g$ and $f_1\circ g$ are still convex.

Do you also know (are given) what are $f_0$ and $f_1$?

Another idea that sometimes works is to subdivide the feasible set into finitely many convex sets. In your case this doesn't help to make $f_2$ convex in each piece. But, who knows. Maybe when you do the transformation above, the $f_2$ becomes convex, but perhaps you lose the convexity of $f_1$, and for this the subdivision trick happens to work.

• Thanks. Good solution (+1). If $f_2(x)$ is a function of two variables. Do you think that your proposed method still works? If $f_2(x)=\sum\limits_{k=p}^{p+n-1}\left(\log_2\left(1+\gamma_k (x_k+z_k)\right)-r_k\right)$. – Jika May 14 '14 at 14:21
• You could try then $x_k=(e^{r_k}-s_k)/\gamma_k-1$, and $z_k=s_k/\gamma_k$ – user149090 May 14 '14 at 14:31
• I think you mean: $x_k=(2^{t_k}-s_k-1)/\gamma_k$, and $z_k=s_k/\gamma_k$? So I introduce two new variables $t_k$ and $s_k$. Am I right? – Jika May 14 '14 at 14:43
• I have forgotten twice that your $\log$ has base $2$. But, you know, it doesn't matter too much since $\log_2(x)=\log(x)/\log(2)$, and $\log(2)>0$. Yes, $t_k$ and $r_k$ are new variables. – user149090 May 14 '14 at 15:16