2
$\begingroup$

I am adding some constraints to my model described in my previous post, where a discontinuous piecewise-quadratic functions is the objective to be minimized in cvx.

Here I have an additional terms, sum(cost2), that is included in the objective as:

variable p(N);
variable cost1(N);
variable cost2(N);
variable delta(N, 4);
variable gamma(N, 3);
expression cost1_exp(4);
expression cost2_exp(3);
minimize sum(cost1)+sum(cost2)
subject to
    p>=0
    for i = 1:N
        -M*(1-delta(i, 1))<=cost1(i)-cost1_exp(1)<=M*(1-delta(i, 1))
        -M*(1-delta(i, 2))<=cost1(i)-cost1_exp(2)<=M*(1-delta(i, 2))
        -M*(1-delta(i, 3))<=cost1(i)-cost1_exp(3)<=M*(1-delta(i, 3))
        -M*(1-delta(i, 4))<=cost1(i)-cost1_exp(4)<=M*(1-delta(i, 4))
        -M*(1-delta(i, 1))<=p(i)<=M*(1-delta(i, 1))
        -M*(1-delta(i, 2))<=p(i)<=5+M*(1-delta(i, 1))
        -M*(1-delta(i, 3))+5<=p(i)<=10+M*(1-delta(i, 1))
        -M*(1-delta(i, 4))+10<=p(i)<=100+M*(1-delta(i, 1))
        sum(delta(i))==1
    end
    for i = 1:N
        -M*(1-gamma(i, 1))<=cost2(i)-cost2_exp(1)<=M*(1-gamma(i, 1))
        -M*(1-gamma(i, 2))<=cost2(i)-abs(cost2_exp(2))<=M*(1-gamma(i, 2))
        -M*(1-gamma(i, 3))<=cost2(i)-abs(cost2_exp(3))<=M*(1-gamma(i, 3))
        -M*(1-gamma(i, 1))<=p(i)<=M*(1-gamma(i, 1))
        -M*(1-gamma(i, 2))<=p(i)<=0.01+M*(1-gamma(i, 1))
        -M*(1-gamma(i, 3))+0.01<=p(i) - 10^-6<=100+M*(1-gamma(i, 1))
        sum(gamma(i))==1
    end

where I add the constraints provided by @Johan to linearize my problem (I have not modified the constraints for quadratic terms) and the cost1_exp is identical as here:

cost1(i) = 0, if p(i) = 0,
cost1(i) = 10*p + 23.6, if 0<p(i)<= 5, 
cost1(i) = 15*p + 45.4, if 5<p(i)<=10, 
cost1(i) = 20*p*p - 10*p + 375, if p(i) > 10

However, the cost function cost2_exp makes the trouble:

cost2_exp(1) = 0, if p = 0,
cost2_exp(2) = 6*(10*log10(p))^2 -10*10*log10(p), if 0<p<= 0.01, 
cost2_exp(3) = 17*10*log10(p) + 42.8, if 0.01<p<=100, 

I try to add constraints as for cost1, and make similar works for cost2.

However, there are still some problems: When p(i) = 0, gamma(i, 1) = 1, gamma(i, 2) = gamma(i, 3) = 0, the cost2_exp(2) and cost2_exp(3) will force the cost to be Inf and -Inf respectively to satisfy the constraints, while cost2_exp(1) force the cost to be 0. In addition, cost2_exp(2) is greater than cost2_exp(3) at p = 0.01, which will force the solver to select cost2_exp(3) when p = 0.01.

To address these problems, I add abs() to force the cost2_exps produce only positive value, which makes the solver to choose cost2 = 0 at p = 0, since the problem is minimization problem. However, this approach can not be adopted to cost2_exp(2) since it is a quadratic function, and should be divided into quadratic and linear term to handle. Also, to force the solver to choose cost2_exp(2) at p = 0.01, I add a small number 10^-6 to prevent the solver from choosing cost2_exp(3) when p = 0.01.

Thus, my question is: How can I deal with this particular case when p = 0 for cost2_exp(2), or I can just not make it an absolute value since it will produce Inf when p = 0?

$\endgroup$
3
$\begingroup$

You are not going to be able to add these logs and quadratic terms to the model via simple double-sided big-M constraints, as they generate non-convex use of convex quadratics and logs, and CVX does not support that. The use of the squared log is not possible either. I don't think it supports automatic modelling of nonconvex use of abs operator either.

Most problematic though is the concave term cost2_exp3. This will not be exponential-cone representable, so CVX cannot be used.

If you plug it into YALMIP instead, it will compile and run, but a general global optimization solver will be invoked (the internal one if you haven't installed any), i.e. the complexity of the problem is most likely harder than you think. Nevertheless, it looks like a simple structure so it could possibly be solved by a global solver.

$\endgroup$
3
  • $\begingroup$ Thanks for answering my question! So if logs are used, the big-M formulation cannot be applied here since it will make the formulation non-convex, and there is no methods to rewrite it to make it convex. The only way to solve this problem is to use YALMIP instead of cvx, to invoke a global solver, such as branch-and-bound, to solve the problem. Am I correct? $\endgroup$ – Yukinari Apr 24 at 16:55
  • $\begingroup$ Correct. This cost can never be made mixed-integer exponential-cone representable and thus CVX is not possible. Post a question on the YALMIP google groups forum and I can give you some hints, it is quickly converted with some copy-paste. $\endgroup$ – Johan Löfberg Apr 24 at 17:01
  • $\begingroup$ Thank you so much! I will try to take a look on YALMIP and post my question again on its google group. $\endgroup$ – Yukinari Apr 24 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.