Implementing Optimization Algorithms in C++
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
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, and is implemented based on my own understanding.
It mainly consists of two parts: mathematical derivation and C++ implementation.
Mathematical Derivation
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.
3. Interior Point Algorithm
Implement the algorithm according to the derivation above.
Complete code is in ConvexOptimization/InteriorPointMethod/.
Running Results
Using the interior point method to solve this linear programming problem, most points can converge to (0, 0), as shown below.
[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.
Reference Links
Special greater-than-or-equal notation for determining positive semidefinite matrices
Lasso sparse constraint + Group Lasso least angle regression algorithm
[3] Soft Thresholding
Soft Thresholding is a very common function. I wrote notes based on the following article:
Understanding the Soft Thresholding function
[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
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:
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.
The image below is a standard lasso example. Its Prox Mapping is shown here:
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:
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
ADMM optimization algorithm, with MATLAB code
Distributed computing, statistical learning, and ADMM
Solving the Fused LASSO problem with ADMM
Below are my own notes:
C++ Implementation
Implementation link:
https://github.com/yufeiran/ConvexOptimization/tree/main/ConvexOptimization/1dFussedLassoUseADMM
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.
Result from the course slides:
