Gurobi: HostID mismatch の対処法

本記事の内容は正確ではありません．後日修正をします．

• What system changes can invalidate a license file? にある通り，WSL2 では reboot の度に MAC アドレスが更新されるそうです．対処法としては，Windows 機に gurobi ライセンスを入れることで解決します（Mac OS の動作確認はしていません）．
• Gurobi Optimizer ダウンロード からインストーラをダウンロードし，ダウンロード後はインストールガイドに従いインストールを行います．インストールガイドは同じ URL から取得できます．

TL;DR

• OctoberSky Co., Ltd. に HostID mismatch が発生した旨を連絡し，新規でライセンス・キーコードを発行してもらう
• 旧ライセンス・キーコードを削除し，新ライセンス・キーコードを所定の位置に配置する
• gurobi.sh を実行し，gurobi が呼び出せることを確認する

バージョン情報

• grbprobe version 9.5.1, build v9.5.1rc2
• PLATFORM=linux64

何が起こったのか

@(Gurobi)有識者:

grbprobe の実行結果がなぜか変わっており，HostID が licence key に記載されている HostID と異なっていることが判明しました．そのため，Gurobi を呼び出すと `gurobipy.GurobiError: HostID mismatch` なるエラーが発生するようになってしまいました．解決する手段はありますか.

— みるか (@mirucaaura) April 9, 2022

ここにある通り，grbprobe を実行したときの HOSTID の値が，以前のものと変わっていました．これにより，ライセンス・キーコード gurobi.lic に記載されている HOSTID の値と一致しないために gurobi を呼び出すことができないという事象が発生しました．

解決まで

最初は自分の環境側で対処可能な事象だと思ったですが，話はそう単純ではなかったようで，Gurobi Optimizer の日本総代理店を務める OctoberSky Co., Ltd. へ上記の旨を連絡しました．ライセンス・キーコードが MAC アドレスと紐づいているようで，やはりインターネット回線の変更に伴い MAC アドレスが変更された（or した）ことが原因のようでした．

後は，メールのやり取りにて，マシン変更申込届の提出を促されるので，それに従います．必要な情報としては，grbprobe の実行結果とマシン変更申込届です．

作業時の注意

Gurobi Optimizer は，いくつかの実行ファイルを使うのですが，これらのファイルが必要なときに参照できるようにするべく，いくつかの環境変数を修正する必要があります．このとき，（インストール先に依りますが）bash シェルのユーザであれば，.bashrc に以下の行を加える必要があります:

export GUROBI_HOME="/opt/gurobi951/linux64"
export PATH="${PATH}:${GUROBI_HOME}/bin"
export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:${GUROBI_HOME}/lib"

また，ライセンス・キーコードの差し替えにおいて，旧ライセンス・キーコードは削除した上で行いましょう．削除を行わない（e.g., リネーム）で差し替えを行うと，gurobi を呼び出したときに旧ライセンス・キーコードを読み取りに行ってしまい，HostID mismatch を起こします．これは，gurobi.lic に記載されている HOSTID の値と，grbprobe を実行して確認できる HOSTID の値が一致しているため，原因が分かりにくい事象であるのですが，きちんと旧ライセンス・キーコードを削除すると解消します．

Q&A

Q: gurobipy.GurobiError: HostID mismatch (licensed to xxxxxxxx, hostid is yyyyyyyy) というエラーが発生しました．どうすればいいですか．
A: gurobi.lic に記載されている HostID が手元の環境の HostID と合致していません．代理店へ連絡しましょう．

Q: Environment variable GUROBI_HOME is not set. というエラーが発生しました．どうすればいいですか．
A: 環境変数が正しく設定されていない可能性があります．もしくは，旧ライセンス・キーコードが残っている可能性があります．前者の場合は，作業時の注意 を参考に環境変数を設定してください．後者の場合は，旧ライセンス・キーコードを物理的に完全に削除してください．

非負制約を含む最適化問題に対する KKT 条件

表題の通りです．以下にまとめました．

『しっかり学ぶ数理最適化』演習問題（第 3 章）

『しっかり学ぶ数理最適化』第 3 章「非線形計画」の演習問題に関する個人的なメモ書きです．

3.1

二次正方行列の正定値性に関する等価な条件の導出の問題です．計算しましょう．

3.2-3.5

関数の凸性に関する問題です．3.2 は平均二乗誤差 $f(a, b) = \frac{1}{n} \sum_{i=1}^{n} (y_i - ax_i - b)^2$ の凸性を示す問題です．関数 $f$ の引数が $(a, b)$ であることに注意して，ヘッセ行列を計算し，その半正定値性を見てあげることによって示すことができます．具体的には，計算したヘッセ行列の二次形式を考えてあげて，その非負性を示せば十分です．3.3 は次の関数: \begin{align} f(x, y) = \max_{i\in [n]} \sqrt{(x_i - x)^2 + (y_i - y)^2} \label{1}\tag{1} \end{align} に関する凸性を示す問題です．ここで，$[n]$ は集合 $\{1,2,\dots,n\}$ を表すものとします．まず前提として，凸集合 $S$ 上で定義される凸関数 $f_1,\,f_2$ に対して，関数 $\max \{ f_1, \, f_2\}$ はまた凸関数であることが成り立ちます．この事実を繰り返し用いれば，$n$ 個の凸関数に対する $\max$ 値関数も凸関数であり，したがって，式 \eqref{1} で定義される関数の凸性を示すためには，$f_i (x,y) := \sqrt{(x_i - x)^2 + (y_i - y)^2}$ が凸関数であることを示せばよいです．書籍の解答では，3.2 と同様にヘッセ行列を計算して，その半正定値性を見ています．3.4 は $f(x) = \| x \|_2$ の凸性を示す問題で，書籍では勾配を用いた凸関数の特徴付けを用いて示しています．より簡単に，任意の $x,\,y\in\mathbb{R}^n$ と任意の実数 $\lambda\in [0,1]$ に対して，$\| \lambda x + (1-\lambda)y \|_2 \leqq \lambda\| x \|_2 + (1-\lambda)\| y \|_2$ が成立することを示してもよいと思います．これは，ノルムの性質より直ちに従います．3.5 はいわゆる log sum exp 関数と呼ばれる次の関数: \begin{align} f(x) = \log \left( \sum_{i=1}^{n} \mathrm{e}^{x_i} \right) \label{2}\tag{2} \end{align} の凸性を示す問題です．この関数は様々な分野で登場する関数で Wikipedia にもページがあります（LogSumExp）．特徴を一つ述べておくと，関数 $f$ の $x_i$ に関する偏微分は \begin{align} \frac{\partial f(x)}{\partial x_i} = \frac{\mathrm{e}^{x_i}}{\sum_{j}\mathrm{e}^{x_j}} \end{align} となり，よく知られた softmax 関数になります．また，本書でも述べられているように $\max\{x_1,x_2,\dots,x_n\}$ を近似する場面でもよく使われます．さて，この関数の凸性ですが，本書ではやはりヘッセ行列を計算し，その半正定値性を見ています．また，こちらのページ で議論されているように，Hölder の不等式に帰着させて示すのも綺麗だと思いました．

3.6

面白い問題です．与えられた非凸最適化問題を上手く変形することによって等価な凸計画問題を導出する問題です．

3.7

無制約二次計画問題を勾配降下法によって解くアルゴリズムにおいて，勾配降下方向にどれくらい進むのかについて決定する最適化問題を解く問題です．具体的には，アルゴリズムの第 $k$ 反復における近似解 $x^{(k)}$，勾配降下方向を $d(x^{(k)})$ としたとき，ステップサイズ $\alpha (>0)$ を変数とする関数 $g(\alpha) := f(x^{(k)} + \alpha d(x^{(k)}))$ を最小化する最適化問題を解く問題です．

3.8

無制約凸二次計画問題をニュートン法で実際に解く問題です．実際に解くといっても，実装する必要はなく，解析的に計算することができる問題です．実際に勾配ベクトル，ヘッセ行列を計算し，与えられた初期点から勾配降下方向に点を移動させてみると更新後の点における勾配ベクトルは $0$ ベクトルとなり，最適性条件を満たすことが分かります．

3.9

制約付き最適化問題を解く問題です．最適性条件を考えることによって解くことができます．

3.10

二次計画問題の双対問題を導出する問題です．本書では，行列 $Q$ が正則行列となっていますが，正定値対称行列が正しいです．対称行列でない場合は，本書 pp.91 と同様の議論によって一般性を失うことなく対称行列に変換することができます．改めて本問題で検討する二次計画問題は以下のように記述されます:

\begin{align} \min_{x} &\quad \frac{1}{2} x^\top Qx + c^\top x \\ \mathrm{s.t.} &\quad Ax = b, \, x\geqq 0. \end{align}

ここで，$Q$ は $n$ 次正定値対称行列，$c\in\mathbb{R}^{n},\, A\in\mathbb{R}^{m\times n},\, b\in\mathbb{R}^{m}$ は定数ベクトル，定数行列とします．

はじめに，双対問題の導出について簡単に述べておきます．与えられた最適化問題（"元問題"と呼ぶことにします，最小化問題とします）の一部の制約条件を緩和して，緩和した制約をペナルティ項として目的関数に組み込んだラグランジュ緩和問題を考えます．すると，ラグランジュ緩和問題の実行可能領域は元問題の実行可能領域よりも広がっており，またペナルティ項が非負であることから，ラグランジュ緩和問題の最適値は元問題の下界を達成することが確認されます．このラグランジュ緩和問題の最適値関数（決定変数はラグランジュ乗数となります）を最大化する問題を考えることによって，元問題の最適値とラグランジュ緩和問題の最適値が一致するようにすることが期待されます．この，ラグランジュ緩和問題の最適値関数を最大化する問題のことをラグランジュ双対問題と呼びます．[双対問題の導出の方法に関する記述おわり]

さて，3.10 の問題に戻りまして，本問題で考える二次計画問題に対するラグランジュ緩和問題を考えてみましょう．まず，制約条件は二つあり，等式制約 $Ax=b$ と決定変数 $x$ に関する非負条件です．等式制約に対するラグランジュ乗数を $u \in \mathbb{R}^{m}$，非負制約に対するラグランジュ乗数を $v\in\mathbb{R}^{n}_{\geqq 0}$ とします．すると，ラグランジュ関数は

\begin{align} L(x, u, v) &:= \frac{1}{2} x^\top Qx + c^\top x + u^\top (Ax-b) - v^\top x \\ &= \frac{1}{2} x^\top Qx + (c + A^\top u - v)^\top x - b^\top u \end{align}

となります．これを $x$ の非負条件の下で最小化する問題（ラグランジュ緩和問題）は次のように定式化されます:

\begin{align} \min_{x} &\quad \frac{1}{2} x^\top Qx + (c + A^\top u - v)^\top x - b^\top u \\ \mathrm{s.t.} &\quad x\in\mathbb{R}^n. \end{align}

いま，行列 $Q$ は正定値対称行列であるから，ラグランジュ緩和問題の目的関数は凸関数であり，その最適解を $\overline{x}$ とすれば，$\overline{x}$ は最適性条件:

\begin{align} \nabla_x L(\overline{x}, u, v) = Q\overline{x} + c + A^\top u - v = 0 \label{3}\tag{3} \end{align}

を満たします．なお，$\frac{1}{2} x^\top Qx$ の $x$ に関する勾配ベクトルが $Qx$ となるのは，$Q$ が対称行列だからです．式 \eqref{3} は $Q$ が正定値行列であるため，

\begin{align} \overline{x} = Q^{-1} (v - c - A^\top u) \end{align}

と表せます．この $\overline{x}$ を用いることによって，ラグランジュ緩和問題の最適値関数は陽に表すことができて，それを最大化する問題は

\begin{align} \max_{u,v} &\quad \frac{1}{2} (v - c - A^\top u)^{\top} Q^{-1} (v - c - A^\top u) - b^\top u \\ \mathrm{s.t.} &\quad v\geqq 0 \end{align}

であり，これが求めるラグランジュ双対問題です．

3.11

遂次二次計画法における Powell の修正 BFGS 公式を用いて近似行列 $B_k$ を更新したとき，$B_k$ が正定値ならば更新後の近似行列 $B_{k+1}$ も正定値となることを示す問題です．

参考

• しっかり学ぶ数理最適化・サポートページ

しっかり学ぶ数理最適化　モデルからアルゴリズムまで (ＫＳ情報科学専門書)

実行列のフロベニウスノルムのメモ

フロベニウスノルム

行列 $\mathbf{A}\in\mathbb{R}^{m\times n}$ に対して，その全成分の二乗和に対してルートをとったものをフロベニウスノルムといい，$\|\mathbf{A}\|_F$ で表す．

また，次に述べるように $\|\mathbf{A}\|_F$ はトレースを用いて次のように表すことができる：

$$ \|\mathbf{A}\|_F = \sqrt{\mathrm{tr}(\mathbf{A}^\top\mathbf{A})}. $$

証明

\begin{align} \|\mathbf{A}\|^2_F &\underset{\text{(1)}}{=} \sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^2 \\ &\underset{\text{(2)}}{=} \sum_{j=1}^{n}\|\mathbf{a}_j\|^2_2 \\ &\underset{\text{(3)}}{=} \sum_{j=1}^{n}\left<\mathbf{a}_j,\mathbf{a}_j\right> \\ &\underset{\text{(4)}}{=}\sum_{j=1}^{n}(A^\top A)_{jj} \\ &\underset{\text{(5)}}{=} \mathrm{tr}(A^\top A). \end{align}

• (1): フロベニウスノルムの定義
• (2): $\|\mathbf{a}_j\|^2_2 = a_{j1}^2 + a_{j2}^2 + \dots + a_{jm}^2$
• (3): ユークリッドノルムの内積表現
• (4): $(A^\top A)_{jj} = \left<\mathbf{a}_j,\mathbf{a}_j\right>$
• (5): トレースの定義

$\|\mathbf{x}\mathbf{x}^\top\|_F$ の導出

tl;dr

• $\mathbf{x}\mathbf{x}^\top$ のフロベニウスノルム（Frobenius norm）を導く
• 体 $K$ として，$K=\mathbb{R}^{m\times n}$ を考える

フロベニウスノルム

行列 $\mathbf{A}\in\mathbb{R}^{m\times n}$ に対して，その全成分の二乗和に対してルートをとったものをフロベニウスノルムといい，$\|\mathbf{A}\|_F$ で表す．

また，次に述べるように $\|\mathbf{A}\|_F$ はトレースを用いて次のように表すことができる：

$$ \|\mathbf{A}\|_F = \sqrt{\mathrm{tr}(\mathbf{A}^\top\mathbf{A})}. $$

証明は 行列のフロベニウスノルムとその性質 を参照． こちら に証明を記載しました．

導出

\begin{align} \|\mathbf{xx}^\top\|_F &= \sqrt{\mathrm{tr}((\mathbf{xx}^\top)^\top\mathbf{xx}^\top)} \\ &= \sqrt{\mathrm{tr}(\mathbf{x}\mathbf{x}^\top\mathbf{xx}^\top)} \\ &= \sqrt{\|\mathbf{x}\|^2_2\cdot\mathrm{tr}(\mathbf{x}\mathbf{x}^\top)} \\ &= \sqrt{\|\mathbf{x}\|^2_2\cdot \|\mathbf{x}\|^2_2} \\ &= \|\mathbf{x}\|^2_2. \end{align}