最优化方法：一、总论

主要参考书目：
1. 最优化方法及其应用/郭科，陈聆，魏友华.-北京：高等教育出版社,2007.7(2013.7重印)

1、优化问题的一般形式

其中G(X)=[g1(X),⋯,gl(X)]T$G(X)=[g_1(X),\cdots ,g_l(X){]}^T$，H(X)=[h1(X),⋯,hm(X)]T$H(X)=[h_1(X),\cdots ,h_m(X){]}^T$。

2、优化问题的迭代解法

解析法只适用于某些简单或特殊的问题，一帮情况下，使用迭代法解决优化问题。

• 收敛速度
  定义：设由算法A产生的迭代点列{Xk}$\{X_k\}$在某种“||⋅||$||\cdot ||$”的意义下收敛于点X∗$X^{\ast }$,即

  limk→0||Xk−X∗||=0,$$\underset{k\to 0}{lim}||X_k-X^{\ast }||=0,$$
  若存在实数 及一个与迭代次数k无关的常数 q>0$q>0$，使得
  limk→0||Xk+1−X∗||||Xk−X∗||α=q,$$\underset{k\to 0}{lim}{\displaystyle \frac{||X_{k+1}-X^{\ast }||}{||X_k-X^{\ast }|{|}^{\alpha }}}=q,$$
  则称算法A为a阶收敛算法。
  一般来说一个算法若能满足a>1$a>1$,即是一个收敛较快的算法。
  这种定义是对应于“爬山”算法定义的，对于退火（其实问题不大，因为k趋于无穷时更差的解被接受的概率趋于0）和遗传等方法不能直接套用

• 计算终止准则
  1.点距准则
  

  ||Xk+1−Xk||≤ε$$||X_{k+1}-X_k||\le \epsilon$$
  
  ε$\epsilon$是一个充分小的数，反应计算精度。
  2.函数下降量准则
  
  |f(Xk+1)−f(Xk)|≤ε$$|f(X_{k+1})-f(X_k)|\le \epsilon$$
  
  当|f(Xk+1)|>1$|f(X_{k+1})|>1$时，可用：
  
  |f(Xk+1)−f(Xk)f(Xk+1)|≤ε$$|{\displaystyle \frac{f(X_{k+1})-f(X_k)}{f(X_{k+1})}}|\le \epsilon$$
  
  ε$\epsilon$是一个充分小的数，反应计算精度。
  3.梯度准则
  
  ||▽f(Xk+1)||≤ε$$||▽f(X_{k+1})||\le \epsilon$$
  
  这一准则对于定义域上的凸函数没有问题，但是对于凹函数有可能误把驻点作为最优点

• 基本流程
  （以爬山算法为例）
  

3、算法复杂度

• 时间复杂度
  若对于规模为n的问题，需要进行T(n)$T(n)$步基本运算（加减乘除）来完成该算法。则该算法的时间复杂度为T(n)$T(n)$。
• 空间复杂度
  算法执行时所需占用的存储单元。

一般我们认为多项式级的复杂度是可以被接受的。