1
$\begingroup$

When I do my project, I need to optimize piecewise linear objective functions (perhaps non convex) with equality constraints.

The piecewise linear objective function may be not convex like this in the graph

enter image description here

Since it is not convex, I fail to get the right result in https://or.stackexchange.com/questions/11583/

Now I am inquiring does there is a recommended global solver to optimize piecewise linear objective functions with equality constraints in Python.

$\endgroup$
1
  • 1
    $\begingroup$ How many line segments do you have? If it's less than, say, 1000, you can just find the minimum on each segment and then take the best of these minima. $\endgroup$ Jan 29 at 19:42

2 Answers 2

3
$\begingroup$

For global optimization of black box functions, I have successfully used scipy's differential evolution (https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.differential_evolution.html) in different projects. Of course, its performance will heavily depend on the characteristics of your problem and the parameters that you choose.

Since you are working with a unidimensional picewiwse linear function, modeling your optimization problem as a MILP is also a viable option. Pyomo can easily help you model your piecewise linear function: https://pyomo.readthedocs.io/en/stable/pyomo_modeling_components/Expressions.html#piecewise-linear-expressions

Open-source solvers (HighS or CBC) should be able to handle small/medium scale MILP problems with piecewise linear functions. For large scale problems, I recommend you to use a commercial solver, such as Gurobi.

$\endgroup$
2
$\begingroup$

Given you represent your 1-dimensional objective function as a sequence of coordinates $((x_i, f_i))_{i=1}^n$ with $x_i < x_j$, then you can in iterate through your points in increasing order, check if $f_i$ is a local optimum, and, if so, check whether it satisfies your equality constraints. If it does, just keep track of the best result seen thus far. If you have $m$ linear constraints, then the runtime of this approach is $O(nm)$.

You can generalize this to dimension $d$ if you are using a grid type structure to your piecewise function with a runtime of something like $O(d 2^d n m)$, though here you'd probably want to just represent the piecewise function as a graph so you can better track which coordinates are neighbors. This idea works well enough if $d$ is a smaller constant and would be simple to program and parallelize.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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