[Math] ny method that convert a concave problem into convex problem

optimization

I have an optimization problem of the form:

\begin{align}
\begin{cases}
x_2 \rightarrow \min,
\\
\text{subject to:} \\
f_1(x) \leq 0, \\
f_2(x) \leq 0,
\end{cases}
\end{align}

with $x= (x_1,x_2)^T$ as the optimization variable.

Here, $f_1(\cdot)$ is a convex function. But $f_2(\cdot)$ is a concave function.

Explicitly, $f_2(x)$ is of the form:
\begin{align}
f_2(x) = 2(D-x_1-2R)+\beta \frac{D^2-x_1^2+2DR-2Rx_1}{4R}-x_2,
\end{align}
with $D,R,\beta$ constant.

How to convert $f_2(x)$ to a convex function? Is there any method that do such a modification?

Thanks in advance.

Best Answer

No, you can't. If $f_2$ was convex, any local optimum will be a global optimum. This is not true if $f_2$ is concave: there may be many local optima. So these are two quite different types of problem, and in general problems with non-convex constraints are much harder. There is no way to "transform" your way out of it.

Related Solutions

[Math] ny method that convert a non-convex problem to a convex one

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

[Math] Normalized objective function in optimization problem

I get ~~different~~ the same results with Gurobi (with $x_1, x_2$ continuous):

----     64 PARAMETER report  

                         f1          f2          x1          x2         obj

max f1              950.000      50.000      50.000     150.000
max f2              640.000     160.000     160.000
utopia              950.000     160.000
min linear dist     640.000     160.000     160.000                   0.326
min quadr dist      747.735     135.138     135.138      41.437       0.069

When I plot these results (in the $f$ space) I see:

The blue line is the efficient frontier (i.e. the best $f_2$ for a given $f_1$).

When we require integer values for $x_1, x_2$ the quadratic solution changes a little bit:

----     65 PARAMETER report  

                         f1          f2          x1          x2         obj

max f1              950.000      50.000      50.000     150.000
max f2              640.000     160.000     160.000
utopia              950.000     160.000
min linear dist     640.000     160.000     160.000                   0.326
min quadr dist      744.000     136.000     136.000      40.000       0.070 (corrected)

No picture for this case as the frontier is now no longer a nice line.

The models are simply:

Best Answer

Related Solutions

[Math] ny method that convert a non-convex problem to a convex one

[Math] Normalized objective function in optimization problem

Related Question