Approximating optimization problems over convex functions
From MaRDI portal
normconvergenceapproximationfinite difference approximationHessian matrixoptimization problemsequencediscrete convex function\(L^2(L^1)\) projectionpositive semidefinite discrete Hessiansemidefinite programming codesspace \(H^K (\Omega)\)spaces \(H^K (\Omega)\), \(L^2 (\Omega)\), \(L^1 (\Omega)\), \(L^\infty (\Omega)\)
Numerical optimization and variational techniques (65K10) Convex programming (90C25) Numerical methods based on nonlinear programming (49M37) Semidefinite programming (90C22) Computational aspects related to convexity (52B55) Existence theories for free problems in two or more independent variables (49J10)
Abstract: Many problems of theoretical and practical interest involve finding an optimum over a family of convex functions. For instance, finding the projection on the convex functions in , and optimizing functionals arising from some problems in economics. In the continuous setting and assuming smoothness, the convexity constraints may be given locally by asking the Hessian matrix to be positive semidefinite, but in making discrete approximations two difficulties arise: the continuous solutions may be not smooth, and functions with positive semidefinite discrete Hessian need not be convex in a discrete sense. Previous work has concentrated on non-local descriptions of convexity, making the number of constraints to grow super-linearly with the number of nodes even in dimension 2, and these descriptions are very difficult to extend to higher dimensions. In this paper we propose a finite difference approximation using positive semidefinite programs and discrete Hessians, and prove convergence under very general conditions, even when the continuous solution is not smooth, working on any dimension, and requiring a linear number of constraints in the number of nodes. Using semidefinite programming codes, we show concrete examples of approximations to problems in two and three dimensions.
Recommendations
- On Convex Functions and the Finite Element Method
- Approximation of convex functions by projections of polyhedra
- Discretization method for semi-definite programming
- Conforming approximation of convex functions with the finite element method
- Structure-preserving function approximation via convex optimization
Cites work
- scientific article; zbMATH DE number 1130740 (Why is no real title available?)
- A numerical approach to variational problems subject to convexity constraint
- CSDP, A C library for semidefinite programming
- Consistency and power in tests with shape-restricted alternatives
- Consistency in concave regression
- Convex Analysis
- Estimating a Convex Function in Nonparametric Regression
- Estimation of a convex function: Characterizations and asymptotic theory.
- Extremal points of a functional on the set of convex functions
- Ironing, Sweeping, and Multidimensional Screening
- Minimizing within Convex Bodies Using a Convex Hull Method
- Minimum Problems over Sets of Concave Functions and Related Questions
- Multidimensional mechanism design: revenue maximization and the multiple-good monopoly
- Newton's problem of the body of minimal resistance in the class of convex developable functions
- Regularity of solutions for some variational problems subject to a convexity constraint.
- Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.
- Semidefinite Programming
- The variation of the spectrum of a normal matrix
- Weakly Differentiable Functions
Cited in
(23)- On standard finite difference discretizations of the elliptic Monge-Ampère equation
- Scaling, proximity, and optimization of integrally convex functions
- Semidefinite approximations of the matrix logarithm
- Programming with semilocally convex functions
- Convex and convex-like optimization over a range inclusion problem and first applications
- Convex approximations in stochastic programming by semidefinite programming
- Solving multidimensional screening problems using a generalized single crossing property
- On the optimality of pure bundling for a monopolist
- On the edge-independence number and edge-covering number for regular graphs
- The numerical solution of Newton's problem of least resistance
- Convergence and Approximation of Optimization Problems
- Approximating parameterized convex optimization problems
- An iterated projection approach to variational problems under generalized convexity constraints
- The optimal value and optimal solutions of the proximal average of convex functions
- An approximation method for the optimization of continuous functions ofnvariables by densifying their domains
- A two-dimensional problem of revenue maximization
- On uniform consistent estimators for convex regression
- Structure-preserving function approximation via convex optimization
- An algorithm for computing solutions of variational problems with global convexity constraints
- Approximation to nonproper problems of convex programming
- Performance optimization over positive \(l_\infty\) cones
- Adaptive, anisotropic and hierarchical cones of discrete convex functions
- Convex optimization of interval valued functions on mixed domains
This page was built for publication: Approximating optimization problems over convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q957934)
