> ## Content Index > Fetch the complete content index at: https://cms.yufeiran.com/llms.txt > Use this file to discover other available public pages before exploring further. # 最优化算法c++实现 - URL: https://cms.yufeiran.com/zui-you-hua-suan-fa-shi-xian-nei-dian-fa/ - Published: 2022-10-19T19:14:46.000Z - Updated: 2026-10-05T14:57:37.000Z - Author: Feiran Yu - Tags: #legacy-import # 背景 最优化方法是一门关于找凸函数的最值点的一系列方法，本文会介绍一些最优化方法的原理以及使用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)求解线性规划问题](https://zhuanlan.zhihu.com/p/34426575?ref=cms.yufeiran.com)，根据自己的理解进行实现。 主要分为两部分：数学推导和C++实现 ## 数学推导 ![—-_20221020135921](https://yufeiran.com/content/images/2022/10/----_20221020135921.jpg) ![—-_20221020135953](https://yufeiran.com/content/images/2022/10/----_20221020135953.jpg) ![netwon](https://yufeiran.com/content/images/2022/11/netwon.jpeg) ## C++实现 实现一个可视化的内点法，主要结构由：向量矩阵运算库、可视化框架和内点法算法组成。 ### 1.向量矩阵运算库 至少需要支持矩阵和向量的乘法 ### 2.可视化框架 这里使用之前写的[miniEngine2D](https://github.com/miniProduction/miniEngine2D?ref=cms.yufeiran.com) ### 3.内点法算法 根据前面的推导实现算法 完整代码在[ConvexOptimization/InteriorPointMethod/](https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/InteriorPointMethod?ref=cms.yufeiran.com)中 ## 运行结果 用内点法计算该线性规划问题，如图所示，绝大部分点都可以收敛到（0，0） ![QQ–20221023222152](https://yufeiran.com/content/images/2022/10/QQ--20221023222152.png) ![QQ–20221024153115](https://yufeiran.com/content/images/2022/10/QQ--20221024153115.png) ![QQ–20221024153122](https://yufeiran.com/content/images/2022/10/QQ--20221024153122.png) # \[2\] 2d fused lasso ## 背景 最优化，是应用数学的一个分支。主要研究在特定情况下最大化或最小化某一特定函数或变量。 通过C++实现经典代码有助于深入理解其数学原理。今天先来实现一个基础的最优化算法2d fused lasso ## 2d fused lasso 目标如下图所示，通过这个2d fused lasso算法，可以将加了噪声的图像尽量的复原。 ![QQ–20221024155721](https://yufeiran.com/content/images/2022/10/QQ--20221024155721.png) ## 参考链接 [【学界/编码】凸优化算法 I: 内点法(interior point method)求解线性规划问题](https://zhuanlan.zhihu.com/p/34426575?ref=cms.yufeiran.com) [判定(半)正定矩阵的特殊大于(等于)简写符号](https://www.cnblogs.com/CreatorKou/p/10134821.html?ref=cms.yufeiran.com) [Sparse fused lasso tutorial](https://statweb.stanford.edu/~bjk/regreg/fusedtutorial.html?ref=cms.yufeiran.com) [Lasso 稀疏约束 + Group Lasso 分组最小角回归算法](https://cloud.tencent.com/developer/article/1835226?ref=cms.yufeiran.com) # \[3\] Soft Thresholding Soft Thresholding是一个非常常见的函数，这里我根据下面这篇文章自己写了一个笔记。 [软阈值(Soft Thresholding)函数解读](https://blog.csdn.net/jbb0523/article/details/52103257?ref=cms.yufeiran.com) ![ffae4ca86e8efee8b405aaabd1e02fa](https://yufeiran.com/content/images/2022/11/ffae4ca86e8efee8b405aaabd1e02fa.jpg) ![64e47058aaa3404000243457b6d1aca](https://yufeiran.com/content/images/2022/11/64e47058aaa3404000243457b6d1aca.jpg) ![3973B9AA-258C-42B0-919C-44C99CBBB94B](https://yufeiran.com/content/images/2022/11/3973B9AA-258C-42B0-919C-44C99CBBB94B.jpeg) # \[4\] Proximal gradient descent ## 背景 近似梯度法 (Proximal gradient method)是一种广义投影形式，用于解决不可微的凸优化问题。这样就可以使得很多问题能够用梯度下降法解出来。 ## 内容 ![—-_20221102150423](https://yufeiran.com/content/images/2022/11/----_20221102150423.png) ![—-_20221102150517](https://yufeiran.com/content/images/2022/11/----_20221102150517.png) ps：零范数是所有非0元素数量 一范数是所有元素绝对值之和 二范数是所有元素平方之和的开方 公式中的二范数是矩阵二范数，可以看成形如AT\*A 的形式，这里注意一下倒数第二行变到倒数第一行，它这个不是直接等于的，看我下面写的把最后一行那个二范数平方打开： ![—-_20221102154909](https://yufeiran.com/content/images/2022/11/----_20221102154909.jpg) 它们实际上不相等，但是，整个式子关心的是对z求最小值，其余的元素都看作常数，对常数加减不影响z取多少时整个式子最小！所以我们可以将配不上的最后一项直接改成g（x），这样就能得到二阶展开的式子。 将上面最后一行的式子用proxt(x)替换，我们可以得到一个迭代公式！用这个迭代公式就能不断迭代出解。 ![—-_20221102164029](https://yufeiran.com/content/images/2022/11/----_20221102164029.png) 下图是一个标准的lasso例子，它的Prox Mapping如图所示： ![—-_20221107095219](https://yufeiran.com/content/images/2022/11/----_20221107095219.png) 根据最优化算法学习-Soft Thresholding这里的介绍，我们发现lasso 的Prox Mapping刚好等于soft-thresholding 算子！于是我们可以得到一个用soft-thresholding的迭代公式： ![3bbb546568723b67de1b1abe4e1a511](https://yufeiran.com/content/images/2022/11/3bbb546568723b67de1b1abe4e1a511.jpg) 不需要求矩阵的逆！ # \[5\] ADMM ## 背景 Alternating Direction Method of Multipliers（ADMM）是这门课老师说的对我们最重要的算法，所以需要特别掌握。 计划使用ADMM算法解决1d Fused LASSO问题。 ## 内容 这个写的最好[凸优化|笔记整理（B）——再看交替方向乘子法（ADMM），Frank-Wolfe方法](https://zhuanlan.zhihu.com/p/267542995?ref=cms.yufeiran.com) [ADMM优化算法（附MATLAB代码）](https://zhuanlan.zhihu.com/p/286235184?ref=cms.yufeiran.com) [分布式计算、统计学习与ADMM算法](https://joegaotao.github.io/2014/02/11/admm-stat-compute/?ref=cms.yufeiran.com) [ADMM算法解Fused LASSO问题](https://zhuanlan.zhihu.com/p/432779076?ref=cms.yufeiran.com) 下面是我自己做的笔记： ![—-18](https://yufeiran.com/content/images/2022/11/----18.jpg) ![—-19](https://yufeiran.com/content/images/2022/11/----19.jpg) ## C++实现 实现代码链接： [https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/1dFussedLassoUseADMM](https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/1dFussedLassoUseADMM?ref=cms.yufeiran.com) ## 实现效果 ρ取0.3，λ取0.3时的效果如下图所示，虽然可以拟合一个比较平滑的曲线，但是对比课件中的算法感觉还是有差距，我推测是由于我的数值计算没有经过特殊处理，全都是用C++的double默认计算。 ![QQ–20221127223325](https://yufeiran.com/content/images/2022/11/QQ--20221127223325.png) 课件中的效果： ![QQ–20221127222926](https://yufeiran.com/content/images/2022/11/QQ--20221127222926.png)