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.
Thanks alot for your help


(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

Thanks for answering,
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…
Would you mind please if I ask for your email to send my code to check?
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 andx+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 
    to be nonnegative, hence there is no need to add additional
    constraints X >= 0 or Y >= 0 to enforce this.

Overloaded methods:
   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.


(Michal Adamaszek) #6

(Apologies for advertisement but that may be of some use for @ramin_hhh who has a Mosek academic license) Mosek will have native support for the exponential cone in next version. Drop an email to Mosek support if you are interested.


CVX solving problem