Can you solve a non-convex function for an interval where it is convex?


(Sander Lam) #1

Hello,

Suppose I want to solve the following optimization problem. Can CVX do that? I know x^3 is not convex or concave, but the function for x => 0 is convex.
I read the FAQ and the forum, but still am not able to find the answer.

min x^3
s.t x => 0

This is obviously a useless optimization. I am trying to solve a much bigger optimization problem, where the objective function might not be convex, but the constraints make it a Convex Program:

My doubt is whether CVX would help me to more efficiently solve this problem. I solved it in MatLab with the fmincon function.

Thank you in advance for your help.


(Mark L. Stone) #2

You can use pow_pos(x,3) for your “useless” optimization. I’ll let you figure out whether pow_pos will do what you need for your non-useless optimization problems.


(Sander Lam) #3

Thank you very much for your reaction.

Is it possible to see, without programming it, whether CVX will be a good tool for solving the big problem?
As in, will CVX probably perform better than the fmincon function in Matlab?


(Mark L. Stone) #4

I don’t know which will be better. How well CVX works may depend on your choice of solver. How well FMINCON will perform may be strongly dependent on starting (initial) value provided to the solver, as well as various algorithm options you choose.


(Sander Lam) #5

I am close to solving my big problem with CVX and have two more questions.

Firstly, I define a function with a power that can differ between any number > 0. The error told me that pow_pos can not be used for powers smaller than 0, but pow_p is not giving me what I want either. Is any documentation available on these functions? Are there other options?
I want to, for example, define this function:
integral = [ f(1).^(power+1) ] / (capacity.^power);

My second question is whether it is possible to make CVX faster, by for example inserting an analytically computed Gradient of Hessian to the program?


(Mark L. Stone) #6

I’m not clear on which are your CVX variables. Is your objective convex? Have you proven it so?

pow_p and pow_pos are documented in the CVX Users’ Guide, and with some additional information using the help command.

You can use analytically computed gradient and Hessian with FMINCON, but cannot do so in CVX (whose solvers in effect calculate whatever gradient and Hessian are needed).


(Sander Lam) #7

My CVX variables are all f_a variables.

I don’t understand why I get the following error with pow_pos, because data.power(a) = 1.

fa = sum(f(k));
disp(data.power(a));
int = data.freeflow(a).*fa + (data.freeflow(a).*data.b(a)pow_pos(fa,(data.power(a)+1))/pow_pos(data.capacity(a),data.power(a)).(data.power(a)+1));

The code above gives the following output:

1

Error using pow_pos (line 16)
Second argument must be greater than or equal to 1.
For other exponents, use POW_P instead.

Error in WardropCVX (line 29)
int = data.freeflow(a).*fa +
(data.freeflow(a).*data.b(a)pow_pos(fa,(data.power(a)+1))/pow_pos(data.capacity(a),data.power(a)).(data.power(a)+1));

Do you have any ideas?


(Mark L. Stone) #8

Please provide a complete reproducible example, with all input data, starting from a fresh MATLAB session. And use preformatted text for your MATLAB, CVX code, so that all symbols are shown in the post.


(Michael C. Grant) #9

The general answer to your question is no; all functions in CVX must be convex over their entire natural domains. (And of course, they must already exist in CVX’s supported function list anyway). We’ve supplied a number of special cases like pow_pos when it is possible to do so mathematically.

It also looks like you’re violating DCP rules in your example as well. If you have not yet fully read the FAQ, please do. I strongly suspect that you will conclude that CVX cannot handle your model, and you will save yourself a lot of frustration trying to make it do so.


(Michael C. Grant) #10

You may find this Math StackExchange post helpful for understanding why it is actually important in practice that the functions inside a convex optimization problem remain convex even outside the feasible region.