> ## 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. # Implementing Optimization Algorithms in C++ - URL: https://cms.yufeiran.com/en-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: #lang-en, #legacy-import # Background Optimization methods are a series of methods for finding extrema of convex functions. This article introduces the principles of several optimization methods and their C++ implementations. Code: [https://github.com/yufeiran/ConvexOptimization](https://github.com/yufeiran/ConvexOptimization?ref=cms.yufeiran.com) # Contents \[1\] Interior point method \[2\] 2D fused lasso \[3\] Soft Thresholding \[4\] Proximal gradient descent \[5\] ADMM # \[1\] Interior Point Method This implementation mainly refers to [Convex Optimization Algorithm I: using the interior point method to solve linear programming problems](https://zhuanlan.zhihu.com/p/34426575?ref=cms.yufeiran.com), and is implemented based on my own understanding. It mainly consists of two parts: mathematical derivation and C++ implementation. ## Mathematical Derivation ![interior point derivation](https://yufeiran.com/content/images/2022/10/----_20221020135921.jpg) ![interior point derivation](https://yufeiran.com/content/images/2022/10/----_20221020135953.jpg) ![newton](https://yufeiran.com/content/images/2022/11/netwon.jpeg) ## C++ Implementation I implemented a visualized interior point method. The main structure consists of a vector/matrix operation library, a visualization framework, and the interior point algorithm. ### 1\. Vector and Matrix Operation Library At minimum, it needs to support matrix-vector multiplication. ### 2\. Visualization Framework Here I used my earlier [miniEngine2D](https://github.com/miniProduction/miniEngine2D?ref=cms.yufeiran.com). ### 3\. Interior Point Algorithm Implement the algorithm according to the derivation above. Complete code is in [ConvexOptimization/InteriorPointMethod/](https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/InteriorPointMethod?ref=cms.yufeiran.com). ## Running Results Using the interior point method to solve this linear programming problem, most points can converge to `(0, 0)`, as shown below. ![result](https://yufeiran.com/content/images/2022/10/QQ--20221023222152.png) ![result](https://yufeiran.com/content/images/2022/10/QQ--20221024153115.png) ![result](https://yufeiran.com/content/images/2022/10/QQ--20221024153122.png) # \[2\] 2D Fused Lasso ## Background Optimization is a branch of applied mathematics. It mainly studies how to maximize or minimize a specific function or variable under certain conditions. Implementing classic algorithms in C++ helps me understand their mathematical principles more deeply. Today I first implement a basic optimization algorithm: 2D fused lasso. ## 2D Fused Lasso The goal is shown below. Through the 2D fused lasso algorithm, a noisy image can be restored as much as possible. ![2d fused lasso](https://yufeiran.com/content/images/2022/10/QQ--20221024155721.png) ## Reference Links [Convex Optimization Algorithm I: using the interior point method to solve linear programming problems](https://zhuanlan.zhihu.com/p/34426575?ref=cms.yufeiran.com) [Special greater-than-or-equal notation for determining positive semidefinite matrices](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 sparse constraint + Group Lasso least angle regression algorithm](https://cloud.tencent.com/developer/article/1835226?ref=cms.yufeiran.com) # \[3\] Soft Thresholding Soft Thresholding is a very common function. I wrote notes based on the following article: [Understanding the Soft Thresholding function](https://blog.csdn.net/jbb0523/article/details/52103257?ref=cms.yufeiran.com) ![soft thresholding](https://yufeiran.com/content/images/2022/11/ffae4ca86e8efee8b405aaabd1e02fa.jpg) ![soft thresholding](https://yufeiran.com/content/images/2022/11/64e47058aaa3404000243457b6d1aca.jpg) ![soft thresholding](https://yufeiran.com/content/images/2022/11/3973B9AA-258C-42B0-919C-44C99CBBB94B.jpeg) # \[4\] Proximal Gradient Descent ## Background The proximal gradient method is a generalized projection form used to solve nonsmooth convex optimization problems. It allows many problems to be solved with gradient descent. ## Content ![proximal gradient notes](https://yufeiran.com/content/images/2022/11/----_20221102150423.png) ![proximal gradient notes](https://yufeiran.com/content/images/2022/11/----_20221102150517.png) Note: the zero norm is the number of nonzero elements. The L1 norm is the sum of absolute values of all elements. The L2 norm is the square root of the sum of squares of all elements. The L2 norm in the formula is a matrix L2 norm and can be seen as a form like `A^T * A`. Pay attention to the transition from the second-to-last line to the last line. It is not directly equal. I expand the squared L2 norm in the last line below: ![derivation](https://yufeiran.com/content/images/2022/11/----_20221102154909.jpg) They are not actually equal. But the whole expression cares about minimizing with respect to `z`; all other elements are treated as constants. Adding or subtracting constants does not affect the value of `z` that minimizes the expression. So we can directly replace the mismatched final term with `g(x)`, yielding the second-order expansion. Replacing the last expression above with `prox_t(x)` gives an iterative formula. Using this formula, we can keep iterating to obtain the solution. ![prox iteration](https://yufeiran.com/content/images/2022/11/----_20221102164029.png) The image below is a standard lasso example. Its Prox Mapping is shown here: ![prox mapping](https://yufeiran.com/content/images/2022/11/----_20221107095219.png) According to the introduction in Optimization Algorithm Study: Soft Thresholding, the Prox Mapping of lasso is exactly the soft-thresholding operator. So we can obtain an iterative formula using soft-thresholding: ![soft threshold iteration](https://yufeiran.com/content/images/2022/11/3bbb546568723b67de1b1abe4e1a511.jpg) No matrix inverse is needed. # \[5\] ADMM ## Background The Alternating Direction Method of Multipliers, ADMM, is the algorithm that our course teacher said is most important for us, so it needs to be mastered carefully. I plan to use ADMM to solve the 1D Fused LASSO problem. ## Content The best notes I found are: [Convex optimization notes B: revisiting ADMM and Frank-Wolfe](https://zhuanlan.zhihu.com/p/267542995?ref=cms.yufeiran.com) [ADMM optimization algorithm, with MATLAB code](https://zhuanlan.zhihu.com/p/286235184?ref=cms.yufeiran.com) [Distributed computing, statistical learning, and ADMM](https://joegaotao.github.io/2014/02/11/admm-stat-compute/?ref=cms.yufeiran.com) [Solving the Fused LASSO problem with ADMM](https://zhuanlan.zhihu.com/p/432779076?ref=cms.yufeiran.com) Below are my own notes: ![ADMM notes](https://yufeiran.com/content/images/2022/11/----18.jpg) ![ADMM notes](https://yufeiran.com/content/images/2022/11/----19.jpg) ## C++ Implementation Implementation link: [https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/1dFussedLassoUseADMM](https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/1dFussedLassoUseADMM?ref=cms.yufeiran.com) ## Result When ( \\rho = 0.3 ) and ( \\lambda = 0.3 ), the result is shown below. It can fit a relatively smooth curve, but compared with the algorithm in the course slides, there is still a gap. I guess this is because my numerical computation has not been specially handled; everything uses C++ `double` by default. ![ADMM result](https://yufeiran.com/content/images/2022/11/QQ--20221127223325.png) Result from the course slides: ![course result](https://yufeiran.com/content/images/2022/11/QQ--20221127222926.png)