【知识框架】优化方法基本原理：梯度下降法、牛顿法、拉格朗日对偶法

梯度下降法

梯度下降法是求解无约束最优化问题的一种最常用方法，实现简单，每一步需要求解目标函数的梯度向量。
以二元函数 z=f(x,y) 等值线俯视图为例：
【知识框架】优化方法基本原理：梯度下降法、牛顿法、拉格朗日对偶法

牛顿法是求解无约束最优化问题的常用方法，收敛速度快，每一步迭代需要求解目标函数的海森矩阵的逆矩阵，计算较为复杂。

拟牛顿法则用正定矩阵近似海森矩阵的逆矩阵，简化了牛顿法。

海森矩阵(Hessian Matrix)是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率。

在约束最优化问题中，利用拉格朗日对偶性将原始问题转换为对偶问题。

最优化问题：

min_{x \in R^{n}} f (x)

s . t . c (x) \leq 0, i = 1, 2, . . ., k

h_{j} (x) = 0, j = 1, 2, . . ., l

引入拉格朗日函数得到：

L (x, α, β) = f (x) + \sum_{i = 1}^{k} α_{i} c_{i} (x) + \sum_{j = 1}^{l} β_{j} h_{j} (x)

定义问题：

Θ_{p} (x) = max_{α, β; α_{i} \geq 0} L (x, α, β)

p^{*} = min_{x} Θ_{p} (x)

定义对偶问题与对偶问题的最优值

Θ_{D} (α, β) = min_{x} L (x, α, β)

d^{*} = max_{α, β; α_{i} \geq 0} Θ_{D} (α, β)

a. 若原始问题与对偶问题都有最优解，则：
d*=p*

Θ_{D} (α, β) = min_{x} L (x, α, β) \leq L (x, α, β) \leq max_{α, β; α_{i} \geq 0} L (x, α, β) = p *

b. 假设f(x)和c(x)是凸函数，h(x)是仿射函数；并假设不等式约束是严格可行的，即存在x,对所有c(x)<0，则存在x*是原始问题最优解，alpha和beta是对偶问题的解，并且有：

p^{*} = d^{*} = L (x^{*}, α^{*}, β^{*})

c. KKT条件

假设f(x)和c(x)是凸函数，h(x)是仿射函数；并假设不等式约束是严格可行的，则x，alpha,beta分别是原始问题和对偶问题的解的充要条件可以归结为——KKT条件。