Pattern for which Ipopt returns suboptimal solutions #832
Replies: 1 comment 2 replies
-
|
Lurking here - I'm also interested in the answer, to better understand IPOPT's internal workings. FWIW my take on this problem is that while the constraint function is twice continuously differentiable, the shape of the constraint landscape, while smoothed, is essentially still a step function. This means that where we make the jump from 0 to 10 we do get quite large values in the Jacobian of the constraints, but outside of that we get zero, with a bit of interpolation due to the tanh. |
Beta Was this translation helpful? Give feedback.
-
|
Thank you for your input.
This made we wonder what happens, if I still have a non-zero slope at the outside part. I approximate the step-function now by the combination of three linear functions. To my surprise, even if I make the step much less steep, I still get (different) suboptimal solutions, depending on my initial guess: My new "step-function" with relatively slow transition, is a combination of three lines using a smooth max function (see https://en.wikipedia.org/wiki/Smooth_maximum)
With this approximated step-function, I do not know the actual optimal solution (I have not cared figuring it out). But I can see a similar behavior: If the initial guess
The switch when Ipopt finds a different solution seems to be around
Adjusted code:Click to see adjusted python codeimport casadi as ca
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
THRSHLD = 1
MIN_SLOPE_CASE_1 = 10
MIN_SLOPE_CASE_2 = 0
"""
^
|
|
x1 - o
| /
| /
THRSHLD - / x2 := (x1-x0)/(t1-t0) = (x1-x0) is slope
| /
| / constraint on x2 is not constant but depends on THRSHLD
x0 - o and as per scenario on the value of x0 or x1
|
+-----------|-----|------------->
t0 t1 := t0+1
Objective function: (x0-0)^2 + (x1-3/4*THRSHLD)^2
Optimal solution: x = [0, 3/4*THRSHLD, 3/4*THRSHLD]
Objective at optimal solution: 0
Scenario A + B: evaluate at beginning of collocation element, i.e. x0
if x0 > THRESHOLD then
x2 := x1-x0 shall be > MIN_SLOPE_CASE_1
else
x2 := x1-x0 shall be > MIN_SLOPE_CASE_2
Scenario A:
initial guess x0 < THRESHOLD
ipopt solution: ok
Scenario B:
initial guess x0 > THRESHOLD
ipopt solution: ok
Scenario C + D: evluate at end of collocation element, i.e. x1
if x1 > THRESHOLD then
x2 := x1-x0 shall be > MIN_SLOPE_CASE_1
else
x2 := x1-x0 shall be > MIN_SLOPE_CASE_2
Scenario C:
initial guess x1 > THRESHOLD
ipopt solution: converged, but bad
Scenario D:
initial guess x1 < THRESHOLD
ipopt solution: ok
where the if-else statements are smoothened using a tanh-step
"""
def sigmoid(x, k):
return 0.5 * (1 + ca.tanh(k * 0.5 * x))
def lower_bound(x):
# smooth_step = sigmoid(x - THRSHLD, k=10)
smooth_step = smoothstep(x, step_at=THRSHLD, step_width=10)
return smooth_step * MIN_SLOPE_CASE_1 + (1 - smooth_step) * MIN_SLOPE_CASE_2
def smoothstep(x, step_at, step_width):
eps = 0.01
width = 0.5 * step_width
slope_edges = 1e-2
a1 = step_at + width
b1 = 1
a0 = step_at - width
b0 = 0
# line representing cases x >= a1
# at (x = a1) I want to have 1. construct line through this point and with a slope of slope_edges
line_1 = slope_edges * (x - a1) + b1
# line representing cases x <= a0
# at (x = a0) I want to have 0. construct line through this point and with a slope of slope_edges
line_2 = slope_edges * (x - a0) + b0
# line representing cases a0 <= x <= a1
# line through the points (a0, 0) and (a1, 1)
line_3 = (b1 - b0) / (a1 - a0) * (x - a0) + b0
# put all together: desired step is min( line_1, max(line_2, line_3) )
line_23 = smooth_max_unit(line_2, line_3, eps=eps)
line_123 = -smooth_max_unit(-line_1, -line_23, eps=eps)
return line_123
def smooth_max_unit(a, b, eps):
return 0.5 * (a + b + ca.sqrt((a - b) ** 2 + eps))
def solve(x0, evaluate_at_beginning: bool):
# Declare variables
x = ca.SX.sym("x", 3)
# Form the NLP
f = (x[0] - 0) ** 2 + (x[1] - 3 / 4 * THRSHLD) ** 2 # objective
idx = 0 if evaluate_at_beginning else 1
g = ca.vertcat(
*[
(x[1] - x[0]) - x[2], # x2 represents slope from x0 to x1 with time step 1
x[2]
- lower_bound(x[idx]), # if x[idx] > THRESHOLD, then x[2] - MIN_SLOPE_CASE_1, else x[2] - MIN_SLOPE_CASE_2
]
)
lbg = [0, 0]
ubg = [0, np.inf]
nlp = {"x": x, "f": f, "g": g}
MySolver = "ipopt"
# Solver options
opts = {"ipopt.linear_solver": "ma27"}
# Allocate a solver
solver = ca.nlpsol("solver", MySolver, nlp, opts)
# Solve the NLP
sol = solver(x0=x0, lbg=lbg, ubg=ubg)
return [
f"x[{idx}]",
f"{x0}",
f"{sol["x"]}",
f"[0, {3/4*THRSHLD}, {3/4*THRSHLD}]",
f"{sol["f"]}",
"0",
]
if __name__ == "__main__":
df = pd.DataFrame(
{}, index=["eval constraint at", "initial guess", "found sol.", "optimal sol.", "found obj.", "optimal obj."]
)
df["scenario A"] = solve(x0=[-1, -1 + 2 * MIN_SLOPE_CASE_1, 2 * MIN_SLOPE_CASE_1], evaluate_at_beginning=True)
df["scenario B"] = solve(
x0=[THRSHLD + 1, THRSHLD + 1 + 2 * MIN_SLOPE_CASE_1, 2 * MIN_SLOPE_CASE_1], evaluate_at_beginning=True
)
df["scenario C"] = solve(x0=[-1, -1 + 2 * MIN_SLOPE_CASE_1, 2 * MIN_SLOPE_CASE_1], evaluate_at_beginning=False)
df["scenario C'"] = solve(x0=[-1, 1.1, 2.1], evaluate_at_beginning=False)
df["scenario D"] = solve(x0=[-1, 0, 1], evaluate_at_beginning=False)
print(df)
x = np.linspace(THRSHLD - 10, THRSHLD + 10, 1000)
plt.plot(x, lower_bound(x))
plt.savefig("demo_lower_bound_function.png") |
Beta Was this translation helpful? Give feedback.
-
|
If I use the tanh function again and make the step less steep by using def sigmoid(x, k):
return 0.5 * (1 + ca.tanh(k * 0.5 * x))
def lower_bound(x):
smooth_step = sigmoid(x - THRSHLD, k=1)
# smooth_step = smoothstep(x, step_at=THRSHLD, step_width=5)
return smooth_step * MIN_SLOPE_CASE_1 + (1 - smooth_step) * MIN_SLOPE_CASE_2then Ipopt converges to the same solutions, independent from the initial guesses I have tested:
But yea, then the problem is obviously also not close to the original problem anymore. Dashed lines are the linear functions from previous post:
|
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Hi,
I constructed an NLP for which Ipopt only finds a suboptimal solution for certain initial guesses. Furthermore, I believe there's a pattern for which initial guesses Ipopt returns a suboptimal solution. I guess Ipopt is stuck in a local minima. Nevertheless, I'm wondering whether this is a bug, a limitation of Ipopt or whether this needs to be considered as "provide bad initial guess, get bad result".
NLP
Decision variables
My NLP consists of three decision variables:
Constraints
There are two constraints:
That means, if$x_1$ is larger then 1, then $x_2$ needs to be larger than 10. Otherwise $x_2$ needs to be only non-negative.
Objective function
The objective function is given by$f := (x_0 - 0)^2 + (x_1 - 0.75)^2$
Optimal solution
The optimal solution I expect is:$x_0^* = 0, x_1^* = 0.75, x_2^* = 0.75$ with an objective value of $0$
Supoptimal solution
I have observed that if I provide a (feasible) initial guess (denoted by subscript$^0$ ) for which $x_1^0 > 1$ , then Ipopt returns an suboptimal solution for which $\tilde{x}_1 > 1$ and $\tilde{x}_2 = 10$ holds, i.e. exactly the lower bound I have specified for the case $x_1 > 1$ .
Examples (with smoothening function as in the code-snippet further below):
If the initial guess starts below the threshold, i.e.$x_1^0 < 1$ , then the returned solution looks ok. For instance:
I (who does not really know how Ipopt works internally), interpret it like this:
Conclusion / Questions
Thank you for taking the time of reading my post. I am grateful for any help.
Best Regards,
Matthias
Code-Snippet
Below is the python-script with four different scenarios:
Here's an image how my smoothening function looks like:
And here is my python-code. SW I use:
and probably not relevant:
And corresponding output:
Beta Was this translation helpful? Give feedback.
All reactions