How to model the following problem in CVX

(Ahmed Al-baidhani) #1

I have the following optimization problem:
\min_{x_i,y_i}~\sum_{i=1}^{n} x_i+y_i \\ \textbf{s.t.}\quad \quad \sum_{i=1}^{n} \ln(1+k_ix_i)+\sum_{i=1}^{n} \ln(1+k_iy_i)\geq B \\ \quad \quad \quad ~ ~ \sum_{i=1}^{n}a_i(3x_i^2+3y_{i}^2+2x_iy_i)+b_{i}(x_i+y_i)+c_i \geq E \\ \quad \quad \quad ~ ~ ~ 0\leq\sum_{i=1}^{n} x_i+y_i \leq S, ~x_{i}\geq 0,~ y_{i} \geq 0.
k_1>k_2> \ldots k_n>0, a_1>a_2> \ldots a_n>0, c_1>c_2> \ldots c_n>0, B>0, E>0 and S>0.

The term 2x_iy_i is against the DCPruleset, hence, the above problem in its current form cannot be solved with CVX. Any idea how to deal with this case?


(Mark L. Stone) #2

That looks like a clunker to me.

Let f = 3*x^2 + 3*y^2 + 2*x*y. Hessian of f = [6 2;2 6], so f is a convex quadratic. The good news is that it can be entered in CVX as 0.5*[x y]*[6 2;2 6]*[x;y]. The bad news is that because a_i > 0, the inequality goes in the wrong direction to be convex.

(Ahmed Al-baidhani) #3

Thank you for the reply.
So the inequality direction makes the problem non-convex any global optimal point cannot be attained, right?

(Mark L. Stone) #4

Because the optimization problem is non-convex,a point satisfying the Karush-Kuhn Tucker (KKT) first order optimality conditions could be a global minimum, a local minimum which is not a global minimum, a saddle point, or a local or global maximum.

There are global solvers available for non-convex problems, but they do not always succeed in finding the globally optimal solution within available run-time and memory.

The only hope for getting this problem entered into CVX and submitted by it to a solver is if CVX’s MIDCP capability can be used to handle the non-convexity via introduction of binary (or integer)variables, I have no reason to believe that can be done in this case, but I am not sure that it can’t be, and haven;t pout in the effort to try to do that. If you find such a formulation, please post it here for the benefit of forum readers.