1. 第一章 概论

1.1. 评价函数

  • 对于无约束,越是迭代,评价函数下降即可
  • 有约束,就得加上限制:是可行点

1.2. 收敛

若不可能有限步找到最优解,就要顾及到收敛速度

ek=xkxlimkek+1ek=C \begin{aligned} e_k=x_k-x^*\\ \lim _{k \rightarrow \infty} \frac {||e_{k+1}||}{||e_k||}=C \end{aligned}

这叫CC为因子rr阶收敛于xx^*

  • 线性收敛:ek+1Cek||e_{k+1}||\leq C||e_k||
  • 超线性收敛:比前者快,多数如此。

limkek+1ekn=Climkek+1ek=C×limkekn1 \begin{aligned} \lim _{k \rightarrow \infty} \frac {||e_{k+1}||}{||e_k||^n}=C \\ \lim _{k \rightarrow \infty} \frac {||e_{k+1}||}{||e_k||}=C \times \lim _{k \rightarrow \infty} {||e_k||}^{n-1} \end{aligned}

  1. local minimun f(x)=0,2f(x)0\Longrightarrow \nabla f(x)=0, \nabla ^2 f(x) \geq 0
  2. f(x)=2f(x)\nabla f(x)=\nabla ^2 f(x)\Longrightarrow local minimum ,eg. y=x3y=x^3

1.3. 迭代下降优化算法

寻找一个搜索方向dkd_k使得每次迭代时函数值减小。

首先选取初始点x0x_0
loop until xk+1x_{k+1}满足终止条件:

  • 构造搜索方向dkd_k
  • 根据 d_k d\_k 确定步长 λ_k\lambda \_k
  • xk+1=xk+λkdkx_{k+1}=x_k+\lambda_k d_k

    需要考虑的问题:

  • 往哪个方向走?d_kd\_{k}

  • 走多远?λk\lambda_k
  • 能找到xx_*吗?
  • 多快能找到?

下面从典型的无优化约束算法开始:

results matching ""

    No results matching ""