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?


The safest way to test an algorithm of this kind is to compute your results in cases where you can derive the minimum exactly through analytic methods (i.e., without relying on comparison with another algorithm that might also fail).  Thus, I would recommend you examine whether there are cases of this optimisation where the minimising value can be obtained in closed form from standard calculus techniques.  If you can find some cases of this kind then you can compare the results of your algorithm to the known minima in these cases.
