KKT条件を利用して、公式解説と同様の解法を導出する方法を紹介します。

KKT条件の説明

以下のような問題の局所最適解を考えます。

\[ \text{minimize}\; f(\boldsymbol x)\\ \text{s.t.}\; g_i(\boldsymbol x) \leq 0\;(i = 1, \ldots, N),\, h_i(\boldsymbol x) = 0 \;(i = 1, \ldots, M) \]

ここで、それぞれの関数は \(n\) 次元ベクトルを引数に持ち実数を返します。

制約について特殊な仮定が成り立つ時、局所最適解 \(\hat{\boldsymbol x}\) について、\(\hat{\boldsymbol x}\) で各関数が微分できることを仮定すると、ある実数 \(\lambda_i\;(i = 1, \ldots, N),\,\mu_i\;(i = 1, \ldots, M)\) が存在し、以下を満たします。

\[ \frac{\partial f(\hat \boldsymbol x)}{\partial x_j} + \sum_{i = 1}^N \lambda_i \frac{\partial g_i(\hat \boldsymbol x)}{\partial x_j} + \sum_{i = 1}^M \mu_i \frac{\partial h_i(\hat\boldsymbol x)}{\partial x_j} = 0\;(j = 1, \ldots, n)\\ \lambda_i \geq 0,\, g_i(\hat\boldsymbol x) \leq 0,\, \lambda_ig_i(\hat\boldsymbol x) = 0\;(i = 1,\ldots, N)\\ h_i(\hat\boldsymbol x) = 0\;(i = 1,\ldots, M) \]

「特殊な仮定」について

KKT条件が適用できるためには、制約が特殊な仮定を満たしている必要があります。この仮定は「制約想定」と呼ばれており、いくつかの種類の制約想定が見つかっています。

例えば、今回の問題を定式化すると、

\[ \text{minimize} -\left(\sum_{i = 1}^{N - 1} \frac12 R_iR_{i + 1} \sin(\phi_i) - \frac12 R_1R_N \sin\left(\frac{2\pi}{3}\right)\right)\\ \text{s.t.} \;\phi_i \geq \frac{\pi}{2N}\;(i = 1, \ldots, N-1),\, \sum_{i = 1}^{N - 1} \phi_i = \frac{2\pi}{3} \]

となります。
この問題はSlater制約想定と呼ばれる制約想定を満たしているため、KKT条件を適用できます。

お気持ち説明

1行目については、無制約の場合には単なる微分になります。特に、\(n = 1\) の場合は「微分可能な最適解 → 微分が 0」という有名な事実に一致します。
制約がついた場合も同様で、制約込みの最小化したい「スコア関数」として

\[ L(\boldsymbol x, \boldsymbol \lambda, \boldsymbol \mu) = f(\boldsymbol x) + \sum_{i = 1}^N \lambda_i g_i(\boldsymbol x) + \sum_{i = 1}^M \mu_i h_i(\boldsymbol x) \]

を用意して、それの微分が 0 になってほしいという感じです。

2行目について、\(g_i(\hat\boldsymbol x) < 0\) の時、この制約があっても \(\boldsymbol x\) を微小に動かすことができ、微小な範囲ではこの制約は無意味です。よって、\(g_i(\hat\boldsymbol x) < 0\) の時は\(\lambda_i = 0\) としておきたいです。これが、\(g_i(\hat\boldsymbol x) \lambda_i = 0\) のお気持ちと言えるでしょう。
\(\lambda_i \geq 0\) のお気持ちを理解するために、1行目の式を書き換えると、

\[ -\nabla f(\hat\boldsymbol x) = \sum_{i = 1}^N \lambda_i \nabla g_i(\hat\boldsymbol x) + \sum_{i = 1}^M \mu_i \nabla h_i(\hat\boldsymbol x) \]

となります。左辺の \(-\nabla f\) は、いわば「 \(f\) をより小さくする方向」といえます。
一方で、右辺は、いわば「制約で禁止されている進行方向」と表現できます。\(\mu_i \nabla h_i\) は「\(h_i\) の値を変化させる方向」、\(\lambda_i \geq 0\) があることで、 \(\lambda_i \nabla g_i\) は「\(g_i\) の値を増加させる方向」となります。
\(\lambda_i \geq 0\) があることで、1行目の式が適切な意味を持つようになりました。

残りの制約は、\(\hat\boldsymbol x\) が制約を満たすことを意味しています。

KKT条件を利用した解法の導出

制約想定の部分でも書きましたが、再度問題を定式化しておきます。

\[ \text{minimize} -\left(\sum_{i = 1}^{N - 1} \frac12 R_iR_{i + 1} \sin(\phi_i) - \frac12 R_1R_N \sin\left(\frac{2\pi}{3}\right)\right)\\ \text{s.t.} \;\phi_i \geq \frac{\pi}{2N}\;(i = 1, \ldots, N-1),\, \sum_{i = 1}^{N - 1} \phi_i = \frac{2\pi}{3} \]

よって、

\[ f(\boldsymbol \phi) = -\left(\sum_{i = 1}^{N - 1} \frac12 R_iR_{i + 1} \sin(\phi_i) - \frac12 R_1R_N \sin\left(\frac{2\pi}{3}\right)\right)\\ g_i (\boldsymbol \phi) = -\phi_i + \frac{\pi}{2N}\;(i = 1, \ldots, N - 1)\\ h_i(\boldsymbol \phi) = \sum_{i = 1}^{N - 1} \phi_i - \frac{2\pi}{3} \]

とすることでKKT条件を適用できて、\(\alpha_i = \frac12 R_iR_{i + 1}\) とすると

\[ -\alpha_i\cos(\phi_i) - \lambda_i + \mu = 0 \;(i = 1, \ldots, N - 1)\\ \lambda_i \geq 0, \, \phi_i \geq \frac{\pi}{2N}, \, \lambda_i(\phi_i - \frac{\pi}{2N} ) = 0\\ \sum_{i = 1}^{N - 1} \phi_i = \frac{2\pi}{3} \]

\(\mu\) を固定して考えます。

\(\phi_i > \frac{\pi}{2N}\) の時、\(\lambda_i = 0\) です。
よって、1行目の等式から、\(\cos(\phi_i) = \mu/\alpha_i \Leftrightarrow \phi_i = \arccos (\mu/\alpha_i)\) です。
これと \(\phi_i > \frac{\pi}{2N}\) から、 \(\arccos(\mu/\alpha_i) > \frac{\pi}{2N}\) です。

\(\phi_i = \frac{\pi}{2N}\) の時、\(\lambda_i \geq 0\) です。
よって、1行目の等式から、

\[ \lambda_i = -\alpha_i \cos(\frac{\pi}{2N}) + \mu \geq 0 \Leftrightarrow \cos(\frac{\pi}{2N}) \leq \frac{\mu}{\alpha_i} \Leftrightarrow \arccos (\frac{\mu}{\alpha_i}) \leq \frac{\pi}{2N} \]

以上から、\(\phi_i = \max(\arccos(\frac{\mu}{\alpha_i}), \frac{\pi}{2N})\) です。

これを等式制約に代入して、

\[ \sum_{i = 1}^{N - 1} \max(\arccos(\frac{\mu}{\alpha_i}), \frac{\pi}{2N}) = \frac{2\pi}{3} \]

\(\arccos(\frac{\mu}{\alpha_i})\) は \(\mu\) についての単調減少関数なので、左辺は\(\mu\) について単調減少します。
よって、 \(\mu\) を2分探索などで計算し、各 \(\phi_i\) を計算することで、この問題を \(O(ND)\) (\(D\) は二分探索のループ回数) で計算できました。

なお、最終的なアルゴリズムとしては、公式解説のものと一致します。