How to best handle piecewise linear objectives and quadratic objectives involving the same variables?

[Arianna]

Hi everyone!

I'm attempting to minimize a function which has both piecewise-linear components and quadratic components using Gurobi. The built-in setPWLObj() is really helpful and simple to use, except that setting a piecewise linear objective for a given variable overrides any other objective for that variable. This appears to be the case even if I attempt to use multi-objectives.

This is presents an issue because my complete objective function is of the form x^T Q x + d \sum_i ||x[i] - x[i]^*|| + \sum_i P_i(x[i] - x[i]^0), where each P_i is piecewise linear. Explicitly, each component of my variable vector x effects the quadratic term, the linear term, and the piecewise linear term of my function. My problem involves both box constraints and linear non-box constraints (e.g. \sum_i x[i] == 1), so Gurobi initially seemed like one of the best options out there. However, this inability to handle piecewise linear objectives in tandem with other objectives may make Gurobi essentially unusable for me.

I've considered two workarounds, but both seem clunky for different reasons.

1. Create another variable vector, let's call it y, and set its objective to the piecewise linear term above. Set the objective of our original variable vector, x, to the first two terms. Then enforce a strict equality: y == x. This clearly seems dumb, and most likely adds extra (unneeded) computational complexity, as the length of x in my case ranges from 7-14, which is already sizable.

2. Manually build my piecewise linear objective using SOS2 constraints and "anchor" variables for each "vertex" of the piecewise linear function. I know this is how piecewise linear functions are implemented internally in Gurobi, so this seems feasible, but I would love to utilize the full force of Gurobi's abilities (and minimize the chance of user error on my end), so I feel like there must/should be a higher-level way to do this.

I would love any ideas/input on how to do this in the most elegant way. For more context, the picture below provides some sample piecewise linear functions of the form that appear in my problem. Notably, each function is convex on one side of the y-axis and 0 on the other, but may not necessarily be convex as a whole. This structure is what initially drew me to convex optimization, but I'm open to other forms of solver if better-suited types exist.

Thank you in advance for your help!

Arianna

[Daniel Espinoza]

Hi Arianna

I'll answer inline

I'm attempting to minimize a function which has both piecewise-linear components and quadratic components using Gurobi. The built-in setPWLObj() is really helpful and simple to use, except that setting a piecewise linear objective for a given variable overrides any other objective for that variable. This appears to be the case even if I attempt to use multi-objectives.

setPWLObj is incompatible with quadratic costs, and multiobjective only suppor linear objectives.

 

This is presents an issue because my complete objective function is of the form x^T Q x + d \sum_i ||x[i] - x[i]^*|| + \sum_i P_i(x[i] - x[i]^0), where each P_i is piecewise linear. Explicitly, each component of my variable vector x effects the quadratic term, the linear term, and the piecewise linear term of my function. My problem involves both box constraints and linear non-box constraints (e.g. \sum_i x[i] == 1), so Gurobi initially seemed like one of the best options out there. However, this inability to handle piecewise linear objectives in tandem with other objectives may make Gurobi essentially unusable for me.

 

If the objective function is convex, you don't need SOS constraints, you only need to define z >= your_objective and minimize z (or a sum of z variables, each one for each pwl term plust the other quadratic and linear terms)

In the convex case you can handle PWL functions at least in two forms:

z >= m_i x + n_i , \forall i \in I (i.e. each supporting linear constraint)

or 

z = f(0) + sum (m_i y_i i \in I)

x = sum (y_i: i \in I)

y_i \in [0,delta_i] .\forall i \in I

where delta_i is the width of the corresponding interval

The first approach allow for refining the function on the fly,

The second is in a sense `lighter' for the solver.

Hope that helps

Best,

Daniel

[zinc...@gurobi.com]

Hello Arianna:

I believe the model you are trying to formulate is a non-convex minimization problem.  I will outline my reasoning for this statement below.  Nevertheless, I believe Gurobi could be a very good solver choice, as using MIP framework one can formulate a desired-quality approximating model --you can consult the example I have alluded to previously-- and solve the subsequent model using the solver typically quite efficiently.  An alternative to this would be trying to identify a solver that would promise to handle non-convex constraints natively, but typically this would come at a cost of dramatically loosing the efficiency of handling MIPs. You may want to consult NEOS Optimization Guide https://neos-guide.org/optimization-tree

Types of Optimization Problems | NEOS neos-guide.org */ As noted in the Introduction to Optimization, an important step in the optimization process is classifying your optimization model, since algorithms for solving optimization problems are tailored to a particular type of problem.

to exploit this option further to try to identify a suitable solver (like KNITRO, IPOPT etc.).  One additional thing to keep in mind when choosing the solver is whether you anticipate extending your model in the future to support integrality or additional logic within the model, where MIP methodology is extremely well suited for.

Now, for non-convexity of F(x) I will offer an "asymptotic" (and a bit hand-wavy) argument, for the sake of brevity.  One can probably build a more rigorous math argument using, say, perspective transformation of convex functions, but I will not be focusing on this now.

1) For simplicity of notation, lets focus on a single bi-linear objective term that gets added to your convex quadratic portion of F(x).  Lets assume x is a scalar, and we are looking at what kind of a function you obtain from   f(x) = p(x) (x - x^0)   product.  Introduce auxiliary   t := x - x^0; then, equivalently you can think of looking at f(t) = p(t) t, where p(t) is continuous, convex on t <= 0, and 0 for t >= 0.  

2) If p(t) is such as above, you can think of p(t) as a limiting case of a sequence of smooth differentiable functions whose second derivative p'' >= 0 for t <= 0 (think of smoothing the break points of the original p(x) ever so slightly).  Now, we can evaluate

f''(t) = p'' t + 2 p'

and so (a) f'' <= 0 if t <= 0, and p(t) is decreasing (this corresponds to your graph in red), and so is concave, and (b) f'' may or may not be positive, if p(t) is increasing.  Moreover, noting that most of the time p'' is zero (since p was piece-wise linear), one can deduce that f'' will be convex if p is increasing -- this corresponds to the decreasing portion of the graph in red (recall p is "flipped", as you put it).

3) So far we have that f(t) term is concave for the blue graph, and only partly convex for the red graph.  I would suggest that an efficient way to handle this situation is to construct a p-w linear approximation in both cases (a) and (b), whereas in case (b) you may further possibly take advantage of the partial convex segment of f(t).  The latter may not be worth the effort though, depending on how many break points "decreasing" segment of p in red has (I would say if there are more than a handful number of such breakpoints, you may as well not bother).

4) Once you construct a p-w linear approximation to f(t), call it ff(t), you can introduce 

w >= ff(t)

and simply add the respective w to the objective F(x) you aim to minimize.

[You can probably plot a few figures of f(t) to confirm that this reasoning makes sense.]

Hope this helps, and please let me know if you have any further questions.

[zinc...@gurobi.com]

Below, the working assertion is the P_i is continuous, convex for (x-x^0) <= 0, and 0 for (x-x^0) >= 0.

[zinc...@gurobi.com]

See also this thread 

"Optimizing a non-convex objective function in Gurobi"