高等数学 / 系统课时

约束优化问题

约束优化问题

约束优化研究的是:在满足规则的候选解中,寻找让目标函数最小或最大的点。本课将建立目标函数、约束、可行域和边界解之间的关系,并用一个二维例子完成建模、求解与代码验证。

学习目标

  • 能把业务限制写成等式或不等式约束
  • 能区分可行解、内部点、边界点与不可行解
  • 能判断最优解为何可能落在约束边界上

约束优化模型包含什么

一个最小化问题通常写成:

min⁡xf(x)\min_{x} f(x)

同时要求:

hi(x)=0,i=1,…,mh_i(x)=0,\quad i=1,\ldots,m
gj(x)≤0,j=1,…,pg_j(x)\le 0,\quad j=1,\ldots,p

其中,f(x)f(x) 是目标函数,决定“好坏”;hi(x)=0h_i(x)=0 是等式约束,要求精确满足;gj(x)≤0g_j(x)\le 0 是不等式约束,限定变量能够活动的范围。所有约束都满足的点称为可行解,这些点组成的集合称为可行域。

例如,训练模型时可以最小化损失函数,同时限制参数范数不超过给定阈值;资源分配时可以最小化成本,同时要求预算、容量和非负条件全部成立。

可行域与边界解

对不等式约束 g(x)≤0g(x)\le 0,若某个可行点满足 g(x)<0g(x)<0,该约束在此点未被“顶住”;若满足 g(x)=0g(x)=0,该约束处于活跃状态。活跃描述的是该条约束取等号。若约束在此处局部冗余,点仍可能在可行域内部,例如 −x2≤0-x^2\le0 在 x=0x=0 处活跃,却没有排除任何实数。等式约束则要求候选点始终落在指定曲线、曲面或更高维集合上。

二维可行域、等高线与边界最优点

若一个无约束全局最优点可行,它仍是约束问题的全局最优点。若无约束最优点不可行,最优点可能落在边界,也可能位于可行域内部。后一种情况在非凸问题中并不矛盾。例如 f(x)=x2(x2−4x+3)f(x)=x^2(x^2-4x+3) 在 [−1/2,1/2][-1/2,1/2] 上的唯一最小点是内点 00,因为括号内为正;而 f(2)=−4f(2)=-4,说明无约束全局最优点不在这个区间。

主示例:在三角形区域内找最小值

考虑目标函数:

f(x,y)=(x−2)2+(y−1)2f(x,y)=(x-2)^2+(y-1)^2

约束为 x≥0x\ge 0、y≥0y\ge 0、x+y≤2x+y\le 2。无约束最小点是 (2,1)(2,1),但它满足 x+y=3>2x+y=3>2,因此不可行。对任何可行点都有 (2−x)+(1−y)≥1(2-x)+(1-y)\ge1。用 a2+b2≥(a+b)2/2a^2+b^2\ge (a+b)^2/2 可得 f(x,y)≥1/2f(x,y)\ge1/2。要达到下界,必须有 x+y=2x+y=2 且 2−x=1−y2-x=1-y,由此得到 (1.5,0.5)(1.5,0.5),它确实可行。

也可以从这条活跃边界出发计算。令 y=2−xy=2-x,得到

f(x,2−x)=(x−2)2+(1−x)2f(x,2-x)=(x-2)^2+(1-x)^2

求导并令其为零,可得 4x−6=04x-6=0,所以 x=1.5x=1.5、y=0.5y=0.5,目标值为 0.50.5。下面用步长为 0.010.01 的网格搜索验证结果:

python
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()

预期输出:

text
x=1.50, y=0.50, f=0.5000

网格搜索只能给出离散精度下的近似解;本例恰好命中解析解。实际问题中,步长越小,计算量越大,因此通常使用专门的约束优化算法,而不是穷举网格。

建模时最容易出错的地方

第一,约束方向写反。例如“使用量不超过 100”应写成 u≤100u\le 100,若统一整理为 g(u)≤0g(u)\le 0,则应写成 u−100≤0u-100\le 0。

第二,只求目标函数驻点,却不检查约束。约束问题的候选解必须先可行,再比较目标值。

第三,只检查一条边界。二维可行域可能包含多条边和多个角点;高维问题也可能有多组活跃约束,遗漏任何一组都可能漏掉最优解。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

约束优化问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通