Abstract Approximating a function with a finite series, e.g., involving polynomials or trigonometric functions, is a critical tool in computing and data analysis. The construction of such approximations via now-standard approaches like least squares or compressive sampling does not ensure that the approximation adheres to certain convex linear structural constraints, such as positivity or monotonicity. Existing approaches that ensure such structure are norm-dissipative and this can have a deleterious impact when applying these approaches, e.g., when numerical solving partial differential equations. We present a new framework that enforces via optimization such structure on approximations and is simultaneously norm-preserving. This results in a conceptually simple convex optimization problem on the sphere, but the feasible set for such problems can be very complex. We establish well-posedness of the optimization problem through results on spherical convexity and design several spherical-projection-based algorithms to numerically compute the solution. Finally, we demonstrate the effectiveness of this approach through several numerical examples.
more »
« less
On approximating minimizers of convex functionals with a convexity constraint by singular Abreu equations without uniform convexity
Abstract We revisit the problem of approximating minimizers of certain convex functionals subject to a convexity constraint by solutions of fourth order equations of Abreu type. This approximation problem was studied in previous articles of Carlier–Radice (Approximation of variational problems with a convexity constraint by PDEs of Abreu type. Calc. Var. Partial Differential Equations 58 (2019), no. 5, Art. 170) and the author (Singular Abreu equations and minimizers of convex functionals with a convexity constraint, arXiv:1811.02355v3, Comm. Pure Appl. Math. , to appear), under the uniform convexity of both the Lagrangian and constraint barrier. By introducing a new approximating scheme, we completely remove the uniform convexity of both the Lagrangian and constraint barrier. Our analysis is applicable to variational problems motivated by the original 2D Rochet–Choné model in the monopolist's problem in Economics, and variational problems arising in the analysis of wrinkling patterns in floating elastic shells in Elasticity.
more »
« less
- Award ID(s):
- 1764248
- NSF-PAR ID:
- 10157537
- Date Published:
- Journal Name:
- Proceedings of the Royal Society of Edinburgh: Section A Mathematics
- ISSN:
- 0308-2105
- Page Range / eLocation ID:
- 1 to 21
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract Combining the classical theory of optimal transport with modern operator splitting techniques, we develop a new numerical method for nonlinear, nonlocal partial differential equations, arising in models of porous media, materials science, and biological swarming. Our method proceeds as follows: first, we discretize in time, either via the classical JKO scheme or via a novel Crank–Nicolson-type method we introduce. Next, we use the Benamou–Brenier dynamical characterization of the Wasserstein distance to reduce computing the solution of the discrete time equations to solving fully discrete minimization problems, with strictly convex objective functions and linear constraints. Third, we compute the minimizers by applying a recently introduced, provably convergent primal dual splitting scheme for three operators (Yan in J Sci Comput 1–20, 2018). By leveraging the PDEs’ underlying variational structure, our method overcomes stability issues present in previous numerical work built on explicit time discretizations, which suffer due to the equations’ strong nonlinearities and degeneracies. Our method is also naturally positivity and mass preserving and, in the case of the JKO scheme, energy decreasing. We prove that minimizers of the fully discrete problem converge to minimizers of the spatially continuous, discrete time problem as the spatial discretization is refined. We conclude with simulations of nonlinear PDEs and Wasserstein geodesics in one and two dimensions that illustrate the key properties of our approach, including higher-order convergence our novel Crank–Nicolson-type method, when compared to the classical JKO method.more » « less
-
more » « less
Abstract We present a new feasible proximal gradient method for constrained optimization where both the objective and constraint functions are given by summation of a smooth, possibly nonconvex function and a convex simple function. The algorithm converts the original problem into a sequence of convex subproblems. Formulating those subproblems requires the evaluation of at most one gradient-value of the original objective and constraint functions. Either exact or approximate subproblems solutions can be computed efficiently in many cases. An important feature of the algorithm is the constraint level parameter. By carefully increasing this level for each subproblem, we provide a simple solution to overcome the challenge of bounding the Lagrangian multipliers and show that the algorithm follows a strictly feasible solution path till convergence to the stationary point. We develop a simple, proximal gradient descent type analysis, showing that the complexity bound of this new algorithm is comparable to gradient descent for the unconstrained setting which is new in the literature. Exploiting this new design and analysis technique, we extend our algorithms to some more challenging constrained optimization problems where (1) the objective is a stochastic or finite-sum function, and (2) structured nonsmooth functions replace smooth components of both objective and constraint functions. Complexity results for these problems also seem to be new in the literature. Finally, our method can also be applied to convex function constrained problems where we show complexities similar to the proximal gradient method.
-
more » « less
Abstract In this study, a mixed finite element model for 3D nonlinear elasticity using a Hu–Washizu (HW) type variational principle is presented. This mixed variational principle takes the deformed configuration and sections from its cotangent bundle as the input arguments. The critical points of the proposed HW functional enforce compatibility of these sections with the configuration, in addition to mechanical equilibrium and constitutive relations. Using this variational principle we construct a mixed FE approximation that distinguishes a vector from a 1‐form, a feature not commonly found in FE approximations for nonlinear elasticity. This distinction plays a pivotal role in identifying suitable FE spaces for approximating the 1‐forms appearing in the variational principle. These discrete approximations are constructed using ideas borrowed from finite element exterior calculus, which are in turn used to construct a discrete approximation to our HW functional. The discrete equations describing mechanical equilibrium, compatibility, and constitutive rule, are obtained by seeking extremum of the discrete functional with respect to the respective degrees of freedom. The discrete extremum problem is then solved numerically; we use Newton's method for this purpose. This mixed FE technique is then applied to a few benchmark problems wherein conventional displacement based approximations encounter locking and checker boarding. These studies help establish that our mixed FE approximation, which requires no artificial stabilizing terms, is free of these numerical bottlenecks.
-
more » « less
Abstract We consider the following basic geometric problem:
Given , a 2‐dimensional black‐and‐white figure is ∊ ‐far from convex if it differs in at least an ∊ fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is ∊ ‐far from convex are needed to detect a violation of convexity with constant probability? This question arises in the context of designing property testers for convexity.We show that
uniform samples (and the same running time) are necessary and sufficient for detecting a violation of convexity in an ∊ ‐far figure and, equivalently, for testing convexity of figures with 1‐sided error. Our algorithm beats thelower bound by Schmeltz [32] on the number of samples required for learning convex figures under the uniform distribution. It demonstrates that, with uniform samples, we can check if a set is approximately convex much faster than we can find an approximate representation of a convex set.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/prm.2020.18
