2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Rahul Nov 30 '14 at 10:34
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.