非线性最优化

• 最优化的问题的一般形式为

Min f(x) s.t. x∈X
f(x) 为目标函数， X∈Eⁿ 为可行域。

如 X= Eⁿ，则以上最优化问题为无约束最优化问题。

约束最优化问题通常写为

Min f(x)
s.t.
c_i(x)=0, i∈E,
c_i(x)>=0, i∈I,
其中E, I分别为等式约束的指标集和不等式约束的指标集，c_i(x)是约束函数。

• 可行点，可行域
• 极小，全局极小（总体极小点），全局严格极小，局部极小，局部严格极小
• 积极与非积极，积极约束，非积极约束
• 可行方向集，线性可行方向集，序列可行方向集
• Farkas引理与K-T条件
• 以上参见《最优化理论与方法》第八章

无约束二次最优化

min f(x) = ½ x^THx+c^Tx, x∈Rⁿ

H是对称阵
基本解法：求导然后找局部极值。

二次规划的一般形式

min f(x) = ½ x^THx+c^Tx, x∈Rⁿ
s.t. Ax≤b（1）

• 当H为对称矩阵时，被称为二次规划(Quadratic Programming，记作QP)。
• 特别，当H正定时，目标函数为凸函数，线性约束下可行域又是凸集。上式被称为凸二次规划。

二次规划的性质

• QP是一种最简单的非线性规划。QP有如下良好的性质，当H是半正定时：
  • K-T条件不仅是最优解的必要条件，而且是充分条件；
  • 局部最优解就是全局最优解。

等式约束下的二次规划

min f(x) = ½ x^THx+c^Tx, x∈Rⁿ
s.t. Ax=b（2）

求解方法：Lagrange乘子法，求解以下无约束二次最优化问题。

L(x,λ) = ½ x^THx+c^Tx+λ^T(Ax-b)

令L(x,λ)对x和λ的导数为零，得线性方程组

Hx+c^T+A^Tλ=0

Ax-b=0

可解得x，即为上式的解。