3
$\begingroup$

I'm encountering a puzzling issue with SciPy's minimize function in a constrained optimization problem. My objective is to optimize a piecewise linear function with an equality constraint. However, the solution provided by the algorithm is different from what I logically expect. I would appreciate guidance on identifying the cause of this discrepancy and how to rectify it. Here's the relevant section of my Python code:

from scipy.optimize import minimize

def f(x):
    if 0 <= x <= 150:
        return x
    elif x >= 150:
        return 150

def objective(x):
    x1, x2 = x
    return f(x1 + 350) + f(x2)

def constraint(x):
    return x[0] + x[1] - 300

x0 = [0, 900]
bounds = [(0, 300), (0, 300)]
con = {'type': 'eq', 'fun': constraint}

result = minimize(objective, x0, bounds=bounds, constraints=con, options={'disp': True})

The output is

Optimization terminated successfully (Exit mode 0) Current function value: 300 Iterations: 1 Function evaluations: 3 Gradient evaluations: 1 (array([ 0., 300.]), 300)

The optimizer returns [0, 300] as the solution with a function value of 300. However, I was expecting [300, 0] to be the correct solution. This is based on the logic that f(x1 + 350) should max out first before x2 is increased, given the nature of the piecewise function f(x).

$\endgroup$
4
  • 1
    $\begingroup$ More to @Rob Pratt 's answer, it appears to have found a local maximum, which is actually the global maximum. So perhaps the solver quit after achieving first order optimality conditions. I wonder what the starting values of x were? Perhaps you can show all the output? The combination of "300 Iterations: 1 Function evaluations: 3 Gradient evaluations:" seems very strange. There are some some solvers which declare first order optimality and terminate if the starting value satisfies (1st order) KKT conditions, without even bothering to look at 2nsd order info or even try to descend, $\endgroup$ Jan 28 at 22:26
  • $\begingroup$ @MarkL.Stone The starting values were x0 = [0, 900]. And the objective function is flat at [0, 300], which is both a local max and a local min. $\endgroup$
    – RobPratt
    Jan 28 at 23:20
  • $\begingroup$ The starting point is infeasible. Perhaps the returned solution was the first feasible point the solver found, and first order optimality conditions are satisfied there, so the solver called it a day. $\endgroup$ Jan 29 at 12:39
  • $\begingroup$ @Mark L. Stone Yes, and I think you and Rob Pratt are totally right. minimize only consider local minimum. And since this function is flat in some areas so that it just returns this solution. $\endgroup$ Jan 29 at 13:31

1 Answer 1

6
$\begingroup$

You are trying to minimize a concave function, and minimize finds only a local minimum. To find a global minimum, use one of the methods under "Global optimization" here: https://docs.scipy.org/doc/scipy/reference/optimize.html#

$\endgroup$
4
  • 1
    $\begingroup$ Thank you very much. I am relatively new to optimization, and I have another question. Are there any global solvers you would recommend for optimizing piecewise linear objective functions with equality constraints? $\endgroup$ Jan 28 at 23:30
  • $\begingroup$ @YiyuanChen it sounds like that's an interesting-enough question to be posted as a new question so that everyone in the community has a chance to post and/or read the answer. You can ask as many (good) questions as you like in Stack Exchange! Also, just fyi, there is also computational science SE. $\endgroup$
    – uhoh
    Jan 29 at 7:43
  • 1
    $\begingroup$ @uhoh Thanks for your suggestions. I have posted this question at scicomp.stackexchange.com/questions/43761 $\endgroup$ Jan 29 at 13:44
  • $\begingroup$ For a global optimiser that can use constraints have a look at scipy.optimize.differential_evolution $\endgroup$ Jan 30 at 2:07

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.