二次规划

二次规划（quadratic programming，QP）在仿射等式、不等式约束下优化二次目标。二次型的曲率决定它是否为凸问题；目标含平方并不自动意味着凸。以下先用一个带资源边界的距离最小化，把可行域、曲率和最优性证书连接起来。

距离最近的可行点

考虑 $min F (x, y) = (x - 2)^{2} + (y - 1)^{2}$ ，要求 $x, y \geq 0, x + y \leq 2$ 。无约束最小点 $(2, 1)$ 超出资源边界。沿边界令 $y = 2 - x$ ，得到 $F = (x - 2)^{2} + (1 - x)^{2} = 2 (x - 3 / 2)^{2} + 1 / 2$ 。候选为 $z = (3 / 2, 1 / 2)$ ，目标值为二分之一。

三角可行域内距目标点最近的候选 — 目标点不可行，最优投影在资源边界上；最优性仍由正文展开式证明。

边界上的计算还不足以排除内部其他点。对任意可行 $u = (x, y)$ ，把平方在z处展开： $F (u) - F (z) = ‖ u - z ‖^{2} + \nabla F (z)^{𝖳} (u - z) = ‖ u - z ‖^{2} + 2 - x - y \geq 0.$ 使用了 $\nabla F (z) = (- 1, - 1)$ 和可行性 $x + y \leq 2$ ，所以z确为全局最优；等号还迫使u=z，故唯一。这是可复查的最优性证明，而非依靠图上的最近外观。

标准形式与凸性

令 $x \in ℝ^{n}$ 为决策向量，数据 $Q \in ℝ^{n \times n}$ 实对称、 $c \in ℝ^{n}$ ，QP可写为 $min \frac{1}{2} x^{𝖳} Q x + c^{𝖳} x + r, G x \leq h, A x = b .$ 其中G、A的列数都是n，h、b分别匹配其行数。Hessian等于Q，因此目标凸当且仅当 $Q ⪰ 0$ ；沿任意方向d的二阶导数 $d^{𝖳} Q d$ 说明了两边的必要性和充分性。若原系数矩阵不对称，二次型只由对称部分 $(Q + Q^{𝖳}) / 2$ 决定，因为反对称部分的二次型恒为零。^[1]

可行集是闭凸多面体。若Q正定且可行集非空，目标随向量长度趋无穷而趋无穷，故在闭可行集上达到最小值；严格凸性又保证唯一。仅半正定不保证有界，例如 $min_{x \in ℝ} - x$ 就是Q为零的无界QP。Q不是半正定时问题仍称QP，但不能沿用凸性保证。

乘子给出的同一证书

对凸QP，若可行点z和乘子 $λ \geq 0, ν$ 满足 $Q z + c + G^{𝖳} λ + A^{𝖳} ν = 0, λ_{i} (G z - h)_{i} = 0,$ 则z全局最优。证明对任意可行u展开目标差，二次余项非负，等式乘子项为零；不等式部分为 $- λ^{𝖳} G (u - z) = λ^{𝖳} (h - G u) \geq 0$ ，其中用了互补条件。主例的资源约束乘子为一，非负约束乘子为零，恰好复现前面的证明。必要性需相应约束资格条件或多面体最优性理论，这里使用的是已验证条件的充分性。

资源边界上配方得到的二次函数 — 边界最小值为二分之一，在 x=3/2、y=1/2 处取得。

变式、非凸反例与直接计算

将资源上限改为一，边界投影得到 $(1, 0)$ ，目标值二；若上限增至三，无约束点 $(2, 1)$ 变为可行，目标零。资源约束虽活跃，乘子也可为零，不能把“在边界”与“乘子严格为正”画等号。

反例为区间 $[- 1, 1]$ 上最小化 $- x^{2}$ 。原点梯度为零，目标为零，但两个端点目标为负一；非凸QP的驻点未必最小。向目标加常数不改变最优点，平方项的正负和交叉项则可能改变曲率。

下例用三条边的线段投影以及可行的无约束点，精确求解本二维模型。若最近点在内部，它必为无约束最小点；否则位于某条边，投影到每条闭线段再比较即覆盖全部可能。函数输入非负资源上限，返回点、目标和候选，不改写输入，只用标准库。固定三边成本为常数；这种枚举不能代替一般高维QP求解器。

Python 3

def triangle_qp(limit=2.0):
    if limit < 0:
        raise ValueError("nonnegative resource limit required")
    target = (2.0,1.0)
    vertices = [(0.0,0.0),(float(limit),0.0),(0.0,float(limit))]
    candidates = vertices[:]
    if sum(target) <= limit:
        candidates.append(target)
    for a,b in zip(vertices,vertices[1:]+vertices[:1]):
        v = (b[0]-a[0],b[1]-a[1])
        norm2 = sum(w*w for w in v)
        if norm2 == 0:
            continue
        t = sum((target[j]-a[j])*v[j] for j in range(2))/norm2
        t = min(1.0,max(0.0,t))
        candidates.append(tuple(a[j]+t*v[j] for j in range(2)))
    value = lambda z:sum((z[j]-target[j])**2 for j in range(2))
    best = min(candidates,key=value)
    return best,value(best),candidates

for limit in (2,1,3,0):
    print(limit,triangle_qp(limit)[:2])
assert triangle_qp()[0] == (1.5,0.5)

参考文献

↑ Boyd and Vandenberghe, Convex Optimization，§4.4及§5.5.3。

[1] Boyd and Vandenberghe, Convex Optimization，§4.4及§5.5.3。

[1]