3
$\begingroup$

I am trying to develop a model, solving an optimization problem which has the following objective function:

variable p(i);
minimize sum(cost)
subject to
p>=0

where cost is defined as:

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

Note that the problem is discontinuous, which means the functions do not match at the breakpoints. As if statement is not allowed to be used in cvx, I think that declaring binary variables as indicators might work, like using the constraint:

$$p(i) - 5 + My >0$$

so that $y$ will be forced to be $1$ when $p(i) \le 5$, and $0$ otherwise. Yet, I still have no idea how to deal with the segment like $5<p(i)\le10$ by indicator variables.

Could anyone help me on this formulation?

$\endgroup$
4
  • $\begingroup$ Your title does not match the stated problem, because the last segment is quadratic. $\endgroup$ Apr 23 at 18:13
  • $\begingroup$ Thanks for the comment. I have modified the title, but not sure if it is correct:( $\endgroup$
    – Yukinari
    Apr 23 at 18:17
  • $\begingroup$ Could you specify the values of constants $b,c,d$ ? $\endgroup$
    – Kuifje
    Apr 23 at 18:23
  • $\begingroup$ Sure. I have edited the post. Thanks for commenting. $\endgroup$
    – Yukinari
    Apr 23 at 18:26
5
$\begingroup$

Although focused on implementing the model in YALMIP instead of CVX (converting the code should be trivial), precisely this case is described in the following tutorial https://yalmip.github.io/modellingif

You basically introduce a binary variable $\delta_i$ for each region, and then add the implications that $\delta_i \rightarrow \{\text{cost} = f_i(x), x \in \text{region}_i\}$ and model these using standard big-M.

$$-M(1-\delta_i)\leq \text{cost}-f_i(x) \leq M(1-\delta_i),\\~-M(1-\delta_i)+ x_i^L\leq x\leq x_{i}^U + M(1-\delta_i)\\\sum_i \delta_i=1$$

(The term with the quadratic cost is actually treated slightly differently to avoid adding nonconvex quadratics, discussed in tutorial)

If the cost is convex, it can be done more efficiently without any binary variables.

The discontinuity at zero is essentially impossible to capture with a numerical solver. You can of course add a region for it to allow the cost to become $0$, but you must understand that a solver can have for instance $x = 10^{-8}$ but still declare that you are in the zero cost region.

$\endgroup$
5
  • $\begingroup$ Thanks for the answer! I still have some questions. Since the problem in my post is not continuous(different from the tutorial), I think modifying the second inequality for big-M as: -M(1 - delta) + lb < x <= ub + M(1 - delta) may fit my problem. Is this correct? Also, is cost a continuous auxiliary variable that I should declare, which allows me to just minimize the sum of costs? $\endgroup$
    – Yukinari
    Apr 23 at 19:00
  • $\begingroup$ You cannot have strict inequalities in real optimization. The function value is simply undefined (out of two possibilities) at the switches..With the data and functional form you have, cost must be a continuous variable, as it can take any non-negative value. $\endgroup$ Apr 23 at 19:08
  • $\begingroup$ but if strict inequalities are not allowed, isn't f(x) are forced to produce identical value at breakpoints? For example, when x = 5, either delta_1 and delta_2 can be 1 since 0<=5<=5 and 5<=5<=10. In this way, the cost could be either 73.6 or 120.4, which is impossible. Or we can do this way because we are minimizing the objective, and 10*5+23.6<15*5+45.4, which thus makes the solver choose the cost as 10*5+23.6? $\endgroup$
    – Yukinari
    Apr 23 at 19:25
  • $\begingroup$ The solver can activate either the left definition or the right definition and thus use either 73.6 or 120.4 as cost. It will pick the value most beneficial to the overall model (if you minimize this function it will of course pick 73.6). This will not only happen for $x=5$ but in a region around $5$ within the numerical tolerances of the solver, i.e. you can get a solution $x=5.000000000001$ with cost 73.6 $\endgroup$ Apr 23 at 19:33
  • $\begingroup$ Thank you so much! I think I got the point. This approach is really amazing for a non-mathematics student like me:) $\endgroup$
    – Yukinari
    Apr 23 at 19:38
2
$\begingroup$

If the constants are such that the cost function is convex (e.g., $b=0$, $c=-25$, $d=-1775$), you could minimize a variable $z$ subject to \begin{align} z &\ge 10p + b \\ z &\ge 15p+c \\ z &\ge 20p^2 -10p +d \\ z &\ge 0 \end{align}

With the above values, the cost function is the maximum of the curves in the figure below:

enter image description here


EDIT: With the constants given by OP after editing his post, the cost function turns out to not be convex, so this does not apply.

$\endgroup$
1
  • $\begingroup$ Thanks for answering. Seems this approach is feasible for the continuous cases. $\endgroup$
    – Yukinari
    Apr 23 at 19: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.