Search for: All records

In this paper, we have studied a decomposition method for solving a class of non-convex two-stage stochastic programs, where both the objective and constraints of the second-stageproblem are nonlinearly parameterized by the first-stage variables. Due to the failure of the Clarkeregularity of the resulting nonconvex recourse function, classical decomposition approaches such asBenders decomposition and (augmented) Lagrangian-based algorithms cannot be directly generalizedto solve such models. By exploring an implicitly convex-concave structure of the recourse function,we introduce a novel decomposition framework based on the so-called partial Moreau envelope. Thealgorithm successively generates strongly convex quadratic approximations of the recourse functionbased on the solutions of the second-stage convex subproblems and adds them to the first-stage mas-ter problem. Convergence has been established for both a fixed number of scenarios and a sequentialinternal sampling strategy. Numerical experiments are conducted to demonstrate the effectiveness of the proposed algorithm. 

In this paper, we focus on the computation of the nonparametric maximum likelihood es- timator (NPMLE) in multivariate mixture models. Our approach discretizes this infinite dimensional convex optimization problem by setting fixed support points for the NPMLE and optimizing over the mixing proportions. We propose an efficient and scalable semis- mooth Newton based augmented Lagrangian method (ALM). Our algorithm outperforms the state-of-the-art methods (Kim et al., 2020; Koenker and Gu, 2017), capable of handling n ≈ 106 data points with m ≈ 104 support points. A key advantage of our approach is its strategic utilization of the solution’s sparsity, leading to structured sparsity in Hessian computations. As a result, our algorithm demonstrates better scaling in terms of m when compared to the mixsqp method (Kim et al., 2020). The computed NPMLE can be directly applied to denoising the observations in the framework of empirical Bayes. We propose new denoising estimands in this context along with their consistent estimates. Extensive nu- merical experiments are conducted to illustrate the efficiency of our ALM. In particular, we employ our method to analyze two astronomy data sets: (i) Gaia-TGAS Catalog (Anderson et al., 2018) containing approximately 1.4 × 106 data points in two dimensions, and (ii) a data set from the APOGEE survey (Majewski et al., 2017) with approximately 2.7 × 104 data points. 

Abstract 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 “$$\ell _0$$ ${\ell }_0$-path” where the discontinuous$$\ell _0$$ ${\ell }_0$-function provides the exact sparsity count; the “$$\ell _1$$ ${\ell }_1$-path” where the$$\ell _1$$ ${\ell }_1$-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$ ${\ell }_1$-path” where the nonconvex nondifferentiable capped$$\ell _1$$ ${\ell }_1$-function aims to enhance the$$\ell _1$$ ${\ell }_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$$\ell _1$$ ${\ell }_1$-path. Our study of the capped$$\ell _1$$ ${\ell }_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$$\ell _1$$ ${\ell }_1$-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$ ${\ell }_0$-path and the$$\ell _1$$ ${\ell }_1$-path. Indeed, while the$$\ell _0$$ ${\ell }_0$-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$ ${\ell }_1$-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$ ${\ell }_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. 

The largest mass extinction event is associated with changes in degassing style of the Siberian Traps volcanism.