next up previous contents

Subsections

1 Largest Small Polygon

Find the polygon of maximal area, among polygons with $n_v$ sides and diameter $ d \le 1 $.

Formulation

This is a classic problem (see, for example, Graham [16]). If $ ( r_i , \theta_i ) $ are the coordinates of the vertices of the polygon, then we must maximize

\begin{displaymath} f(r,\theta) = \ {\textstyle{\frac{1}{2}}}\sum _{i=1}^{n_v-1} r_{i+1} r_i \sin(\theta_{i+1}-\theta_i) \end{displaymath}

subject to the constraints

\begin{displaymath} \begin{array}{rl} r_i^2 + r_j^2 - 2r_ir_j\cos(\theta_i-\thet... ... \pi] , \ r_i \ge 0, & \qquad 1 \le i \le n_v . \\ \end{array}\end{displaymath}

Our implementation follows [14] and fixes the last vertex by setting $ r_{n_v} = 0 $ and $ \theta_{n_v} = \pi $. By fixing a vertex at the origin, we can add the bounds $ r_i \le 1 $.

Graham [16] showed that the optimal solution is regular for odd $n$ but not regular for even $n$ except $ n=4 $. Another interesting feature of this problem is the presence of order $n_v^2$ nonlinear nonconvex inequality constraints. We also note that as $n_v \rightarrow \infty$, we expect the maximal area to converge to the area of a unit-diameter circle, $\pi/4 \approx 0.7854$. This problem has many local minima. For example, for $n_v=4$ a square with sides of length $1/\sqrt{2}$ and an equilateral triangle with another vertex added at distance $1$ away from a fixed vertex are both global solutions with optimal value $f = \frac{1}{2}$. Indeed, the number of local minima is at least $O(n_v!)$. Thus, general solvers are usually expected to find only local solutions. Data for this problem appears in Table 1.1.



Table 1.1: Largest-small polygon problem data
Variables $ 2 n_v $
Constraints $ ( {\textstyle{\frac{1}{2}}}n_v + 1 ) ( n_v - 1 ) $
Bounds $ 2 n_v $
Linear equality constraints 0
Linear inequality constraints $ n_v - 1 $
Nonlinear equality constraints 0
Nonlinear inequality constraints $ {\textstyle{\frac{1}{2}}}n_v ( n_v - 1 ) $
Nonzeros in $ \nabla ^2 f(x) $ $ 6 n_v $
Nonzeros in $ c'(x) $ $ 2 n_v ( n_v - 1 ) $

Performance

Results for the AMPL implementation are summarized in Table 1.2. A polygon with almost equal sides is the starting point. Global solutions for several $n_v$ are shown in Figure 1.1.



Table 1.2: Performance on largest small polygon problem
Solver $n_v=25$ $n_v=50$ $n_v=75$ $n_v=100$
LANCELOT 12.83 s 398.12 s 1148.2 s $\ddagger$
$f$ 7.79715e-01 7.83677e-01 7.84747e-01 $\ddagger$
$c$ violation 8.89750e-06 1.40500e-06 2.81600e-06 $\ddagger$
iterations 61 192 176 $\ddagger$
LOQO 3.49 s 30.16 s 268.9 s $\ddagger$
$f$ 7.64714e-01 7.77520e-01 7.77554e-01 $\ddagger$
$c$ violation 1.2e-09 4.0e-09 1.4e-09 $\ddagger$
iterations 110 203 566 $\ddagger$
MINOS 2.11 s 28.45 s 98.54 s 344.81 s
$f$ 7.64383e-01 6.57163e-01 7.60729e-01 7.72803e-01
$c$ violation 1.2e-13 2.2e-16 2.7e-13 1.3e-10
iterations 11 35 46 105
SNOPT 1.14 s 12.69 s 91.07 s 256.6 s
$f$ 7.79740e-01 7.84016e-01 7.84769e-01 7.85040e-01
$c$ violation 2.9e-10 9.1e-10 1.1e-09 1.5e-07
iterations 23 58 148 190
$\dagger$ Errors or warnings. $\ddagger$ Timed out.

Figure 1.1: Polygons of maximal area with $ n_v=6, 10, 20$ (left, center, right)
\includegraphics[width=1.9in]{ps/poly6.eps} \includegraphics[width=1.9in]{ps/poly10.eps} \includegraphics[width=1.9in]{ps/poly20.eps}

next up previous contents
Liz Dolan
2001-01-02