约束优化、拉格朗日乘子与对偶性

给训练损失、资源预算或调度目标加上约束，会改变优化问题。边界极小点的普通梯度可以非零；乘子只有与正确符号、可行性及定理假设一起使用才有意义。本课构造完整证书，推导投影和对偶界，说明驻点报告或有限罚项为何不自动解出约束问题。

检索检查： 模块 19 提供凸支持不等式、曲率界与梯度下降；模块 18 提供梯度和Jacobian维数。实验使用NumPy，仅需CPU。全课把不等式写成g_i(x)≤0，并采用拉格朗日项+λ_i g_i(x)的符号约定。

将问题写成：在x∈D、g_i(x)≤0、h_j(x)=0下极小化f(x)。满足全部限制的点组成可行集C；D是目标和约束共同有定义的域。不可行点的目标再小，也不能作为原始问题的解。可行集可能为空、不连通、无界，或是低维曲面；这些性质影响存在性及算法。连续目标在非空紧可行集上取得极小值；在无界集合上，仅闭性不保证取得。

若g_i(x)=0，则该不等式在x处活跃；g_i(x)<0则不活跃。等式始终必须满足，并非由求解器选择“开启”。盒约束0≤x_i≤1写成−x_i≤0和x_i−1≤0，梯度分别为−e_i、+e_i。改变限制方向却不改变乘子约定，会改变驻点方程。冗余表达可给出相同C，却产生不同乃至不唯一的乘子表示。

可行方向描述局部几何。在光滑边界g_i(x)=0处，一条可微可行曲线的速度d必须满足∇g_i(x)ᵀd≤0；等式曲线要求∇h_j(x)ᵀd=0。这是必要线性化检查，并不总能由此构造真实曲线。曲率或奇异约束可能排除通过线性化的方向。例如x²=0在零点的线性化为零，可行集却仅有零点。第2节解释缺少的正则性。

对非空闭凸C⊂Rⁿ，欧氏投影P_C(v)是极小化‖p−v‖²/2的唯一p∈C。存在性：取一个可行点，以v为中心截取足够大的闭球；球外点的距离不可能优于该可行点，而球内闭交集紧，故取得极小。唯一性来自平方距离严格凸：若两个不同点都最优，其中点将更近。非凸C的最近点可能不唯一，选择规则需另写，也不能沿用本课的凸投影结论。

投影的变分刻画为：p=P_C(v)当且仅当对所有z∈C，有(v−p)ᵀ(z−p)≤0。必要性是在可行线段p+t(z−p)上对平方距离求t=0的右导数。充分性展开‖z−v‖²=‖p−v‖²+‖z−p‖²−2(v−p)ᵀ(z−p)，后两项非负。这是全局最近点证明，并非有限采样比较。对v,w的两个投影不等式相加，得到‖P_C(v)−P_C(w)‖²≤(v−w)ᵀ(P_C(v)−P_C(w))；由Cauchy–Schwarz可知投影不扩张。

盒的目标按坐标分离，因此标量裁剪恰好给出投影。单纯形的公共阈值则耦合坐标。把v降序排列为u₁≥…≥u_n，定义θ_j=(Σ_{i≤j}u_i−1)/j，令ρ为满足u_ρ>θ_ρ的最大下标。取θ=θ_ρ及x_i=max(v_i−θ,0)。选出的正坐标和为1，其余不超过阈值；第3节的KKT证书将证明最优。至少首下标合格，因为u₁>u₁−1。排序代价O(n log n)，投影也有计算成本。

等式h:Rⁿ→Rᵐ的Jacobian J_h有m行，每行为一个约束梯度的转置。若可行点的等式梯度线性独立，则J_h满行秩m，切空间为N(J_h)。可微约束局部极小点沿所有切向的一阶目标变化为零，因此∇f属于N(J_h)⊥=C(J_hᵀ)，存在ν∈Rᵐ使∇f+J_hᵀν=0。等式拉格朗日函数L(x,ν)=f(x)+νᵀh(x)的x梯度正是这个驻点方程。

从切向量到实际附近可行曲线，需要正则水平集定理，它是隐函数定理的推论。本课明确陈述该正则性结果；仅凭线性代数不能在奇异点证明任意零空间向量都描述真实曲面。这就是满行秩属于必要性假设的原因。等式乘子不限制正负，因为等式没有单侧内部或不等式方向。乘子依附于所写方程，缩放方程会反向缩放乘子。

一般二次f=(1/2)xᵀQx+cᵀx、等式Ax=b、Q对称时，驻点和可行性组成Qx+Aᵀν=−c、Ax=b。块矩阵为[[Q,Aᵀ],[A,0]]，常称鞍点系统。若Q正定且A行独立，矩阵可逆：齐次解满足Qd+Aᵀw=0、Ad=0，左乘dᵀ得dᵀQd=0，因此d=0；再由Aᵀw=0及行独立得w=0。应求解该系统，而不是显式构造逆矩阵。

全空间正定是充分条件，却强于实际需求。原始唯一性只需保持Ax=b的非零方向d∈N(A)上有dᵀQd>0，此时目标沿仿射可行空间严格凸。A行独立时，同一证明在N(A)上也使块系统可逆。法向曲率可以为负而不破坏这个约束极小值。一般非线性约束还通过拉格朗日Hessian引入曲率，所以在弯曲曲面上仅检查∇²f可能不足。

正则性下，驻点是必要候选条件，并非无条件极小证书。在圆x²+y²=1上极小化x²+y²，每个可行点的值相同，也都可配乘子满足驻点。在同一圆上极小化x，驻点则产生(−1,0)与(1,0)，分别是极小和极大。必须比较值、使用合适二阶条件，或在适用时给凸全局证书。圆等式非线性，可行集也非凸。

若存在适当可微最优解分支和值函数，乘子可衡量敏感性。将限制写成h(x)−b=0时，V对b的导数是−ν而非+ν。直线例中V′(b)=b/2=−ν：对f(x(b))求导，用驻点方程及J_h x*′=1即可。切换、退化或不可微值函数处，唯一普通导数可能不存在。没有检查这些条件及扰动约定，不能把乘子解释为适用于任意有限变化的固定价格。

对可微f,g_i,h_j，令L=f+Σλ_i g_i+Σν_j h_j。Karush–Kuhn–Tucker条件分四项：原始可行g_i≤0、h_j=0；对偶可行λ_i≥0；互补λ_i g_i=0；驻点∇f+Σλ_i∇g_i+Σν_j∇h_j=0。各项作用独立。互补仅允许活跃不等式有正乘子，但也允许活跃约束的乘子为零。不等式符号依附于g≤0约定，等式ν仍无限制。

光滑问题的局部极小点在适当约束资格下存在KKT乘子。一个充分资格是等式梯度与所有活跃不等式梯度在该点线性独立，简称LICQ。它排除活跃梯度冗余和奇异表示。本课陈述带资格必要性定理，而不以未证明的方向推理代替。其他资格可能更弱，因此LICQ失败不等于不存在乘子；反之，无资格最优点确实可能没有乘子，如奇异等式例。

凸KKT给全局充分证书：f及g_i在共同凸域可微凸，h=Ax−b仿射。在可行KKT点x，固定λ,ν后的L因λ≥0而凸。驻点和凸支持不等式给L(x)≥L(x*)=f(x*)；对任意可行x，又有L(x)≤f(x)。合并即f(x)≥f(x*)。这项充分性不需要约束资格；资格用于断言最优点必能产生这样的证书。

单纯形投影取g_i=−x_i、h=Σx_i−1，驻点为x_i−v_i+θ−λ_i=0。给x_i=max(v_i−θ,0)，选λ_i=max(θ−v_i,0)，符号和互补均成立。v=(1.2,.4,−.2)时x*=(.9,.1,0)、θ=.3、λ=(0,0,.5)。平方距离强凸、单纯形凸，所以证书证明唯一全局投影，也解释公共阈值为何不是任意归一化技巧。

资源分配常用预算Σx_i≤B及非负性。在a=(3,1)、B=2下极小化Σ(x_i−a_i)²/2，解为x=(2,0)，预算乘子1，两个下界乘子均零。驻点x−a+λ_B(1,1)−λ_lower=0；第二坐标下界活跃却零价格。本例B=2的值导数为−λ_B=−1，表示放宽上预算降低损失；越过该值时活跃集会改变。

非凸时KKT点可能是极大或鞍点。在−1≤x≤1上极小化−x²，x=0与两个零乘子满足KKT，但全局极小值−1在端点取得。零点没有活跃不等式，资格并无问题；充分性仍失败，因为目标不凸。必要性正则条件不能补出缺少的目标凸性。数值残差表应说明正在使用哪个定理，不能将每个小驻点数值都称为“全局最优”。

固定λ≥0和任意ν，对偶函数q(λ,ν)=inf_{x∈D}L(x,λ,ν)在整个共同域取下确界，不再次施加原始约束。若保留这些限制，通常算出另一对象。对偶值可能为−∞；只在方便的x处求L得到的是该下确界的上界，而非自动获得原始最优的下界。解析求q时，必须验证真实极小化，或控制正确方向的误差。

弱对偶可直接证明：任意原始可行x满足λ_i g_i(x)≤0、νᵀh(x)=0，所以q≤L(x)≤f(x)，进而q≤原始下确界p。这甚至适用于非凸目标与约束；关键是乘子符号、可行性和真正的域下确界。对偶问题在λ≥0、ν任意下最大化q，最优上确界d≤p*。两最优值相等称强对偶，需要超出这个基本界的理由。

即使原始问题非凸，对偶函数对乘子仍凹。固定x时L对乘子仿射；两个乘子向量的加权L至少等于两个对应下确界的相同加权和，再对x取下确界仍保留该下界。因此q在混合乘子处大于等于q的加权和，即凹不等式。−∞扩展值需谨慎处理，却不会使任意非凸问题变容易，也不会消除对偶间隙。

单纯形平方距离问题的等式乘子θ、下界向量λ≥0给L的Rⁿ极小点x=a−θ1+λ，及q=θ(Σa_i−1)−λᵀa−‖θ1−λ‖²/2。θ=.3、λ=(0,0,.5)时q=.11，匹配f(.9,.1,0)。最优证书的L极小点恰好可行，但推导q时并未施加原始可行性。其他乘子下L极小点可以违反单纯形，这是允许的。

可行候选x和有效对偶界q给0≤f(x)−p*≤f(x)−q，因此可计算原始对偶间隙提供目标精度证书，即使未知原始优化器。前提是q真的为下界，x真的可行。不可行候选可出现f(x)<q，却不违反弱对偶，因为定理从未比较不可行值。负不等式乘子也破坏下界符号论证。应同时报告可行残差、对偶界有效性与候选差。

近似q若偏高，就不能安全作为下界。内层求解器返回L(x_trial,λ,ν)≥q，不能直接拿它代替q认证间隙。若已证明L_trial−q≤ε，则L_trial−ε才是有效下界。小二次可配方并在适当误差分析下求解；大系统的近似轨迹可以有用，却只有控制了误差方向才成为严格界。

标准有限维凸问题中，f,g_i在Rⁿ凸且有限值，等式Ax=b仿射。一个有用的Slater充分条件是存在x̄满足Ax̄=b及所有g_i(x̄)<0。原始最优值有限时，该条件给强对偶及取得的对偶最优。本课陈述带假设的Slater定理，而不把它误当投影或梯度下降的直接推论；完整证明使用分离超平面。原始阅读给出该定理，前面的弱对偶和凸KKT充分性证明则独立成立。

若函数限制在凸域，对应版本使用共同域相对内部中的可行点，而不是强求整个环境空间内部。相对内部指在仿射包内的内部。单纯形在环境空间内部为空，但在和为1的超平面内相对内部非空，需明确域和定理版本。某些仿射不等式可用更弱的精细Slater版本；本课有限值严格版本已足够。充分条件不能改写成无条件等价。

强对偶比较下确界与上确界，不单独保证原始最优取得，也不保证乘子唯一。例如在R上极小化exp(x)，无约束的原始下确界与对偶值均为零，却无有限x取得零。若原始与对偶都取得且值相等，q≤L≤f链迫使互补及全局L极小。在可微问题及对应域假设下，再得驻点KKT。原始取得仍是需独立证明的事实。

Slater失败不能断定正间隙。在x=0及x≤0下极小化x²，没有严格不等式点能满足等式，却有p*=0及零乘子给q=0，仍强对偶。等式与不等式部分冗余。这区分可行集几何与具体代数表示，也说明简单条件失败时，其他约束资格或精细定理可能仍适用。

再看在x²≤0下极小化x。唯一可行点零，p*=0，无严格可行点。λ>0时q=inf_x(x+λx²)=−1/(4λ)，λ=0时为−∞。λ→∞时上确界为零，因此最优值意义上强对偶，但无有限乘子取得。KKT在x=0要求1+2λx=0，不可能。该例分开零间隙、对偶取得及乘子必要性，不能把三者合并成一个标签。

反过来，严格可行不能替代凸性。−1≤x≤1下极小化−x²，零点满足两个仿射不等式严格可行；然而R上的L始终保留负二次最高项，因此每个λ≥0均有q=−∞，d*=−∞而p*=−1。凸Slater不适用，因为目标凹。内部可行点与KKT驻点不能使问题变凸。实验3正是诊断这种无效推断。

对偶乘子有带资格的扰动解释。将限制写成g_i(x)≤u_i、h(x)=v。若原问题最优原始与对偶值匹配，其最优对偶对给V(u,v)≥V(0,0)−λᵀu−νᵀv：用该乘子求平移后的对偶下界即可。这是值函数的支持界；V可微时导数为对应负乘子，否则多个对偶最优可给不同支持斜率。正上预算乘子描述指定单位下放宽预算的局部价值，并非任何有限扰动的固定价格。

对非空闭凸C和可微f，投影梯度为x⁺=P_C(x−α∇f(x))，从可行x开始，α>0。精确投影使所有迭代可行。对投影变分式取z=x，得∇f(x)ᵀd≤−‖d‖²/α，d=x⁺−x。结合L-Lipschitz梯度下降引理，得f(x⁺)≤f(x)−(1/α−L/2)‖d‖²。因此在可行线段上光滑界成立时，0<α<2/L对非零投影移动给严格下降。它论证的是可行更新，不是未投影提案。

定义G_α(x)=(x−P_C(x−α∇f(x)))/α。由投影刻画，其为零当且仅当对所有z∈C有∇f(x)ᵀ(z−x)≥0。f凸时支持不等式给全局极小证书。边界普通梯度仍可非零。映射依赖α及投影度量，小计算映射要转成距离保证还需适当误差界。舍入或不准投影造成零结果，并不等于精确数学不动点。

凸f、α≤1/L时，用极小点x比较。x处凸支持及x⁺处光滑上界给f(x⁺)−f(x)≤∇f(x)ᵀ(x⁺−x*)+(L/2)‖d‖²。投影不等式把首项界为(x−x⁺)ᵀ(x⁺−x*)/α。展开内积，丢弃非正项−(1/α−L)‖d‖²/2，得到望远镜界f(x⁺)−f(x*)≤(‖x−x*‖²−‖x⁺−x*‖²)/(2α)。求和及目标单调给f(x_k)−f(x*)≤‖x₀−x*‖²/(2αk)。取得的x*、凸性、精确投影与固定步长须随速率一起声明。

罚函数方法改变目标。等式h=0的平方罚项f+(ρ/2)‖h‖²抑制违反，但有限ρ通常仍留残差。在x=0下极小化(x−2)²/2，原解为零，罚目标极小点却是2/(1+ρ)>0。ρ增大时约束梯度贡献趋近所需等式乘子，但点依旧不可行。大ρ还可能恶化曲率条件。因此精确投影与有限光滑罚项求解不同的中间问题。

某些非光滑罚项在适当假设及足够大权重下可精确。本标量例的(x−2)²/2+ρ|x|在ρ≥2时以零为极小点，因为零处左导−2−ρ≤0、右导−2+ρ≥0，且目标凸。这一示例不意味着有限平方罚项普遍精确，也不消除非光滑最优性处理。使f无定义的域违反仍必须阻止；罚项不能计算非法输入的对数。

完整QP流程为：明确Q,c,C，检查凸性和可行性，能解析时先推候选，再运行具有步长及投影契约的方法，最后检查原始和对偶量。实验3故意提供通过驻点但不可行的点，以及使对偶下界失效的负乘子。容差应以各方程单位声明；约束缩放会改变原始残差及乘子。求解器停止、数学可行和目标精度证书是不同结论。

探索器用二维单纯形x+y=1、x,y≥0，目标为到a=(a₁,a₂)的半平方距离。精确投影x=clip((a₁−a₂+1)/2,0,1)、y=1−x。移动a跨越活跃集切换，再选择不可行候选或负乘子错误。驻点与对偶表达式均按该候选重算；小驻点残差或候选差不能跳过可行性与符号检查。

这些基础支持资源分配、约束学习及后续支持向量形式。应用可能加入非光滑损失、大规模稀疏系统或噪声梯度，需要自己的方法契约。本课成果是完整小凸证书及有理据的可行算法，并明确非凸KKT、资格失败和有限罚项为何不能自动继承同样结论。

实验1 · 盒与单纯形投影

下载 lab1_box_and_simplex.py

"""Euclidean projections with feasibility and variational checks; NumPy only."""
import numpy as np


def simplex_projection(v):
    v = np.asarray(v, dtype=float)
    if v.ndim != 1 or len(v) == 0 or not np.all(np.isfinite(v)):
        raise ValueError("a nonempty finite vector is required")
    ordered = np.sort(v)[::-1]
    thresholds = (np.cumsum(ordered) - 1.0) / np.arange(1, len(v) + 1)
    eligible = np.flatnonzero(ordered - thresholds > 0)
    theta = thresholds[eligible[-1]]
    return np.maximum(v - theta, 0.0), theta


if __name__ == "__main__":
    np.set_printoptions(precision=8, suppress=True)
    v = np.array([1.2, 0.4, -0.2])
    lower, upper = np.zeros(3), np.ones(3)
    box = np.clip(v, lower, upper)
    simplex, theta = simplex_projection(v)
    clip_then_normalise = box / box.sum()
    print("input:", v)
    print("box projection:", box)
    print("simplex projection:", simplex, "threshold:", f"{theta:.8f}")
    print("clip then normalise:", clip_then_normalise)
    print("squared distances: projection=%.8f shortcut=%.8f" % (
        np.sum((simplex-v)**2), np.sum((clip_then_normalise-v)**2)))
    assert np.all(simplex >= 0) and abs(simplex.sum()-1) < 1e-12
    assert np.sum((simplex-v)**2) < np.sum((clip_then_normalise-v)**2)
    vertices = np.eye(3)
    variational = (vertices-simplex) @ (v-simplex)
    print("(v-projection) dot (vertex-projection):", variational)
    assert np.max(variational) < 1e-12
    for vector in [np.array([-3., -2., -1.]), np.zeros(3), np.array([2., 2., 2.])]:
        p, t = simplex_projection(vector)
        print("input", vector, "->", p, "threshold", f"{t:.8f}")
        assert np.all(p >= 0) and abs(p.sum()-1) < 1e-12
    print("PASS: feasible nearest points; normalisation shortcut is not projection")

input: [ 1.2  0.4 -0.2]
box projection: [1.  0.4 0. ]
simplex projection: [0.9 0.1 0. ] threshold: 0.30000000
clip then normalise: [0.71428571 0.28571429 0.        ]
squared distances: projection=0.22000000 shortcut=0.28897959
(v-projection) dot (vertex-projection): [ 0.   0.  -0.5]
input [-3. -2. -1.] -> [0. 0. 1.] threshold -2.00000000
input [0. 0. 0.] -> [0.33333333 0.33333333 0.33333333] threshold -0.33333333
input [2. 2. 2.] -> [0.33333333 0.33333333 0.33333333] threshold 1.66666667
PASS: feasible nearest points; normalisation shortcut is not projection

运行前推两个最近点及阈值，比较归一化捷径的平方距离。在本有限单纯形检查全部顶点，就能借凸组合证明整个集合的变分不等式。

实验2 · 可行投影梯度下降

下载 lab2_projected_gradient.py

"""A convex simplex QP: feasible iterates and a projected-gradient residual."""
import numpy as np
from lab1_box_and_simplex import simplex_projection

if __name__ == "__main__":
    np.set_printoptions(precision=8, suppress=True)
    a = np.array([1.2, .4, -.2])
    target, _ = simplex_projection(a)
    x = np.ones(3) / 3
    eta = .5  # L=1; eta<=1/L supports the stated convex gap bound.
    objective = lambda z: .5 * np.sum((z-a)**2)
    previous = objective(x)
    print("analytic optimum:", target, "objective:", f"{objective(target):.8f}")
    for k in range(1, 31):
        proposed = x-eta*(x-a)
        updated, _ = simplex_projection(proposed)
        projected_residual = np.linalg.norm(x-updated) / eta
        assert np.min(updated) >= 0 and abs(updated.sum()-1) < 1e-12
        current = objective(updated)
        assert current <= previous+1e-14
        x, previous = updated, current
        if k in (1, 2, 5, 10, 30):
            print("k=%2d x=%s objective=%.10f step-mapping-norm=%.3e" % (
                k, x, current, projected_residual))
    at_optimum, _ = simplex_projection(target-eta*(target-a))
    print("ordinary gradient at optimum:", target-a)
    print("projected-gradient mapping at optimum:", (target-at_optimum)/eta)
    print("unconstrained update from optimum:", target-eta*(target-a))
    assert np.linalg.norm(x-target) < 1e-8
    assert np.linalg.norm(target-at_optimum) < 1e-12
    print("PASS: feasible descent; boundary optimum need not have zero ordinary gradient")

analytic optimum: [0.9 0.1 0. ] objective: 0.11000000
k= 1 x=[0.7 0.3 0. ] objective=0.1500000000 step-mapping-norm=9.933e-01
k= 2 x=[0.8 0.2 0. ] objective=0.1200000000 step-mapping-norm=2.828e-01
k= 5 x=[0.8875 0.1125 0.    ] objective=0.1101562500 step-mapping-norm=3.536e-02
k=10 x=[0.89960938 0.10039063 0.        ] objective=0.1100001526 step-mapping-norm=1.105e-03
k=30 x=[0.9 0.1 0. ] objective=0.1100000000 step-mapping-norm=1.054e-09
ordinary gradient at optimum: [-0.3 -0.3  0.2]
projected-gradient mapping at optimum: [ 0. -0.  0.]
unconstrained update from optimum: [ 1.05  0.25 -0.1 ]
PASS: feasible descent; boundary optimum need not have zero ordinary gradient

检查每个迭代总和、非负及目标下降，解释x*处普通梯度与投影映射的区别。更新前测得的残差属于该起始点，不属于新接受点。

实验3 · KKT 对偶及罚项错误

下载 lab3_kkt_and_dual_faults.py

"""Check all KKT residuals, a dual bound, and qualifications; NumPy only."""
import numpy as np

a = np.array([1.2, .4, -.2])


def report(label, x, lam, nu):
    gradient = x-a
    stationarity = gradient + lam - nu
    equality = abs(x.sum()-1)
    inequality = max(0.0, -float(x.min()))
    dual_feasibility = max(0.0, -float(nu.min()))
    complementarity = np.max(np.abs(nu*x))
    f = .5*np.sum((x-a)**2)
    q = lam*(a.sum()-1)-nu@a-.5*np.sum((lam-nu)**2)
    print(label)
    print("  residuals: equality=%.3e inequality=%.3e dual=%.3e stationarity=%.3e complementarity=%.3e" % (
        equality, inequality, dual_feasibility, np.linalg.norm(stationarity), complementarity))
    print("  objective=%.8f dual=%.8f candidate difference=%.8f" % (f, q, f-q))
    valid_dual = dual_feasibility == 0
    feasible = equality < 1e-12 and inequality == 0
    print("  dual bound valid:", valid_dual, "candidate feasible:", feasible)
    return feasible and valid_dual and max(np.linalg.norm(stationarity), complementarity) < 1e-12


if __name__ == "__main__":
    np.set_printoptions(precision=8, suppress=True)
    assert report("correct certificate", np.array([.9, .1, 0]), .3, np.array([0., 0., .5]))
    assert not report("infeasible despite matching stationarity", np.array([1., .2, 0]), .2, np.array([0., 0., .4]))
    assert not report("negative lower-bound multiplier", np.array([.9, .1, 0]), .3, np.array([0., 0., -.5]))
    print("qualification failure: minimise x subject to x^2=0")
    print("  only feasible x=0; constraint gradient=0; stationarity 1+lambda*0 cannot vanish")
    print("  q(lambda)=-1/(4*lambda) for lambda>0; supremum 0, never attained")
    for lam in (1., 10., 100.):
        print("  lambda=%.0f dual bound=%.8f" % (lam, -1/(4*lam)))
    print("nonconvex KKT false certificate: minimise -x^2 subject to -1<=x<=1")
    print("  x=0, multipliers=0 pass KKT; f=0, but x=1 gives f=-1")
    print("  on R, every Lagrangian remains a downward quadratic: dual value=-infinity")
    for rho in (1., 10., 100.):
        # f=.5*(x-2)^2, equality x=0; squared penalty rho*x^2/2.
        x = 2/(1+rho)
        print("squared penalty rho=%.0f minimiser=%.8f equality violation=%.8f" % (rho, x, abs(x)))
        assert x > 0
    print("PASS: stationarity alone fails; qualification, convexity and feasibility matter")

correct certificate
  residuals: equality=0.000e+00 inequality=0.000e+00 dual=0.000e+00 stationarity=7.850e-17 complementarity=0.000e+00
  objective=0.11000000 dual=0.11000000 candidate difference=-0.00000000
  dual bound valid: True candidate feasible: True
infeasible despite matching stationarity
  residuals: equality=2.000e-01 inequality=0.000e+00 dual=0.000e+00 stationarity=5.551e-17 complementarity=0.000e+00
  objective=0.06000000 dual=0.10000000 candidate difference=-0.04000000
  dual bound valid: True candidate feasible: False
negative lower-bound multiplier
  residuals: equality=0.000e+00 inequality=0.000e+00 dual=5.000e-01 stationarity=1.000e+00 complementarity=0.000e+00
  objective=0.11000000 dual=-0.39000000 candidate difference=0.50000000
  dual bound valid: False candidate feasible: True
qualification failure: minimise x subject to x^2=0
  only feasible x=0; constraint gradient=0; stationarity 1+lambda*0 cannot vanish
  q(lambda)=-1/(4*lambda) for lambda>0; supremum 0, never attained
  lambda=1 dual bound=-0.25000000
  lambda=10 dual bound=-0.02500000
  lambda=100 dual bound=-0.00250000
nonconvex KKT false certificate: minimise -x^2 subject to -1<=x<=1
  x=0, multipliers=0 pass KKT; f=0, but x=1 gives f=-1
  on R, every Lagrangian remains a downward quadratic: dual value=-infinity
squared penalty rho=1 minimiser=1.00000000 equality violation=1.00000000
squared penalty rho=10 minimiser=0.18181818 equality violation=0.18181818
squared penalty rho=100 minimiser=0.01980198 equality violation=0.01980198
PASS: stationarity alone fails; qualification, convexity and feasibility matter

报告所显示的五个残差量，包括分开的等式与不等式可行性。解释不可行候选为何低于有效对偶界、负乘子为何失效，以及资格和凸定理错误。下载实验2时请把其导入的投影脚本也保存在同一目录。

练习1–12必做，选做13–14在十二小时核心安排外增加35分钟。

阅读作者的Convex Optimization配套页中对偶与约束极小化章节。把带资格Slater读成有假设的定理，再比较本课直接弱对偶及凸KKT证明。

明确可行集、推投影、解一个直线约束二次，按g≤0写完整KKT。证明弱对偶及凸KKT充分性，准确识别Slater何时提供额外定理。

结业任务： 完成单纯形QP证书，推一次投影步及下降系数，诊断奇异资格和非凸驻点例，不混淆间隙、取得与可行性。

可以继续： 你能把约束算法连接到可行几何和证书。接下来概率建立明确模型、条件与不确定性，而不把未说明的数值频率当作数学事实。见课程总览。