python 3.x - Scipy.optimize not respecting constraints - Stack Overflow

admin管理员组

文章数量:1122832

I'm trying to create a script that will minimize the maximum distance between the ends of two lines at three different orientations. The first line, A, has a fixed origin and length, while line B's origin and length are the parameters I'm trying to optimize to minimize the maximum distance between the end points. I have two constraints, the Euclidean distance between the origins must be greater than 0.1, and the endpoints of line B for each rotation have to be at least 0.1 units further away from the origin of line A than the endpoints of line A for that rotation. When I run the script, the constraints are ignored.

Here is my code to create the optimization problem. Constraint 1 and 2 are both ignored.

# Define the length of line A
length_A = 0.5

# Define the endpoint positions of line A after each rotation
A_origin = np.array([0, 0])
A_ends = np.array([
    A_origin + [0, -length_A],  # Initial position
    A_origin + [-length_A, 0],  # After 90-degree rotation
    A_origin + [0, length_A]
])
# Display results
print("Origin of line A:", A_origin)
print("Ends of line A:", A_ends)
# Objective function: Minimize the maximum distance between endpoints of A and B
def max_distance_to_A(params, A_ends):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Define rotations for line B endpoint based on origin and length
    B_ends = np.array([
        B_origin + [0, -length_B],  # Initial position
        B_origin + [-length_B, 0],  # After 90-degree rotation
        B_origin + [0, length_B]    # After 180-degree rotation
    ])

    # Calculate distances between each corresponding end of lines A and B
    distances = [np.linalg.norm(B_end - A_end) for B_end, A_end in zip(B_ends, A_ends)]

    # Objective: Minimize the maximum distance across all rotations
    return max(distances)

# Constraint function: Ensures all constraints are met
def distance_constraints(params, A_ends):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Constraint 1: Origin of line B must be at least 0.1 away from origin of A
    constraint1 = (np.linalg.norm(B_origin) - 0.1)
    # Constraint 2: End of line B should not be closer to origin [0,0] than the end of line A
    B_ends = np.array([
        B_origin + [0, -length_B],
        B_origin + [-length_B, 0],
        B_origin + [0, length_B]
    ])

    constraint2 = []
    for B_end, A_end in zip(B_ends, A_ends):
        dist_B_end_to_origin = np.linalg.norm(B_end)
        dist_A_end_to_origin = np.linalg.norm(A_end)
        constraint2.append(dist_B_end_to_origin - dist_A_end_to_origin - 0.1)

    all_constraints = [constraint1] + constraint2
    # Combine all constraints
    return all_constraints

# Wrapper for constraints in SciPy format
def constraint_func(params, A_ends):
    constraints = distance_constraints(params, A_ends)
    return [{'type': 'ineq', 'fun': lambda params, c=c:c} for c in constraints]

And then here's my code to run Scipy's optimize function

def debug_callback(params):
    print(f"Current parameters: {params}")
    print(f"Constraint values: {distance_constraints(params, A_ends)}")
    print(f"Objective value: {max_distance_to_A(params, A_ends)}")

initial_guess = [0.5, 0.5, 0.6]  # [x, y, length_B]

# Optimize
result = minimize(
    fun=max_distance_to_A,
    x0=initial_guess,
    args=(A_ends,),
    constraints=constraint_func(initial_guess, A_ends),
    method='SLSQP',
    callback=debug_callback,
    options={'disp': True, 'ftol': 1e-5}
)
# Extract optimal origin and length of line B
B_origin_opt = result.x[:2]
length_B_opt = result.x[2]

# Display results
print("Optimal origin of line B:", B_origin_opt)
print("Optimal length of line B:", length_B_opt)
print("Minimum of maximum distance:", result.fun)
print(f"Constraint values: {distance_constraints(result.x, A_ends)}")

When I run the code, scipy minimizes the objective function while ignoring the constraints, and then runs until the iteration limit is reached since the constraints are not respected but doesn't try to change the control variables to fix this.

Objective value: 1.2382318026714528e-08
Iteration limit reached    (Exit mode 9)
            Current function value: 1.2382318026714528e-08
            Iterations: 100
            Function evaluations: 1088
            Gradient evaluations: 100
Optimal origin of line B: [-1.22005976e-09 -5.21614408e-09]
Optimal length of line B: 0.49999999289408037
Minimum of maximum distance: 1.2382318026714528e-08
Constraint values: [-0.09999999464306945, -0.10000000188977556, -0.10000000588585986, -0.10000001232206371]

I'm trying to create a script that will minimize the maximum distance between the ends of two lines at three different orientations. The first line, A, has a fixed origin and length, while line B's origin and length are the parameters I'm trying to optimize to minimize the maximum distance between the end points. I have two constraints, the Euclidean distance between the origins must be greater than 0.1, and the endpoints of line B for each rotation have to be at least 0.1 units further away from the origin of line A than the endpoints of line A for that rotation. When I run the script, the constraints are ignored.

Here is my code to create the optimization problem. Constraint 1 and 2 are both ignored.

# Define the length of line A
length_A = 0.5

# Define the endpoint positions of line A after each rotation
A_origin = np.array([0, 0])
A_ends = np.array([
    A_origin + [0, -length_A],  # Initial position
    A_origin + [-length_A, 0],  # After 90-degree rotation
    A_origin + [0, length_A]
])
# Display results
print("Origin of line A:", A_origin)
print("Ends of line A:", A_ends)
# Objective function: Minimize the maximum distance between endpoints of A and B
def max_distance_to_A(params, A_ends):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Define rotations for line B endpoint based on origin and length
    B_ends = np.array([
        B_origin + [0, -length_B],  # Initial position
        B_origin + [-length_B, 0],  # After 90-degree rotation
        B_origin + [0, length_B]    # After 180-degree rotation
    ])

    # Calculate distances between each corresponding end of lines A and B
    distances = [np.linalg.norm(B_end - A_end) for B_end, A_end in zip(B_ends, A_ends)]

    # Objective: Minimize the maximum distance across all rotations
    return max(distances)

# Constraint function: Ensures all constraints are met
def distance_constraints(params, A_ends):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Constraint 1: Origin of line B must be at least 0.1 away from origin of A
    constraint1 = (np.linalg.norm(B_origin) - 0.1)
    # Constraint 2: End of line B should not be closer to origin [0,0] than the end of line A
    B_ends = np.array([
        B_origin + [0, -length_B],
        B_origin + [-length_B, 0],
        B_origin + [0, length_B]
    ])

    constraint2 = []
    for B_end, A_end in zip(B_ends, A_ends):
        dist_B_end_to_origin = np.linalg.norm(B_end)
        dist_A_end_to_origin = np.linalg.norm(A_end)
        constraint2.append(dist_B_end_to_origin - dist_A_end_to_origin - 0.1)

    all_constraints = [constraint1] + constraint2
    # Combine all constraints
    return all_constraints

# Wrapper for constraints in SciPy format
def constraint_func(params, A_ends):
    constraints = distance_constraints(params, A_ends)
    return [{'type': 'ineq', 'fun': lambda params, c=c:c} for c in constraints]

And then here's my code to run Scipy's optimize function

def debug_callback(params):
    print(f"Current parameters: {params}")
    print(f"Constraint values: {distance_constraints(params, A_ends)}")
    print(f"Objective value: {max_distance_to_A(params, A_ends)}")

initial_guess = [0.5, 0.5, 0.6]  # [x, y, length_B]

# Optimize
result = minimize(
    fun=max_distance_to_A,
    x0=initial_guess,
    args=(A_ends,),
    constraints=constraint_func(initial_guess, A_ends),
    method='SLSQP',
    callback=debug_callback,
    options={'disp': True, 'ftol': 1e-5}
)
# Extract optimal origin and length of line B
B_origin_opt = result.x[:2]
length_B_opt = result.x[2]

# Display results
print("Optimal origin of line B:", B_origin_opt)
print("Optimal length of line B:", length_B_opt)
print("Minimum of maximum distance:", result.fun)
print(f"Constraint values: {distance_constraints(result.x, A_ends)}")

When I run the code, scipy minimizes the objective function while ignoring the constraints, and then runs until the iteration limit is reached since the constraints are not respected but doesn't try to change the control variables to fix this.

Objective value: 1.2382318026714528e-08
Iteration limit reached    (Exit mode 9)
            Current function value: 1.2382318026714528e-08
            Iterations: 100
            Function evaluations: 1088
            Gradient evaluations: 100
Optimal origin of line B: [-1.22005976e-09 -5.21614408e-09]
Optimal length of line B: 0.49999999289408037
Minimum of maximum distance: 1.2382318026714528e-08
Constraint values: [-0.09999999464306945, -0.10000000188977556, -0.10000000588585986, -0.10000001232206371]

• python-3.x
• optimization
• scipy
• constraints
• scipy-optimize

Share Improve this question Follow edited Nov 27, 2024 at 21:59 Conor Carson asked Nov 21, 2024 at 15:55 Conor CarsonConor Carson 1133 bronze badges 5

• 1 Can you make this example reproducible? The A_ends and A_origin variables are not defined. – Nick ODell Commented Nov 21, 2024 at 16:57
• 1 return [{'type': 'ineq', 'fun': lambda params: c} for c in constraints] This lambda uses a variable not passed as an argument. This means that it uses the value of the variable at the time that the lambda is called, not the value at the time it is defined. This is called late binding, and it would cause this code to only respect the last constraint defined. – Nick ODell Commented Nov 21, 2024 at 17:00
• Good catch. A common fix is like return [{'type': 'ineq', 'fun': lambda params, c=c: c} for c in constraints] (assuming the rest of that code makes sense). – Matt Haberland Commented Nov 22, 2024 at 0:08
• @MattHaberland I added your line to my code, but now it computes the optimal value without respecting the constraints, sees that the constraints aren't respected, and then runs until the max iteration is reached without trying to change the control variables to respect the constraints. Does anyone know why this is happening or how to fix it? (I'm new to here, not really sure how I'm supposed to ask questions so can someone let me know if I'm doing anything wrong) – Conor Carson Commented Nov 27, 2024 at 21:08
• Without taking a close look, I see that the loop doesn't produce constraints that depend on params; they just return c. So if they are not satisfied initially, they will never be satisfied. I'd suggest defining your constraint functions separately, without a loop. They should accept params and return a non-negative values when params is acceptable. – Matt Haberland Commented Nov 28, 2024 at 23:48

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

The very simplest fix here is to change your constraints so that they directly reference distance_constraints.

    constraints=[{'type': 'ineq', 'fun': distance_constraints, 'args': (A_ends,)}],

(Note: although distance_constraints() is returning multiple values, it is fine to put this in a single constraint, as SciPy supports vector-valued constraints.)

Full corrected code

import numpy as np
from scipy.optimize import minimize
import matplotlib.pyplot as plt

# Define the length of line A
length_A = 0.5

# Define the endpoint positions of line A after each rotation
A_origin = np.array([0, 0])
A_ends = np.array([
    A_origin + [0, -length_A],  # Initial position
    A_origin + [-length_A, 0],  # After 90-degree rotation
    A_origin + [0, length_A]
])
# Display results
print("Origin of line A:", A_origin)
print("Ends of line A:", A_ends)
# Objective function: Minimize the maximum distance between endpoints of A and B
def max_distance_to_A(params, A_ends):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Define rotations for line B endpoint based on origin and length
    B_ends = np.array([
        B_origin + [0, -length_B],  # Initial position
        B_origin + [-length_B, 0],  # After 90-degree rotation
        B_origin + [0, length_B]    # After 180-degree rotation
    ])

    # Calculate distances between each corresponding end of lines A and B
    distances = [np.linalg.norm(B_end - A_end) for B_end, A_end in zip(B_ends, A_ends)]

    # Objective: Minimize the maximum distance across all rotations
    return max(distances)

# Constraint function: Ensures all constraints are met
def distance_constraints(params, A_ends):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Constraint 1: Origin of line B must be at least 0.1 away from origin of A
    constraint1 = (np.linalg.norm(B_origin) - 0.1)
    # Constraint 2: End of line B should not be closer to origin [0,0] than the end of line A
    B_ends = np.array([
        B_origin + [0, -length_B],
        B_origin + [-length_B, 0],
        B_origin + [0, length_B]
    ])

    constraint2 = []
    for B_end, A_end in zip(B_ends, A_ends):
        dist_B_end_to_origin = np.linalg.norm(B_end)
        dist_A_end_to_origin = np.linalg.norm(A_end)
        constraint2.append(dist_B_end_to_origin - dist_A_end_to_origin - 0.1)

    all_constraints = [constraint1] + constraint2
    # Combine all constraints
    return all_constraints


def debug_callback(params):
    print(f"Current parameters: {params}")
    print(f"Constraint values: {distance_constraints(params, A_ends)}")
    print(f"Objective value: {max_distance_to_A(params, A_ends)}")

initial_guess = [0.5, 0.5, 0.6]  # [x, y, length_B]

# Optimize
result = minimize(
    fun=max_distance_to_A,
    x0=initial_guess,
    args=(A_ends,),
    constraints=[{'type': 'ineq', 'fun': distance_constraints, 'args': (A_ends,)}],
    method='SLSQP',
    callback=debug_callback,
    options={'disp': True, 'ftol': 1e-5}
)
# Extract optimal origin and length of line B
B_origin_opt = result.x[:2]
length_B_opt = result.x[2]

# Display results
print("Optimal origin of line B:", B_origin_opt)
print("Optimal length of line B:", length_B_opt)
print("Minimum of maximum distance:", result.fun)
print(f"Constraint values: {distance_constraints(result.x, A_ends)}")

From the output, we can tell that the constraints are all non-negative.

Plotting the result

But do the constraints/objective match the problem we mean to solve? For this kind of thing, I like to write some plotting code, to visually represent the problem at hand.

def get_B_ends(params):
    B_origin = np.array(params[:2])
    length_B = params[2]

    # Constraint 1: Origin of line B must be at least 0.1 away from origin of A
    constraint1 = (np.linalg.norm(B_origin) - 0.1)
    # Constraint 2: End of line B should not be closer to origin [0,0] than the end of line A
    B_ends = np.array([
        B_origin + [0, -length_B],
        B_origin + [-length_B, 0],
        B_origin + [0, length_B]
    ])
    return B_origin, B_ends
def plot_optimization(result, initial_guess):
    for pt in A_ends:
        plt.plot([A_origin[0], pt[0]], [A_origin[1], pt[1]], 'ro-', label='A')

    B_origin, B_ends = get_B_ends(initial_guess)
    for pt in B_ends:
        plt.plot([B_origin[0], pt[0]], [B_origin[1], pt[1]], 'bo-', label='initial guess')
    B_origin, B_ends = get_B_ends(result.x)
#     print(A_origin, A_ends)
#     print(B_origin, B_ends)
    for pt in B_ends:
        plt.plot([B_origin[0], pt[0]], [B_origin[1], pt[1]], 'go-', label='final optimized')
    plt.axis('equal')
    handles, labels = plt.gca().get_legend_handles_labels()
    by_label = dict(zip(labels, handles))
    plt.legend(by_label.values(), by_label.keys())
    plt.show()
plot_optimization(result, initial_guess)

Output:

Comparing your goals, code comments, and the output of this optimization process, I see three things to comment on.

1. In constraint 1, you want the origin of line B to be at least 0.1 away from origin of A. However, it is actually checking that it is at least 0.1 away from (0, 0). This will only be the same thing if A_origin is at (0, 0).
2. In constraint 2, you want the end of line B to not be closer to origin [0,0] than the end of line A. However, it is actually checking that it is not closer than the end of line A plus 0.1.
3. It's not doing a very good job of finding a point which minimizes the maximum distance between corresponding rotated A and B points.

Issues 1 and 2 are not something I can solve - you might have intended the things I'm pointing out. Issue 3 is solvable, however.

To me, this looks like a local minima problem: the optimization problem contains multiple local minima, and the local optimizer is not capable of telling the difference between a local minima and the global minimum.

To check this, a simple way is to vary the initial value, and see if it can find a better result.

initial_guess = [-0.01, 0.0, 0.6]

With this initial guess, it finds a better result. This shows that global optimization is required.

Basinhopping

I usually use basinhopping for a problem like this. Basinhopping is a two-phase approach that alternates between random hops and local minimization.

However, in order to respect your constraints, it requires that you define an acceptance function. This function detects if the random hopping step has changed the parameters in a way that is forbidden by your constraints.

Example:

from scipy.optimize import basinhopping

initial_guess = [0.5, 0.5, 0.6]  # [x, y, length_B]
ftol = 1e-5

def accept_test(f_new=None, x_new=None, f_old=None, x_old=None):
    cons = distance_constraints(x_new, A_ends)
    # SLSQP allows constraint violations of up to ftol
    # Allow that here too
    accept = (np.array(cons) >= -ftol).all()
    return accept

result = basinhopping(
    max_distance_to_A,
    x0=initial_guess,
    minimizer_kwargs=dict(
        args=(A_ends,),
        constraints=[{'type': 'ineq', 'fun': distance_constraints, 'args': (A_ends,)}],
        method='SLSQP',
        callback=debug_callback,
        options={'disp': True, 'ftol': ftol}
    ),
    accept_test=accept_test,
    niter=100,
)
# Extract optimal origin and length of line B
B_origin_opt = result.x[:2]
length_B_opt = result.x[2]

# Display results
print("Optimal origin of line B:", B_origin_opt)
print("Optimal length of line B:", length_B_opt)
print("Minimum of maximum distance:", result.fun)
print(f"Constraint values: {distance_constraints(result.x, A_ends)}")
plot_optimization(result, initial_guess)
print(result)

Output:

本文标签： python 3xScipyoptimize not respecting constraintsStack Overflow