# Does cvx solve nonlinear convex problems?

(John) #1

Hello all,
I am really confused…some of my friends say that they used cvx for their nonlinear convex programming…
I have a serious question: some days ago I asked for writing xlog(1+x/y) in cvx, and you told me how to write it: rel_entr(x+y,y)+rel_entr(y,x+y) .
But here is my question: CAN we put constraints like x
log(1+x/y) < const. ?
I wrote this constraint on cvx (the whole of problem is linear except this), cvx (under MOSEK academic license) gives this error…:
Successive approximation method to be employed.
** For improved efficiency, Mosek is solving the dual problem.**
** Mosek will be called several times to refine the solution.**
** Original size: 860 variables, 300 equality constraints**
** 200 exponentials add 1600 variables, 1000 equality constraints**
-----------------------------------------------------------------
** Cones | Errors |**
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
** 0/ 0 | 7.000e+00 0.000e+00 0.000e+00 | Unbounded**
** 0/ 0 | 7.000e+00 0.000e+00 0.000e+00 | Unbounded**
** 0/ 0 | 7.000e+00 0.000e+00 0.000e+00 | Unbounded**
-----------------------------------------------------------------
Status: Infeasible
Optimal value (cvx_optval): -Inf
but without this constraint the problem had been solved correctly.

(Mark L. Stone) #2

You need to pay attention to the warnings and caveats at http://cvxr.com/cvx/doc/advanced.html#the-successive-approximation-method .

CVX accepted your problem, but reported that it is infeasible. Well, if you had a problem which was “solved correctly” and you add an additional constraint, it is certainly possible to end up with a problem which is infeasible.

Have you tried increasing the value of `const` in your constraint to see whether a feasible solution is found for some value of `const` ? A more systematic thing you could try is to make `const` a CVX variable, and otherwise keep your optimization problem as is, except change the objective to `minimize(const)` . Presuming CVX’s successive approximation method succeeds (converges), this should produce the smallest value of `const` for which the problem you really want to solve is feasible. Presumably (i.e., presuming CVX’s infeasibility determination is correct), your current value of `const` is less than what that value will turn out to be.

(John) #3

The problem is not about the value of Constant, I take it nearly infinity! but cvx still gives error or fails.
Actually I think constraints like sigma(xlog(1+x/y)) <= const can not be handled easily in Successive Convex Approximation method and mosek or other solvers fail…
TIA

(Mark L. Stone) #4

As foe feasibility, note that in the code `x*log(1+x/y)=rel_entr(x+y,y)+rel_entr(y,x+y)` , as provided by Michal_Adamaszek in Writing x*log(1+x/y) , both `y` and`x+y` must be nonnegative, or `rel_entr` will be infinity. Therefore, if your other constraints don’t allow a solution in which both `y` and `x+y` are nonnegative, your program will be infeasible.

help rel_entr
rel_entr Scalar relative entropy.
rel_entr(X,Y) returns an array of the same size as X+Y with the
relative entropy function applied to each element:
{ X.*LOG(X./Y) if X > 0 & Y > 0,
rel_entr(X,Y) = { 0 if X == 0 & Y >= 0,
{ +Inf otherwise.
X and Y must either be the same size, or one must be a scalar. If X and
Y are vectors, then SUM(rel_entr(X,Y)) returns their relative entropy.
If they are PDFs (that is, if X>=0, Y>=0, SUM(X)==1, SUM(Y)==1) then
this is equal to their Kullback-Liebler divergence SUM(KL_DIV(X,Y)).
-SUM(rel_entr(X,1)) returns the entropy of X.

``````Disciplined convex programming information:
rel_entr(X,Y) is convex in both X and Y, nonmonotonic in X, and
nonincreasing in Y. Thus when used in CVX expressions, X must be
real and affine and Y must be concave. The use of rel_entr(X,Y) in
an objective or constraint will effectively constrain both X and Y
constraints X >= 0 or Y >= 0 to enforce this.

cvx/rel_entr
``````

If that hasn’t resolved the matter, the other thing you can try is to use CVX 3.0beta with solvers SCS or ECOS. In this configuration, the solvers’ native exponential cone capability will be employed, thereby avoiding CVX’s successive approximation method. So the solution process may be more reliable. However, CVX 3.0beta is still buggy, so you could encounter difficulties due to that.

Everything on this forum is handled by public posting rather than email. If you show the complete output from CVX/MOSEK, perhaps someone can make a better assessment of how to interpret the outcome.

(John) #5

Thanks alot for detailed explanations.