最优化理论之无约束优化基本结构及其python应用

自古以来，凡是追求尽善尽美是人类的天性，因而产生了科学，工程，数学，经济和商业等领域的实际问题时，人们欲从众多可行的方案中选择最优或近似最优的解决方案，那么最优化方法就是专门解决这类问题的一个强有力工具。最优化方法包括无约束优化与约束优化直线搜索方法,无约束优化方法,约束优化方法，今天我们先来讨论无约束优化理论的基本结构。

本文内容：

1. 符号约定

梯度向量（列向量）

g(x) = \nabla f(x) = [\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\frac{\partial f(x)}{\partial x_3},...,\frac{\partial f(x)}{\partial x_n}]^T

海森矩阵

G(x) = \nabla^2f(x) = \begin{bmatrix} \frac{\partial^2 f(x)}{\partial x_1^2} & \frac{\partial^2 f(x)}{\partial x_1\partial x_2} & \cdots & \frac{\partial^2 f(x)}{\partial x_1\partial x_n}\\ \frac{\partial^2 f(x)}{\partial x_2\partial x_1} & \frac{\partial^2 f(x)}{\partial x_2^2} & \cdots & \frac{\partial^2 f(x)}{\partial x_2\partial x_n}\\ \vdots & \vdots & \cdots& \vdots \\ \frac{\partial^2 f(x)}{\partial x_n\partial x_1} & \frac{\partial^2 f(x)}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f(x)}{\partial x_n^2}\end{bmatrix}

2. 最优性条件

（1）最优解的类型

（2）最优性条件

3. 无约束优化算法的基本结构

（1）线搜索型方法：

（2）信赖域方法：

（3）线搜索和信赖域方法的比较：

（4）线搜索型的四个要素：

（5）步长：

例子：求 min f(x)=\frac{1}{2}x^THx+c^Tx+b,H\succeq 0 的每一步下降步长的表达式？

解：

\phi (\alpha) = \frac{1}{2}(x^k+\alpha d^k)^T H (x^k+\alpha d^k)+c^T(x^k+\alpha d^k) + b \\ =\frac{1}{2}(d^k)^THd^k\alpha^2+[(d^k)^THx^k+c^Td^k]\alpha +b\\ \phi'(\alpha) = (d^k)^THd^k\alpha + (d^k)^THx^k+c^Td^k = 0\\ \alpha_k^* = -\frac{(d^k)^THx^k+c^Td^k}{(d^k)^THd^k}

（2）0.618法：

（3）二分法：

如果 0">\phi'(\frac{a_0+b_0}{2})>0 ，则 [a_1,b_1]=[a_0,\frac{a_0+b_0}{2}] ，反之。

f(x_k+\alpha d_k) \le f(x_k)+\rho g_k^Td_k\alpha ,\rho \in (0,1)

说明：Armijo准则使用了 f(x_k+\alpha d_k) 的切线控制最大步长，并给定步长的一个上界，但是并没有给出步长的下界（因为下界是0），但是实际中我们不需要过于小的步长，因为过小的步长将导致收敛速度太慢。

（2）Goldstein准则：

\boxed{f(x_k+\alpha d_k) \le f(x_k)+\rho g_k^Td_k\alpha ,\rho \in (0,\frac{1}{2})\\f(x_k+\alpha d_k) \ge f(x_k)+(1-\rho) g_k^Td_k\alpha,\rho \in (0,\frac{1}{2})}

（3）二次插值法：（只设定了上限 \alpha_0 ）

设在0， 0)">\alpha_0(\alpha_0>0) 两点已知， \phi(0)=f(x_k),\phi'(0)=g_k^Td_k,\phi(\alpha_0)=f(x_k+\alpha_0d_k) ，假定在点 \alpha_0 处不满足Armijo准则，那么构造二次插值多项式： p(\alpha)=a\alpha^2+b\alpha+c ，插值点为： p(0)=\phi(0),p'(0)=\phi'(0),p(\alpha_0)=\phi(\alpha_0) ，求出插值系数：

\alpha_1 = \frac{-\phi'(0)\alpha_0^2}{2[\phi(\alpha_0)-\phi(0)-\phi'(0)\alpha_0]}

（4）三次插值法（同时设定上限与下限）：

设三个点与四个插值数据： \phi(0),\phi'(0),\phi(\alpha_0),\phi(\alpha_1) ，设置插值多项式： p(\alpha) = a\alpha^3+b\alpha^2+c\alpha+d ，最终求解插值系数：

c=\phi(0),d=\phi'(0)

（6）信赖域方法：

在点 x_k ，我们想要求下降方向 d_k ，我们不可能求解极小化问题 min\; f(x_k+d) 去得到 d_k ，因为这与原问题一样复杂。我们采用原函数的二阶近似，采用泰勒展开来简化问题：

原问题：

min_d\; f(x_k+d)

简化后问题：

0">q_k(d) = f_k+g_k^Td+\frac{1}{2}d^TG_kd\\ min\;q_k(d),\\s.t.||d||\le \Delta_k,\Delta_k>0

求解出第k步的方向后需要对 \Delta_k 修正以获得 \Delta_{k+1} ，修正的依据应该是在 x_k 处， q_k(d_k) 近似 f(x_k+d_k) 的程度决定的，因此：

\Delta f_k = f(x_k)-f(x_k+d_k)\\ \Delta q_k = q_k(0)-q_k(d_k),q_k(0)=f(x_k)\\ \gamma_k = \frac{\Delta f_k}{\Delta q_k}

\gamma_k 的大小反映了在 x_k 处， q_k(d_k) 近似 f(x_k+d_k) 的程度决定的，当 \gamma_k 接近于1时，近似程度好；当 \gamma_k 接近于0时，近似程度不好。最后可以输出整个算法！

至于算法为什么取0.75和0.25，是因为查看了作者论文，作者说到了算法对0.75和0.25不敏感。

4. python实现精确线搜索

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
class Optimizer():
    # 求函数值f(x) = x^2
    # 求导数
    # 精确线搜索求步长
    # 梯度下降
    
    def __init__(self):
        pass
    def f_x(self,x):
        return x**2
    def gradient(self,x):
        return 2*x 
    def alpha (self,x,d_k): 
        return -x/d_k
    def start(self):
        x_0 = 100
        for i in range(0,5000):
            if (self.gradient(x_0)>10**(-8)):
                
                a = self.alpha(x_0,-self.gradient(x_0))
                x_new = x_0 - a* self.gradient(x_0)
                x_0 = x_new
                print(x_0)
            else:
                break
                
        return (x_0,self.f_x(x_0))
if __name__ == '__main__':
    opz = Optimizer()
    opz.start()

5. 结语

以上就是最优化理论之无约束优化基本结构及其python应用文章的全部内容，在下一次的分享中，将会给大家带来具体的无约束优化算法，包括最速下降法，牛顿法，拟牛顿法以及共轭梯度法等。

《数值最优化方法》--高立

Bilibili 崔雪婷老师的最有化课程

（编辑：成都站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!