最优化算法c++实现

    背景

    最优化方法是一门关于找凸函数的最值点的一系列方法,本文会介绍一些最优化方法的原理以及使用C++的实现。
    代码在https://github.com/yufeiran/ConvexOptimization 中

    目录

    [1] 内点法(interior point method)
    [2] 2d fused lasso
    [3] Soft Thresholding
    [4] Proximal gradient descent
    [5] ADMM

    [1] 内点法(interior point method)

    主要参考这篇文章【学界/编码】凸优化算法 I: 内点法(interior point method)求解线性规划问题,根据自己的理解进行实现。
    主要分为两部分:数学推导和C++实现

    数学推导

    ----_20221020135921
    ----_20221020135953
    netwon

    C++实现

    实现一个可视化的内点法,主要结构由:向量矩阵运算库、可视化框架和内点法算法组成。

    1.向量矩阵运算库

    至少需要支持矩阵和向量的乘法

    2.可视化框架

    这里使用之前写的miniEngine2D

    3.内点法算法

    根据前面的推导实现算法
    完整代码在ConvexOptimization/InteriorPointMethod/

    运行结果

    用内点法计算该线性规划问题,如图所示,绝大部分点都可以收敛到(0,0)
    QQ--20221023222152
    QQ--20221024153115

    QQ--20221024153122

    [2] 2d fused lasso

    背景

    最优化,是应用数学的一个分支。主要研究在特定情况下最大化或最小化某一特定函数或变量。
    通过C++实现经典代码有助于深入理解其数学原理。今天先来实现一个基础的最优化算法2d fused lasso

    2d fused lasso

    目标如下图所示,通过这个2d fused lasso算法,可以将加了噪声的图像尽量的复原。
    QQ--20221024155721

    参考链接

    【学界/编码】凸优化算法 I: 内点法(interior point method)求解线性规划问题
    判定(半)正定矩阵的特殊大于(等于)简写符号
    Sparse fused lasso tutorial
    Lasso 稀疏约束 + Group Lasso 分组最小角回归算法

    [3] Soft Thresholding

    Soft Thresholding是一个非常常见的函数,这里我根据下面这篇文章自己写了一个笔记。
    软阈值(Soft Thresholding)函数解读
    ffae4ca86e8efee8b405aaabd1e02fa
    64e47058aaa3404000243457b6d1aca
    3973B9AA-258C-42B0-919C-44C99CBBB94B

    [4] Proximal gradient descent

    背景

    近似梯度法 (Proximal gradient method)是一种广义投影形式,用于解决不可微的凸优化问题。这样就可以使得很多问题能够用梯度下降法解出来。

    内容

    ----_20221102150423
    ----_20221102150517
    ps:零范数是所有非0元素数量 一范数是所有元素绝对值之和 二范数是所有元素平方之和的开方

    公式中的二范数是矩阵二范数,可以看成形如AT*A 的形式,这里注意一下倒数第二行变到倒数第一行,它这个不是直接等于的,看我下面写的把最后一行那个二范数平方打开:
    ----_20221102154909

    它们实际上不相等,但是,整个式子关心的是对z求最小值,其余的元素都看作常数,对常数加减不影响z取多少时整个式子最小!所以我们可以将配不上的最后一项直接改成g(x),这样就能得到二阶展开的式子。
    将上面最后一行的式子用proxt(x)替换,我们可以得到一个迭代公式!用这个迭代公式就能不断迭代出解。
    ----_20221102164029

    下图是一个标准的lasso例子,它的Prox Mapping如图所示:
    ----_20221107095219

    根据最优化算法学习-Soft Thresholding这里的介绍,我们发现lasso 的Prox Mapping刚好等于soft-thresholding 算子!于是我们可以得到一个用soft-thresholding的迭代公式:
    3bbb546568723b67de1b1abe4e1a511
    不需要求矩阵的逆!

    [5] ADMM

    背景

    Alternating Direction Method of Multipliers(ADMM)是这门课老师说的对我们最重要的算法,所以需要特别掌握。
    计划使用ADMM算法解决1d Fused LASSO问题。

    内容

    这个写的最好凸优化|笔记整理(B)——再看交替方向乘子法(ADMM),Frank-Wolfe方法
    ADMM优化算法(附MATLAB代码)
    分布式计算、统计学习与ADMM算法

    ADMM算法解Fused LASSO问题

    下面是我自己做的笔记:
    ----18

    ----19

    C++实现

    实现代码链接:
    https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/1dFussedLassoUseADMM

    实现效果

    ρ取0.3,λ取0.3时的效果如下图所示,虽然可以拟合一个比较平滑的曲线,但是对比课件中的算法感觉还是有差距,我推测是由于我的数值计算没有经过特殊处理,全都是用C++的double默认计算。

    QQ--20221127223325
    课件中的效果:
    QQ--20221127222926