Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

• 成果类型: Article
• 署名作者: He, Ziyu; Han, Shaoning; Gomez, Andres; Cui, Ying; Pang, Jong-Shi
• 署名单位: University of Southern California; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01966-0
• 发表日期: 2024
• 页码: 517-566
• 关键词: space search algorithm; markov random-fields; scalable algorithms; variable selection; optimization; formulations; optimality

摘要

This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the l(0)-path where the discontinuous l(0)-function provides the exact sparsity count; the l(1)-path where the l(1)-function provides a convex surrogate of sparsity count; and the capped l(1)-path where the nonconvex nondifferentiable capped l(1)-function aims to enhance the l(1)-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped l(1)-path. Our study of the capped l(1)-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped l(1)-regularized problem offers interesting theoretical properties and practical compromise between the l(0)-path and the l(1)-path. Indeed, while the l(0)-path is computationally prohibitive and greatly handicapped by the repeated solution ofmixed-integer nonlinear programs, the quality of l(1)-path, in terms of the two criteria-loss and sparsity-in the estimation objective, is inferior to the capped l(1)-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.