I want to get the lower bound of a non-convex program through the dual problem. Can I do it using CVX?
For example, I have the following problem:
min f0(x)
s.t. f1(x) <= 0
Here, f1(x) is non-convex. Let, the lagrange dual function, g§ = inf_x (f0(x) + p*f1(x).
The optimal dual solution: max_p g§. This dual solution is a lower bound of my original primal problem.
I know that CVX does not handle non-convex problems. But, my dual problem is concave here. Therefore, can CVX provide me a lower bound of the primal problem using the concave dual problem?
I am also looking for other softwares that provide lower bound of non-convex programs using the dual problems. Any suggestion will be very appreciated.
Like you’ve pointed out, CVX does not handle non-convex problems. This means that you cannot write your problem in its primal form and expect CVX to do anything except throw an error.
However, as you’ve also pointed out, your dual problem is concave. You have to derive the dual problem by hand and actually find the closed-form expression for g(p) = \inf_x \left(f_0(x) + p \, f_1(x)\right). Then you can input the problem in CVX.
At the moment, there is no active development in a modeling language that provides lower bounds on non-convex problems. You can check out a Python package called CVXPY, which does sequential convex programming on non-convex programs. I’m not sure if you can extract the lower bounds directly. To the best of my knowledge, it is currently abandonware.
Long story short, you have to find the dual function by hand, then put that into a CVX problem to obtain a lower bound. There may be new / upcoming features in CVX I’m not aware of, but MCG will likely correct me in that case.
Nice answer. There’s really nothing to add here. CVX simply cannot handle non-convex problems in any way (except of course for the recent addition of mixed-integer support). You must compute the dual by hand, and express it in DCP form, for CVX to handle it.
