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.
Best 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.