非线性规划：无约束问题

min⁡f(x)x∈En\begin{matrix} \min f(x) & x∈E^n\end{matrix}

梯度法

基本思路

泰勒展开：f(x)=f(x0)+f′(x0)(x−x0)+12f′′(x0)(x−x0)2+⋯+f(n)(x0)n!(x−x0)n+Rn(x)f(x) =f(x_0) + f'(x_0)(x-x_0) + \dfrac{1}{2}f''(x_0)(x-x_0)^2 + \cdots + \dfrac{f^{(n)}(x_0)}{n!}(x-x_0)^n + R_n(x)

f(x)f(x)有一阶连续偏导数，具有极小点x∗x^*。x(k)x^{(k)}表示向极小点的第kk次近似

x(k+1)=x(k)+λkP(k)λk≥0\begin{matrix} x^{(k+1)} = x^{(k)} + λ_kP^{(k)} & λ_k≥0 \end{matrix}

将f(x)f(x)在x(k)x^{(k)}处，泰勒展开

f(x)=f[x(k)+λP(k)]=f(x(k))+λk▽f(x(k))TP(k)+o(λ)lim⁡λ→0o(λ)λ<0\begin{matrix} f(x) = f[x^{(k)} + λP^{(k)}] = f(x^{(k)}) + λ_k▽f(x^{(k)})^TP^{(k)} + o(λ) & \lim\limits_{λ→0} \dfrac{o(λ)}{λ} < 0 \end{matrix}

为了使目标函数值能得到尽量大的改善，必须寻求使f(x(k))TP(k)f(x^{(k)})^TP^{(k)}取最小值的P(k)P^{(k)}

▽f(x(k))TP(k)=∥▽f(x(k))∥⋅∥P(k)∥cos⁡θ▽f(x^{(k)})^TP^{(k)} = \|▽f(x^{(k)})\| ⋅ \|P^{(k)}\| \cosθ

当θθ为钝角时，即可下降，为180°180°时（cos⁡θ=−1\cosθ=-1），下降最快有

P(k)=−▽f(x(k))P^{(k)}=-▽f(x^{(k)})

称为负梯度方向。

计算步骤

海赛（Hessian）矩阵：H(x)=[∂2f∂x12∂2f∂x1∂x2∂2f∂x2∂x1∂2f∂x22]H(x) = \left[\begin{array}{c} \frac{∂^2f}{∂x_1^2} & \frac{∂^2f}{∂x_1∂x_2} \\ \\ \frac{∂^2f}{∂x_2∂x_1} & \frac{∂^2f}{∂x_2^2} \end{array}\right]

求步长

λk=▽f[x(k)]T⋅▽f[x(k)]▽f[x(k)]T⋅H(x(k)⋅▽f[x(k)]λ_k = \dfrac{ ▽f[x^{(k)}]^T ⋅ ▽f[x^{(k)}] }{ ▽f[x^{(k)}]^T ⋅ H(x^{(k}) ⋅ ▽f[x^{(k)}] }

停止条件

其中εε为精度，满足以上任意一条时，停止迭代。

例

求f(x)=(x1−1)2+(x2−1)2f(x) = (x_1 - 1)^2 + (x_2 - 1)^2的极小点，已知ε=0.1ε=0.1。

解

梯度表达式：▽f(x)=[2(x1−1)2(x2−1)]▽f(x) = \left[\begin{array}{c} 2(x_1-1) \\ 2(x_2-1) \end{array}\right]

求步长

λ0=[−2−2][−2−2][−2−2][2002][−2−2]=12λ_0 = \dfrac{ \left[\begin{array}{c} -2 & -2 \end{array}\right] \left[\begin{array}{c} -2 \\ -2 \end{array}\right] }{ \left[\begin{array}{c} -2 & -2 \end{array}\right] \left[\begin{array}{c} 2 & 0 \\ 0 & 2 \end{array}\right] \left[\begin{array}{c} -2 \\ -2 \end{array}\right] } = \dfrac{1}{2}

迭代

x(1)=x(0)−λ0▽f(x(0))=[00]−12[−2−2]=[11]x^{(1)} = x^{(0)} - λ_0▽f(x^{(0)}) = \left[\begin{array}{c} 0 \\ 0 \end{array}\right] - \dfrac{1}{2} \left[\begin{array}{c} -2 \\ -2 \end{array}\right] = \left[\begin{array}{c} 1 \\ 1 \end{array}\right]

▽f(x(1))=[00]▽f(x^{(1)}) = \left[\begin{array}{c} 0 \\ 0 \end{array}\right]，∥▽f(x(1))∥=0<0.1=ε\|▽f(x^{(1)})\|=0<0.1=ε，迭代停止

故x(1)x^{(1)}即为在精度ε=0.1ε=0.1下的极小点。