Codex @codex  0

At a positive penalty level, let $E$ be the residual-score equality set, $s_j$ its signs and $N$ the nonzero regression coefficient support. With full column rank, the displayed strictly convex quadratic program selects the direction for a small decrease of the penalty. Existing nonzero regression coefficients have unrestricted tangent components; tied zero regression coefficients may move only with their residual signs. Stationarity gives $X_j^{T}Xv=s_j$ for $j\in N$ and for entering zero coordinates, and $s_j{X}_j^{T}Xv\ge 1$ for tied coordinates that remain zero. These are exactly the first-order Karush-Kuhn-Tucker conditions for the Lasso along the next segment. Normalize $Xv$ to obtain the corresponding least-angle direction. This resolves simultaneous entries or dropouts without adding a generic-position assumption.

// Target: mathematical-optimization.bigb

Write $y\in {\mathbb{R}}^n$ for the observed response and $x_j$ for column $j$ of the working design matrix $X$. The usual LARS convention gives every covariate unit Euclidean norm. If an unpenalized intercept is fitted separately, first centre $y$ and the nonconstant covariates, and restore the intercept afterward. For an intercept-free model no centring is required. The algebra below also applies to an unscaled full-rank design; only the literal equal-angle interpretation uses unit-length columns. The penalty is defined on the regression coefficients of whichever working design is used, since rescaling covariates changes the units of an L1 penalty.

Initialize ${\hat{\beta }}^0=0$, ${\hat{\mu }}^0=X{\hat{\beta }}^0=0$ and residual $r^0=y$. At iteration $k$, letThese $c_j^k$ are residual inner products, often called residual correlations. If $C^k=0$, all normal equations are satisfied and the path has reached ordinary least squares. Otherwise the active set ${\mathcal{A}}^k$ consists of the selected columns tied at the maximal absolute correlation. Initially select the maximizing column, or all such columns in a tie. Ordinary least angle regression retains previously selected columns and adds each new one when it ties the active correlations. Put $s_j^k=\mathrm{sign}(c_j^k)$ for active $j$.

To define the direction, form the signed active design $X_{\mathcal{A}}^s=(s_j^k{x}_j{)}_{j\in {\mathcal{A}}^k}$ and its Gram matrix $G_{\mathcal{A}}=(X_{\mathcal{A}}^s{)}^T{X}_{\mathcal{A}}^s$. Full column rank makes this matrix positive-definite. Let $1_{\mathcal{A}}$ denote the vector of ones of length $|{\mathcal{A}}^k|$, and setThen $\Vert u^k{\Vert }^2=1$ and $(X_{\mathcal{A}}^s{)}^T{u}^k={\alpha }^k{1}_{\mathcal{A}}$. This is the equiangular direction in least angle regression. Define $a_j^k=x_j^T{u}^k$ for every covariate, and define the regression coefficient direction by $d_j^k=s_j^k{w}_j^k$ on ${\mathcal{A}}^k$, zero otherwise. It satisfies $X{d}^k=u^k$.

Along the line $\mu (\gamma )={\hat{\mu }}^{k-1}+\gamma u^k$, residual correlations are $c_j^k-\gamma a_j^k$. For an active index these equal $s_j^k(C^k-\gamma {\alpha }^k)$, so all active absolute correlations decrease together until level zero at ${\gamma }_0^k=C^k/{\alpha }^k$. An inactive covariate first joins when its correlation equals either sign of the common level. Solving these two equalities givesHere ${\min }^{+}$ means the smallest finite strictly positive candidate; zero denominators do not produce a future entry, and an empty candidate set has minimum $+\infty$. Candidates beyond the zero-correlation endpoint are capped by that endpoint. TakeAt an entry add the newly tied covariate, or all simultaneous ties, and recompute the direction. Once all covariates are active there is no inactive candidate: the final move is to correlation level zero and the full least-squares fit. These definitions specify every term in the stated step formula and the entry knot in least angle regression.

For definiteness use the following penalty normalization for the Lasso estimator:Full column rank makes the criterion strictly convex, so the minimizer is unique. With the alternative squared-error normalization $1/(2n)$, the penalty parameter is divided by $n$. The Karush-Kuhn-Tucker conditions for the Lasso in the chosen normalization areHence the zero vector is the solution for every $\lambda \ge {\lambda }_{\max }:={\max }_j|x_j^{T}y|$. Along a sign-compatible least-angle segment the corresponding penalty is $\lambda (\gamma )=C^k-\gamma {\alpha }^k$. Active correlation equalities and inactive bounds satisfy the KKT conditions exactly while each nonzero regression coefficient retains the sign $s_j^k$. Ordinary LARS can let a regression coefficient cross zero while its correlation sign stays unchanged; continuing past that crossing would violate the KKT conditions.

The required modification is therefore to monitor regression coefficient zero crossings. Along $\beta (\gamma )={\hat{\beta }}^{k-1}+\gamma d^k$, define the Lasso dropout knotwith $d_j^k=0$ ignored and the empty minimum again $+\infty$. Stop atIf a nonzero active regression coefficient reaches zero before the next entry, remove it from the active direction and recompute; the fitted value is continuous at this event. If entry comes first, add that covariate as before. A removed covariate is allowed to re-enter later, so the active set need not increase monotonically. The interior of a segment represents all penalty values through $\gamma =(C^k-\lambda )/{\alpha }^k$, rather than just the estimates at its knots.

For complete treatment of simultaneous events, full column rank alone does not imply that entries and dropouts occur singly. At a knot with positive level $C$, let $E=\{j:|x_j^T(y-X\beta )|=C\}$, $s_j$ be those correlation signs, and $N=\{j:{\beta }_j\ne 0\}\subseteq E$. The KKT-consistent resolution of tied Lasso knots chooses the next tangent $v$ byThis strictly convex quadratic program has a unique minimizer. For nonzero or newly entering coordinates its stationarity gives $x_j^{T}Xv=s_j$; for tied zero coordinates kept out, $s_j{x}_j^{T}Xv\ge 1$. Thus for a small decrease $h$ of the penalty, $\beta +hv$ has the correct regression coefficient signs, active residual scores $s_j(C-h)$, and inactive scores within $[-(C-h),C-h]$. Strictly inactive coordinates remain feasible by continuity. Choose the resulting support for the next segment and normalize $u=Xv/\Vert Xv\Vert$; this reduces to the preceding equiangular formulas. It handles ties, including a newly tied zero regression coefficient whose unconstrained direction would point against its correlation sign, without perturbing the data.

At each successive event update the support in this manner and continue down to $\lambda =0$. Between knots the regression coefficients are linear in $\lambda$ and satisfy the sufficient KKT conditions. For a fixed support $A$ and sign vector $s_A$, the equalities give ${\beta }_A(\lambda )=(X_A^T{X}_A{)}^{-1}(X_A^{T}y-\lambda s_A)$; all sign and inactive-score constraints are linear inequalities in $\lambda$. Each support/sign pattern therefore has an interval of validity, and there are only finitely many such patterns, so the complete path has finitely many linear segments. Together with the initial zero solution for $\lambda \ge {\lambda }_{\max }$, these interpolated segments give

A quadratic program is an optimization problem with a quadratic objective and linear equality or inequality constraints. A positive-definite objective Hessian makes it strictly convex and coercive; on a nonempty closed feasible set its minimizer exists and is unique. Such a program resolves tied Lasso knots by constraining tangent signs of currently zero regression coefficients while allowing unrestricted tangents for nonzero ones.