We consider the problem of approximating a semialgebraic set with a sublevel-set of a polynomial function. In this setting, it is standard to seek a minimum volume outer approximation and/or …
We consider the problem of approximating a semialgebraic set with a sublevel-set of a polynomial function. In this setting, it is standard to seek a minimum volume outer approximation and/or maximum volume inner approximation. As there is no known relationship between the coefficients of an arbitrary polynomial and the volume of its sublevel sets, previous works have proposed heuristics based on the determinant and trace objectives commonly used in ellipsoidal fitting. For the case of star-convex semialgebraic sets, we propose a novel objective which yields both an outer and an inner approximation while minimizing the ratio of their respective volumes. This objective is scale-invariant and easily interpreted. Numerical examples are given which show that the approximations obtained are often tighter than those returned by existing heuristics. We also provide methods for establishing the star-convexity of a semialgebraic set by finding inner and outer approximations of its kernel.
This letter considers the problem of approximating a semialgebraic set with a sublevel-set of a polynomial using sum-of-squares optimization. In this setting, it is standard to seek a minimum volume …
This letter considers the problem of approximating a semialgebraic set with a sublevel-set of a polynomial using sum-of-squares optimization. In this setting, it is standard to seek a minimum volume outer approximation or maximum volume inner approximation. This is made difficult by the lack of a known relationship between the coefficients of an arbitrary polynomial and the volume of its sublevel sets. Previous works have proposed heuristics based on the determinant and trace objectives commonly used in ellipsoidal fitting. We propose a novel objective which yields both an outer and an inner approximation while minimizing the ratio of their respective volumes. This objective is scale-invariant and easily interpreted. We provide justification for its use in approximating star-convex sets. Numerical examples demonstrate that the approximations obtained are often tighter than those returned by existing heuristics when applied to convex and star-convex sets. We also provide algorithms for establishing the star-convexity of a semialgebraic set by finding inner and outer approximations of its kernel.
We show that there exists, for each closed bounded convex set C in the Euclidean plane with nonempty interior, a quadrangle Q having the following two properties. Its sides support …
We show that there exists, for each closed bounded convex set C in the Euclidean plane with nonempty interior, a quadrangle Q having the following two properties. Its sides support C at the vertices of a rectangle r and at least three of the vertices of Q lie on the boundary of a rectangle R that is a dilation of r with ratio 2. We will prove that this implies that quadrangle Q is contained in rectangle R and that, consequently, the inner approximation r of C has an area of at least half the area of the outer approximation Q of C. The proof makes use of alignment or Schüttelung, an operation on convex sets.
We study $\mathbb{R}^2\oplus\mathbb{R}$-separately convex hulls of finite sets of points in $\mathbb{R}^3$, as introduced in \cite{KirchheimMullerSverak2003}. When $\mathbb{R}^3$ is considered as a certain subset of $3\times 2 $ matrices, this …
We study $\mathbb{R}^2\oplus\mathbb{R}$-separately convex hulls of finite sets of points in $\mathbb{R}^3$, as introduced in \cite{KirchheimMullerSverak2003}. When $\mathbb{R}^3$ is considered as a certain subset of $3\times 2 $ matrices, this notion of convexity corresponds to rank-one convex convexity $K^{rc}$. If $\mathbb{R}^3$ is identified instead with a subset of $2\times 3$ matrices, it actually agrees with the quasiconvex hull, due to a recent result \cite{HarrisKirchheimLin18}.
We introduce complexes, which generalize $T_n$ constructions. For a finite set a $K$-complex is a $2+1$ complex whose extremal points belong to $K$. The $2+1$-complex convex hull of $K$, $K^{cc}$, is the union of all $2+1$ $K$-complexes. We prove that $K^{cc}$ is contained in the $2+1$ convex hull $K^{rc}$.
We also consider outer approximations to $2+1$ convexity based in the locality theorem \cite[4.7]{Kirchheim2003}. Starting with a crude outer approximation we iteratively chop off $D$-prisms. For the examples in \cite{KirchheimMullerSverak2003}, and many others, this procedure reaches a $K$-complex in a finite number of steps, and thus computes the $2+1$ convex hull.
We show examples of finite sets for which this procedure does not reach the $2+1$ convex hull in finite time, but we show that a sequence of outer approximations built with $D$-prisms converges to a $2+1$ $K$-complex. We conclude that $K^{rc}$ is always a $K$-complex, which has interesting consequences.
We study $\mathbb{R}^2\oplus\mathbb{R}$-separately convex hulls of finite sets of points in $\mathbb{R}^3$, as in KirchheimMullerSverak2003. This notion of convexity, which we call $2+1$ convexity, corresponds to rank-one convex convexity, or …
We study $\mathbb{R}^2\oplus\mathbb{R}$-separately convex hulls of finite sets of points in $\mathbb{R}^3$, as in KirchheimMullerSverak2003. This notion of convexity, which we call $2+1$ convexity, corresponds to rank-one convex convexity, or quasiconvexity, when $\mathbb{R}^3$ is identified with certain subsets of matrices. We introduce '$2+1$ complexes', which generalize $T_n$ constructions, define the '$2+1$-complex convex hull of a set', and prove that it is an inner approximation to the $2+1$ convex hull. We also consider outer approximations to $2+1$ convexity based in the locality theorem of rank convexity, by iteratively chopping off '$D$-prisms'. For many finite sets, this procedure reaches a '$2+1$ $K$-complex' in a finite number of steps, and thus computes the $2+1$ convex hull. We show examples of finite sets for which this procedure does not reach the $2+1$ convex hull in a finite number of steps, but we show that there is always a sequence of outer approximations built with $D$-prisms that converges to a $2+1$ $K$-complex. We conclude that $K^{rc}$ is always a '$2+1$ $K$-complex', which has interesting consequences.
In this paper it is shown that a set is the union of k convex subsets if and only if every finite subset of it is contained in some k …
In this paper it is shown that a set is the union of k convex subsets if and only if every finite subset of it is contained in some k convex subsets of it.This is a characterization of a set as the union of a finite number of convex sets by conditions on its finite subsets.Also, a proof of McKinney's theorem for unions of two convex sets is given using similar methods.Richard McKinney has given a characterization of unions of two convex sets.In this paper a complete characterization of unions of convex sets is given, and we give another proof of McKinney's result.Here, a k-partition of a set A is a family 6P={SX, S2, ■ • • , Sk} of subsets of A, having k elements, where A¿n5,J=0 for ijtj, and (JLi S¡=S.A property F of sets is said to be hereditary if, given any set A with property F, any subset F<= S has property P. I. First, we prove a theorem which enables us to by-pass further reference to Zorn's Lemma.
So far, we have approximated functions defined on a compact set K ⊂ ℂ, and the approximating functions were polynomials or rational functions. Now we shall approximate functions defined on …
So far, we have approximated functions defined on a compact set K ⊂ ℂ, and the approximating functions were polynomials or rational functions. Now we shall approximate functions defined on a set F that is closed in a domain G. Functions analytic or meromorphic in G will serve as approximating functions. In the special case where G = ℂ, one obtains approximation by entire functions. Here the rate of approximation (as z → ∞) also plays a role. Several of these theorems can be used to construct analytic functions with complicated boundary behavior; we deal with these questions at the end of the chapter, in §5.
Abstract In a Hilbert space, or in general, in a uniformly convex Banach space E, if K is a closed convex subset of E and a ∊ E, then there …
Abstract In a Hilbert space, or in general, in a uniformly convex Banach space E, if K is a closed convex subset of E and a ∊ E, then there is a unique point x 0 ∊ K, called the best approximation of a in K, such that . In this paper, we consider the more general problem when a is replaced by a finite subset A = {a 1 a 2,…an } of a normed linear space E.
Given a convex set $\Omega$ of $\mathbb{R}^n$, we consider the shape optimization problem of finding a convex subset $\omega\subset \Omega$, of a given measure, minimizing the $p$-distance functional $$\mathcal{J}_p(\omega) := …
Given a convex set $\Omega$ of $\mathbb{R}^n$, we consider the shape optimization problem of finding a convex subset $\omega\subset \Omega$, of a given measure, minimizing the $p$-distance functional $$\mathcal{J}_p(\omega) := \left(\int_{\mathbb{S}^{n-1}} |h_\Omega-h_\omega|^p d\mathcal{H}^{n-1}\right)^{\frac{1}{p}},$$ where $1 \le p <\infty$ and $h_\omega$ and $h_\Omega$ are the support functions of $\omega$ and the fixed container $\Omega$, respectively. We prove the existence of solutions and show that this minimization problem $\Gamma$-converges, when $p$ tends to $+\infty$, towards the problem of finding a convex subset $\omega\subset \Omega$, of a given measure, minimizing the Hausdorff distance to the convex $\Omega$. In the planar case, we show that the free parts of the boundary of the optimal shapes, i.e., those that are in the interior of $\Omega$, are given by polygonal lines. Still in the $2-d$ setting, from a computational perspective, the classical method based on optimizing Fourier coefficients of support functions is not efficient, as it is unable to efficiently capture the presence of segments on the boundary of optimal shapes. We subsequently propose a method combining Fourier analysis and a recent numerical scheme, allowing to obtain accurate results, as demonstrated through numerical experiments.
In this paper,with the aid of the w~*- sequential compactness of bounded closed balls in the conjugate space of a separable space,we proved that the convex hull of a finite …
In this paper,with the aid of the w~*- sequential compactness of bounded closed balls in the conjugate space of a separable space,we proved that the convex hull of a finite union of bounded closed balls in l~∞ is closed.
In this note we give an elementary proof that an arbitrary convex function can be uniformly approximated by a convex \cinf-function on any closed bounded subinterval of the domain. An …
In this note we give an elementary proof that an arbitrary convex function can be uniformly approximated by a convex \cinf-function on any closed bounded subinterval of the domain. An interesting byproduct of our proof is a global equation for a polygonal (piecewise affine) function.
article Free Access Share on A New Convex Hull Algorithm for Planar Sets Author: William F. Eddy Department of Statistics, Carnegie-Mellon University, Schenley Park, Pittsburgh, PA Department of Statistics, Carnegie-Mellon …
article Free Access Share on A New Convex Hull Algorithm for Planar Sets Author: William F. Eddy Department of Statistics, Carnegie-Mellon University, Schenley Park, Pittsburgh, PA Department of Statistics, Carnegie-Mellon University, Schenley Park, Pittsburgh, PAView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 3Issue 4Dec. 1977 pp 398–403https://doi.org/10.1145/355759.355766Online:01 December 1977Publication History 173citation1,590DownloadsMetricsTotal Citations173Total Downloads1,590Last 12 Months148Last 6 weeks24 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
We generalize the existing formulation and results on linear separability of sets. In order to characterize the solution of the generalized problem, we use the concepts of convex hulls. For …
We generalize the existing formulation and results on linear separability of sets. In order to characterize the solution of the generalized problem, we use the concepts of convex hulls. For finite sets, it is well known the Support Vector Machine technique for finding the optimal separating hyperplane. Here we consider arbitrary sets, allowing infinite, unbounded and nonclosed sets. The problem is formulated as an optimization problem with possibly infinitely many constraints. We prove existence and uniqueness of the solution. Besides, we present some examples and counterexamples to many properties discussed in the text and statements in the literature.
Abstract Research in high energy physics (HEP) requires huge amounts of computing and storage, putting strong constraints on the code speed and resource usage. To meet these requirements, a compiled …
Abstract Research in high energy physics (HEP) requires huge amounts of computing and storage, putting strong constraints on the code speed and resource usage. To meet these requirements, a compiled high-performance language is typically used; while for physicists, who focus on the application when developing the code, better research productivity pleads for a high-level programming language. A popular approach consists of combining Python, used for the high-level interface, and C++, used for the computing intensive part of the code. A more convenient and efficient approach would be to use a language that provides both high-level programming and high-performance. The Julia programming language, developed at MIT especially to allow the use of a single language in research activities, has followed this path. In this paper the applicability of using the Julia language for HEP research is explored, covering the different aspects that are important for HEP code development: runtime performance, handling of large projects, interface with legacy code, distributed computing, training, and ease of programming. The study shows that the HEP community would benefit from a large scale adoption of this programming language. The HEP-specific foundation libraries that would need to be consolidated are identified.