**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Convex hull

Summary

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.
Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every compact convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points.
The algorithmic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its dual problem of intersecting half-spaces, are fundamental problems of computation

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (10)

Related publications (88)

Loading

Loading

Loading

Related lectures (84)

Related units (6)

Related concepts (66)

Convex set

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins

Topological vector space

In mathematics, a topological vector space (also called a linear topological space and commonly abbreviated TVS or t.v.s.) is one of the basic structures investigated in functional analysis.
A topol

Banach space

In mathematics, more specifically in functional analysis, a Banach space (pronounced ˈbanax) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the co

Related courses (31)

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees, describe scalable solution techniques and algorithms, and illustrate the trade-offs involved.

MATH-329: Continuous optimization

This course introduces students to continuous, nonlinear optimization. We study the theory of optimization with continuous variables (with full proofs), and we analyze and implement important algorithms to solve constrained and unconstrained problems.

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years.

This thesis consists of two parts. The first part is about a variant of Banach's fixed point theorem and its applications to several partial differential equations (PDE's), abstractly of the form [ \mathcal Lu + \mathcal Q(u) = f.] The main result of this first part asserts that an equation having this form admits a solution if the datum $f$ satisfies a certain smallness assumption. This result (we call it \emph{the fixed point method}) is relatively simple to use and can be applied to a large variety of PDE's. The downside is that it guarantees the existence of solutions only for "small" data. The equations we deal with are Jacobian equations, non-linear elliptic PDE's, transport problems and the semi-linear wave equation. The second part of the thesis treats the $\emph{two well problem}$ in two dimensions [ \nabla u \in \mathbb{S}_A \cup \mathbb{S}_B\quad \text{almost everywhere in}\ \Omega, ] [ u = u_0\quad \text{on}\ \partial\Omega. ] For the non-degenerate case $\det(A),\det(B) \neq 0$, we show a non-existence result for piecewise regular solutions if $A$ and $B$ are non-orthogonal. For the degenerate and semi-degenerate cases, we give a characterisation for the rank-one convex hull of $\mathbb{S}_A \cup \mathbb{S}_B$ and several existence results for Lipschitz and piecewise affine solutions. Finally, for each case, we construct several explicit non-trivial solutions for well-chosen boundary conditions $u_0$.

We investigate how probability tools can be useful to study representations of non-amenable groups. A suitable notion of "probabilistic subgroup" is proposed for locally compact groups, and is valuable to induction of representations. Nonamenable groups admit nonabelian free subgroups in that measure-theoretical sense. Consequences for affine actions and for unitarizability are then drawn. In particular, we obtain a new characterization of amenability via some affine actions on Hilbert spaces. Along the way, various fixed-point properties for groups are studied. We also give a survey of several useful facts about group representations on Banach spaces, continuity of group actions, compactness of convex hulls in locally convex spaces, and measurability pathologies in Banach spaces.

We consider the problem of provably finding a stationary point of a smooth function to be minimized on the variety of bounded-rank matrices. This turns out to be unexpectedly delicate. We trace the difficulty back to a geometric obstacle: On a nonsmooth set, there may be sequences of points along which standard measures of stationarity tend to zero, but whose limit points are not stationary. We name such events apocalypses, as they can cause optimization algorithms to converge to non-stationary points. We illustrate this explicitly for an existing optimization algorithm on bounded-rank matrices. To provably find stationary points, we modify a trust-region method on a standard smooth parameterization of the variety. The method relies on the known fact that second-order stationary points on the parameter space map to stationary points on the variety. Our geometric observations and proposed algorithm generalize beyond bounded-rank matrices. We give a geometric characterization of apocalypses on general constraint sets, which implies that Clarke-regular sets do not admit apocalypses. Such sets include smooth manifolds, manifolds with boundaries, and convex sets. Our trust-region method supports parameterization by any complete Riemannian manifold.