这一讲研究约束优化算法。无约束时,沿负梯度走即可尝试下降;有约束时,还必须保证新点满足限制。比如分配 10 辆车到三条路,三个流量必须非负,而且总和必须始终为 10。
先学习怎样调用求解器处理线性规划和二次规划,再学习 Frank–Wolfe、投影梯度下降,以及处理非线性约束的 SQP。贯穿全讲的问题是:既让目标变小,又让变量安排符合规则。
共 44 页。按原课件顺序,左侧看原页,右侧读讲解。
图中圈出的 method='highs' 是 SciPy 线性规划接口展示的方法选择。HiGHS 是求解器体系,接口还可选择对偶单纯形或内点方法。
原页关于单纯形法“难以处理大型问题”的概括过宽。现代对偶单纯形仍是实用算法;旧的独立 simplex 实现停用,也不等于整个算法家族被淘汰。
本课写应用代码时,可直接用 linprog(..., method='highs'),把注意力放在模型和结果。求解后查看 res.success、res.message、res.x 和 res.fun,分别确认求解状态、说明、参数和目标值。只有成功求解后,才把输出当成对应模型的最优解。
原问题是最小化 ,约束为 、、。其中 没有限定符号。
from scipy.optimize import linprog
res = linprog([-1, 4], A_ub=[[-3, 1], [1, 2]],
b_ub=[6, 4], bounds=[(None, None), (-3, None)],
method='highs')
print(res.x, res.fun)
结果为 ,最优值 −22。手算核对:由 得 ,而 满足全部约束并达到这个下界,所以确为最优。
表示各活动的完成时刻,不是开始时刻。活动开始时刻等于“完成时刻减工期”。
递推检查:A=8,B=18,C=27,D=35,E=23,F=33,G=37,H=36,I=47。所以最早完工为47 天,关键路径 A→B→C→D→G→I 的工期和为 47。
E 等 B,F 等 E,H 等 F,I 等 G 和 H。完整的后半段分别是 、、、、。例如 G 必须等 C、D、F 中最晚的 D 在第 35 天结束,所以 。I 等较晚的 G,得到 。
课件把变量固定为 ,共十个。目标只取最后一个变量,因此 。
A_ub=-A、b_ub=-b。完成时刻设为非负; 可设为自由变量,因为 已间接给出下界。调用求解器得到最优 。不同最优输出的非关键活动时刻可能含等待,但都应满足工期和先后关系。
矩阵难读时,任取一行翻回原来的活动关系检查。例如 D 的约束必须同时含 B、C 两位前置,不能漏掉其中之一。
from scipy.optimize import linprog
tasks = "ABCDEFGHI"
duration = dict(zip(tasks, [8, 10, 9, 8, 5, 10, 2, 3, 10]))
before = dict(zip(tasks, ["", "A", "B", "BC", "B", "E", "CDF", "F", "GH"]))
column = {task: i for i, task in enumerate(tasks)}
A_ub, b_ub = [], []
for task in tasks:
for parent in before[task] or [None]:
row = [0] * 10
row[column[task]] = -1
if parent is not None:
row[column[parent]] = 1
A_ub.append(row)
b_ub.append(-duration[task])
row = [0] * 10
row[column[task]], row[9] = 1, -1
A_ub.append(row)
b_ub.append(0)
res = linprog([0] * 9 + [1], A_ub=A_ub, b_ub=b_ub,
bounds=[(0, None)] * 9 + [(None, None)], method="highs")
print(res.success, res.fun)
column 给每项任务的完成时刻分配一列,第 10 列留给 。每个前置关系生成一行,例如 C 在 B 后完成,写成 ,B 列填 1,C 列填 −1。A 没有前置任务,所以只填 A 列。第二种行是 。程序直接生成“小于等于”的矩阵,输出 True 47.0。
设 是活动 缩短的天数,实际工期为 。例如 A 原来 8 天,压缩 2 天后变为 6 天。
一组最优压缩方案为 。成本为 。对应最早完成时刻为 6、14、23、28、18、27、30、30、40。
压缩原关键路径后,其他分支可能成为瓶颈。G 行中 表示 G 的开工时刻,它至少等于 C、D、F 三个完成时刻的最大值。
只取两条路径也能给任何方案算费用下界。A→B→C→D→G→I 原长 47,压缩量之和 至少是 7。A→B→E→F→H→I 原长 46, 至少是 6。
分别乘 5,500 和 3,500 后相加,得到 。对照表格里的真实费用,这个加权和对 A 每天多算 4,000,对 D 多算 1,000,对 E 多算 2,000。其余各项都等于或低于真实费用。
最多多算 ,因为 A、D、E 分别最多压缩 2、3、1 天。因此任意可行方案至少花 。本页的方案满足所有前置关系并达到下界,所以最优。
图中代码分为变量、约束、目标和求解四部分。
xA = cp.Variable(name="xA", nonneg=True) 建立非负压缩变量;其余 和完成时刻 同样建立。constraints = [xA <= 2, ...] 收集最大压缩量限制。 与 xG <= 0 合起来固定 。TB == TA+10-xB 让单一前置的活动紧接前项开始。在此没有资源冲突、等待也不降低成本的模型中,可选择这种最早安排。>= 表示必须等最晚的前置完成,不能把它们全部改成等式。Ti <= 40,再写 objective = cp.Minimize(总成本)。problem = cp.Problem(objective, constraints) 组成问题;problem.solve() 求解。用 problem.value 读最优成本,xA.value 等读变量值。最优额外成本为 46500。输出可能出现约 的微小零值或很小的越界残差,结合求解状态与容差读数,不必把它解释为另一个压缩方案。
完整课堂程序和具体输出可以逐行对照。打开 70 行代码讲解。
这页与上一页数学模型相同,只换了建模接口。把对应关系看清,就不需要重新学一套优化原理。
model = Model() 创建模型。addVar(lb=0, ub=2, name="xA") 建立 的变量;lb 是下界,ub 是上界。addVar(lb=0, ...) 建立。setObjective(成本表达式, GRB.MINIMIZE) 声明最小化成本。addConstr(TD >= TC+8-xD) 添加一条数学约束,每个前置关系各写一条。model.optimize() 求解,之后从变量的 .X 属性取数值、从 model.ObjVal 取目标值。原页注释里的 setParam('Method',2) 是指定求解方法的可选设置,去掉注释才会执行。无论使用哪个接口,最终应检查的是同一组工期、预算和 40 天完工条件。
这一页把 、、 翻译成代码。先用第18页的例子把所有数据补齐:最小化 ,要求两项非负、总和为1。
import numpy as np
import cvxpy as cp
n = 2
P = 2*np.eye(n)
q = np.zeros(n)
G = -np.eye(n)
h = np.zeros(n)
A = np.array([[1., 1.]])
b = np.array([1.])
x = cp.Variable(n)
objective = cp.Minimize(0.5*cp.quad_form(x, P) + q.T @ x)
constraints = [G @ x <= h, A @ x == b]
prob = cp.Problem(objective, constraints)
prob.solve()
print(x.value)
print(prob.value)
P=2I,所以二次项为 。q=0 表示没有额外一次项。G=-I,h=0 表示 ,也就是 。G是 ,h长度为2。A=[[1,1]],b=[1] 表示 。A是 ,b长度为1。cp.Variable(n) 建立长度为2的待求变量;quad_form(x,P) 表达 ,@ 是矩阵乘法。Problem 把目标和约束放在一起,solve() 求解。x.value 是解向量,prob.value 是一个目标值,二者不同。输出应接近 、目标值0.5。先核对两项非负、和为1,再核对 。
课件的 objective 行末多了一个逗号,实际输入时删掉。否则 Python 会把目标变成元组。这里的P半正定,目标是凸的。
从可行点 出发,在它附近用一阶近似表示目标:
例如 ,当前梯度为 。要最小化 ,就把总量全放在第二个变量,得到 。
原页子问题的约束应写为 ,而不是 ,因为现在真正正在选择的变量是 。
解出近似问题,不等于可以直接跳过去。用 、 算一次:在 ,导数为−2,线性近似是 ,它在区间内的最小点为 。若直接跳到1,下一轮导数变成2,线性近似的最小点又是−1。两端来回跳,原目标一直是1,而真正最优点0的目标是0。
所以 LP 解主要告诉我们往哪边走;还要决定走多远。这就是下一页采用 的原因。
课件给出两种策略:
from scipy.optimize import minimize_scalar
result = minimize_scalar(lambda alpha: f(x + alpha*d),
bounds=(0, 1), method='bounded')
alpha = result.x
x = x + alpha*d
递减步长不一定让每一轮目标或 gap 都单调下降;精确线搜索会在当前线段上选较好的位置,但每轮要多算几次目标。比较时应使用相同起点和同一个停止指标,并把总耗时也记下来。
为什么固定0.01还可能振荡?Frank–Wolfe乘步长的是“当前点到所选顶点”的向量d。接近均衡时,顶点仍可能很远;若每次还按固定比例走,实际位移未必缩到零。课堂把0.01改成0.001后,gap仍会先下降,再进入平台或波动。
递减也不是越快越好。 从1/2、1/3逐渐缩小;若改成 ,后面的步子很快接近零,剩下的总移动量可能不够。在同一交通例子中,从均分起点跑10000轮,平方分母的版本仍约为 ,gap约32.22,离均衡还很远。
这与普通梯度下降的固定学习率要区分:梯度下降的实际位移是“学习率×梯度”;梯度变小时,固定学习率也能产生越来越小的位移。
先把成本积分,得到交通势函数:
以第 2 路为例,。第 1、3 路只换掉常数。对第i项求导,得到 。因此梯度的三个分量,恰好是当前三条路线的耗时。原页展开式的三次项系数应全部为1/3,老师代码使用的也是这个积分结果。
当前流量 一旦固定, 就是三个固定数字。子问题为:
用课堂的示意系数20、25、15算:目标 。取 就达到150,所以全部放在第三条路最好。20、25、15只是演示线性子问题的数字;实际每轮使用当前成本计算出的系数。
代码于是只需先建零向量,再执行 y[np.argmin(c)] = 10。若最低成本并列,任选一条最低成本路线,也能得到一个最优顶点解。
把子问题中的全部需求分给当前最快路线,叫全有全无分配。真正更新为 :保留一部分旧流量,只让一部分向最快路线调整。可行域中的连续分流,由这些顶点分配的组合逐渐形成。
势函数用来刻画均衡,通常不等于总出行时间 。
图里比较递减步长与精确线搜索。横轴为迭代次数,纵轴为Frank–Wolfe gap,使用对数刻度。
比较时还要算每轮花多少工作。递减步长只算一次 ;精确线搜索还要多次计算目标,解一个一维问题。因此外层迭代数差不多时,线搜索可能花更多CPU时间。
这也解释本方法的取舍:每轮LP有时很便宜,特别是本例只需找最小成本的路线;但便宜的一轮可能要重复很多次。应同时看gap、迭代次数和总运行时间。
另附的 三种步长练习程序 会从同一个起点分别重跑递减、线搜索、回溯三种策略,便于公平比较。
投影写成
平方距离等于 ,对 是凸二次函数,所以当 由线性限制构成时,投影就是凸 QP。
PGD 每轮解的是“最近点”子问题;Frank–Wolfe 每轮解的是“线性目标最低点”子问题。二者都利用可行域结构,但目标和结果不同。
课堂实现把梯度步得到的点叫y,再建立一个新的决策变量z来做投影。z与y长度相同;cp.sum_squares(z-y) 就是距离平方。最小化距离和最小化距离平方,选出的最近点相同,因为平方在非负距离上保持大小顺序。
这一步的目标很简单,即使原来的f含指数或其他复杂非线性,投影仍只处理“离y最近”这个二次目标。代价是每轮需要一个QP,而Frank–Wolfe每轮需要一个LP。
把目标写成 。对总量约束 用乘子 ,对各个 用乘子 。第 i 个驻点式为 。
若 ,互补条件给 ,于是 。若 ,驻点式给 ,所以 。合并两种情况就是 ,最后用总量确定 。
仍用 ,所以梯度为 。下面完整算一次梯度步和CVXPY投影:
import numpy as np
import cvxpy as cp
x = np.array([10., 0., 0.])
alpha = 0.05
c = np.array([4., 25., 50.]) + x**2
y = x - alpha*c
z = cp.Variable(3)
projection = cp.Problem(
cp.Minimize(cp.sum_squares(z-y)),
[z >= 0, cp.sum(z) == 10]
)
projection.solve()
x = z.value
print(x)
x 是当前可行流量;先取 ,三项非负且和为10。c 为当前梯度,算得 。y=x-alpha*c 得到 ,它还不是合法流量。z=cp.Variable(3) 是待求的投影流量。非负限制和总量限制必须同时写。sum_squares 把三个坐标差分别平方后相加;求解器寻找满足约束、且这个和最小的z。z.value 读取解向量,结果约 。重新赋给x,下一轮再算新的c。不能只把y的负数裁成零,那会得到 ,总流量只剩4.8。投影要同时保住非负与总量10。
重复这个更新,流量会接近 。原页展开势函数沿用了第33页的系数笔误,计算时使用正确积分式。
打开可运行的三种步长程序:它从均分起点分别跑0.005、0.05、0.5,每轮都解上述投影QP,并把比较图保存到“运行结果”。
图中比较步长 0.005、0.05、0.5。横轴为迭代次数,纵向为对数刻度;原图未标纵轴指标名,这里主要比较下降速度与振荡。蓝线对应 0.005,缓慢改善;橙线对应 0.05,约 50 次降到很小;绿线对应 0.5,持续振荡。
过大步长为何会振荡,可以从交通例子直接算出:
投影保证每轮满足约束,但不自动保证每轮接近最优。选好步长依旧重要。由于最优点在边界,正确停止信号可用 ,而不能要求原目标梯度本身趋于零。
复现结果:另附程序从相同均分流量出发,各更新100次,并统一用Frank–Wolfe gap衡量约束最优性:
| 固定步长 | 100次后的流量 | gap |
|---|---|---|
| 0.005 | 约(6.048316,3.951684,0) | 约0.13309 |
| 0.05 | 约(6.05,3.95,0) | 约 |
| 0.5 | 在(10,0,0)与(0,10,0)之间振荡 | 约790与1210交替 |
这张 复现图 的纵轴明确标成gap,便于与Frank–Wolfe比较。步长0.05接近解后,投影后的实际位移会趋近零;固定步长本身并不意味着每次移动同样远。
在当前点 附近,用位移 表示候选新点。课件的演示子问题应写为:
原页二阶项缺少 ,按泰勒展开应补上。这里演示使用目标 Hessian;标准 SQP 通常使用拉格朗日函数 Hessian 或其近似,把约束曲率也计入,并配合步长控制。
把本讲三种近似连起来:Frank–Wolfe用一次目标近似、保留原线性约束;SQP用二次目标近似、一次约束近似。每轮移动到新点后,近似都要重新计算,不能把第一轮的近似一直用到底。
对代码采用的四次目标,有
三条约束梯度分别为 、、。每轮代码依次做以下工作:
0.5*d.T @ H @ d + grad @ d。这里变量是 d,不是原参数 x。-g_i-grad_gi @ d >= 0。x = x + d。位移很小时停止,是本页的简化判断。例如从 开始,目标梯度和 Hessian 都为零,三条线性化限制为 、、。此时首个二次模型退化为常数目标,所以实用算法还需更完整的曲率与步长处理。
取 ,目标梯度为 ,Hessian为 ,三个约束值为 。于是这一轮QP为:
该QP最优点的前两条约束取等号。解 、,得 。第三条有余量,所以 。把 代入 QP 的目标梯度,得 。 加上约束梯度 并令和为零, 得 。 用 消去,得到 。两个乘子非负,驻点和互补都成立,因此该可行位移就是凸 QP 的最优解。
更新得到 。把它代回原始约束,前两项均为 。它满足的是线性化约束,暂时没有满足原弯曲约束。
上一页已经给出一个具体原因:满足近似约束,不等于满足原约束。从 出发,第一轮得到 ,前两条原始约束违反量都是 。
这两轮说明“每轮重建局部模型”的作用。其他非线性问题中,还可能遇到奇异或不定Hessian、不可行子问题、全步过大等情况,实用SQP会加入曲率处理和步长接受准则,兼顾目标与约束违反程度。
二阶目标的系数仍应为 。本页打印式漏了1/2,代码中的0.5是正确的。
最后介绍 SLSQP,即 Sequential Least Squares Programming。使用 SciPy 时可以显式选择这个方法:
from scipy.optimize import minimize
def f(x):
return x[0]**4 + x[1]**4
def g1(x):
return x[0]**2 - x[0] + 1 - x[1]
def g2(x):
return x[0]**2 - 4*x[0] + 6 - x[1]
def g3(x):
return x[0]**2 - 3*x[0] + x[1] - 2
cons = [{'type': 'ineq', 'fun': lambda x: -g1(x)},
{'type': 'ineq', 'fun': lambda x: -g2(x)},
{'type': 'ineq', 'fun': lambda x: -g3(x)}]
res = minimize(f, x0=[1.5, 2.5], method='SLSQP',
constraints=cons,
options={'ftol': 1e-10, 'maxiter': 1000})
print(res.success, res.message)
print(res.x, res.fun)
print([g1(res.x), g2(res.x), g3(res.x)])
ftol 控制求解精度,maxiter 限制最大迭代轮数。本讲的方法选择现在可以连起来:LP/QP 先利用专门结构;线性可行域上可用 Frank–Wolfe 或 PGD;一般光滑非线性约束可考虑 SQP/SLSQP。选择以后,仍要把目标、变量顺序和约束方向写正确。
课堂演示约五轮得到 ,对应的是代码采用的 目标。这里的重点是复杂模型 → 局部简单子问题 → 更新 → 重新近似这条设计思路;SciPy的SLSQP负责更完整的数值实现。