高等数学 / 系统课时
约束优化问题
约束优化问题
约束优化研究的是:在满足规则的候选解中,寻找让目标函数最小或最大的点。本课将建立目标函数、约束、可行域和边界解之间的关系,并用一个二维例子完成建模、求解与代码验证。
学习目标
- 能把业务限制写成等式或不等式约束
- 能区分可行解、内部点、边界点与不可行解
- 能判断最优解为何可能落在约束边界上
约束优化模型包含什么
一个最小化问题通常写成:
同时要求:
其中, 是目标函数,决定“好坏”; 是等式约束,要求精确满足; 是不等式约束,限定变量能够活动的范围。所有约束都满足的点称为可行解,这些点组成的集合称为可行域。
例如,训练模型时可以最小化损失函数,同时限制参数范数不超过给定阈值;资源分配时可以最小化成本,同时要求预算、容量和非负条件全部成立。
可行域与边界解
对不等式约束 ,若某个可行点满足 ,该约束在此点未被“顶住”;若满足 ,该约束处于活跃状态。活跃描述的是该条约束取等号。若约束在此处局部冗余,点仍可能在可行域内部,例如 在 处活跃,却没有排除任何实数。等式约束则要求候选点始终落在指定曲线、曲面或更高维集合上。

若一个无约束全局最优点可行,它仍是约束问题的全局最优点。若无约束最优点不可行,最优点可能落在边界,也可能位于可行域内部。后一种情况在非凸问题中并不矛盾。例如 在 上的唯一最小点是内点 ,因为括号内为正;而 ,说明无约束全局最优点不在这个区间。
主示例:在三角形区域内找最小值
考虑目标函数:
约束为 、、。无约束最小点是 ,但它满足 ,因此不可行。对任何可行点都有 。用 可得 。要达到下界,必须有 且 ,由此得到 ,它确实可行。
也可以从这条活跃边界出发计算。令 ,得到
求导并令其为零,可得 ,所以 、,目标值为 。下面用步长为 的网格搜索验证结果:
def objective(x, y):
return (x - 2) ** 2 + (y - 1) ** 2
def main():
best = None
# 用整数条件 i+j<=200 枚举三角形内的网格点
for i in range(201):
x = i / 100
for j in range(201 - i):
y = j / 100
value = objective(x, y)
if best is None or value < best[0]:
best = (value, x, y)
value, x, y = best
print(f"x={x:.2f}, y={y:.2f}, f={value:.4f}")
if __name__ == "__main__":
main()预期输出:
x=1.50, y=0.50, f=0.5000网格搜索只能给出离散精度下的近似解;本例恰好命中解析解。实际问题中,步长越小,计算量越大,因此通常使用专门的约束优化算法,而不是穷举网格。
建模时最容易出错的地方
第一,约束方向写反。例如“使用量不超过 100”应写成 ,若统一整理为 ,则应写成 。
第二,只求目标函数驻点,却不检查约束。约束问题的候选解必须先可行,再比较目标值。
第三,只检查一条边界。二维可行域可能包含多条边和多个角点;高维问题也可能有多组活跃约束,遗漏任何一组都可能漏掉最优解。