Scipy.optimize 不尊重约束

问题描述 投票：0回答：1

我正在尝试创建一个脚本，以最小化三个不同方向的两条线末端之间的最大距离。第一条线 A 具有固定的原点和长度，而线 B 的原点和长度是我试图优化的参数，以最小化端点之间的最大距离。我有两个约束，原点之间的欧几里德距离必须大于 0.1，并且每次旋转的线 B 的端点必须比该旋转的线 A 的端点距离线 A 的原点至少远 0.1 个单位。当我运行脚本时，约束将被忽略。

这是我创建优化问题的代码。约束 1 和 2 都被忽略。

# 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]

然后这是我运行 Scipy 优化功能的代码

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)}")

当我运行代码时，scipy 最小化目标函数，同时忽略约束，然后运行直到达到迭代限制，因为不遵守约束，但不会尝试更改控制变量来解决此问题。

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
1个回答
0
投票

这里最简单的解决方法是更改约束，以便它们直接引用

distance_constraints
。

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

（注意：虽然 

distance_constraints()
返回多个值，但可以将其放入单个约束中，因为 SciPy 支持向量值约束。）

完整更正的代码

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)}")

从输出中，我们可以看出约束都是非负的。

绘制结果

但是约束/目标与我们要解决的问题相符吗？对于这种事情，我喜欢编写一些绘图代码，以直观地表示手头的问题。

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)

输出：

optimization result

比较您的目标、约束条件和优化过程的输出，我发现有三件事需要评论。

  1. 在约束 1 中，您希望线 B 的原点距 A 的原点至少 0.1。然而，它实际上是检查它距 (0, 0) 至少 0.1。仅当 A_origin 位于 (0, 0) 时，这才会是相同的事情。
  2. 在约束 2 中，您希望 B 行的末尾不比 A 行的末尾更接近原点 [0,0]。然而，它实际上是检查它不比 A 行的末尾加 0.1 更近。
  3. 它并没有很好地找到一个点来最小化相应旋转的 A 点和 B 点之间的最大距离。

问题 1 和 2 不是我能解决的问题 - 你可能已经想到了我指出的事情。不过，问题 3 是可以解决的。

对我来说，这看起来像一个局部最小值问题：优化问题包含多个局部最小值，并且局部优化器无法区分局部最小值和全局最小值之间的区别。

要检查这一点，一个简单的方法是改变初始值，看看是否可以找到更好的结果。

initial_guess = [-0.01, 0.0, 0.6]

通过这个初步猜测，它找到了更好的结果。这说明需要全局优化。

盆地跳跃

我通常使用盆地跳跃来解决这样的问题。 Basinhopping 是一种两阶段方法，在随机跳跃和局部最小化之间交替。

但是，为了尊重您的约束，它需要您定义一个接受函数。此函数检测随机跳跃步骤是否以您的约束所禁止的方式更改了参数。

示例：

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)

输出：

basinhopping optimization

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.