凸性、梯度方法与无约束优化

梯度给局部敏感性，优化器据此寻较小目标。是否下降、收敛、留在域内、达到全局极小，还需额外假设。本课证明凸与下降，精确分析二次特征模态，对照数值训练中可能出现的停止和牛顿失败。

检索检查：用模块13对称模态、正定二次型与模块18列梯度、Hessian、损失归约。下降证明只用模块16中值定理，无隐藏积分先修。实验用课程固定NumPy基线。

问题指定目标f、可行域D，最小化D内f。无约束常为全Rⁿ或对数正输入等自然开域，不表示允许域外评价。全局极小x须属于D且对所有可行x有f(x)≤f(x)。下确界是目标值最大下界，未必被任何点取得，逼近该界的算法不自动产生取得点。

(0,1)上f=x下确界零但无极小点，实线exp下确界零只在x→−∞逼近；小梯度或长轨迹不能修复。−x²全实域无有限下界。非空紧致域上连续目标由最值定理取得极小，域、有界、取得都是选择求解器前的数学性质。

局部极小只比较邻域内可行点，严格版对不同点严格不等。驻点是内部可导零梯度，只是候选；边界极小可梯度非零，折点极小可无经典梯度，下一模块系统处理约束。

乘正常数保留极小集合却缩放梯度H、步长和梯度容差解释；加常数保留导数极小却改目标数值。不同日志需比较归约尺度，低目标不自动等于准确参数或好预测，优化误差与泛化不同。

可逆z=Sx且g(z)=f(S⁻¹z)时问题对应，但z欧氏梯度步映回通常是矩阵缩放更新而非原标量步。若特征变换却罚项不调整，目标可能变了，要说明再参数化还是新建模选择。

实现报告初点、步选择、接受目标和停止量。最大步数结束尝试，小更新、梯度或目标变化只认证定理联系的量。有限几个起点成功不证明任意非凸网络全局保证。

凸集包含任两点的全部线段(1−t)x+ty，0≤t≤1。凸函数满足f(混合)≤(1−t)f(x)+tf(y)，图在弦下。不同点、内部t严格则严格凸。凸是全局线段性质，不要求光滑：|x|有折点仍凸；光滑不必凸，如−x²。

有限Jensen：非负权α和一时f(Σα_i x_i)≤Σα_i f(x_i)。归纳去零权，将前k−1点按总权合成一点，与最后点用二点凸，再用前点归一权归纳。前总权零则只最后一点相等。这里是有限代数平均，期望与无限混合另需模型可积性。

开凸域可导f的凸等价支持不等式f(y)≥f(x)+∇f(x)ᵀ(y−x)。凸段不等式重排差商、t↓0得它；反过来令z为混合，分别在z对x,y写支持，再加权梯度项消去，恢复凸。判据需所有点对，不是一次切线样本。

C²开凸域H处处半正定等价凸。沿段二阶dᵀHd≥0，中值使一阶不减，给线段支持；反向凸使对称二阶差非负，除t²取极限得所有d的dᵀHd≥0。单点正曲率仅局部。

μ>0强凸定义f−μ‖x‖²/2凸。可导支持式多μ‖y−x‖²/2，C²时H处处≽μI充分。强凸给统一二次裕量，严格凸仅严格弦。x⁴全实线严格凸却零处二阶零，不能用任意正μ统一强凸。

非负和、仿射复合保凸，负倍不行；有限凸函数最大值也凸，因为每函数段值≤加权端值≤加权端最大值。故凸可不光滑，光滑方法另检查可导假设。

内部可导局部极小全部一阶方向率零，即梯度零。C²下驻点H正定严格局部最小、负定最大、不定鞍点，由二阶模型统一余项得。半正定带零方向无结论，高阶决定，都是邻域分类。

凸改变证书：可导凸且可行内部梯度零，支持式使全域目标不更低。凸函数任何局部极小都全局，即使不可导：若远处更低，凸线段给任意近更低点，矛盾。严格凸让取得极小唯一，否则两同低点中点更低；仍不保证开或无界域取得。

强凸且有无约束极小x，双向支持相加得(∇f(x)−∇f(x))ᵀ(x−x*)≥μ‖x−x*‖²，极小梯度零与柯西给距离≤‖∇f(x)‖/μ。强凸下模型最小化位移给目标差≤‖梯度‖²/(2μ)。都是统一μ及取得假设下界，不是任意模型小梯度解释。

10⁻¹²(x−100)²有μ=2·10⁻¹²，零处梯度−2·10⁻¹⁰轻松过10⁻⁶容差，解距离却100，证书也是100。要距离≤.01需精确梯度≤2·10⁻¹⁴。目标差数字很小，可符合目标差标准却不符参数标准，需决定实际要哪一种精度。

仅凸下支持给目标差≤梯度范数乘到解距离；已知距离界R才得R‖梯度‖。无R或更强结构，小梯度不决定有用统一目标差。非凸驻点需分类或其他全局证据。

约束改变必要条件：[0,∞)上x在零最小、梯度一，可行方向不能向左。本课零梯度全局证书假设内部无约束和凸域，下一课改为明确乘子与边界条件。

梯度下降x_new=x−η∇f(x)，η正。负梯度是欧氏一阶最陡方向，有限步仍可过冲离域。设包含整段x到y的凸区域上梯度L-Lipschitz，L>0，差范数≤L‖y−x‖，则下降引理f(y)≤f(x)+∇f(x)ᵀ(y−x)+L‖y−x‖²/2。

无需积分的证明：d=y−x，φ(t)=f(x+td)−f(x)−t∇f(x)ᵀd−Lt²‖d‖²/2。导数=[∇f(x+td)−∇f(x)]ᵀd−Lt‖d‖²≤0，由柯西和L界。中值使φ不增，φ(1)≤φ(0)=0。整段须留在已知界的域。

固定合法η、目标下有界，累加下降得Σ‖g_k‖²≤(f₀−f_inf)/[η(1−Lη/2)]，若假设始终成立，梯度范数趋零。前K最小平方梯度≤同常数/K，是驻残差保证，不证明全局最小或输入数列收敛，也不无条件套网络。

凸与取得极小给目标速率。η=1/L、e=x−x，平方距离递推与支持给‖e_next‖²≤‖e‖²−2(f−f)/L+‖g‖²/L²，下降将最后项界为2(f−f_next)/L。于是f_next−f*≤L(‖e‖²−‖e_next‖²)/2。累加，再用目标递减使末差≤平均，得到k≥1时差≤L‖e₀‖²/(2k)。需光滑凸和取得，不只贴O(1/k)标签。

若还有μ强凸，上一节‖g‖²≥2μ目标差，配下降给每步差最多因子1−μ/L。局部估曲率不自动建立统一μ、L，定理需全局或不变域假设；SPD二次的模态提供更精确参数率。

回溯无需已知全局L：方向p先满足gᵀp<0，初α正、缩因子β∈(0,1)、Armijo c∈(0,1)，仅在域内且f(x+αp)≤f(x)+cαgᵀp时接受。可导使方向商趋gᵀp，严格低于c gᵀp，所以足够小α在开邻域能通过，精确算术下有限次缩减停止。非下降牛顿方向不由此变合法，也不独自证明全局收敛。

实际线搜索限制尝试次数并用数值容差，未成功应报告失败而非接受末个拒绝点。极小接受步可能反映曲率、域限制或错误方向，不认证小梯度或解误差，需报告不等式与停止原因，尤其求值有舍入噪声时。

对称SPD二次目标唯一解Ax*=b，误差e_new=(I−ηA)e。正交特征基每模态系数乘1−ηλ_i。对每个初误差都收敛需全部幅度<1，所以精确区间0<η<2/λ_max，是本二次家族必要充分，不是把一般充分下降界误作所有目标必要。

η=2/λ_max时激发最高模态恒幅交替，更大则增长；初误差没有该分量可能仍沿其他模态收敛，一次幸运轨迹不能证全局稳定。η=0不动，和模块13动力学、模块17欧拉因素呼应。

ρ=max|1−ηλ_i|，正交给‖e_k‖≤ρ^k‖e₀‖，目标差为加权模态平方，所以≤ρ^{2k}初差。谱区间[μ,L]最优固定最坏步2/(μ+L)，平衡低端1−ημ与高端ηL−1，因子(L−μ)/(L+μ)=(κ−1)/(κ+1)。仿射绝对值区间最大在端点；μ=L时η=1/L一次解完。

diag(1,100)用η=.01立刻杀刚模态却慢因子.99，200步原慢一变约.13398。平衡2/101两幅99/101更快、刚模态可交替；η=.1刚因子−9发散，即使低曲率坐标改善。

z=Sx、g=f(S⁻¹z)的H=S⁻ᵀA S⁻¹，S=diag(1,10)使diag(1,100)变单位阵，z单位步立即解。映回x_new=x−S⁻¹S⁻ᵀ∇f，是预条件更新，所有项一致变换时问题含义保留，坐标度量和算法改变，不宣称每个特征归一化总改进统计模型。

奇异PSD二次若b在C(A)，解族x*+N(A)，正模态可收敛、初始核分量保持；若b有核方向n的非零分量，tn目标含−t bᵀn，沿一侧无下界。只逆非零曲率或加对角不能隐藏这一问题性质。

牛顿用二次局部模型解H(x)p=−∇f，提x+p。求解系统而非显式形成逆，数学作用同而可用适当数值求解器。H对称正定、g非零时gᵀp=−pᵀHp<0，局部下降；远处全步仍需域和有限下降检查。

奇异H可方向不唯一或系统不一致。diag(2,0)、g=(−2,0)最小范数方向(1,0)，从(0,5)到极小(1,5)，保平坦坐标，最小步范数非最小解范数。g不在H像则无精确解，最小二乘方向是不同局部近似，还需下降检查。

阻尼将H改H+δI、选正定获得下降方向，修改局部步模型，不自动等于给原目标加ridge。若真改目标，梯度也要一致改。非凸保障可拒上坡，仍不无条件全局最优。

坐标下降固定其他只改一坐标，SPD二次精确沿i最小为x_i−g_i/A_ii，下降量g_i²/(2A_ii)，除非坐标梯度零。循环后坐标使用刚更新值，不同于旧向量同时对角预条件步。收敛需适当日程假设，不能只凭有限坐标改善。

旋转二次从零，第一坐标3x₁+x₂=2得2/3，第二用新值解x₁+3x₂=−1得−5/9，降低但还非(7/8,−5/8)。牛顿一次耦合解、梯度用统一标量，单步工作不同，迭代数不公平比较成本。

非退化极小附近牛顿可二次局部收敛，要求H足够正则、邻近可逆、起点在有效邻域，不适于直接套奇异极小或远起点。精确二次例整个目标等局部模型所以本课完整证明一步。回溯可能帮助到邻域，局部定理自身不证明所有起点到达。

停止需命名精度量：目标变化小可舍入、平坦、阻尼造成，梯度小可目标缩放，更新小可人为小步。已证明强凸或其他界时把计算残差转请求距离或差并加误差裕量，否则报告真实残差、步和原因。

训练目标优化不决定预测有效性，目标可能误设、评价数据可能不同、训练全局极小仍可泛化差，后面统计处理。本课成果是能推更新、检查域曲率、区分定理、有限轨迹和有用启发式。

实验1 · 精确二次模态与牛顿系统

下载 lab1_quadratic_modes.py

"""Eigenmodes determine the full constant-step interval of a quadratic."""
import numpy as np
np.set_printoptions(precision=6, suppress=True)
A = np.array([[3.0,1.0], [1.0,3.0]])
b = np.array([2.0,-1.0])
optimum = np.linalg.solve(A, b)
eigenvalues = np.linalg.eigvalsh(A)
def objective(x):
    return 0.5*x@A@x-b@x
start = np.array([3.0,2.0])
print("Eigenvalues / unique optimum / optimal objective:", eigenvalues, optimum, objective(optimum))
print("eta      mode factors           error after 30      objective after 30")
for eta in [0.2, 1/3, 0.5, 0.55]:
    x = start.copy()
    history = [objective(x)]
    for _ in range(30):
        x -= eta*(A@x-b)
        history.append(objective(x))
    factors = 1-eta*eigenvalues
    error = np.linalg.norm(x-optimum)
    print(f"{eta:.6f}", factors, f"{error:.10e}", f"{objective(x):.10f}")
    if np.max(np.abs(factors)) < 1:
        assert error < 1e-5
        assert all(next_value <= value+1e-12 for value, next_value in zip(history, history[1:]))
    else:
        assert error > 1
print("Strict interval: 0 < eta < 2/lambda_max =", 2/eigenvalues[-1])
newton = start-np.linalg.solve(A, A@start-b)
print("Exact quadratic Newton result:", newton)
assert np.allclose(newton, optimum, atol=1e-12, rtol=0)

Eigenvalues / unique optimum / optimal objective: [2. 4.] [ 0.875 -0.625] -1.1875
eta      mode factors           error after 30      objective after 30
0.200000 [0.6 0.2] 7.8161433852e-08 -1.1875000000
0.333333 [ 0.333333 -0.333333] 1.6404273111e-14 -1.1875000000
0.500000 [ 0. -1.] 3.3587572106e+00 21.3750000000
0.550000 [-0.1 -1.2] 7.9728940561e+02 1271339.6050933360
Strict interval: 0 < eta < 2/lambda_max = 0.5
Exact quadratic Newton result: [ 0.875 -0.625]

先推解、谱和每因子，解释边界持续模态、过大增长、牛顿精确解。轨迹说明已推全称区间，不替代证明。

实验2 · 曲率、条件与坐标

下载 lab2_scaling_conditioning.py

"""A coordinate change changes curvature and the effective gradient metric."""
import numpy as np
A = np.diag([1.0,100.0])
start = np.array([1.0,1.0])
print("Raw curvature eigenvalues / condition number:", np.diag(A), np.linalg.cond(A))
print("eta      steps      endpoint                norm")
for eta, steps in [(0.01,200), (2/101,200), (0.1,10)]:
    x = start.copy()
    for _ in range(steps):
        x -= eta*(A@x)
    print(eta, steps, x, np.linalg.norm(x))
    if eta == 0.1:
        assert np.linalg.norm(x) > 1e9
    else:
        assert np.linalg.norm(x) < np.linalg.norm(start)

# z=S*x, so x=S^-1*z; preserve the mathematical objective under this change.
S = np.diag([1.0,10.0])
inverse_S = np.diag([1.0,0.1])
transformed_A = inverse_S.T@A@inverse_S
z = S@start
assert np.allclose(transformed_A, np.eye(2))
z -= transformed_A@z  # eta_z=1 on identity curvature.
recovered = inverse_S@z
print("Transformed curvature / condition number:", transformed_A, np.linalg.cond(transformed_A))
print("One transformed-coordinate step, mapped back:", recovered)
assert np.allclose(recovered, 0, atol=1e-12)
preconditioned = start-inverse_S@inverse_S.T@(A@start)
assert np.allclose(preconditioned, recovered)
print("Same objective, different coordinate geometry; the equivalent raw update uses a matrix preconditioner.")

Raw curvature eigenvalues / condition number: [  1. 100.] 100.0
eta      steps      endpoint                norm
0.01 200 [0.13397967 0.        ] 0.13397967485796206
0.019801980198019802 200 [0.0183132 0.0183132] 0.0258987713130135
0.1 10 [3.4867844e-01 3.4867844e+09] 3486784401.0
Transformed curvature / condition number: [[1. 0.]
 [0. 1.]] 1.0
One transformed-coordinate step, mapped back: [0. 0.]
Same objective, different coordinate geometry; the equivalent raw update uses a matrix preconditioner.

预测.01慢因子、2/101平衡因子、.1坏因子，验证变换H为单位再映回，说明原坐标的预条件含义。

实验3 · 奇异、非下降与停止故障

下载 lab3_newton_and_stopping_faults.py

"""Singular or indefinite curvature and small gradients need qualified handling."""
import numpy as np
np.set_printoptions(precision=6, suppress=True)

H = np.diag([2.0,0.0])
b = np.array([2.0,0.0])
x = np.array([0.0,5.0])
gradient = H@x-b
try:
    np.linalg.solve(H, -gradient)
except np.linalg.LinAlgError:
    print("Singular Newton system: direct solve has no unique direction.")
direction, *_ = np.linalg.lstsq(H, -gradient, rcond=1e-12)
next_x = x+direction
print("Minimum-norm direction / resulting minimiser:", direction, next_x)
assert np.allclose(next_x, [1,5])  # Flat coordinate is preserved, not forced to zero.
print("Nonunique minima: first coordinate one, any second coordinate.")

def f(t):
    return t**4-3*t*t
t = 0.1
g, curvature = 4*t**3-6*t, 12*t*t-6
newton_direction = -g/curvature
print("Nonconvex Newton direction / gradient-dot-direction:", newton_direction, g*newton_direction)
print("Objective before / raw Newton step:", f(t), f(t+newton_direction))
assert g*newton_direction > 0 and f(t+newton_direction) > f(t)
# Replace a non-descent direction by -gradient; backtrack with explicit Armijo c.
descent, alpha, c = -g, 1.0, 1e-4
for _ in range(50):
    if f(t+alpha*descent) <= f(t)+c*alpha*g*descent:
        break
    alpha *= 0.5
else:
    raise RuntimeError("No accepted finite backtracking step")
print("Safeguarded step / objective:", alpha, f(t+alpha*descent))
assert f(t+alpha*descent) < f(t)

# Zero gradient is not sufficient for a nonconvex minimum.
print("Saddle x^2-y^2 at zero: gradient zero, value along (0,0.1) =", -0.1**2)
assert -0.1**2 < 0

coefficient, location, target = 1e-12, 0.0, 100.0
small_gradient = 2*coefficient*(location-target)
mu = 2*coefficient
gradient_tolerance = 1e-6
print("Scaled objective gradient / tolerance:", small_gradient, gradient_tolerance)
print("Naive gradient test passes / solution error:", abs(small_gradient)<gradient_tolerance, abs(location-target))
print("Strong-convexity error certificate ||gradient||/mu:", abs(small_gradient)/mu)
assert abs(small_gradient) < gradient_tolerance and abs(location-target) == 100
print("For distance tolerance 0.01, sufficient gradient threshold:", mu*0.01)
print("State which quantity termination certifies; objective scaling changes gradient thresholds.")

Singular Newton system: direct solve has no unique direction.
Minimum-norm direction / resulting minimiser: [1. 0.] [1. 5.]
Nonunique minima: first coordinate one, any second coordinate.
Nonconvex Newton direction / gradient-dot-direction: -0.10136054421768709 0.06041088435374151
Objective before / raw Newton step: -0.029900000000000006 -5.553238278345991e-06
Safeguarded step / objective: 1.0 -1.218589138944
Saddle x^2-y^2 at zero: gradient zero, value along (0,0.1) = -0.010000000000000002
Scaled objective gradient / tolerance: -2e-10 1e-06
Naive gradient test passes / solution error: True 100.0
Strong-convexity error certificate ||gradient||/mu: 100.0
For distance tolerance 0.01, sufficient gradient threshold: 2e-14
State which quantity termination certifies; objective scaling changes gradient thresholds.

区分最小步范数和平坦解，查非凸方向符号、Armijo接受、缩放距离证书。小目标差可符合哪标准，却参数仍远？

1–12必做，13–14选做额外35分钟，不计入十二小时核心。

用作者Convex Optimization伴随站的凸函数与无约束极小选段，本课独立推支持、下降、谱界，实验写清约定。

证明凸例、局部全局证书、L下降及各二次模态，比较梯度、循环坐标、牛顿成本保障。

结业任务：diag(1,100)全称区间0<η<.02，平衡2/101因子99/101。解释.1为何仅首模态起点可成功，坐标尺度为何改更新度量。

可以继续：你能将行为联系目标域曲率假设。下一模块加入可行方向、乘子、KKT与对偶界。见总览。