まず、問題文の条件を最適化問題として定式化する部分は公式解説と同様です。

(最適化問題とは、\(\text{subject to}\) で示された制約条件のもと \(\text{maxmize}\) で示された目的関数の最大値を求める (\(\text{minimize}\) なら目的関数の最小値) という問題のことをいいます。)

考える最適化問題を以下に示します (公式解説と同じ式です)。

\( \begin{aligned} &\text{maximize} &&-\frac{1}{2}R_1R_N\sin{\frac{2}{3}\pi}+\sum_{i=1}^{N-1}\frac{1}{2}R_iR_{i+1}\sin{\phi_i}\\ &\text{subject to} && \frac{\pi}{2N}\le\phi_i &&&(i=1,\dots N-1)\\ & &&\sum_{i=1}^{N-1} \phi_i=\frac{2}{3}\pi&&& \end{aligned} \)

結論から言うと、この最適化問題の制約条件は等式制約と不等式制約からなるため、KKT 条件 (カルーシュ・クーン・タッカー条件) を用いて解くことができます。

KKT 条件

以下の最適化問題を考える。

\( \begin{aligned} & \text{maximize} && f({\bm x})\\ &\text{subject to} && g_i({\bm x})\leq0 &&& (i=1,\dots,m)\\ & && h_i({\bm x})=0 &&& (i=1,\cdots,l) \end{aligned} \)

このとき、目的関数 \(f(\bm{x})\) の極大値 (特に、目的関数が上に凸なら最大値) を与える \(\bm{x^*}=(x_1,x_2,\dots,x_n)^\top\) は、ある実数の組 \(\bm{\mu}=(\mu_1,\dots,\mu_m)^\top, \bm{\lambda}=(\lambda_1,\dots,\lambda_l)^\top\) が存在して次の条件をすべて満たす (= KKT 条件) 。

\( \begin{aligned} \frac{\partial{f}}{\partial{x_i}}(\bm{x^*})-\sum_{j=1}^{m}\mu_j\frac{\partial{g_j}}{\partial{x_i}}(\bm{x^*})-\sum_{j=1}^{l}\lambda_j\frac{\partial{h_j}}{\partial{x_i}}(\bm{x^*})=0&&& (i=1,\dots,n)\\ g_i(\bm{x^*})\leq 0&&& (i=1,\dots,m)\\ h_i(\bm{x^*})= 0&&& (i=1,\dots,l)\\ \mu_i\geq 0&&& (i=1,\dots,m)\\ \mu_i=0 \lor g_i(\bm{x^*})=0&&& (i=1,\dots,m) \end{aligned} \)

なお、以上の主張は極大値の十分条件についてしか議論していないが、最適化問題の各関数に特定の条件 (制約想定) が保証されているとき、KKT 条件が極大値を与える必要条件となる。

今回の問題では、有効な不等式制約 \(g_i(\bm{x})\) について \(\displaystyle \nabla g_i(\bm{x})\) が一次独立であるため、一次独立制約想定により KKT 条件と最大値が必要十分条件であることが保証される。よって KKT 条件を満たす実数の組を見つければそれが答えの最大値である。

解法

この問題において KKT 条件をそのまま適用すると、以下のような式となります。

\( \begin{aligned} \frac{1}{2}R_iR_{i+1}\cos{\phi_i}+\mu_i-\lambda=0&&& (i=1,\dots,N-1)\\ \frac{\pi}{2N}-\phi_i\leq 0&&& (i=1,\dots,N-1)\\ \sum_{i=1}^{N-1}\phi_i=\frac{2}{3}\pi&&&\\ \mu_i\geq 0&&& (i=1,\dots,N-1)\\ \mu_i=0 \lor \frac{\pi}{2N}-\phi_i= 0&&& (i=1,\dots,N-1) \end{aligned} \)

この式において、等式制約だけが面倒な形をしていますが、他の制約はすべて \(\phi_i, \mu_i\) ごとに独立した式になっています。そこで、第 5 式の「または」の部分で場合分けしてみます。

1. \(\mu_i=0\) のとき

第 2, 5 式より、\(\displaystyle \frac{\pi}{2N}\leq\phi_i\) が必要です。

また第一式より、\(\displaystyle \frac{1}{2}R_iR_{i+1}\cos{\phi_i}=\lambda\) です。これより、各三角形の面積を \(\phi_i\) で微分した値は定数となることがわかります。

逆関数 \(\arccos\) を用いることでそのような \(\phi_i\) は容易に求まります (定義域と値域に注意すること)。

2. \(\mu_i>0\) のとき

第 5 式より、\(\displaystyle \frac{\pi}{2N}-\phi_i=0\) すなわち \(\phi_i=\displaystyle \frac{\pi}{2N}\) と定まります。第 1 式に代入すると、\(\displaystyle \frac{1}{2}R_iR_{i+1}\cos{\frac{\pi}{2N}}=\lambda-\mu_i\) となります。\(\lambda\) は定数ですが、左辺の値に帳尻を合わせられるような \(\mu_i\geq 0\) を適当に取れば良いことがわかります。

ここで、1. と 2. の両方が考うるケースでは、本来最大化したい目的関数の値をより大きくするのは 1. のケースなので (\(\because \phi_i\) が大きい方が三角形の面積は広くなる) 、可能な限り 1. の方を適用し、どうしても値域・定義域外になるときのみ 2. を適用すればよいでしょう。

KKT 条件で最適解を導出する

以上の条件より、第 2 式を無視すると各 \(i\) を独立に決められることがわかりました。

先程の KKT 条件における第 2 式は角度の総和についてのものでした。

各角は、他の条件の等式・不等式を変形することで一意に定めることができました。よってその角の総和もすぐに求まります。

しかし、角の総和 \(\frac{2\pi}{3}\) から上記の方法で角を決定するのは大変です。そこで、二分探索を用いることで条件を満たす \(\lambda\) の値を求めることが可能です。

以上で角度のパラメータがすべて求まったので、面積の最大値も計算することができます。

(以上の内容は取っ掛かりこそ違うものの本質は公式解説と同じ内容です。)

おまけ: KKT 条件の簡単な導出とお気持ち

ここでは、KKT 条件の証明は行いませんが、KKT 条件に至るまでの考え方の導入を行います。

\(C^1\) 級関数、つまり一階微分可能で一階導関数が連続な関数のことを以下滑らかな関数と呼びます。なお、この問題に現れる関数はすべて定義域で滑らかです。

突然ですが、目的関数に制約条件によるペナルティを課す、という考え方で目的関数を拡張してみます。ここで現れる関数は全て滑らかであることを仮定します。

\(\displaystyle L(\bm{x}, \bm{\mu}, \bm{\lambda})=f(\bm{x})-\sum_{i=1}^{m}\mu_i g_i(\bm{x})-\sum_{i=1}^{l}\lambda_i h_i(\bm{x}) (\mu_i\geq 0)\)

この関数 \(L\) では、等式制約や不等式制約に違反した項が存在すると、それに対応する変数が適当な値を取ることでいくらでも大きな値を取ってしまいます (ペナルティ関数法やバリア関数法などと共通の考え方です)。

この関数において、通常の多変数関数における停留点の探索 (\(\bm{x}\) ) に加え、追加した変数 (スラック変数) で微分した偏導関数が \(0\) になることも条件に入れることで、この関数 \(L\) の極大値を求めることができます (スラック変数での微分は元の制約条件の項がそのまま出るためです)。

特に、不等式制約がない場合はラグランジュの未定乗数法と呼ばれより簡単に解くことができると知られています。

不等式制約がある場合は、先程の \(L\) 式を \(\bm{x}, \bm{\mu}, \bm{\lambda}\) で偏微分した係数が \(0\) になることが条件になるのですが、不等式の扱いを多少考えないといけません。導出は省略しますが、それをまとめたのが KKT 条件です。