2025-12-14

館山を旅行してきた。（その2）

旅行

昨日の続き。

2日目

朝起きてひと風呂浴びて朝食。

朝食もバイキングで、朝からたっぷり食べた。

そしてコーヒー飲みながら本を読んだり。いい時間だよねぇ。

部屋に戻ってからは毎年恒例のふりかえりとかをして、お昼にはちょっと外出。

道の駅白浜野島崎

続いて道の駅白浜野島崎へ。

ここは道の駅きょなん以上に何もなくてビックリした。とりあえずスタンプはゲット。一応、来年1月にカフェがオープン予定っぽいけど、こんなに何もないとなぁ（＾＾；

野島埼灯台

最後に野島埼灯台。

ここのせと食堂でお昼を食べたかったんだけど、なんか閉まってた。閉店してしまったのかはちょっと分からなかったけど、残念。前来たときに食べた海女定食が美味しかったんだけどなぁ。

代わりに亀の家三愛というお店でお昼。

ここも普通に美味しかった。とくにお味噌汁がやたら美味しくて、なんか出汁とかが違うのかも。

2日目はこれだけで、あとはホテルに戻ったんだけど、天気もよかったし、海沿いを走るのが最高に気持ちよかったね。

3日目

3日目は10時ちょっと前にホテルをチェックアウトして、そこからは怒涛の道の駅巡り。房総の道の駅はできるだけ回って（2つだけルートからかなり離れてるので今回は断念）、そこからさらに千葉の真ん中らへんに点在する道の駅を回った。

道の駅ちくら・潮風王国

海沿いを気持ちよく走ってまず向かったのは道の駅ちくら・潮風王国。

これまでにも横を素通りしたことはあったけど、中まで入ったのは今回が初めて。なんか中に大きな生簀とかもあって、凄かった。

マグロの生ハムというのがあって、気になって買って帰ったんだけど、いや、これが美味しかった。ちゃんとマグロでありつつ生ハムでもあって、こういうのもあるんだね。これはまた来たら買いたいと思う。

道の駅ローズマリー公園

続いてはローズマリー公園。

ここは何度も来てるのでお馴染みの場所。ただ、スタンプは押してなかったので、押してきた。あと、いつもははなまる市場しか見てなかったけど、なんかシェイクスピアの展示室とかあったのを今回初めて知った。

道の駅和田浦WA・O

また車を少し走らせて、道の駅和田浦WA・O。

クジラの骨格標本、凄いよね。

ここはクジラ推しな感じで、クジラに関する商品がいろいろあった。くじら肉まんが気になったので買って食べてみたけど、うん、まぁ普通の肉まんだったかなｗ

道の駅鴨川オーシャンパーク

海沿いの道の駅のラストは道の駅鴨川オーシャンパーク。

ここでもスタンプを押して、展望台へ。見晴らしがめっちゃよかった。

この時点で大体12時半で、お昼をどうしようか迷ったけど、朝もたっぷり食べたし肉まんも食べたばかりだったので、ここではパスしてあとで食べることにした。

道の駅ふれあいパーク・きみつ

ここからは山の方に入っていって、まず向かったのが道の駅ふれあいパーク・きみつ。

ここも以前、濃溝の滝を見にきたときに来たことがあった。ただやはりスタンプは押してなかったので、今回ゲット。

ちなみに濃溝の滝は今回はスルー。朝方が一番いい時間帯という話なので、その時間に来るのであれば別だけど、そうでなければ何度も見るようなところではない気がする（＾＾；

ここは隣接する片倉ダム記念館でジビエな食材がいろいろ手に入るのが魅力。で、次の場所でご飯だと食堂が閉まってる可能性がある時間だったので、ここでジビエ料理を食べていくことにした。

本当は一品料理でよかったんだけど、バイキングしかないようだった。 3,000円とかなので、ちょっとお高い・・・ただ、いろいろ食べれたのでよかったかな。とくに鹿肉のシュラスコが美味しかったので、たくさん食べた。写真にはないけど、ハチミツで味付けされたピザもお菓子感覚で食べれてよかったなぁ。

道の駅たけゆらの里おおたき

バイキングは1時間あったので本とか読みながらゆっくりと食べていたかったところではあったんだけど、あと5つ回りたかったので、30分くらいで離脱。次に向かった。

ここからは亀山湖の近くを走り抜けたりと、さっきまでは海沿いを走ってたのとは一転、山の中を走っていった。途中、すれ違いが難しいような場所もあったりして、そこはちょっと大変だったけど、基本的には走りやすくて気持ちよかったなぁ。紅葉もいい感じだったし。

そんな感じで道の駅たけゆらの里おおたきに到着。

時間もあまりなかったので、道の駅自体はスタンプだけ押して離脱。

道の駅むつざわつどいの郷

次は道の駅むつざわつどいの郷。

ここはかなりキレイな施設でビックリした。温泉もあるっぽい。時間がなくて入れなかったけど・・・

奥の方に花市場もあって、ここもかなりよかった。シクラメンが安く売ってたので、買う予定はなかったんだけど買って帰ったり。

道の駅ながら

続いては道の駅ながら。

とりあえずスタンプは押したけど、この時点で16時半くらい。あと2つ回りたかったんだけど、木更津の方は17時で終わりということで、ちょっと間に合わない感じだった。

道の駅あずの里いちはら

最後に向かったのが道の駅あずの里いちはら。

これで17時ちょい過ぎとかなんだけど、もう辺りは真っ暗。冬だよねぇ。

さすがに疲れが出てきて眠気があったので、ここでちょっと仮眠。 1時間くらい休んで18時くらいに道の駅を出た。

自宅へ

帰りはアクアラインを通って帰ろうかなと考えてたんだけど、ちょっと遠回りになるのと渋滞してそうだったので、来たときと同じように帰ることにした。ただ、やっぱり渋滞が凄かった。トイレにも行きたくなったので幕張手前で一度降りて、休憩を挟んで高谷JCT奥の市川南ICから乗り直したり。千葉から帰るときはいつも渋滞なので、そこだけなんとかなってほしいところ。

まぁそんな感じで1日で9つの道の駅を回れた。 3日間全部だと15個と、かなりいい感じだったなぁ。今回、グリーンファーム館山、三芳村鄙の里、木更津うまたくの里には行けなかったので、これらはまた別の機会に行きたい。

今日はここまで！

2025-12-13

館山を旅行してきた。（その1）

旅行

12/5(金)〜7(日)で館山を旅行して、道の駅をいろいろ巡ってきた。

千葉へ

自宅を11時ごろに出発して、技術書典19の本を発送したあと、高速に乗って千葉へ。

外環〜東関東道〜館山道と進んでいったんだけど、平日なのに普通に渋滞してた（＾＾；完全に止まってしまうとかはなかったけど、なかなか大変だったなぁ。途中からはさすがに流れていたので気持ちよく走れたけど。

道の駅保田小学校

まず向かったのは道の駅の保田小学校。

以前来たときは休日で、第2駐車場にやっと停められるとかだったけど、今回は平日ということもあって普通に停められた。道の駅のスタンプをゲットして、軽く散策したら次へ。

ばんや

時間も14時くらいになってておなかも空いてたので、ばんやへ。

ばんやには自転車で一度来たことがあったけど、そのとき以来。そのときはお風呂に入りたかったのもあって新館の方に入ったけど、今回は本館の方へ。

休日の昼とかは凄い混んでるんだと思うけど、平日で14時も過ぎてたので普通に入れた。他にも何組かお客さんはいて、やっぱり人気はあるんだと思う。

何にしようか迷ったんだけど、お寿司を頼んだ。

いやー、やっぱり美味しいね。これとアジ寿司も食べたかったんだけど、単品では頼めなかったので、今回は断念。もうちょい食べたい感じはあったんだけど、追加で5貫はさすがに厳しい（＾＾；

道の駅きょなん

ばんやを出たら次は道の駅きょなん。車を数分走らせたら到着w

一応近くに菱川師宣記念館とかもあったりするけど、建物としてはこれだけで、中も観光案内があるくらいだったり。今となっては珍しいけど、昔はこういうのが普通だったりしたのかなぁ？とりあえずスタンプだけ押して次へ。

道の駅富楽里とみやま

次は道の駅富楽里とみやまだけど、ここも車を10分くらい走らせるだけで到着。本当に道の駅だらけだなぁ（＾＾；

ここの2階でスタンプを押してフードコートをぶらぶらと歩いてたんだけど、ソフトクリームが美味しそうだったので思わず注文。

いやー、これは美味しかったね。また来ることがあればぜひ食べたいと思った。

道の駅とみうら枇杷倶楽部

ここからは少し車を走らせて（といっても30分くらいだけど）、道の駅とみうらへ。

時間としては16時くらいなんだけど、けっこう日が落ちてきてる。冬という感じよね。

ここでもスタンプはゲット。来たこと自体は何度かあったけど、スタンプラリーを始めてからは初めてだったからね。

以前来たときはシェイクを飲んでて、それがめっちゃ美味しかったんだけど、今回はすでに閉まってたので買えず。まぁソフトクリーム食べて満足してたので、そこまで残念ではなかったけど。

道の駅おおつの里

この日最後に向かったのが道の駅おおつの里。

ここでもスタンプをゲット。

そして中をいろいろ見て回ったけど、ビニールハウスの中を歩く感じで、これまた珍しく感じた。いろいろ花が売っていて、その中で金魚草がかなりいい感じだったので、悩んだ末に購入。 2泊するので家まで保つかなぁというのがあったけど、大丈夫だった。これはかなりよかったと思う。

ホテルへ

そんなわけで、初日は合計5つの道の駅を巡って、ホテルへ。

17時チェックインの予定だったんだけど、けっこう遅れて17時半に到着。

今回泊まったのは館山リゾートホテル。

ここは以前にも泊まってて、展望風呂の他、サウナもあるのがとてもいい。お風呂には合計6回くらい入ってるかもw

ちなみにサウナは以前来たときよりもパワーアップしてて、セルフロウリューできるようになってた。まぁ、桶に水が少ししか入ってなかったりとかはあったけど（＾＾；

夕食はバイキングで、今回は飲み放題つき。

ここはバイキングだけど料理が普通に美味しくて、お刺身もお肉もよかったなぁ。めちゃくちゃ食べて、デザートなんかもつまみながら本を読んだりもして、時間いっぱい堪能した。

今日はここまで！

2025-12-12

Vivliostyleと禁則処理の話。

技術組版

技術同人誌を書く場合、何かしらの組版システムを使うことが多い。 $\TeX$ であったり、Re:VIEWであったり、Vivliostyleであったり。最近はTypstも注目を集めている。

こういった組版システムを使うメリットの一つは、禁則処理をシステム側が適切に扱ってくれること。そのおかげで行頭に句読点がきたりしないかとかを気にせずに執筆に集中できる。

ただ、自分は最近Vivliostyleを使うことが多いんだけど、禁則処理がうまくされずに困ったことがあったので、その話をしてみたい。

これは技術書同人誌博覧会 Advent Calendar 2025の12日目の記事です。

結論

まず結論を書いてしまうと、Vivliostyleで禁則処理がうまく働くようにするには、2つの設定が必要になる：

原稿（Markdown）のフロントマターでlang: 'ja'を指定する
スタイルシート（CSS）で改行規則の設定として:root {line-break: strict;}を指定する

2つ目の設定はCSSで禁則について調べると普通に出てくるので、とくに問題はないと思う。

見落としがちなのが1つ目の設定。 CSSで改行規則として禁則処理をすると指定していても、HTMLのlang属性が"ja"になっていない場合、和文における禁則処理のルールが適用されないっぽい。

自分はモロにこの罠にハマって、なんで禁則処理がうまくいかないんだろうと頭を悩ませることになった。普段Markdownを書くときはlang属性とか別に気にしないからなぁ。でもそれではダメなので、Vivliostyleの原稿としてMarkdownを書くときは、もう常にフロントマターを書く勢いでやっていった方がよさそう。

<!-- 普段の場合、最初から書いてOK -->

# 見出し1

本文がどーたらこーたら・・・

<!-- Vivliostyleで原稿を書く場合、まずはフロントマターでlang: 'ja'を指定する -->
---
lang: 'ja'
# 他にも設定あれば書く
---

# 見出し1

本文がどーたらこーたら・・・

今年書いた同人誌の場合

ここからは余談で、今年書いた同人誌の場合、禁則処理をどうしてたかについて。

今年出したのは次の2冊：

これらはいずれもVivliostyleで書いてるんだけど、実は禁則処理の設定が違ってる。

1冊目のビジネスモデル本は2つ目の設定はしたものの1つ目の設定をしてなかったので、禁則処理がうまくいかずに困ったりした。けど、実物を見てもらえれば分かるんだけど、禁則処理で問題になってるところはないはず。じゃあどうやっているのかというと、全力でチェックしてひたすら書き直すことで対処している。言い方や説明の順序とかをとにかく書き換えて、問題になるような場所が出ないように人力で調整した。これは本当に大変だった・・・

これはさすがにツラかったので、2冊目の設計書本は頑張って調べて、1つ目の設定が必要なことを突き止めた。そのおかげもあって、快適に執筆することができた。やっぱり禁則処理をシステム側でやってくれるのは楽よ。当たり前の話ではあるんだけど、1冊目の苦労を味わったあとだったので、改めてそのありがたみを感じた。

ちなみに、過去の同人誌はBOOTHでも扱ってるので、気になった方はぜひ。

今日はここまで！

2025-12-04

『しっかり学ぶ数理最適化』と線形計画問題の話。

勉強会数学最適化

『しっかり学ぶ数理最適化』の勉強会の話で、線形計画問題の標準形について言及した。

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

作者:梅谷俊治
講談社

Amazon

今日はそれについて詳しく書いてみたい。

これは数理最適化 Advent Calendar 2025の4日目の記事です。

不等式標準形

線形計画問題でまず紹介されるのは不等式標準形：

$\begin{array}{ll} \mathrm{max.} & \boldsymbol{c}^\top \boldsymbol{x} \\ \mathrm{sub.\ to} & A\boldsymbol{x} \le \boldsymbol{b} \\ &\boldsymbol{x} \ge \boldsymbol{0} \\ \end{array}$

この形の嬉しいところは $\boldsymbol{x} \in \mathbb{R}^2$ なら実行可能領域をグラフに可視化できるので直観的に分かりやすいというところ。

実際、『しっかり学ぶ数理最適化』でも例題をグラフで可視化している：

これはとても分かりやすいし、（今もそうかは分からないけど）このように可視化して最適化問題を解くのは高校数学でも出てきたりする。

ただ、これを単体法で解くためにはスラック変数を導入して等式標準形に直すことになる。すると、各辺が $x_i = 0$ に対応することになり、2つの変数を0にする（＝非基底変数にする）と各頂点に対応することになるんだけど、これが慣れてないとちょっと分かりにくいっぽい。

実際、図としては2次元なんだけど、各点の座標を表示した図を見ると（目的値の $z$ を含めて）6次元となっていて、これはどういうことなんだ？と混乱する人も。

そして、実際にはここからは行列演算で解いていくので元の変数とスラック変数とで差はないんだけど、あとから導入された変数ということで差を感じてしまう可能性も。

等式標準形

そうやってあとから等式標準形にして混乱が生じるくらいなら、最初から等式標準形で考えた方がいいのでは？というのが自分の考え。

線形計画問題の等式標準形は次のようになっている：

$\begin{array}{ll} \mathrm{min.} & \boldsymbol{c}^\top \boldsymbol{x} \\ \mathrm{sub.\ to} & A\boldsymbol{x} = \boldsymbol{b} \\ &\boldsymbol{x} \ge \boldsymbol{0} \\ \end{array}$

余談だけど、実はこれは線形計画問題を一般化した錐線形計画問題（CLP: Cone Linear Programming）の形に従うものとなっている。

錐線形計画問題では内積を $\langle\boldsymbol{x}, \boldsymbol{y}\rangle$ とし、閉凸錐 $\mathcal{K}$ に対して次のような問題を考える：

$\begin{array}{ll} \mathrm{min.} & \langle\boldsymbol{c}, \boldsymbol{x}\rangle \\ \mathrm{sub.\ to} & \langle \boldsymbol{a}_i, \boldsymbol{x} \rangle = b_i \quad(i = 1, \ldots, m) \\ &\boldsymbol{x} \in \mathcal{K} \\ \end{array}$

これで内積 $\langle \boldsymbol{x}, \boldsymbol{y} \rangle = \boldsymbol{x}^\top \boldsymbol{y}$ とし、閉凸錐 $\mathcal{K} = \{\boldsymbol{x}| \boldsymbol{x} \ge \boldsymbol{0}\}$ としたものが線形計画問題。

また、対称行列の集合に対して内積を $X \bullet Y$ とし、閉凸錐を半正定値行列の集合としたものは半正定値計画問題（SDP: Semi-Definite Programming）になるし、内積をベクトルの内積、閉凸錐を2次錐にすると、2次錐計画問題（SOCP: Second-Order Cone Programming）となる。

ここで、1つ目の制約は $\boldsymbol{x}$ がアフィン空間に入っていることを示し、2つ目の制約はその空間が閉凸錐で切り取られた部分が実行可能領域になることを示している。なので、実は1つ目の制約はそれほど重要ではなく、2つ目の制約の違いこそが各問題の違いを生んでいるとも言えたり。（勉強したのがだいぶ前なのでけっこう曖昧だけど（＾＾；）

閑話休題で、線形計画問題の話に戻ってくると、つまり実行可能領域の境界を生んでるのは $\boldsymbol{x} \ge \boldsymbol{0}$ という制約であり、 $x_i = 0$ と固定するものが増えるたびにアフィン空間の次元が落ちて、最終的には面→辺→頂点へとなっていくことになる（点になったのが各基底解）。

先程の例題だと、5次元空間の中に2次元のアフィン平面があり、これが $\boldsymbol{x} \ge \boldsymbol{0}$ という制約で区切られた凸多面体になっていて、 $\boldsymbol{x}$ の1つの成分を0にすると辺になり、2つの成分を0にすると頂点になる。そしてこの凸多面体を $x_1\mathrm{-} x_2$ 平面に射影してきたものが本に載っている図となる。

・・・とまぁ書いたけど、これを説明してると難しい。これは図で表現しにくいものを図で表現しようとしてるからで、分かりやすくするために図を導入してるはずなのに、かえって難しくなってしまっている。これでは本末転倒なので、まずは形式的に処理できる行列演算の形で説明して、あとから幾何的な解釈を説明する方がよさそうとなる。そして、図での説明をしないなら不等式標準形をわざわざ出す嬉しさもないので、初めから等式標準形で考えていけばいいよねと。

等式標準形で説明した場合、理論的にもちょっと嬉しいところがあって、この双対問題は次のように書ける：

$\begin{array}{ll} \mathrm{max.} & \boldsymbol{b}^\top \boldsymbol{y} \\ \mathrm{sub.\ to} & A^\top\boldsymbol{y} + \boldsymbol{z} = \boldsymbol{c} \\ &\boldsymbol{z} \ge \boldsymbol{0} \\ \end{array}$

このとき、相補性条件は $\boldsymbol{x}^\top\boldsymbol{z} = 0$ と書けて、とてもシンプルな形になる。よく出てくる相補性条件の式はゴチャゴチャしすぎなんよね。

ちなみに錐線形計画問題だと双対問題は以下：

$\begin{array}{ll} \mathrm{max.} & \langle\boldsymbol{b}, \boldsymbol{y}\rangle \\ \mathrm{sub.\ to} & \sum_i y_i \boldsymbol{a}_i + \boldsymbol{z} = \boldsymbol{c} \\ &\boldsymbol{z} \in \mathcal{K}^\ast \\ \end{array}$

（ただし $\mathcal{K}^\ast$ は $\mathcal{K}$ の双対錐）

そして相補性条件は $\langle \boldsymbol{x}, \boldsymbol{z} \rangle = 0$ となるんだけど、見ての通り等式標準形で考えていれば錐線形計画問題との接続もスムーズなことが分かると思う。（強双対定理についてはもう少し条件が必要になるけど）

そんなわけで、不等式標準形から始めることが多いけど、等式標準形に絞って説明して、補足として幾何的なイメージを伝えた方がよさそうだと思うんだよねぇ。

今日はここまで！

2025-12-03

『しっかり学ぶ数理最適化』の定式化の話。

勉強会数学最適化

昨日、『しっかり学ぶ数理最適化』の勉強会に参加してきたことを書いた。

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

作者:梅谷俊治
講談社

Amazon

この中で定式化についていくつか気になったところがあったことも書いた。今日はそれについて詳しく書いてみたい。

これは数理最適化 Advent Calendar 2025の3日目の記事です。

生産計画問題

まずは線形計画問題の定式化の一例として挙げられていた生産計画問題に関して。

これは複数期間に渡る生産を考えて、生産量と在庫量をどうするか決める問題なんだけど、フローのように考えて各期間をノードとして表現し、入ってくる量（＝生産量と前期の在庫量）と出ていく量（＝次期への在庫量と需要量）が一致するという制約があるよねという話をしている。これ自体は納得いくんだけど、一緒に載っていた図2.3についていろいろ議論があった。

この図を見ると最後の期間 $T$ について次期への在庫 $s_{jT}$ の矢印が出てるけど、これって必要なの？ということ。

最適化した結果として、在庫を残すことに意味はないのでこの値は結局0になるんだけど、それならこの矢印は不要なのでは？というのが出た意見。これはもっともな意見で、反論するならそれは最適化の結果として分かることだから、とりあえず矢印を書いてるとか、他との様子を揃えるために矢印を書いてるとなりそう。ただ、それであるなら $s_{j0}$ の矢印が1期のノードに入ってくる方が自然で、ここも制約によって結局は0にはなるんだけど、0になるから書かないというのであれば、最後の $s_{jT}$ も同じように書いてない方が統一性が出てくる。さらに致命的なのが一番上にあるノードに入ってきてる $\sum_{t=1}^T d_{jt}$ という量で、これはつまりフローとして流れている総量が保存されてるよということを言いたかったんだろうと思うけど、情報としては冗長だし（各ノードから出てる $d_{jt}$ がまとめられてないのだから、各ノードに入ってくる $x_{jt}$ も別にまとまってる必要はない）、この図で出ていく量に注目するならここは $\sum_{t=1}^T d_{jt} + s_{jT}$ でなければならないので、整合性が取れてない。

おそらく、この図で書くなら $s_{jT}$ はない方がスッキリしそう。それか、一番上のノードをなくしてしまって、一番左には $s_{j0}$ が入ってくる矢印、一番右には $s_{jT}$ が出ていく矢印を書くと、数式を一番適切に表現できて、図としてもキレイな感じがする。

凸な非線形関数の近似

これも線形計画問題の定式化の話で、凸な非線形関数の最小化問題を線形計画問題で近似的に表現して解こうというもの。いくつかの点をサンプリングして隣接する2点を通る直線を使えば近似できるよね、というもので、多くの人は納得してた。

けど、どうして線形計画問題として考える必要があるのか分からないという人がいて、議論してみるとたしかにそうだねとなった。

というのも、サンプリングした点を線分で結んでいくので、近似した区分線形関数の最小値はサンプリングした点よりも下がることがないから。サンプリングした点の中で関数値が最小値になっているものが、線形計画問題として解くまでもなく最小と分かる。

実際にはこの凸な区分線形関数を単に最小化するわけではなく、制約として現れてきたり、他の制約によって領域が限定されたりするので、線形計画問題の制約として表現すること自体は意味がないわけではないんだけど、この例のように単純化しすぎてしまってると、たしかに線形計画問題として考える必要がそもそもなくなってしまうというのはちょっと盲点だった。

公平な予算分配の問題

絶対値やmin/maxを含む式を線形計画問題として定式化する例の一つとして、予算を公平に分配する問題が紹介されてた：

ただこれ、 $a_{ij}$ や $b_i$ が何を意味しているのかの説明が完全に漏れてる（＾＾；いまだに修正されてないので、みんなこういったところは流し読みしてるんだろうなぁ・・・（自分も一人で読んでたら絶対気にしてなかったと思う）

この $a_{ij}$ や $b_i$ が何を意味するのか、どこかに記述があるんじゃないかとみんなで探し回ったけど、見つからず。まぁ、意味合いは解釈できたので、自分の方からみんなに説明しておいた。

ここでは $n$ 個の事業があり、それぞれへの配分額を $x_j$ 、そして予算の合計を $B$ としてるんだけど、 $i$ が何を意味するのか、そして $a_{ij}$ と $b_i$ が何を意味するのかが説明されてない。

おそらく、事業をやることで達成すべき指標（たとえば売上とか、顧客満足度とか、環境への貢献とか）が $m$ 個あり、それぞれの達成目標が $b_i$ として与えられていて、各事業に予算 $x_j$ を与えることでそれぞれの指標が $a_{ij}x_j$ 伸びるので、その合計で目標を達成できるようにしよう、という感じ。その中で、予算が一番小さいものを最大化することで、指標を達成する配分の中で、最も公平な配分を得ようとしている、という感じなのかなぁと。

最短経路問題の完全単模性

これは直近の勉強会でやったところで、最短経路問題は完全単模行列になってるから、線形計画問題に緩和して単体法で解けばいいよ、という話。その直前には（有向グラフの）隣接行列は完全単模になることが紹介されていて、なるほど、これは最短経路問題の行列は隣接行列になってるということなのね、というのが自然な理解。

けど、ここで実際に示された式はこれ：

ここでみんな、「ん？これって隣接行列になってるの？」と止まることになった。

これも少し考えて解決したからみんなに説明したけど、本で説明があるともっとよかったなぁという気はする。まぁ、なるほどねと分かった嬉しさもあったけど。

これは2つ目の制約の符号が逆になってた方が分かりやすくて、 $-\sum_{e \in \delta^{-}(t)} x_e = -1$ となっていた方がよさそう。そうすると、1つ目の制約は $(\overbrace{1 \cdots 1}^{\delta^{+}(s)}\, 0 \cdots 0) \boldsymbol{x} = 1$ 、2つ目の制約は $(0 \cdots 0 \, \overbrace{-1 \cdots -1}^{\delta^{-}(t)}) \boldsymbol{x} = -1$ 、それ以外の制約は $(0 \cdots 0\, \overbrace{1 \cdots 1}^{\delta^{+}(v)}\, 0 \cdots 0\, \overbrace{-1 \cdots -1}^{\delta^{-}(v)}\, 0 \cdots 0) \boldsymbol{x} = 0$ と書けるので、この行ベクトルを積み重ねて作った行列で今度は逆に一つの有向辺 $e$ に注目してその列を見ると、その始点にあたる頂点での係数は1、終点にあたる頂点での係数は-1になるので、たしかに隣接行列になってる。

こんな感じで、なんとなく読み飛ばしてしまいそうなところも、じっくりと読んでいくといろいろ気になることがあった。

今日はここまで！

2025-12-02

『しっかり学ぶ数理最適化』の勉強会に参加してみた。

勉強会数学最適化

数理最適化の入門書として、モデリングからアルゴリズムまで幅広く学べるようになっている『しっかり学ぶ数理最適化』。

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

作者:梅谷俊治
講談社

Amazon

自分も買ってはいたんだけど、読むのが後回しになっていて、ずっと読んでいなかった。けっこうな厚さがある本だと、気合を入れないとなかなか読み始められないよね（＾＾；

そんな中、去年の12月にconnpassで勉強会の募集があった：

これはいい機会だと思って参加し、そのあとも継続的に参加し続けてる。そこで、勉強会の様子や感想を紹介してみたい。

これは数理最適化 Advent Calendar 2025の2日目の記事です。

勉強会の進め方

勉強会は月1回で、毎月第2土曜日の9:30〜12:30で開催されている。 3時間あるけど、最初の10〜20分は挨拶や近況報告のアイスブレークがあり、途中で10分くらいの休憩を挟むことが多いので、実質2時間半くらい。毎回10人前後集まっている感じ。

スタイルとしては、誰か一人がチューターを務めたり、発表者になったりというのではなく、みんなで一緒にワイワイと議論を深めていく感じ。ランダムに読む人を決めて、ある程度のまとまりを声に出しながら読んでもらったら、そこで分からなかったこととかを議論して次に進むというのを繰り返す。

声に出して読んでもらうというのがけっこう大きくて、じっくりと読んでいくので、なんとなく読み飛ばしてしまいそうなところも「あれ？」となって議論になることがけっこうあった。参加してる人のバックグラウンドにも幅があるので、人によって引っ掛かりポイントが違ったりというのもあったり。こういうのを通して本当にじっくりと読み進められているのは、なかなかいい経験になってると思う。

ただその分時間がかかってるのも事実で、けっこうなスローペースで進んでる。しっかりとやろうとすると、どうしてもそうなるよねぇ。これまで12回開催していて、1章と2章が終わり、3章はスキップして（これは当初の予定通り）、今は4章の完全単模行列周り。 2章までが74ページ、4章に入ってからが29ページとかなので、合計100ページちょっとで、一回あたり10ページ弱とか。 4章の残りは130ページ強あるので、このペースだと追加であと1年ちょっと掛かる計算（＾＾；まぁどこかキリのいいところまでなのかなぁ。

感想とか

ここからは本の感想とか勉強会で思ったこととか。

定式化の例がたっぷり

数理最適化の入門書だと定式化されたあとの解き方に関する理論やアルゴリズムの話が中心となるけど、この本はその前の定式化に関する話がたっぷりと書かれているのがやはり特徴的。正直、一人で読んでたら「そんな応用もあるんだなぁ」くらいで軽く読み飛ばしてたと思うんだけど、今回はみんなで読み合わせしていったこともあって、かなりじっくりと読んでいった。整数計画のスケジューリング問題とか長方形詰め込み問題とかは、上手いこと定式化するなぁとみんなで感心したり。

ただ、じっくり読んでいった分、「これってどうなってるんだろう？」みたいなののもちょこちょこあったり。これについてはまた別の記事で話してみたい。

ちなみに、「2.1 線形計画問題の定式化」で3回くらい使ってて、「4.1 整数計画問題の定式化」で直近3回が使われてる（まだ途中であと1回くらい必要）。たぶんここまでじっくり読んでる勉強会は他にないと思う。

区切りが分かりにくい場合がある

じっくり読んでてちょっと気になったのは、話題やコンテキストの切り替わりがちょっと分かりにくい場合があったこと。

たとえば、「2.1.3 連立1次方程式の近似解」では、最初に平均誤差を最小化する例を出し、次にその応用として回帰分析で平均誤差を最小化する例、さらに最悪誤差を最小化する例、さらには予算分配を公平にする例を出していたりするんだけど、区切りがちょっと分かりにくい。

とくに、最初の平均誤差を最小化する例では、係数の$a_{ij}$や$b_i$が与えられ、変数の$x_j, z$を最適化するのに対し、次の回帰分析の例では、変数にあたる$x_i, y_i$が与えられたもので、係数にあたる$w_i$を最適化するので、ちょっとややこしそう。たしかに使ってるテクニック自体は同じなんだけど、同じ文字が一方では与えられたもの、他方では求めたいものになってるので、しっかりと区切りを入れてコンテキストが変わったことを分かりやすくした方がいいのかも。正直、自分も慣れてしまってるので混乱はなかったけど、いろんな人がいると、たしかに混乱する人もいるなぁと思ったり。

あと、「2.3.1 双対問題」では双対問題の導出を行っているんだけど、最初に不等式標準形の双対問題を導出したあと、続けて非負制約のない問題の双対問題の導出、さらには等式標準形の双対問題の導出まで行っている。それぞれが地味に混み入った話なんだけど、それが続けて行われてるので、パッと見だと今何をやってるのかが分からなくなる。これと同じことが「2.3.2 緩和問題」でもラグランジュ緩和を用いた形での導出で繰り返されてるので、ややこしさを増している感じ。

正直、標準形を1つ決めれば、いずれも標準形に変形してこれるのだから、その標準形についてだけ議論した方がスッキリしそう。実際、そのあとの双対定理についての議論は等式標準形についてだけ議論してるし。

単体法を図で説明する功罪

線形計画問題を導入するとき、不等式標準形にすることで実行可能領域を2次元のグラフで図示し、単体法では各頂点を巡るようにして最適解に辿り着くんだという説明はよくあるもの。ただ、この説明は直観的で分かりやすいものの、いいところばかりではないよなぁとも思ったり。

具体的には、単体法を解くためにスラック変数を導入して等式標準形に直すわけだけど、このときに元の変数とスラック変数との差はなんなのかという議論が起きてたり、元の2次元の図でスラック変数がどのように現れているのかの理解に手間取っていたりがあった。各直線が変数の1つが0になってることを表してたり、直線の交わりである頂点は変数2つが0になってる（5変数で制約が3つなので非基底変数の数は2個）ことを表してたりというのが、「2次元で」考えてるとなかなか掴みにくい。

そのあとの図（たとえば図2.8や2.9）だと、2次元の図なのに点の座標は（目的関数値の$z$を入れて）6次元で表現されてて、実際にはこれが5次元空間にある実行可能領域を2次元平面に射影したものであることが暗に示されてるんだけど、まぁなかなか厳しそう。

これについてもまた別の記事で話してみたいと思ってるけど、等式標準形とそこでの行列演算に話を絞って、幾何的なイメージはあとから与えた方がこのギャップを生じなくていいのかもなぁと思う。

双対問題や相補性条件の意義

個人的に意外に感じたのが、双対問題とか相補性条件を考える意義は何なのか？という話がけっこう出ていたこと。

あまり深く考えず、双対問題っていうのがあるのねーとか、そういうのを考えたときに主問題と双対問題でキレイな関係性が言えるのねーとか、素朴に捉えていたんだけど、なんで双対問題なんか考えるの？みたいな声がけっこうあった。

これは双対性の議論をする前に単体法の議論を終わらせていたのが大きくて、すでに単体法で解けるようになってる（＝最適解が分かってる）のに、なんでさらに双対問題とかを考えて最適解を上とか下から抑えようとしているの？という疑問で、まぁ言われてみればたしかに。あえてそれでも考えようというなら、何かしらの嬉しさがほしいわけだけど、その嬉しさがなかなか出てこないもどかしさがあったっぽい。

理論的には双対問題と相補性がアルゴリズムの背後にあって正しさを支えてくれているようなところがあるんだけど、まぁそういうのを知らなくてもすでに解けちゃってるので、あとからそういうのを言われてもまぁ響かないよなぁ（＾＾；

かといって、先に双対理論をちゃんとやってから単体法を説明するのだと、アルゴリズムに辿り着く前に諦めちゃう可能性もあるし、このあたりは難しいところ。

もちろん、後述の感度分析とか、（精度保証のある）近似アルゴリズムとかだと、双対問題が最適値の下界（や上界）として機能するといった応用的な嬉しさもちゃんとあるんだけど、そういった話をするにはさらに議論を重ねないといけないし。

感度分析

感度分析についてはしっかりと勉強してなかったので、ここで改めてしっかりと勉強できたのがよかった。

ただ、説明がちょっと分かりにくかったかも。どういう変更が入った場合を考えるのか、どういう条件を満たされてた場合には解が変わらないのか、条件が満たされてない場合にはどうやって計算を続けていけばいいのかとかの全体像がまず最初に示されているとよかった気がする。

独学の難しさ

勉強会に参加してて思ったのは、独学だとなかなか大変なんだろうなということ。

自分は数理最適化についてある程度勉強してたし、他にも数理最適化について知見がありそうな人がいたので、必要に応じて助け舟を出していたところがあった。でも、そういった助け舟がない状態で本を読むのだと、それだけで理解していくのはなかなか大変そうに感じた。なので、数理最適化について何も知らない人は、一人で読んでいくというよりも、ある程度知ってる人と一緒に読んでいったり、相談する場があったりするとよさそう。本当は一人で読み進めていっても理解できるのが一番いいとは思うけど。

今日はここまで！