# Projecting onto convex shapes - best fit convex polygon

I am interested in studying a problem of the form $\min F(\Omega)$ where $\Omega$ varies in the class of convex, open sets in the plane. An idea is to deform $\Omega$ at each step using a steepest descent algorithm, and if the deformed shape $\Omega_d$ is not convex, project it in some way on the space of convex sets.

I guess there are different ways of doing this. I've tried replacing $\Omega_d$ by its convex hull. This is not satisfactory, since at some moment we might get into a cyclic situation: for example if $\Omega$ has a segment in its boundary, the algorithm pulls the segment inwards, but convexification brings it back where it was.

To avoid this, we could consider a form $\Omega'$ which convex, and is closest to $\Omega$ in the sense of least squares. For examples, if $\rho_0$ is a radial parametrization of $\Omega$, and $(x_i)$ is a discretization of $[0,2\pi)$ then we could solve $$\min_{\rho} \sum_{i = 1}^n (\rho(x_i)-\rho_0(x_i))^2$$ where $\rho$ is the radial function of a convex shape.

Is there any simple way to impose the convexity constraint on $\rho$ in the discrete setting? In the end, the above optimization problem is equivalent to fitting the closest convex polygon to a set of points in the plane, in the sense of least squares. Is there any known algorithm to find such a best fit convex polygon.

If I write the analytic condition (positive curvature in 2D), it will need the derivatives $\rho',\rho''$, which is not pleasant: if I parametrize the radial function by Fourier coefficients, it comes to solving a quadratic optimization problem under quadratic constraints.

• Have you considered using a representation of $\Omega$ that guarantees convexity, such as an intersection of half-planes? Then you can freely do gradient descent without ever leaving the space of convex sets. (However, you may have to introduce new half-planes at vertices when needed, and remove half-planes that become redundant.)
– user3883
Nov 30, 2014 at 10:34

The set of convex sets is infinite dimensional, which is not amenable to computation. I would discretize this by replacing your solution set (consisting of all convex sets) by a finite dimensional set -- for example, polygons with $N$ vertices. This finite dimensional set can conveniently be represented as the intersection of $N$ half-spaces and you would then write your optimization over the parameters that determine these half spaces.