In a recent contest in Romania, there was a problem that was formulated as follows:
Given a convex polygon $$$P$$$ given by points $$$(x_i, y_i)$$$ in the 2D plane and a number $$$R$$$, construct a polygon $$$P'$$$ given by $$$(x'_i, y'_i)$$$, such that:
- the Euclidean distance between $$$(x_i, y_i)$$$ and $$$(x'_i, y'_i)$$$ is at most $$$R$$$
- the area of polygon $$$P'$$$ is as much as possible
It is guaranteed that any two points on the polygon are at distance at least $$$2R$$$ apart.
The problem was a bit awkwardly stated, as it required the area not to be the largest possible, but as large as the "model solution". In case you are interested, the task (in Romanian), can be found here. Keep in mind that the task at hand is a bit ill-posed and has some notable problems with floating point precision. However, I'm not as concerned about that.
It feels to me that the problem might actually be convex; however, I don't have the mathematical skills to (dis)prove it.
The problem can be formulated in terms of constrained optimization as follows:
max $$$x'_1 y'_2 + x'_2 y'_3 + ... + x'_n y'_1 - x'_2 y'_1 - x'_3 y'_2 - ... - x'_1 y'_n$$$
s.t. $$$(x'_i - x_i)^2 + (y'_i - y_i)^2 \leq R^2$$$
(here $$$x'_i, y'_i$$$ are the actual variables to optimize, excuse me for that)
The constrained space is convex. The objective function seems concave, but I'm not sure how to prove that. For three points, the hessian of the objective function looks like this.
The model solution is to iteratively fix all points apart from one and optimize for a single point (up to convergence). It can be proven rather easily that the best placement lies on the intersection between the perpendicular from $$$(x_i, y_i)$$$ to the vector given by $$$(x_{i - 1}, y_{i - 1})$$$ and $$$(x_{i + 1}, y_{i + 1})$$$ and the circle of radius $$$R$$$. Check it out.
I have some questions about this:
- Is the constrained optimization convex?
- If yes/no, does the algorithm above produce the global maximum?
- How are these types of "iterative optimization" algorithms called in literature? Are there known bounds for convergence (in the convex case)?
