基于SLSQP的带约束凸离散函数优化问题求助

针对你遇到的「仅在离散点上有定义的凸函数，需要用SLSQP或其他方法做带约束最小化」的问题，我整理了几个实用的解决方案，结合凸函数的特性来适配你的场景：

方案一：利用凸性做二分查找（最优最快） #

因为你的目标函数是凸函数，且预存的x_vals是排序好的，对应的y_vals序列必然是单峰凸序列（先递减到最小值，再递增）。这种情况下，完全不需要用优化器，直接用二分查找就能快速定位最小值点，时间复杂度仅为O(logN)，对于1e6量级的数据来说效率极高。

代码示例 #

import numpy as np

def find_min_discrete_convex(x_vals, y_vals):
    # 确保x_vals是递增排序的（你的代码里已经用np.sort处理过）
    left, right = 0, len(x_vals) - 1
    while left < right:
        mid = (left + right) // 2
        # 凸序列的单峰特性：若mid点值小于mid+1点，说明最小值在左半区间
        if y_vals[mid] < y_vals[mid+1]:
            right = mid
        else:
            left = mid + 1
    # 最终left=right就是最小值点的索引
    min_idx = left
    return x_vals[min_idx], y_vals[min_idx]

# 测试你的示例场景
f = lambda x: x**2
N = 1000000
x_vals = np.sort(np.random.random(N))*2 - 1
y_vals = f(x_vals)

min_x, min_y = find_min_discrete_convex(x_vals, y_vals)
print(f"离散点中的最小值点：x={min_x:.6f}, y={min_y:.6f}")

这个方法完全规避了连续优化器对函数连续性的要求，直接利用凸函数的数学特性，是最适合你场景的方案。

方案二：适配SLSQP的离散函数包装（需用优化器时） #

如果因为存在复杂约束（比如不等式约束）必须使用SLSQP，我们可以把离散函数包装成连续可导的近似函数，同时保证凸性不变。

这里的关键是用np.searchsorted快速定位输入x对应的离散区间（仅O(logN)时间，计算量可以忽略），然后用线性插值近似目标函数，用区间斜率近似梯度——因为原函数是凸的，线性插值的近似函数也是凸的，能满足SLSQP的优化假设。

代码示例 #

from scipy.optimize import minimize
import numpy as np

# 预准备离散数据
f = lambda x: x**2
N = 1000000
x_vals = np.sort(np.random.random(N))*2 - 1
y_vals = f(x_vals)

# 包装连续目标函数：用线性插值近似离散凸函数
def discrete_convex_func(x):
    x = np.asarray(x).item()
    idx = np.searchsorted(x_vals, x)
    # 处理边界情况
    if idx == 0:
        return y_vals[0]
    if idx == len(x_vals):
        return y_vals[-1]
    # 取相邻离散点做线性插值
    x_left, x_right = x_vals[idx-1], x_vals[idx]
    y_left, y_right = y_vals[idx-1], y_vals[idx]
    t = (x - x_left) / (x_right - x_left)
    return (1 - t)*y_left + t*y_right

# 包装梯度函数：用相邻点的斜率近似
def discrete_convex_grad(x):
    x = np.asarray(x).item()
    idx = np.searchsorted(x_vals, x)
    if idx == 0:
        return (y_vals[1] - y_vals[0])/(x_vals[1] - x_vals[0])
    if idx == len(x_vals):
        return (y_vals[-1] - y_vals[-2])/(x_vals[-1] - x_vals[-2])
    x_left, x_right = x_vals[idx-1], x_vals[idx]
    y_left, y_right = y_vals[idx-1], y_vals[idx]
    return (y_right - y_left)/(x_right - x_left)

# 用SLSQP执行带边界约束的最小化
initial_guess = 0.5
bounds = [(-1, 1)]
result = minimize(
    discrete_convex_func,
    initial_guess,
    method='SLSQP',
    bounds=bounds,
    jac=discrete_convex_grad  # 提供梯度能大幅提升优化效率
)

print(f"SLSQP优化结果：x={result.x[0]:.6f}, y={result.fun:.6f}")
print(f"真实最小值：x=0.0, y=0.0")

注意事项 #

你提到「计算量过大无法采用线性插值」，但np.searchsorted的计算成本极低（1e6个点每次查找仅约20次比较），完全不会成为瓶颈。如果是担心插值误差，由于你有1e6个密集离散点（区间[-1,1]内平均间距2e-6），插值误差会非常小，完全可以接受。

方案三：复杂约束下的凸优化建模 #

如果存在线性不等式/等式约束，也可以用凸优化库（如cvxpy）结合离散点的凸插值来建模，但本质和方案二类似，核心还是通过插值将离散函数转化为连续凸函数后再优化。

内容的提问来源于stack exchange，提问作者HolyMonk