면적이 최대가 되는 다각형 찾기
n 변과 직경 d≤1 다각형 중에서 면적이 최대가 되는 다각형을 구합니다.
Mathematica 11에서는 FindMinimum에 IPOPT 솔버가 더해져 대규모 제약 조건부 최적화 문제를 보다 효율적으로 풀 수 있게 되었습니다.
다각형의 꼭지점 수를 n으로 나타냅니다.
In[1]:=
n = 50;
를 다각형의 제 
번째 꼭지점의 극좌표로 합니다.
In[2]:=
vars = Join[Array[r, n], Array[\[Theta], n]];이러한 제약 조건 
, 
, 
, 
을 만족합니다.
In[3]:=
varbounds =
Join[Table[0 <= r[i] <= 1, {i, n - 1}], {r[n] == 0},
Table[0 <= \[Theta][i] <= Pi, {i, n - 1}], {\[Theta][n] == Pi}];다각형의 면적은 정점 i, i+1 그리고 n (원점) 삼각형의 면적의 합입니다.
In[4]:=
area = 1/2 Sum[
r[i] r[i + 1] Sin[\[Theta][i + 1] - \[Theta][i]], {i, 1, n - 1}];모든 두 정점 사이의 거리는 1을 초과할 수 없습니다.
In[5]:=
constr1 =
Flatten[Table[
0 < r[i]^2 + r[j]^2 -
2 r[i] r[j] Cos[\[Theta][i] - \[Theta][j]] <= 1, {i, 1,
n - 1}, {j, i + 1, n}], 2];정점의 순서가 존재하기 때문에 다음과 같은 제약 조건도 존재합니다.
In[6]:=
constr2 = Table[\[Theta][i] <= \[Theta][i + 1], {i, 1, n - 1}];변수의 초기점을 선택합니다.
In[7]:=
x0 = vars /. {r[i_] ->
4. i (n + 1 - i)/(n + 1)^2, \[Theta][i_] -> \[Pi] i/n};제약 조건의 대상이 되는 면적을 최대화합니다.
In[8]:=
sol = FindMaximum[{area, constr1, constr2, varbounds},
Thread[{vars, x0}]];직교 좌표계로 변환합니다.
In[9]:=
rectpts =
Table[FromPolarCoordinates[{r[i], \[Theta][i]}], {i, 1, n}] /.
sol[[2]];해를 플롯합니다.
In[10]:=
Show[ListPlot[rectpts, PlotStyle -> {Blue, PointSize -> Medium}],
Graphics[{Opacity[.1], Blue, EdgeForm[Blue], Polygon[rectpts]}],
AspectRatio -> 1, ImageSize -> Medium]Out[10]=
