# How can I verify that my algorithm finds the minimum of a convex program?

I'm testing out an algorithm for the lasso. That is, the problem is to find the $$\beta$$ which solves the following:

$$\min\frac{1}{2} \left\| y-X\beta\right\|_2^2 + \lambda \|\beta\|_1$$

How can I verify that the $$\beta$$ I find with my algorithm is the minimum? A few ideas I had:

• I could try several values of $$\beta$$ in a random search, but as $$\beta$$ is normally a vector (normally sized 100 and above) this is very computationally expensive
• Checking how the convex cost changes. I've looked at how the evaluation of the convex optimisation problem changes throughout the algorithm, and it does indeed decrease until it flattens out. I'm not sure this is sufficient proof though.
• Can I generate data where I know what the minimum is?
• You could compare your results with that of an existing algorithm Sep 16, 2022 at 8:32
• @Henry In terms of the obtained $\beta$ or the convex function cost? I've done this and achieved a lower minimum, but the $\beta$ values don't really match. Sep 16, 2022 at 9:32
• I was thinking you could take $y,X,\lambda$ and compare the $\beta$ results, perhaps several times with different $y,X,\lambda$ Sep 16, 2022 at 9:44
• @Henry I have done that and whilst there is some agreement with $\beta$, it's not that strong. But like I mentioned, the $\beta$ obtained from my algorithm achieves a lower minimum. So I'm not sure what to make of it. Sep 16, 2022 at 9:46
• If you can reduce that to a small example, it might be worth editing your question to show what $y,X,λ$ you used and what $\beta$ results you get from the two algorithms Sep 16, 2022 at 9:51