We are assuming here that the regularization constraint is active. If it becomes inactive at ψ¯, the solution is optimal for any value of ψ ≥ ψ**¯. The equalities**
follow from the complementarity conditions, omitted here. Notice that other constraints may also hold with equality. The homotopy algorithm is included in **Algorithm 1.** The primal update of the algorithm traces the solution in the linear segments and the dual updates determines the update direction the sections with non-linearities.

The algorithm implementation is written with the focus on simplicity; an efficient implementation relies on factorization of the matrices. Two homotopy continuation methods - DASSO (James et al., 2009) and primal dual pursuit (Asif, **2009) - have been proposed**
for the Dantzig selector. These homotopy methods are very efficient when the problems have sparse solutions, as is often the case with Dantzig selectors.

RALP cannot be solved directly using the methods for the Dantzig selector, however, because of its different structure. This structure can be used to develop a different homotopy method for solving RALP, which is described in **Appendix B. In addition, a method** based on parametric linear program solvers has been developed for regularized linear programs. However, the parametric simplex algorithm cannot take advantage of sparse RALP solutions and therefore is not applicable to large RALP. The finite-time convergence of Algorithm 1 **can be, however, shown identically to** DASSO, or other related algorithms.