Linear-step solvability of some folded concave and singly-parametric sparse optimization problems
Linear-step solvability of some folded concave and singly-parametric sparse optimization problems
复制标题
DOI：
10.1007/s10107-021-01766-4
复制
发表时间：
2022-01
影响因子：
2.7
通讯作者：
A. Gómez;Ziyu He;J. Pang
中科院分区：
文献类型：
--
作者：
A. Gómez;Ziyu He;J. Pang
本文研究了由两两分离目标定义的统计估计稀疏优化问题的几种版本。稀疏性（即）函数由一个折叠凹函数近似；两两分离产生了z型目标。在给出几个实际的估计问题来说明z结构之后，我们引入了一种线性阶跃内外环算法来计算非凸不可微折叠凹稀疏性问题的方向平稳解。当专门化到一个带z矩阵的二次损失函数和一个分段二次折叠凹稀疏函数时，该算法的总体复杂度在问题的变量数上是一个低阶多项式；因此，该算法在这种二次情况下是强多项式的。我们还考虑了该问题的参数化版本，该问题具有加权正则器和带（隐藏）z矩阵的二次损失函数。我们提出了两种情况下的线性步进算法，这取决于变量是否有规定的符号或未知的符号。在这两种情况下，都提出了一种参数化算法，并在适当的权值条件下证明了其强多项式性。该参数算法可与区间搜索方案相结合，用于选择参数以优化二层设置中的二级目标函数。该分析利用了z函数的最小元素性质，对于二次损失函数，利用了具有隐藏z矩阵的线性互补问题的强多项式可解性。后一类矩阵的起源可以追溯到Olvi Mangasarian的一篇鼓舞人心的论文，我们将本文献给他。
This paper studies several versions of the sparse optimization problem in statistical estimation defined by a pairwise separation objective. The sparsity (i.e.,) function is approximated by a folded concave function; the pairwise separation gives rise to an objective of the Z-type. After presenting several realistic estimation problems to illustrate the Z-structure, we introduce a linear-step inner-outer loop algorithm for computing a directional stationary solution of the nonconvex nondifferentiable folded concave sparsity problem. When specialized to a quadratic loss function with a Z-matrix and a piecewise quadratic folded concave sparsity function, the overall complexity of the algorithm is a low-order polynomial in the number of variables of the problem; thus the algorithm is strongly polynomial in this quadratic case. We also consider the parametric version of the problem that has a weighted-regularizer and a quadratic loss function with a (hidden) Z-matrix. We present a linear-step algorithm in two cases depending on whether the variables have prescribed signs or with unknown signs. In both cases, a parametric algorithm is presented and its strong polynomiality is established under suitable conditions on the weights. Such a parametric algorithm can be combined with an interval search scheme for choosing the parameter to optimize a secondary objective function in a bilevel setting. The analysis makes use of a least-element property of a Z-function, and, for the case of a quadratic loss function, the strongly polynomial solvability of a linear complementarity problem with a hidden Z-matrix. The origin of the latter class of matrices can be traced to an inspirational paper of Olvi Mangasarian to whom we dedicate our present work.