第十四课

1.非线性最优化

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

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)是约束函数。

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

2.无约束二次最优化

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

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

3.二次规划的一般形式

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

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

4.二次规划的性质

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

5.等式约束下的二次规划

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，即为上式的解。

6.二次规划的有效集方法

• 直观解释：将不起作用约束去掉，将起作用约束作为等式约束，
  通过解一系列等式约束的二次规划来实现不等式约束的优化
• 基本原理：若x为问题（1）的最优解，则它也是问题

min ½ x^THx+c^Tx

s.t. a_i^Tx=b_i,i∈I

的最优解，其中a_i是A的第i行，I为起作用约束指标集（有效集）。

• 反之，若x为（1）的可行解，又是（3）的K-T点，且相应的乘子λ_i≥ 0，
  则x为（1）的最优解。

• 算法步骤（迭代法）：
  • 设当前迭代点为x_k，它也是（1）的可行解。该点的有效集记作I_k，
    为寻求x_k点的迭代方向d，用乘子法求解。

min ½(x_k+d)^TH(x_k+d)+c^T(x_k+d)

s.t. a_i^Td=0,i∈I_k

• 若所得最优值d_k=0，则x_k是（3）的最优解。
  • 为判断它是否（1）的最优解，考察对应于有效约束的乘子λ_i≥ 0是否成立。
    若成立，则x_k是K-T点，由二次规划性质x_k是（1）的最优解。
• 若最优值d_k≠ 0，则取x_k+1=x_k+αd_k，在x_k+1为可行点的条件下确定d_k方向的步长α_k。
  • 如果存在p不在I_k中，使得a_px_k+1=b_p，则将p加入有效集。
• 如果存在I_k中的指标q，使得λ_i< 0, 则x(k)不是最优解，从有效集中去掉q。