凸优化整理(二)

接凸优化整理

基于线搜索的下降算法基本思路

1. 给定初始点(x^0)，k=0；
2. 判断(x^k)是否满足终止条件：是，则终止；
3. 寻找(x^k)处的下降方向(d^k)；
4. 选择合适的步长(α_k)>0，使得

；

1. 令

；令k=k+1；转第1步。

这里的终止条件一般为∇f((x^k))=0，但是在实际计算的时候，我们不会直接判断为0，而是二范数小于一个非常小的数，如(10^{-4})或者(10^{-6})

(||∇f(x^k)||_2)≤ɛ，这个ɛ就是这个非常小的数。

如果f(x)是凸函数的时候，就已经找到了最优解；如果f(x)是非凸函数的时候，是一个困难问题，此时我们依然会使用梯度为0为终止条件，这样至少可以找到一个平稳点，它有可能是一个局部解。

终止条件也可以是如果(||x^k-x^{k+N}||_2)≤ɛ，说明又经过了N次迭代(N会根据实际的问题来取)，并没有发生太大的改变，依然还是在一个非常小的邻域中，此时也可以终止。又有f((x^k))-f((x^{k+N}))≤ɛ，说明经过了N次迭代，函数值的改变是非常小的，此时也可以终止。

下降方向：可以使用负梯度方向，-∇f((x^k))，这里称为最速下降法。它的收敛速度会比较慢。负梯度方向不是唯一选择，还有牛顿方向，共轭梯度方向等等。

步长：可以将α代入到函数中，f((x^k)+α(d^k))=Φ(α)，这是一个关于α的一元函数，这里就是求该一元函数最小

min Φ(α)，α≥0

我们在确定这个(α_k)的过程就称为一维线搜索问题。

收敛性问题：点列

首先得是收敛的，不能是发散的。不同的算法产生的点列，对于评价算法好坏会有一个“收敛速度”的概念。

线搜索方法

求解一元问题

，其解记为(α^*).

• 如果f(x)为简单函数，如

，如何线搜索？

这是一个二次函数，

为二次项，H为正定的海塞矩阵；

为线性项；b为常数。

由于H正定，则f(x)为一个凸函数，将f(x)代入 Φ(α)有

Φ(α)=(1\over 2)((x^k+αd^k)^TH)((x^k+αd^k))+(c^T) ((x^k+αd^k))+b

       =(1\over 2)((d^k)^TH)(d^k)(α^2)+(((d^k)^TH)(x^k)+(c^T)(d^k))α+b

进行线搜索，就是求

min Φ(α)，由于α的二次项系数是大于0的，故这是一个开口向上的一元二次函数求最小，则直接导数为0即可。

Φ'(α)=((d^k)^TH)(d^k)α+ ((d^k)^TH)(x^k)+(c^T)(d^k)=0

(α^*)=-((d^k)^THx^k+c^Td^k\over (d^k)^THd^k)

基于搜索区间的直接搜索法

我们的问题是min Φ(α)，α>0

什么是搜索区间？包含(α^*)；单谷(single basin)；记为(a_0,b_0)

单谷是在一个区间中，Φ(α)函数图像形如上图，先单调递减，再单调递增。这样的一个区间 (a_0,b_0)称为搜索区间。