凸計画問題の理論を使って課金額を最適化しよう - 京都大学艦これ同好会　会員の雑記ブログ

こんにちは，京艦同のK6です．本記事ではMATLABの凸計画問題ソルバーを使って資源課金をする際に必要な最適化について解説します．

概要
凸計画問題とは？
- 凸計画問題における最適解の一意性
- 証明
艦隊運営の線形計画問題への変換
- 線形制約の組み合わせによる凸集合の生成
- 証明
数値的解法
- 内点法
MATLABを使った数値例
おわりに

概要

艦隊これくしょんというゲームは様々なプレイスタイルがあります．「いい暇つぶしになる」「キャラがかわいいからそれだけで十分」「究極の艦隊強化を求め，甲種勲章を積んでいきたい」「PvP要素がある以上競争心が燃えてたまらない」等，いずれも正解と結論付けることは不可能です．筆者は最近このゲームとの向き合い方，そしてリアルとの両立に非常に悩んでいます．

ただ，真剣に向き合う以上，きちんとした考察を通って一番効率いい艦隊運営をしないと時間の無駄になることは確かです．雑な例えをしますと，一か月500時間のプレイで90%の効率しか出せていないのは50時間もの貴重な人生を毎月毎月無駄にしているということです（艦これ自体も人生の無駄ですが）．常に非効率を恐れることはあまり良い気持ちではありませんが，性格的に仕方ない感じがします．

無駄話は良しとして，最近趣味でやっていた研究が実用性のあるやつだったので紹介したいと思います．筆者は戦果記録を走った経験があり，現在タウイタウイ泊地のサーバー内戦果記録を保持しています．幸い資源無課金で鯖記録保持者という名を手に入れることが出来ましたが，この世は基本，ありとあらゆるものが金の力で動いています．戦果も例外ではありません．今後戦果記録に挑む提督に諭吉の力を借りる者は少なくないでしょう．

課金をする際に，ある疑問が生まれます．もちろん諭吉は誰にとっても有限なものです．できれば少額で済ませたいのがほとんどだと思います．となると，記録戦果を走る一か月でどの海域を回るか，どの遠征を送るか，どの任務を捨てるかを判断しないといけません．適当に長距離，海上護衛，北方鼠を送って足りない分は全部出撃セットで埋めればいいんじゃないか？と思う方もいるかもしれませんが，それはあくまでも感覚的な議論で，課金額を最小化できたと言えるわけではありません．

本記事ではその疑問を解決します．資源課金および艦隊運営を線形計画問題に置き換え，それが凸計画問題となっていることを示します．凸計画問題は最適化の分野において非常に深く研究されている部分であり，最適化問題の中では比較的解きやすい部類の問題です．簡単な証明によりこのような問題は一意的な最適解を持ち，CVX等の数値ソルバーが求める最適解は大域的最適解であることが示されます．

凸計画問題とは？

凸計画問題とはある集合に属する最適化変数を調整し，それらの変数を引数とする目的関数を最小，または最大化する問題です．数学的には以下のように記述されます．

$\underset{x\in\mathbb{R}^n}{\text{minimize}}\hspace{1cm}f(x) \\ \text{subject to}\hspace{1cm}x\in\mathcal{C}.$

ここで目的関数 $f(x)$ および集合 $\mathcal{C}$ は凸関数と凸集合を表しています． $x\in\mathcal{C}$ は解の候補となるため，実行可能集合，または実行可能解と呼びます（Feasible Set）．凸集合 $\mathcal{C}$ を凸な制約関数で表現すると，この定義は以下のように記述されます．

$\underset{x\in\mathbb{R}^n}{\text{minimize}}\hspace{1cm}f(x) \\ \text{subject to}\hspace{1cm}g_i(x)\geq0,\hspace{1cm}(i=1,\dots,m), \\ \hspace{3.23cm}h_j(x)=0,\hspace{1cm}(j=1,\dots,p).$

$f(x),\,g_i(x),\,h_j(x)$ が凸関数で表される凸計画問題は非凸計画問題に比べて非常に解きやすくなる性質をいくつか有します．その一つが最適解の一意性であり，局所的に最適（ $f(x)$ が最小）である解は大域的最適となることです．この性質により，数値ソルバーが与える最適解は大域的最適解であることが保証され，凸計画問題は簡単に解かれます．

次の節からは凸計画問題における最適解の一意性，そして艦これにおける艦隊運営が凸計画問題になることを証明していきます．難しい証明ではありませんが，数学に興味がない方はそれらをとばして数値例に進んでください．

凸計画問題における最適解の一意性

上述した通り，凸計画問題はとても大事な性質を有し，（局所的）最適解を一つしか持たないという点です．例えば凸関数

$f_1(x) = ax^2,\,\hspace{1cm}(a\gt 0)$

を考えましょう．この関数が最小となる点は

$f_1(0) = 0$

で求まります．一方，非凸な関数

$f_2(x) = \sin{x}$

は最小となる点が一意的に求まりません．このことを以下のように証明します．

証明

まず，凸集合および凸関数の定義から始めます．

ある集合 $\mathcal{C}$ が以下を満たす場合，その集合は凸集合という．

$\forall x,y\in\mathcal{C},\,\forall\lambda\in[0,1] \\ \lambda x + (1-\lambda)y\in\mathcal{C}$

つまり，凸集合に属する２つの要素 $x,y$ を考えると，それらを結ぶ線分上にあるすべての点は同じ凸集合に属することを記述しています．

ある関数 $f\,:\,X\rightarrow\mathbb{R}$ が以下を満たす場合，その関数は（弱い意味での）凸関数という．

$\forall x,y\in X,\,\forall\lambda\in[0,1] \\ f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$

言い換えると，２次元平面での座標 $(x,f(x))$ および $(y,f(y))$ を結ぶ線分は常に関数 $f$ より上に存在し， $f$ の上平面に存在する領域は凸集合となることを意味します．

これらの定義に基づいて以下を証明します．

凸な目的関数 $f$ および制約関数 $g_i(x),\,h_j(x)$ で表される凸計画問題は，唯一の最適解（目的関数の最適値）を持つ．

証明は背理法で行います．二つの異なる実行可能な最適解 $x^*, y^*\,(x^*\neq y^*)$ が存在し，これらは以下の最適値を与えるとします．

$f(x^*) = f(y^*) = m$

$f$ は凸関数なので， $\lambda\in[0,1]$ に対して以下が成り立ちます．

$f(\lambda x^* + (1-\lambda)y^*)\leq \lambda f(x^*) + (1-\lambda) f(y^*)$

制約関数 $g_i(x),\,h_j(x)$ も凸関数なので，扱っている実行可能集合は凸集合となり， $\lambda x^* + (1-\lambda)y^*$ は実行可能解であることが確認されます．

ここで $x^*,y^*$ での最適値を代入すると

$f(\lambda x^* + (1-\lambda)y^*)\leq m$

まず，等号が成立しない場合を考えましょう．そのとき $\lambda x^* + (1-\lambda)y^*$ は $x^*, y^*$ よりも最適値を与え，最初の仮定に矛盾し，最適解は二つ以上存在できないことを意味します．

また，等号が成立する場合， $f(\lambda x^* + (1-\lambda)y^*)$ は直線を描いており，直線上すべての点は最適解となりますが，興味の対象である目的関数の最適値が $m$ となることは変わりありません．（このややこしい議論を回避するためには強い意味で凸な目的関数が必要です．）

艦隊運営の線形計画問題への変換

遠征による資源の収入およびアイテム屋での課金はすべて線形式で表されます．例えば　 $n,d,b$ をそれぞれ燃料，弾薬，バケツとし， $c, k$ を長距離遠征と海上護衛遠征の回数とします．とすると遠征による収入は以下のような線形式で表現できます．

$n = 240k\\d = 120c + 240k\\b = 0.5c$

*補給やキラは無視しています

**行列で表すと簡単な形にまとめられます

ここで必要な資源量を $n_\text{req},d_\text{req},b_\text{req}$ とすると，遠征の必要な回数は以下の不等式を解くことで求まります．

$n_\text{req} \leq 240k\\d_\text{req} \leq 120c + 240k\\b_\text{req} \leq 0.5c$

アイテム屋での資源入手も同様な形で不等式に加えることができます．さらに，資源の初期量や他の入手方法（甲種勲章等）は各不等式において線形関係ではなく定数（バイアス）として表されます．このような式の設計より艦隊運営は前述した制約関数

$g_i(x)=a_i^Tx+b_i\geq0,\hspace{1cm}(i=1,\dots,m) \\ h_j(x)=c_j^Tx+d_j=0,\hspace{1cm}(j=1,\dots,p)$

の形で書くことができ，もし目的関数まで線形であるとすると，これは線形計画問題と呼ばれます．線形計画問題は凸計画問題の一種であり，これまでと同様な議論が可能です．

線形制約の組み合わせによる凸集合の生成

線形制約関数のまとまりが凸集合であることは自明ですが，一応次節に証明を書いておきます．以下の参考図を見ると感覚的にわかると思いますが，本格的な証明に入る前にこの図を用いて証明したいことを説明します．

各不等式制約は最適化変数の空間上に半空間を許容可能な部分空間としています．簡単のため2変数，つまり2次元の最適化空間を考えると，各制約は2次元平面上の半平面を定義しています．複数の制約はこれらの半平面の共通集合を定義し，半平面はすべて凸集合であるため，それらの共通集合も凸集合になることが分かります．

等式制約についてはさらに簡単なケースですので説明を省略します．

線形制約で作る凸集合（Wikipedia: Linear Programming）

証明

許容可能な集合 $\mathcal{F}$ が以下のように線形制約で定義されているとします．この集合が凸集合であることを証明していきます．

$\mathcal{F}=\{x\in\mathbb{R}^n\,|\,g_i(x)=a_i^Tx+b_i\geq0,\,\,(i=1,\dots,m)\}$

まず， $\mathcal{F}$ 内の二点 $x,y$ を考えると，定義により以下が成り立ちます．

$\forall i,\, g_i(x)=a_i^Tx+b_i\geq0,\, g_i(y)=a_i^Ty+b_i\geq0$

次に $x,y$ を結ぶ線分上にある点 $z$ を考えます．

$z = \lambda x + (1-\lambda) y,\,\lambda\in[0,1]$

$g_i(z)$ を計算すると

$\forall i,\,g_i(z)=a_i^T( \lambda x + (1-\lambda) y)+b_i \\ \hspace{1.9cm}=\lambda (a_i^Tx+b_i)+(1-\lambda)(a_i^Ty+b_i) \\ \hspace{1.9cm}=\lambda g_i(x) + (1-\lambda)g_i(y)\geq0$

となり， $z\in\mathcal{F}$ が得られます．任意の2点 $x,y$ に対してこれが成り立つため，集合 $\mathcal{F}$ は凸集合であることが示されます．

等式制約に関しても同様の証明ができ，上の不等号をすべて等号に置き換えるだけなので省略します．

数値的解法

これまでは最適化問題を凸計画問題として定式化する方法を議論してきましたが，本節ではこのような凸計画問題を実際に解くアルゴリズムについて軽く紹介します．繰り返し言及した通り，凸計画問題を効率良く解くアルゴリズムは多く開発されており，それらは複数のプログラミング言語で関数として組み込まれています．本記事では最適化の分野でよく知られている内点法（Interior-Point Methods）を紹介し，実際の数値例を見ていきます．

内点法

内点法は凸計画問題を解くための効率良いアルゴリズムとして知られています．このアルゴリズム概要を簡潔に紹介します．

まず，制約を満たしながら目的関数を最小化するために，バリア関数 $B(x,\mu)$ というものを定義します．（等式制約は簡単のため割愛します）

$B(x,\mu)=f(x)-\mu\sum_{i=1}^{m}\ln{(g_i(x))}$

ここでパラメータ $\mu\gt0$ は小さい定数を表します．不等式制約 $g_i(x)$ は目的関数 $f(x)$ の凸性を保ちながら障壁（バリア）を作るため，この関数は微分可能であり，ニュートン法等の方法で最小となる点を探すことが可能です．以下に一次元の例を示します．

最適化問題

$\underset{x\in\mathbb{R}}{\text{minimize}}\hspace{1cm}x \\ \text{subject to}\hspace{1cm}x+1\geq0, \\ \hspace{3.23cm}-x+1\geq0.$

に対するバリア関数は以下のように定義されます．

$B(x,\mu)=x-\mu(\ln{(x+1)}+\ln{(-x+1)})$

$\mu=0.02,\,0.05,\,0.1$ の場合のグラフの概形は以下の通りです．

$\mu$ が小さいほどバリア関数は元の制約関数 $f(x)$ に近い形になっていき， $\mu\rightarrow 0$ では最適値 $f(-1)=-1$ が得られます．ニュートン方向への更新を辿りながら徐々に $\mu$ を減らしていくと，このアルゴリズムが最適解に収束することは感覚的に理解できると思います．

MATLABを使った数値例

適当な要求資源を定め，必要な課金額を最小化するコードを組みました．目的関数は総課金額，制約関数は入手資源の必要資源との差分にしています．最適化変数としてはアイテム屋での各アイテム購入数，そして最適解の候補となる遠征を送る時間数です．

要求燃料・弾薬は80万，要求バケツは8千，資源カンスト状態を仮定しています．その他の詳細は以下のソースコードを確認してください．

最適化問題を解くにあたってはMATLABのCVX環境を利用しました．

fuel_req = 8*10^5; %必要燃料の定義（出撃資源総和等） 5000 5000
ammo_req = 8*10^5; %必要弾薬
bucket_req = 8*10^3; %必要バケツ

reqs = [fuel_req;ammo_req;bucket_req];
reso_cap = 3.5*10^5; %資源カンストを仮定
bucket_cap = 3*10^3; %バケツカンストを仮定
exped_total_hours = 3*20*31; %遠征に使える時間数を定義
max_exped_time = 20*31; %一個の遠征に使える時間数の上限（1個の遠征を2艦隊で送れない）
offsets = [reso_cap;reso_cap;bucket_cap];

shopweights = [1200 0   0 500; %アイテム屋で購入する際にもらう資源量
               0    250 0 500;
               0    0   6   3];
expedweights = [-32 220 222.86 115.64 153; %遠征2,5,21,a2,41を選択肢とする
                240 244 180     63.27 -40;
                1   0   0       1.09    1];
shopcosts = [300 100 300 300]; %課金アイテムの値段

cvx_begin
    variables k(4) e(5) %変数の定義；kは課金アイテムの数；eは遠征の時間数
    minimize shopcosts*k %最適化する目的関数は課金額
    subject to %制約を設定
        k >= 0 %非負制約
        e(4) == 0; %（任意）a2をゼロ設定（キラ多め）
        % e(5) == 0; %（任意）41をゼロ設定
        0 <= e <= max_exped_time %非負制約，時間制約2
        sum(e) <= exped_total_hours %時間制約1
        shopweights*k + expedweights*e + offsets >= reqs %資源制約
cvx_end

これを実行すると次の変数値が得られます．

k = [3.4998e-07;1.5119e-07;473.5808;373.7784];
e =  [417.1797;620.0000;202.8203;0.0000;620.0000];

小数点を切り上げ，微小量は無視すると得られる最適解は次の通りです．

高速修復材パック×474個
出撃セット×374個
長距離×418時間
海上護衛×620時間
北方鼠輸送×203時間
ブルネイ泊地×620時間

必要課金額は254400円．（払えねえ，，，）

この例ではキラ付け回数の削減を想定し，海峡警備遠征はゼロとする制約を加えています．他にも必要に応じて適宜制約を作ることが可能です．

おわりに

最初に想定していたより少し数学が重い記事となってしまいましたが，興味を持って読んでいただきありがとうございます．もしこのような最適化をやってみたいけど，プログラミング言語を使える環境ではないという方はDiscord（id: ha15224）にて対応いたします．

記事の数値例は既知の資源量を与え，必要な課金額を最小化する最適化を行いました．類似した問題として許容課金額を与え，出せる最大戦果を計算するプログラムも考えられます．可能ならbonodereへの導入も検討したいと思います．

ではまた．