最优化原理与算法复习

DungDaj · 发表于 2022-5-10 14:55

一、无约束优化

1 线搜索

线搜索类算法的数学表述为：给定当前迭代点，首先通过某种算法选取向量，之后确定正数，则下一步的迭代点可写作

$x_{k+1} = x_k + α_k d_k$
我们称为迭代点处的搜索方向，为相应的步长．这里要求是一个下降方向，即

$(d_k)^T \nabla f(x_k)<0$
这个下降性质保证了沿着此方向搜索函数 $f$ 的值会减小．线搜索类算法的关键是如何选取一个好的方向 $d_k \in R^n$ 以及合适的步长 .
首先讨论如何选取适当的步长.
1.1 非精确线搜索

1.1.1 线搜索准则
下面介绍的线搜索准则都是单调线搜索，还有一些非单调线搜索准则，这里不加介绍

Armijo准则

Armijo准则对步长作了本质要求，即保证每一步迭代充分下降。

定义: 设是点处的下降方向，若
$f(x_k+\alpha d_k)\leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k$
则称步长满足Armijo准则，其中 $c_1\in(0,1)$ 是一个常数.

但Armijo准则并不能保证迭代能够顺利进行，例如 $\alpha = 0$ 就是一个满足Armijo准则的步长。因此常常需要其他准则来配合Armijo准则使用。下面列举两种准则。

Goldstein-Armijo准则
为了克服 Armijo 准则的缺陷，我们需要引入其他准则来保证每一步的不会太小。
定义: 设是点处的下降方向，若
$\begin{align*} f(x_k+\alpha d_k) &\leq f(x_k) + c \alpha \nabla f(x_k)^T d_k \\ f(x_k+\alpha d_k) &\geq f(x_k) + （1-c） \alpha \nabla f(x_k)^T d_k \end{align*}$
则称步长满足 Goldstein 准则,其中 $c\in(0,\frac{1}{2})$ .

# Goldstein-Armijo一维线搜索

Wolfe-Armijo准则

Goldstein准则能够保证函数值充分下降，但是它可能避开了最优函数值，为此我们引入Armijo-Wolfe准则。

定义： 设是点处的下降方向，若
$\begin{align*} f(x_k+\alpha d_k) &\leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k \\ \nabla f(x_k+\alpha d_k)^T d_k &\geq c_2 \nabla f(x_k)^T d_k \end{align*}$
则称步长满足Wolfe准则，其中 $c_1,c_2 \in (0,1)$ 为给定的常数且 $c_1<c_2$ .

#Wolfe-Armijo一维搜索
1.1.2 线搜索算法

回退法

1.2 精确线搜索

1.2.1 试探法

黄金分割法

黄金分割法是一种区间收缩法，其主要用于求解单峰函数的极值问题。其利用了单峰函数的性质，排除极值不可能存在的区间，从而达到逐渐缩小目标区间的效果。
求极小值的黄金分割法具体实现流程如下：

给定 $a,b,\varepsilon >0$ .
计算 $x_1 = a + 0.382(b-a),x_2=a + 0.618(b-a)$ .
若 $b-a<\varepsilon$ ，停止，输出 $x_*=\frac{a+b}{2}$ ;否则转(4).
计算 $f_1 = f(x_1),f_2 = f(x_2)$ .
如果 $f_1 > f_2$ ，令 $a = x_1,x_1 = x_2,x_2 = a+0.618(b-a)$ , 否则令 $b= x_2,x_2 = x_1,x_1 = a+0.382(b-a)$ ,转(3).

#黄金分割法
def goldenSearch(a,b,fun,epsilon = 0.01):
x1 = a + 0.382 * (b-a)
x2 = a + 0.618 * (b-a)
f1 = fun(x1)
f2 = fun(x2)
while b-a > epsilon:
 print(&#39;a={},b={},x1={},x2={}&#39;.format(a,b,x1,x2))
 if f1 < f2:
 b = x2
 x2 = x1
 x1 = a + 0.382 * (b - a)
 f1 = fun(x1)
 f2 = fun(x2)
 else:
 a = x1
 x1 = x2
 x2 = a + 0.618 * (b - a)
 f1 = fun(x1)
 f2 = fun(x2)
return (b+a)/2, fun((b+a)/2)

if __name__ == &#39;__main__&#39;:
fun = lambda x: 2*x**2 - x - 1
print(goldenSearch(-10,10,fun,0.01))

斐波那契法

斐波那契法是分割法求解一维极小值问题的最优策略，而黄金分割法只是近似最优。
求极小值的斐波那契法实现流程如下。
#斐波那契法
import math
class Fibs:
def __init__(self):
      self.a = 0
      self.b = 1
def __next__(self):
      self.a, self.b = self.b, self.a + self.b
      return self.a
def __iter__(self):
      return self
def FibsSearch(a,b,fun,epsilon = 0.01,delta = 0.001):
ctrl = math.ceil((b-a)/epsilon)
i = 0
fibs = Fibs()
F = []
for f in fibs:
      if f > ctrl:
         break
      else:
         F.append(f)
         i += 1
F.insert(0,0)
n = len(F) - 1

x1 = a + F[n-2]/F[n] * (b-a)
x2 = a + F[n-1]/F[n] * (b-a)
f1 = fun(x1)
f2 = fun(x2)
print(a, &#39;\t&#39;, b, &#39;\t&#39;, fun(x1), &#39;\t&#39;, fun(x2))

for k in range(1,n-1):
      if k == n-2:
         i = k
         break
      if f1 > f2:
         a = x1
         x1 = x2
         x2 = a + F[n-k-1]/F[n-k] * (b-a)
         f1 = fun(x1)
         f2 = fun(x2)
      else:
         b = x2
         x2 = x1
         x1 = a + F[n-k-2]/F[n-k] * (b-a)
         f1 = fun(x1)
         f2 = fun(x2)
      print(a,&#39;\t&#39;, b,&#39;\t&#39;, fun(x1),&#39;\t&#39;, fun(x2))
k = i
x1 = x1
x2 = x1 + delta
f1 = fun(x1)
f2 = fun(x2)
if f1 > f2:
      a = x1
else:
      b = x2
print(a,&#39;\t&#39;,b,&#39;\t&#39;,fun(x1),&#39;\t&#39;,fun(x2))
return a,b,fun(x1),fun(x2)
if __name__ == &#39;__main__&#39;:
fun = lambda x: 2 * x ** 2 - x - 1
print(FibsSearch(-1,1,fun,0.16,0.01))
1.2.2 函数逼近法

牛顿法

我们首先介绍解方程的牛顿迭代法，即常说的切线迭代法，其选取一个可微函数上的初始点 $x_1$ ,在其处作切线，在切线与 $x$ 轴交点处作垂线与函数得到一个新的交点作为 $x_2$ ，如此不断迭代。
容易得到牛顿迭代法的迭代公式为
$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$
而极值优化中的牛顿法则可以看作是对 $f'$ 通过切线法求解零点，从而求解函数的驻点，这要求函数是二阶可微的。
很明显牛顿迭代法是一个局部算法，初始点的选取对算法的收敛性和收敛速度有很大影响
牛顿迭代法的计算步骤：

取初始点 $x_0$ ,允许误差 $\varepsilon$ ,计数器 $k=0$ .
若 $\parallel f'(x_k) \parallel < \varepsilon$ ，停止迭代，得到 $x_*=x_k$ .
否则，根据迭代公式计算 $x_{k+1}$ ,置 $k=k+1$ ，回到（2）.

割线法
抛物线法

本文使用 Zhihu On VSCode 创作并发布

		自动登录	找回密码
密码			立即注册