融合Lasso分位数回归的半光滑牛顿法
Semismooth Newton Method for Fused-Lasso Quantile Regression
摘要: 目的:针对带融合Lasso惩罚的高维分位数回归中,原始空间交替方向乘子法(ADMM)仅具一阶收敛、迭代次数多、计算耗时长的问题,构造一种可利用解的稀疏与分段常数结构的二阶算法。方法:引入残差变量与系数差变量将问题分裂为可分离形式,借助Fenchel共轭推导对偶问题,把高维系数空间压缩到低维对偶变量空间;建立增广拉格朗日框架克服检验损失引起的对偶退化,并将内子问题归结为箱约束上的强半光滑残差方程,用投影半光滑牛顿法结合活跃集策略求解,再以Sherman-Morrison-Woodbury恒等式把牛顿系统由自由变量维数降到活跃变量维数。结果:在对偶广义雅可比非奇异的条件下,证明内层牛顿法局部超线性收敛、精确求解时二次收敛,外层增广拉格朗日迭代全局收敛且渐近线性。正态误差下的模拟实验表明,相较QFLASSO,所提QFL-SSNAL以更少的迭代次数和更短的运行时间达到相同的估计精度。结论:QFL-SSNAL为带空间或顺序结构的高维稀疏分位数回归提供了一种高效可靠的求解方法。
Abstract: Objective: In high-dimensional quantile regression with the fused-Lasso penalty, primal-space alternating direction methods of multipliers (ADMM) enjoy only first-order convergence and require many iterations and long running time. This paper aims to develop a second-order algorithm that exploits both the sparsity and the piecewise-constant structure of the solution. Methods: Auxiliary variables for the residual and for the successive coefficient differences are introduced to split the problem into a separable form. The dual problem is derived through Fenchel conjugation, compressing the high-dimensional coefficient space into a low-dimensional dual variable space. An augmented Lagrangian framework is established to overcome the degeneracy of the dual problem caused by the check loss. The inner subproblems are reformulated as strongly semismooth residual equations over a box constraint and solved by a projected semismooth Newton method with an active-set strategy. The Newton system is further reduced from the dimension of free variables to that of active variables via the Sherman-Morrison-Woodbury identity. Results: Under the nonsingularity of a generalized dual Jacobian, the inner Newton method is shown to converge locally superlinearly, and quadratically when the Newton system is solved exactly; the outer augmented Lagrangian iterations converge globally with an asymptotic linear rate. Simulation experiments under normal errors show that, compared with QFLASSO, the proposed QFL-SSNAL attains the same estimation accuracy with markedly fewer iterations and shorter running time. Conclusion: QFL-SSNAL provides an efficient and reliable solver for high-dimensional sparse quantile regression with spatial or ordered structure.
文章引用:文广建, 姚胜伟, 罗楚微. 融合Lasso分位数回归的半光滑牛顿法[J]. 应用数学进展, 2026, 15(11): 129-138. https://doi.org/10.12677/aam.2026.1511437

参考文献

[1] Koenker, R. and Bassett, G. (1978) Regression Quantiles. Econometrica, 46, 33-50.
https://doi.org/10.2307/1913643
[2] Tibshirani, R. (1996) Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58, 267-288.
https://doi.org/10.1111/j.2517-6161.1996.tb02080.x
[3] Belloni, A. and Chernozhukov, V. (2011) ℓ1-Penalized Quantile Regression in High-Dimensional Sparse Models. The Annals of Statistics, 39, 82-130.
https://doi.org/10.1214/10-aos827
[4] Zhang, C. (2010) Nearly Unbiased Variable Selection under Minimax Concave Penalty. The Annals of Statistics, 38, 894-942.
https://doi.org/10.1214/09-aos729
[5] Tibshirani, R., Saunders, M., Rosset, S., Zhu, J. and Knight, K. (2005) Sparsity and Smoothness via the Fused Lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 67, 91-108.
https://doi.org/10.1111/j.1467-9868.2005.00490.x
[6] Gu, Y., Fan, J., Kong, L., Ma, S. and Zou, H. (2018) ADMM for High-Dimensional Sparse Penalized Quantile Regression. Technometrics, 60, 319-331.
https://doi.org/10.1080/00401706.2017.1345703
[7] Chen, L., Sun, D. and Toh, K. (2016) A Note on the Convergence of ADMM for Linearly Constrained Convex Optimization Problems. Computational Optimization and Applications, 66, 327-343.
https://doi.org/10.1007/s10589-016-9864-7
[8] Wu, X., Liang, R., Zhang, Z. and Cui, Z. (2025) Multi-Block Linearized Alternating Direction Method for Sparse Fused Lasso Modeling Problems. Applied Mathematical Modelling, 137, Article 115694.
https://doi.org/10.1016/j.apm.2024.115694
[9] Mirzaeifard, R., Venkategowda, N.K.D., Gogineni, V.C. and Werner, S. (2023) Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties. IEEE Open Journal of Signal Processing, 5, 213-228.
https://doi.org/10.1109/ojsp.2023.3344395
[10] Li, X., Sun, D. and Toh, K. (2018) A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems. SIAM Journal on Optimization, 28, 433-458.
https://doi.org/10.1137/16m1097572
[11] Rockafellar, R.T. (1997) Convex Analysis. Princeton University Press.
[12] Combettes, P.L. and Wajs, V.R. (2005) Signal Recovery by Proximal Forward-Backward Splitting. Multiscale Modeling & Simulation, 4, 1168-1200.
https://doi.org/10.1137/050626090
[13] Rockafellar, R.T. (1976) Monotone Operators and the Proximal Point Algorithm. SIAM Journal on Control and Optimization, 14, 877-898.
https://doi.org/10.1137/0314056
[14] Li, X., Sun, D. and Toh, K. (2018) On Efficiently Solving the Subproblems of a Level-Set Method for Fused Lasso Problems. SIAM Journal on Optimization, 28, 1842-1866.
https://doi.org/10.1137/17m1136390
[15] Robinson, S.M. (1981) Some Continuity Properties of Polyhedral Multifunctions. Mathematical Programming Studies, 14, 206-214.
https://doi.org/10.1007/bfb0120929
[16] Qi, L. and Sun, J. (1993) A Nonsmooth Version of Newton’s Method. Mathematical Programming, 58, 353-367.
https://doi.org/10.1007/bf01581275
[17] Facchinei, F. and Pang, J.-S. (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer.
[18] Lima, M.V.S., Ferreira, T.N., Martins, W.A. and Diniz, P.S.R. (2014) Sparsity-Aware Data-Selective Adaptive Filters. IEEE Transactions on Signal Processing, 62, 4557-4572.
https://doi.org/10.1109/tsp.2014.2334560