Linear-time convexity test for low-order piecewise polynomials

DOI10.1137/19M1290851MaRDI QIDQ5857296zbMATH OpenOpenAlexFDO

Authors Shambhavi Singh, Yves Lucet

Publication date 31 March 2021

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/19m1290851

zbMATH Keywords

convex constraintsconvexity testdifference definiteoptimizationpiecewise cubic functionspiecewise linear-quadratic functions

Mathematics Subject Classification ID

Convexity of real functions of several variables, generalizations (26B25) Nonsmooth analysis (49J52) Convex functions and convex programs in convex geometry (52A41) Convex programming (90C25)

Recommendations

• On convexity of piecewise polynomial functions on triangulations
• Piecewise-convex maximization problems: algorithm and computational experiments
• On the convexity of piecewise-defined functions
• Piecewise-convex maximization problems.
• On the structure of convex piecewise quadratic functions

Cites work

• H^1-projection into the set of convex functions: A saddle-point formulation
• A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions
• A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation
• A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings
• A numerical method for variational problems with convexity constraints
• A technique to derive the analytical form of convex envelopes for some bivariate functions
• Adaptive, anisotropic and hierarchical cones of discrete convex functions
• An algorithm for computing solutions of variational problems with global convexity constraints
• An iterated projection approach to variational problems under generalized convexity constraints
• Characterizing and testing subdifferential regularity in piecewise smooth optimization
• Conforming approximation of convex functions with the finite element method
• Convex parametric piecewise quadratic optimization: theory and algorithms
• Cubic regularization of Newton method and its global performance
• Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization
• Faster than the fast Legendre transform, the linear-time Legendre transform
• Global optimization based on local searches
• Handling Convexity-Like Constraints in Variational Problems
• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 446509 (Why is no real title available?)
• scientific article; zbMATH DE number 1807400 (Why is no real title available?)
• scientific article; zbMATH DE number 5351713 (Why is no real title available?)
• scientific article; zbMATH DE number 477581 (Why is no real title available?)
• scientific article; zbMATH DE number 1894735 (Why is no real title available?)
• scientific article; zbMATH DE number 776091 (Why is no real title available?)
• scientific article; zbMATH DE number 3078450 (Why is no real title available?)
• Minimizing within Convex Bodies Using a Convex Hull Method
• Network flows. Theory, algorithms, and applications.
• NON-CONVERGENCE RESULT FOR CONFORMAL APPROXIMATION OF VARIATIONAL PROBLEMS SUBJECT TO A CONVEXITY CONSTRAINT
• Noncoincidence of approximate and limiting subdifferentials of integral functionals
• On Newton's problem of minimal resistance
• On the convexity of piecewise-defined functions
• On the structure of convex piecewise quadratic functions
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes
• Regularity of solutions for some variational problems subject to a convexity constraint.
• Sparse/Robust Estimation and Kalman Smoothing with Nonsmooth Log-Concave Densities: Modeling, Computation, and Theory
• The minimum of quadratic functionals of the gradient on the set of convex functions
• The piecewise linear-quadratic model for computational convex analysis
• Two problems in economics
• Variational Analysis
• What shape is your conjugate? A survey of computational convex analysis and its applications

Cited in

(5)

• Linear interval parametric approach to testing pseudoconvexity
• A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions
• Closest univariate convex linear-quadratic function approximation with minimal number of pieces
• Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
• An efficient local approach to convexity testing of piecewise-linear hypersurfaces

Describes a project that uses

Uses Software

• na13
• Matlab

This page was built for publication: Linear-time convexity test for low-order piecewise polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5857296)