1
$\begingroup$

It seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure when one is interest in finding local extrema or KKT points only.

Out of curiosity, suppose that I have a simple problem that is

$\begin{array}{*{20}{c}} {\min }&{abc}\\ {}&{a_1 \le a \le a_2}\\ {}&{b_1 \le b \le b_2}\\ {}&{c_1 \le c \le c_2} \end{array}$

Here $a_1,a_2,b_1,b_2,c_1,c_2$ are some positive numbers

And I know that the following decomposition exist from high school math

$abc = \frac{{{{\left( {a - b - c} \right)}^3} + {{\left( {a + b + c} \right)}^3} - \left[ {{{\left( {a + b - c} \right)}^3} + {{\left( {a - b + c} \right)}^3}} \right]}}{{24}}$

Then how can I set up a convex concave procedure to solve this problem ?

Note that since $a_1,a_2,b_1,b_2,c_1,c_2$ are just some number it is not clear if the individual cubic terms are convex or are concave. This has give rise to some difficulty in determining which term to linearize for the convex concave procedure.

Would you kindly help me with this ?

P/S: I already know that this problem can be tackle through geometric programming but I just want to know how to tackle it using a convex concave procedure.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Why not change variables to $(\alpha, \beta, \gamma) = (\ln a, \ln b, \ln c)$? Now you can minimize the log of the objective $\alpha + \beta + \gamma$ instead, subject to $\ln a_1 \leq \alpha \leq \ln a_2$ and so on, which is a linear program. $\endgroup$
    – Max
    Commented Jul 4 at 17:56
  • 3
    $\begingroup$ In fact, as stated, the problem is trivially minimized by setting each variable to its lower bound. A more thorough example may be helpful. $\endgroup$
    – Max
    Commented Jul 4 at 17:57
  • $\begingroup$ I already know that this problem can be tackle through geometric programming but I just want to know how to tackle it using a convex concave procedure. Your approach is actually a geometric programming approach $\endgroup$
    – Tuong Nguyen Minh
    Commented Jul 4 at 19:55
  • $\begingroup$ The convex concave procedure is not a universal algorithm applicable to all problems, your example included. You could linearize the mutilinear term $xyz$ based on the gradient about the previous iteration's point; that would essentially make this Sequential Linear Programming, which is not the convex concave procedure. Perhaps you should re-read the paper you linked. $\endgroup$
    – Mark L. Stone
    Commented Jul 6 at 20:39

1 Answer 1

Reset to default
2
+50
$\begingroup$

I cannot help you with setting up the convex-concave procedure, but I can help you to a DC formulation that works on the entire domain of a, b and c. In particular, since $xy = 0.5(w^2 - x^2 - y^2)$ for $w=x+y$, it is easy to show that

$$xyz = 0.5(v^2 - r^2 - z^2),\; v=r+z,\; r=0.5(w^2 - x^2 - y^2),\;w=x+y.$$

With this reformulation your objective function $abc$ can be replaced with a simple DC expression, accompanied by two linear constraints and one simple DC constraint. Hope you find this useful.

Elaboration on the DC constraints:

The paper you link defines a DC constraints as $f_i(x) - g_i(x) \leq 0$ for convex functions $f_i(x)$ and $g_i(x)$. Hence, as example (3) in the paper shows, $f_i(x) - g_i(x) = 0$ can modeled as $f_i(x) - g_i(x) \leq 0$ and $g_i(x) - f_i(x) \leq 0$. This is also the trick you need to put $r=0.5(w^2 - x^2 - y^2)$ on standard form.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you but I just get a straight feeling. What is the difference between DC programming and con vex concave procedure. I thought they are the same ? $\endgroup$
    – Tuong Nguyen Minh
    Commented Jul 12 at 2:09
  • 1
    $\begingroup$ What I mean is that I know just enough of DC programming to produce the reformulation above, but I don't know the convex-concave procedure nor any other way to solve DC programs in theory or practice. I am more familiar with disciplined convex optimization, particularly conic optimization, which also solves geometric programming including the program above. $\endgroup$
    – Henrik Alsing Friberg
    Commented Jul 12 at 5:48
  • $\begingroup$ Oh thank you ! frankly i do not knơw much about dc programming too $\endgroup$
    – Tuong Nguyen Minh
    Commented Jul 12 at 6:10
  • $\begingroup$ Sorry but can you show me with constraint is DC ? $\endgroup$
    – Tuong Nguyen Minh
    Commented Jul 12 at 12:03
  • 1
    $\begingroup$ I updated the answer. $\endgroup$
    – Henrik Alsing Friberg
    Commented Jul 12 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.