An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
From MaRDI portal
Abstract: Shape-constrained convex regression problem deals with fitting a convex function to the observed data, where additional constraints are imposed, such as component-wise monotonicity and uniform Lipschitz continuity. This paper provides a unified framework for computing the least squares estimator of a multivariate shape-constrained convex regression function in . We prove that the least squares estimator is computable via solving an essentially constrained convex quadratic programming (QP) problem with variables, linear inequality constraints and possibly non-polyhedral inequality constraints, where is the number of data points. To efficiently solve the generally very large-scale convex QP, we design a proximal augmented Lagrangian method (proxALM) whose subproblems are solved by the semismooth Newton method (SSN). To further accelerate the computation when is huge, we design a practical implementation of the constraint generation method such that each reduced problem is efficiently solved by our proposed proxALM. Comprehensive numerical experiments, including those in the pricing of basket options and estimation of production functions in economics, demonstrate that our proposed proxALM outperforms the state-of-the-art algorithms, and the proposed acceleration technique further shortens the computation time by a large margin.
Recommendations
- A Computational Framework for Multivariate Convex Regression and Its Variants
- A dual active set algorithm for optimal sparse convex regression
- Multivariate convex regression with adaptive partitioning
- A penalized method for multivariate concave least squares with application to productivity analysis
- A Newton Method for Convex Regression, Data Smoothing, and Quadratic Programming with Bounded Constraints
Cites work
- A Computational Framework for Multivariate Convex Regression and Its Variants
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A nonsmooth version of Newton's method
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems
- Composite difference-MAX programs for modern statistical estimation problems
- Consistency in concave regression
- Consistency of multidimensional convex regression
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- scientific article; zbMATH DE number 4082855 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1862807 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Monotone Operators and the Proximal Point Algorithm
- Multivariate convex regression with adaptive partitioning
- Newton and quasi-Newton methods for normal maps with polyhedral sets
- Nonparametric least squares estimation of a multivariate convex regression function
- Nonparametric option pricing under shape restrictions
- On convergence rates of convex regression in multiple dimensions
- On efficiently solving the subproblems of a level-set method for fused lasso problems
- On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
- Point Estimates of Ordinates of Concave Functions
- Proximité et dualité dans un espace hilbertien
- Quadratic convergence of Newton's method for convex interpolation and smoothing
- Regularity and well-posedness of a dual program for convex best \(C^{1}\)-spline interpolation
- Representation theorem for convex nonparametric least squares
- Semismooth and Semiconvex Functions in Constrained Optimization
- Semismooth Matrix-Valued Functions
- Smooth minimization of non-smooth functions
- Smoothing and first order methods: a unified framework
- Some continuity properties of polyhedral multifunctions
- Sparse Convex Regression
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- The Nonparametric Approach to Demand Analysis
- The Nonparametric Approach to Production Analysis
- The statistical sleuth. A course in methods of data analysis
- Valuing American options by simulation: a simple least-squares approach
Cited in
(11)- A penalized method for multivariate concave least squares with application to productivity analysis
- Efficient second-order shape-constrained function fitting
- Multivariate convex regression with adaptive partitioning
- A Computational Framework for Multivariate Convex Regression and Its Variants
- A dual active set algorithm for optimal sparse convex regression
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- Convex support vector regression
- Subgradient regularized multivariate convex regression at scale
- An efficient CGA\_ADMM for the metric nearness problem
- An efficient algorithm for the _p norm based metric nearness problem
- Boundary problem and overfitting reduction in convex regression
This page was built for publication: An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2146447)
