凸优化笔记第九周

fwalker

梯度下降算法在机器学习理论和凸优化理论中都是非常重要的方法，凸优化里的梯度下降算法重在理论分析。
梯度下降算法

我们讨论的是无约束的优化问题，我们希望目标函数 最小，因此我们想要找到这样的一个x：


梯度下降算法是用来求解这样的x的，当下降算法迭代到终止条件时，得到的x近似于最优点。
数学形式

初始化：给定定义域内的初始点x
循环进行：
       1.
       2. 确定步长
       3. 更新  
直到 满足终止条件

任何的下降算法都有三个要素：下降方向、步长选择、终止条件。对于梯度下降算法，其下降方向选择的是负梯度方向，步长选择方向下面会讲三种：固定步长法、精确搜索算法、回溯搜索算法。终止条件一般自己设置，比如梯度的范数小于某一个值就作为终止条件。

为什么要选择负梯度作为下降方向？

我们不妨设现在在x0，想要使优化函数值下降。
那么在x0处对函数Taylor展开：


假如我们沿着d方向，走了t步，那么有：


函数的变化值：


假设我们步长很小，即t很小，那么后面的高阶项可以了近似忽略，也就有：


这个 就类似于内积，选择 会是其值最小。
刚刚说步长很小，那么如果步长不小呢？步长很大，沿着负梯度就未必是最小的了。沿着负梯度走很长的步，最终函数值也有可能增加。但是，我们这种优化问题只是考虑的局部信息，不知道全局信息，如果从局部来看，负梯度是相对来说比较好的选择方向。
梯度下降算法会收敛吗？

我们会有一个疑惑，采用梯度下降算法会不会收敛？是不是会在最优值附近来回移动？比如下面这张图：


如果我们步长选择不合适的话，梯度下降算法有可能像上图那样不收敛。那么如何用数学的语言去研究这个算法是否收敛呢？目前来看，不动点理论可以很好的讨论这一问题。
我们可以将迭代过程视为一个映射T(x)。那么梯度下降算法对应的迭代映射可以写为 。考虑到步长t根据x的取值，因此准确表示为x的函数t(x)。所以映射准确应该写为 。
我们定义满足下面条件的映射被称为压缩映射T(x)：

对于任意x,y都成立。
对于压缩映射，存在Banach fixed point定理：
如果T()是一个压缩映射，那么：
1.存在唯一的一个 ，使得 （该点被称为不动点）。
2.任意一个x， 定义一个序列 ，有：


第一个结论说明，压缩映射存在唯一一个不动点，如果这个映射是迭代过程的话，该不动点有：




这说明不动点就是局部最优点，而对于凸函数，局部最优点也是全局最优点，因此不动点就是我们要找的全局最优点。
第二个结论说明，任意一个点在压缩映射下，会不断地接近不动点，且收敛速度可以用  刻画。
我们梳理一下，下降算法的迭代过程都能够用映射表示，如果这个映射是一个压缩映射，那么在不断地迭代过程中，会收敛到不动点（最优点），且收敛速度可以由  保证。
因此，我们只要证明这个下降算法的迭代过程是一个压缩映射，就能够证明该算法收敛，且得到其收敛速度上界。
凸函数的强凸性

对于一般的凸函数，我们很难去直接分析其迭代过程（是否是一个压缩映射），因此，我们需要对凸函数进行加强，研究一些具有特殊性质的凸函数。人们发现，具有强凸性的凸函数，其下降算法能够得到很好的理论分析。
数学形式（强凸性）

一个凸函数具有强凸性，意味着：

这里的小于等于号不是数值意义上的，不是指  里的每个元素都大于等于 中对应位置的元素值。这个小于等于号是广义不等式，对应的是半正定锥。等价于 、 是半正定锥。等价于  矩阵特征值在 集合内。

强凸性推导出一些重要性质

我们来讨论强凸性下凸函数的下降算法。下面的所有部分由默认了前凸性这一前提条件。
在 这一下降过程：
利用Taylor公式：
根据强凸性：




两边同时选择  ，使得值最小（注意左右两边选择的  可能不同，但是不等式依然成立）
那么左边最小就是最优值( )，右式最小就对应于一个二次函数的最小值( )。
因此，
同理也有：


综上，得到一个性质：


也可以证明：


结合(3)、（4），有：


（3）、（4）、（5）这三个不等式，刻画的是 三者之间的关系。这三个工具足够我们讨论梯度下降算法的收敛性了。
简单梳理一下，我们在算法理论处说如果一个下降算法对应的映射能够被证明是压缩映射，那么这个算法会收敛到最优点，且收敛速度可以由压缩系数  刻画。后来，我们讨论了凸函数的强凸性，因为一般的凸函数很难被证明是压缩映射，但是具有强凸性的凸函数，其对应的梯度下降算法，可以被证明是压缩映射。因此，之后的目标就是：
利用强凸性以及凸函数本身具有的性质，证明下降算法是否有压缩映射。
下降算法中步长选择有多种方法，本篇文章只讨论三种，下面会分别证明其是否具有压缩映射。
选择步长

固定步长法

固定步长，顾名思义，步长是一个常数，因此固定步长的下降算法的映射： 。
对于任意x,y， 有


最后一个等式，用了插值定理。
两边同时取范数：


现在就拆出了压缩映射的形式。 是A的特征值最大绝对值（数学定义是谱半径）。F(A)将二维矩阵映射成立一维值。


m,M分别是强凸性里的定义的两个数。我们取  (1 - tm + 1 - tM = 0)，此时压缩系数被放缩的最小，因此，该算法对应的压缩系数：



，只要选择步长 ，该算法一定收敛，且收敛速度可以刻画（已知了  ）。
可以看到，固定步长法选择根据m,M，才能选择步长t，否则且收敛性不能被保证。我们可能知道这个凸函数是强凸性的，但是不知道具体的界限m,M。这个时候，需要自适应的选择t。后面两种算法都是这个思路。
精确直线搜索

在选择步长前，我们已经知道里下降方向d，那一个想法就是，选择的步长使其最小：


需要研究这种搜索方式的收敛性及收敛速度，虽然直观上看，f(x)是越来越小，看起来可能收敛。




两边同时选择t，使其最小，这样左边就是我们精确直线搜索一步后的值：


利用（3）：




其中， 是x经过一次精确直线搜索后的值，可以看到，出现了指数收敛。
回溯直线搜索

该搜索首先选择两个超参数 。
选取步长过程如下：






简单解释：这个算法希望找到的是能减少一定量的步长，可能初学者会有疑问，这个t不断的乘以 这一个系数，会陷入循环跳出出来吗？当t足够小的时候， 。而 （d是负梯度方向），所以t足够小，会跳出循环。
收敛性分析：


右边是上界，如果上界成立，也即：


也即：


那么则有：


所以只要满足 ，就会跳出  循环。
考虑到t有一个初始值，因此，我们得到最终跳出循环的t，一定满足 。




这个也会保证回溯直线搜索指数收敛。
简单的demo

优化问题




优化问题

代码实现

/*
* Author: houzhinan
* Date: 2021-11-13
* Last Modified: 2021-11-13 19:38
* Desc: progarmming for Homework 9
*/

#include <iostream>
#include <vector>
#include <fstream>

std::vector<std::vector<float>> A({{1.0,0.0},{0.0,100.0}});
float alpha = 0.4;
float beta = 0.5;

/**************************************************
                Formulation
1. object function
2. gradient
3. termination condition
**************************************************/

// object function f(x)
float function(std::vector<float> x){
    return 0.5*x[0]*x[0]*A[0][0] + 0.5*x[1]*x[1]*A[1][1];
}

// gradient
std::vector<float> getGradient(std::vector<float> x){
    return std::vector<float>({A[0][0]*x[0], A[1][1]*x[1]});
}

// termination condition
bool isEnded(std::vector<float> x){
    std::vector<float> gradient = getGradient(x);
    float norm = gradient[0] * gradient[0] + gradient[1] * gradient[1];
    return (norm < 0.0001);
}

/**************************************************
                Solution
1.calculate the gradient as descent direction
2.calculate step size by three method
2.1 constant step size
2.2 backtracking line search
2.3 exact line search
3. I/O
4. main function
**************************************************/

// descent direction - negative gradient
std::vector<float> getDescentDirection(std::vector<float> x){
    std::vector<float> gradient = getGradient(x);
    return std::vector<float>({-1*gradient[0], -1*gradient[1]});
}

// constant step size
float getConstantStep(std::vector<float> x){
    float step = 2.0 / (A[0][0] + A[1][1]);
    return step;
}

// backtracking line search
float getBackTrackingStep(std::vector<float> x){
    float step = 1.0;
    std::vector<float> gradient = getGradient(x);
    std::vector<float> direction = getDescentDirection(x);
    while(function(std::vector<float>({x[0] + step*direction[0], x[1] + step*direction[1]}))
          >= function(x) + alpha*step*(gradient[0]*direction[0] + gradient[1]*direction[1])
         ){
        step = beta * step;
    }
    return step;
}

// exact line search
float getExactLineStep(std::vector<float> x){
    // step = argmin_t f(x + t*d)
    std::vector<float> direction = getDescentDirection(x);
   
    float step = -1 * (A[0][0] * x[0] * direction[0] + A[1][1] * x[1] * direction[1])
                / (A[0][0] * direction[0] * direction[0] + A[1][1] * direction[1] * direction[1]);

    return step;
}



// output into txt
void output(std::vector<std::vector<float>> result, std::string filename){
    //TODO:
    std::ofstream fout(filename);
    for(auto point:result){
        fout << point[0] << "," << point[1] << ',' << point[2] << std::endl;   
    }
    fout.close();
}

int main(){
    //1. initialize
    std::vector<float> x({100, 1});
    std::vector<std::vector<float>> result;
    result.push_back(std::vector<float>({x[0], x[1], function(x)}));
    //2. algorithm
    while(!isEnded(x)){
        //2.1 get descent direction
        std::vector<float> direction = getDescentDirection(x);
        //2.2 get step size
        float step = getConstantStep(x);
        //2.3 move x
        x[0] += step * direction[0];
        x[1] += step * direction[1];
        //2.4 save result
        result.push_back(std::vector<float>({x[0], x[1], function(x)}));
    }
    //3. output
    output(result, "./Result/constant_step.txt");
    return 0;
}可视化结果




固定步长法迭代过程



精确直线搜索迭代过程



回溯直线搜索迭代过程

一些工程上的思考

上面的demo只是针对这一个函数，并没有进一步泛化到一般的优化目标函数。比如不再是二维的而是多维的，精确直线搜索不再能够直接求出，而需要迭代才能求出步长....
这个就涉及到复杂的求解器实现了，或许等我大四下学期有空闲时间了，再搞一搞这种优化器设计。
梯度下降法有问题吗？

以精确搜索为例，（6）式告诉我们：


收敛速度 。
当 时，目标优化函数等高线类似于一个个圆，这个时候迭代非常快，因为梯度直接指向圆心。
当 时，目标优化函数等高线类似于一个个非常扁的圆，这个时候会来回震荡非常麻烦。

时，梯度下降算法迭代慢，人们加以改进，例如将椭圆变化到圆（牛顿法）。或者引入动量来克服震荡（动量法）...