NExOS.jl
¶Shuvomoy Das Gupta
The sparse regression problem (also known as regressor selection problem) is concerned with approximating a vector $b\in\mathbf{R}^{m}$ with a linear combination of at most $k$ columns of a matrix $A\in\mathbf{R}^{m\times d}$ with bounded coefficients. The problem can be written as the following optimization problem $$ \begin{equation} \begin{array}{ll} \textrm{minimize} & \|Ax-b\|_{2}^{2}+\frac{\beta}{2}\|x\|^{2}\\ \textrm{subject to} & \mathbf{card}(x)\leq k\\ & \|x\|_{\infty}\leq M, \end{array} \end{equation} $$ where $x\in\mathbf{R}^{d}$ is the decision variable, and $A\in\mathbf{R}^{m\times d},b\in\mathbf{R}^{m},$ and $M>0$ are problem data.
First, load the packages.
using Random, NExOS, ProximalOperators
Let us generate some random data for this problem.
m = 25
n = 50
A = randn(m,n)
b = randn(m)
M = 100
k = convert(Int64, round(m/3))
beta = 10^-10
1.0000000000000006e-10
Create the problem instance in NExOS
.
C = SparseSet(M, k) # Create the set
f = LeastSquares(A, b, iterative = true) # Create the function
settings = Settings(μ_max = 2, μ_mult_fact = 0.85, verbose = false, freq = 250, γ_updt_rule = :adaptive, β = beta) # settings
z0 = zeros(n) # create an initial point
problem = Problem(f, C, settings.β, z0) # problem instance
Problem{ProximalOperators.LeastSquaresIterative{1,Float64,Float64,Array{Float64,2},Array{Float64,1},ProximalOperators.AAc},SparseSet{Int64,Int64},Float64,Array{Float64,1}}(description : Least squares penalty domain : n/a expression : n/a parameters : n/a, SparseSet{Int64,Int64}(100, 8), 1.0000000000000006e-10, [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 … 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
Time to solve the problem.
state_final = solve!(problem, settings)
State{Array{Float64,1},Int64,Float64}([0.24701000766550982, -0.24356676418901654, 5.398080115334404e-8, -3.4929684602205246e-9, 2.6065156412524142e-8, 1.5946069144306067e-8, -7.630900321164644e-9, 3.907322609359914e-9, -3.972535918634318e-8, -2.317536490058187e-9 … -3.069384498367188e-9, 9.744408143847951e-9, -1.2217929273801725e-8, -2.9938485516205667e-8, 1.2370000675166513e-9, -0.2324999125397446, -5.372515086168684e-9, 0.5657579002049802, -3.4057851523858884e-8, 2.9848750351434576e-8], [0.24701000772586093, -0.24356676425942392, 5.7244326295707174e-8, -3.7041633897196132e-9, 2.7640953104422848e-8, 1.691009427084463e-8, -8.092314755556757e-9, 4.1435552164323004e-9, -4.2127065930870655e-8, -2.4576877899582207e-9 … -3.2550197141275017e-9, 1.0333505843181107e-8, -1.2956586048500635e-8, -3.1748567496928025e-8, 1.3116831310921374e-9, -0.23249991218033036, -5.697292475655342e-9, 0.5657579004409481, -3.611700315797661e-8, 3.165346638765637e-8], [0.24701000766550976, -0.2435667641890165, -5.3690129855456e-7, 3.474180488783803e-8, -2.592477377230451e-7, -1.586017446844432e-7, 7.589884391165743e-8, -3.886290048478037e-8, 3.9511475131091067e-7, 2.305098150516354e-8 … 3.052927946946281e-8, -9.691915181179844e-8, 1.2152134699676747e-7, 2.977736466590621e-7, -1.2302334444824045e-8, -0.2324999125397446, 5.3435551293638174e-8, 0.5657579002049802, 3.3874574390849054e-7, -2.9688173793408416e-7], 2, 3.9235795081516326e-9, 6.882125117023454e-8, 9.385625688121253e-9, 9.68794389337658e-8)
Let us take a look at the quality of the solution.
log10(state_final.fxd_pnt_gap) <= -4 # if the fixed point gap is less than 10^-4 (to determin if the algorithm has converged)
true
log10(state_final.fsblt_gap) <= -4 # this is to test if the found solution by NExOS is locally optimal
true
f(state_final.x) # this gives the objective value of the solution found by NExOS
3.510658260563844