12录优性条件 二阶必要条件：若于二阶可微，由一阶必要条件有 f+al)=f()+a2V"f(W+O(o) 由若V2f(x)非半正定，由定义存在t使得tTV2f(x)t<0,从而在a充分小时即有f()>f(运+a), 矛盾 二阶充分条件：由正定定义，对任何t,a272f(x)t>0,从而在a充分小时一定有f()< f(位+a)。对每个单位向量t考虑最优的a()>0,由于所有可能t构成的集合（高维球面）是紧集，且 可验证a()连续性，存在a0=mi血ta()>0,于是{杠|x-<ao}内五是最小点，从而是极小值。 不过，这里只有必要条件与充分条件，并不能完整进行刻画。好在，当函数∫有一定性质的时候， 必要条件可以提升为充要条件，这个重要性质就是凸性。 定义1.5（凸函数） R”上的西f为凸函数，当其满足对红，y∈R”,入∈0,1有 f(+(1-)≤()+(1-)f( 对凸函数还有两个重要的等价定义，这里进行列举，后文凸优化中详细证明： 命遵1.6（凸函数等价定义） R”上的可微函数∫为凸函数 当且仅当其满足对红，y∈R”有 f)≥fa)+Vfx)(g-x) R上的二阶可微函数∫为凸函教，当且仅当其满足对V红∈R有f(x)半正定 事实上凸函数不必定义在R”上，只需要定义在凸集上就可以谈论，此处由于问题是无约束的，考虑 全空间即可。 有了等价定义后，就可以有无约束优化的最优条件： 定理17（凸函数下的充要条件） f(工)是R”上的可微凸函教，则五是全局最优解的充要条件是了f()=0, 证明必要性根据之前定理得到。对于充分性，由一阶等价条件直接得到()≥∫()。 1.2.2约束问题的最优条件 在有约束的情况下，想判断一个点是否是局部最优解就要困难很多。约束导致可行域的复杂，也 导致了最优判定必须考虑边界的情况。对此，有如下的直观定义与性质： 定义1.8（可行方向、下降方向） Rm中，对x∈S与非零向量d,若存在6>0使得x+d∈S,以∈(0，)，则称d是S在x处 的可行方向，并记所有S在r处的可行方向集合为F(红，S) 对Rm上实函数f与向量工，非零向量d,若存在6>0使得f(x+d<f(r),以∈(0，)，则 称d为f在x处的下降方向，并记所有S在x处的下降方向集合为Do(红，S)。 若f可微，记所有满足Vf(x)Td<0的向量d构成D(红，f). 1.2 最优性条件 二阶必要条件：若 f 二阶可微，由一阶必要条件有 f(¯x + αt) = f(¯x) + 1 2 α 2 t T ∇2 f(x)t + O(α 3 ) 由若 ∇2f(x) 非半正定，由定义存在 t 使得 t T ∇2f(x)t < 0，从而在 α 充分小时即有 f(¯x) > f(¯x + αt)， 矛盾。 二阶充分条件：由正定定义，对任何 t，1 2 α 2 t T ∇2f(x)t > 0，从而在 α 充分小时一定有 f(¯x) < f(¯x + αt)。对每个单位向量 t 考虑最优的 α(t) > 0，由于所有可能 t 构成的集合 (高维球面) 是紧集，且 可验证 α(t) 连续性，存在 α0 = mint α(t) > 0，于是 {x | ∥x − x¯∥ < α0} 内 x¯ 是最小点，从而是极小值。 不过，这里只有必要条件与充分条件，并不能完整进行刻画。好在，当函数 f 有一定性质的时候， 必要条件可以提升为充要条件，这个重要性质就是凸性。 定义 1.5 (凸函数) ♣ R n 上的函数 f 为凸函数，当其满足对 ∀x, y ∈ R n , λ ∈ [0, 1] 有 f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) 对凸函数还有两个重要的等价定义，这里进行列举，后文凸优化中详细证明： 命题 1.6 (凸函数等价定义) ♠ R n 上的可微函数 f 为凸函数，当且仅当其满足对 ∀x, y ∈ R n 有 f(y) ≥ f(x) + ∇f(x) T (y − x) R n 上的二阶可微函数 f 为凸函数，当且仅当其满足对 ∀x ∈ R n 有 ∇2f(x) 半正定。  事实上凸函数不必定义在 R n 上，只需要定义在凸集上就可以谈论，此处由于问题是无约束的，考虑 全空间即可。 有了等价定义后，就可以有无约束优化的最优条件： 定理 1.7 (凸函数下的充要条件) ♡ f(x) 是 R n 上的可微凸函数，则 x¯ 是全局最优解的充要条件是 ∇f(¯x) = 0。 证明 必要性根据之前定理得到。对于充分性，由一阶等价条件直接得到 f(y) ≥ f(¯x)。 1.2.2 约束问题的最优条件 在有约束的情况下，想判断一个点是否是局部最优解就要困难很多。约束导致可行域的复杂，也 导致了最优判定必须考虑边界的情况。对此，有如下的直观定义与性质： 定义 1.8 (可行方向、下降方向) ♣ R n 中，对 x ∈ S 与非零向量 d，若存在 δ > 0 使得 x + λd ∈ S, ∀λ ∈ (0, δ)，则称 d 是 S 在 x 处 的可行方向，并记所有 S 在 x 处的可行方向集合为 F(x, S)。 对 R n 上实函数 f 与向量 x，非零向量 d，若存在 δ > 0 使得 f(x + λd) < f(x), ∀λ ∈ (0, δ)，则 称 d 为 f 在 x 处的下降方向，并记所有 S 在 x 处的下降方向集合为 D0(x, S)。 若 f 可微，记所有满足 ∇f(x) T d < 0 的向量 d 构成 D(x, f)。 4