OR でわかる線形代数

c

オペレーションズ・リサーチ

OR でわかる線形代数

小市 俊悟

理系の大学生であれば1年生で習うであろう，線形代数学の知識が，OR，特に最適化のなかでどのように 使われているかを紹介する．線形代数学で学ぶことが必ずしもそのまま使われているわけではないが，その アイディアは最適化のそこかしこに現れる．線形代数学の言葉を用いるならば，線形代数学はORという空 間を張るベクトルの一つと言えよう．

キーワード：ガウスの消去法，線形結合（一次結合），対角化，線形計画問題，双対問題

1.

はじめに

大学で「線形代数学」の講義を担当することになっ て，書店で線形代数学の教科書を探したが，その数の 多さに驚いたことを思い出す．これは，線形代数学を 理解してもらいたいという熱意ある著者が単純に多い ためなのかもしれないが，多くの理系学生が線形代数 学の理解に苦しんでいることの現れでもないかと思う．

高校数学から「行列」が消えてしまい，大学に入って 初めて「行列」に直面し，線形代数学に苦しむ学生が ますます増えないかと心配である．

さて，本特集は，企業などでORに触れることとなっ た方や，ORを学び始めた学生を対象にした「ORと 数学・統計」ということで，本稿は特にORで使われ る「線形代数学」がテーマである．体系化された現代 数学において，線形代数学は，線形空間と線形写像を 研究する分野という位置づけであるが，ORを利用す る人にとっては，ベクトルや行列を研究する分野とい う理解でもおよそ十分であろう．本稿も，ベクトルや 行列を取り上げているので線形代数学というぐらいの 立場である．線形代数学の講義で聞いた言葉がところ どころに出てくるなぁ，という感じでお読みいただけ れば幸いである．

形 線

数 代 0 1 1 0

=

線 形

代 数

線形代数学に関する標準的な用語については，線形 代数学の専門書にゆずることにして，OR，特に最適化 に関連する線形代数学について，ORを学びたい，も しくは学び始めた方に参考になる（かもしれない）こ こいち しゅんご

南山大学

〒466–8673愛知県名古屋市昭和区山里町18 [email protected]

とを本稿に綴る．ベクトルの内積については，たとえ ばxyのように行列（ベクトル）の転置（右肩に を付けて表す）を利用して書くことにする．

2.

数式も言葉

思い出せば，小学生の頃の「算数」では，数式3+2 = 5 にも，「みかんが3個，リンゴが2個あるとき，全部 で果物は何個あるでしょう」（答えは，もちろん5個）

のような実際的な意味があった．ところが，おそらく 方程式を扱うあたりから，「計算する」ことに重点が置 かれるようになってしまう．「計算量」のような話をす るまでもなく，「計算できなければ答えはでない」とこ ろもあるので，それはそれで重要なことではあるもの の計算ばかりをすることは，ややもすれば，「数学= 面倒=つまらない」な印象を与えてしまう．

残念ながら，大学における線形代数学でも，特に初 学者向けの講義では，「（行）基本変形」や「行列式の 計算」といった煩雑な計算が中心になる．これは，線 形代数学に出てくる定理の証明が計算と不可分，すな わち連立一次方程式を解くことに帰着されることも多 いからであろう．しかし，特に初学者に，そこまでわ かったうえで線形代数学を学んでもらうことは，なか なか期待できないことである．線形代数学で計算ばか りさせられたという印象が残るのも無理はない．

機械的な計算のために，数学がちょっぴり嫌いになっ てしまった方に対して，ORは算数的な楽しみを与え てくれるかもしれない．ORに出てくる数式には，抽 象度が高いものもあるけれど，幸いにして実際的な意 味をもつものが多い．さらに，幸いなことに，ORに おいて，実際に計算することは，一部の専門家を除い て計算機がすることである．ORを実践する人にとっ ては，数式の意味を理解すること，そして，意味ある 数式を（これまた，技術的には良し悪しがあるが）立

てられることが（これまでの筆者の経験からすれば）

重要である．

3.

ガウスの消去法と線形計画問題

ORに出てくる数式には，実際的な意味があること の例として，次のような生産計画問題を取り上げ，そ れを線形計画問題として表現することにしよう．

ともに原料XとYを使った2種類のジュース1 と2がある．どちらも，10 ml当たり3円で販売 される．ジュース1は，10 ml作るのに，原料X を2 ml，原料Yを3 ml必要とする．ジュース 2は，10 ml作るのに，原料Xを1 ml，原料Y を4 ml必要とする．原料XとYは，それぞれ 40 ml，100 mlある．作ったジュースはすべて売 れるものとして，売り上げが最も大きくなるよう にジュース1と2を作りなさい．

ジュース1をx1×10 ml，ジュース2をx2×10 ml 作るものとしよう．このとき，売り上げは，ジュース 1と2ともに10 ml当たり3円で販売されるので，

3x1+ 3x2

と表される．これを，最大化するのが目的である．さ て，問題文を読めば，原料に限りがあるので，ジュース をいくらでも作ることができるわけではない．ジュー ス1をx1×10 ml，ジュース2をx2×10 ml作ると き，原料XとYについて，その使用量は，それぞれ 2x1+x2，3x1+ 4x2 となる．これらが原料の利用可 能量を超えてはいけないから，次の二つの（不等）式 が成り立たないといけない．

2x1+x2≤40, (1) 3x1+ 4x2≤100. (2) 作る量が負ということもありえないから，

x1≥0, x2≥0 (3) という条件も加えておく．以上は，まとめて次のよう に記述される．

(P) maximize 3x1+ 3x2

subject to 2x1+x2≤40, 3x1+ 4x2≤100, x1≥0, x2≥0.

ここで，行列やベクトル

A= 2 1

3 4

,b= 40

100

,c= 3

3

,x= x1

x2

,0=

0 0

を導入すれば，問題(P)は，

(P’) maximize cx subject to Ax≤b,

x≥0.

と書ける．一般に，行列やベクトルを使って，問題(P’) のように書ける問題を線形計画問題と呼ぶ．次節の内 容を含めて，線形計画問題についてもっと詳しく，ま たより実際的な問題を知りたい方は，文献[1]などを 参照していただきたい．

まずは，問題(P)を解いてみよう．問題(P)は，変 数がx1とx2の二つだから平面に図示することができ る．式(1)，(2)，(3)を制約式と呼ぶが，図1では，そ れらを満たす変数の領域が灰色で示されている（境界 を含む）．この領域に入る変数は，制約式を満たすとい う意味で実行可能であるとされ，この領域のことを実 行可能領域と呼ぶ．図1において，原点を通る破線は，

ベクトルcに平行な直線で，これをとする．問題(P) の目的は，cxを最大化することであったが，ベクト ルcとxのなす角をθとすれば，cx=cxcosθ であることを思い出してもらい，さらにcが定数で あることを踏まえると，結局，xcosθを最大にすれ ばよいことがわかる．またまた，ここで，xcosθ^は，

ベクトルx（の先端）から直線におろした垂線の足 と原点を結ぶ線分の長さに等しいことを思い出しても らうと，図1から，cxを最大にするベクトルx^∗は，

直線2x1+x2= 40と3x1+ 4x2= 100の交点を表す ベクトル

x^∗= 12

16

であり，売り上げの最大値は3×12 + 3×16 = 84で あることがわかるであろう．この程度の問題であれば，

高校数学の知識でも解けなくはない．

さて，今の解法は，2変数だからできたところもあ るし，線形代数学といっても内積ぐらいしか出てこな い．（線形代数学は幾何学という人もいるが）どちら かというと幾何学的な解法であった．それでは，もう 少し線形代数学のテクニックを使ってみよう．線形代 数学で習うテクニックと言えば，連立一次方程式を解 くためのガウスの消去法である．行基本変形を使って，

図1 問題(P)の実行可能領域

階段行列を作る，あれである．

とは言ってみたものの，問題(P)にガウスの消去法 を適用するにはいささか問題がある．それは，問題(P) が不等式で書かれていることである．不等式は，辺々 の足し算はできるが引き算はそうもいかない．そこで，

Ax≤bの部分だけでも，新たな変数s1とs2を導入す ることで等式にする．すなわち，制約式(1)，(2)，(3) を次のように書き換える．

2x1+ x2+s1 = 40, (4) 3x1+ 4x2 +s2= 100, (5) x1≥0, x2≥0, s1≥0, s2≥0. (6) このように書けることは，式(4)をs1について解い て，s1≥0に代入すれば，式(1)が得られることなど からわかるだろう．それでは，新たな制約式(4)と(5) の部分を線形代数学でおなじみの拡大係数行列と呼ば れる行列

2 1 1 0 40

3 4 0 1 100

(7)

で表すことにしよう．制約式(6)もあるが，しばらく はこの行列にのみ着目する．

さて，式(7)の行列は，第3列と第4列でできる 行列が単位行列であることからわかるように列を入れ 替えれば，すぐに階段行列になる．もし，連立一次方 程式を解く問題であれば，これ以上，行基本変形をす る必要はない．(x1, x2, s1, s2) = (0,0,40,100)がその 答え（解）である．単位行列（となる部分）の列に相 当しない変数（この場合，x1とx2）を0にしてしま うのが，ガウスの消去法による連立一次方程式の解法 であったことを思い出してもらいたい．ところで，解

(x1, x2, s1, s2) = (0,0,40,100)は実行可能ではあるが，

x1とx2が0では何の売り上げもないので問題(P)の 最大値を与えるような解ではない，すなわち，最適解 ではないことは明らかであろう．

では，x1が正になるような解を求めてみよう．その ためには，第1列が単位行列の一部になるようにガウ スの消去法を行えばよい．

2 1 1 0 40

3 4 0 1 100

−→

1 ¹₂ ¹₂ 0 20 3 4 0 1 100

−→

1 ¹₂ ¹₂ 0 20 0 ⁵₂ −³₂ 1 40

(8) これで，(x1, x2, s1, s2) = (20,0,0,40)という解が得 られた．この解が，先ほどの解よりよいのはすぐにわ かるだろう．では，（この解が最適解でないことは知っ ているが）この解は最適解であろうか．これについて は悩ましい．式(8)の行列を一度，連立一次方程式の 形式に戻そう．

x1+1 2x2+1

2s1 = 20, (9) 5

2x2−3

2s1+s2= 40. (10) 単純に考えて，x2が0なのはもったいない．しかし，

s1はすでに0だから，式(9)においてx2を大きくしよ うとすると，x1を小さくしなければならない．トレー ドオフが生じるのである．これだから線形計画問題は 難しい．式(10)には，x1が現れないので，このトレー ドオフには関係しない．式(9)にだけ着目しよう．変 数x1とx2の係数の比は1 : 1/2なので，x2を2大 きくしたら，x1を1小さくするという関係である．い ま，ジュース1も2も10 mlで3円だったので，x1を 1小さくしてでも，x2を2大きくできるのであれば，

それは売り上げに貢献する．ということで，x2を大き くするのが得策のようである．変数x2も正になるよ うにガウスの消去法を再び用いれば，次のようになる．

1 ¹₂ ¹₂ 0 20 0 ⁵₂ −³₂ 1 40

−→

1 ¹₂ ¹₂ 0 20 0 1 −³₅ ²₅ 16

−→

1 0 ⁴₅ −¹₅ 12 0 1 −³₅ ²₅ 16

これで，最適解(x1, x2, s1, s2) = (12,16,0,0)が得ら れた．

ここまでに説明した解法は，単体法と呼ばれる線形 計画問題の標準的な解法を参考にして，対象を問題(P) に限定し，なおかつガウスの消去法（行基本変形）を 知っていればできる計算で最適解が得られるようにし たものである．本来の単体法は，一般的な線形計画問 題に適用できるように，辞書と呼ばれる，より簡便な 表記法を用いたり，変数選択や（上でややごまかした）

解の最適性などについて，より細かな条件設定がされ ている．単体法をもっときちんと知りたい方は，最適 化法についての専門書[2]などを読んでいただきたい．

単体法について，最後に付け加えたいことがある．上 では解く過程で三つの解を得たが，変数x1とx2だけ に着目すると，それらは，

(x1, x2) = (0,0)→(20,0)→(12,16) というものだった．これら3点は，いずれも，四角形と して図1に示された実行可能領域の頂点である．これ は偶然ではないというのが，伝えたいことである．一 般に，線形計画問題の実行可能領域は（凸な）多角形 を一般化した多面体と呼ばれる集合になる．これに関 連してよく知られた事実として，「もし，実行可能領域 である多面体が頂点をもつならば，頂点（を表すベク トル）のなかに最適解がある」という事実がある．単 体法にとって，この事実は重要であり，実際，単体法 の手順を解析すると，単体法は，多面体が頂点をもつ とき，頂点を辿ることで最適な頂点（解）を見つける ような手法になっている．線形計画法の理論的な研究 においては，多面体の研究も盛んであり，そこでは行 列の階数が頻出する．

4.

線形結合と双対問題

線形代数学の講義をもつと，意外とある質問が，「ベ クトルの線形結合（一次結合）って何ですか」という質 問である．簡単に答えるならば，「いくつかのベクトル があるとき，それらに実数をかけて足したもの」とで もなろうか．補足として，「かける実数を変えると違う ベクトルになるけど，それらも全部，線形結合」という 具合である．きちんと，その定義を述べると次のよう になる．ベクトルa1,a2, . . . ,akと実数t1, t2, . . . , tk

に対して，

t1a1+t2a2+· · ·+tkak

をベクトルa1,a2, . . . ,akのt1, t2, . . . , tkを係数とす

る線形結合という．慣れれば，5の倍数とか，3で割っ て余りが1の整数，みたいなものと発想は同じような 気もするが，ベクトルということもあって，とらえど ころがないのかもしれない．

さて，この節では，前節に引き続き問題(P)を用い て，その双対問題を考えつつ，この線形結合を振り返 りたいと思うが，不等式が出てくることもあって，ベ クトルにかける実数はすべて非負，すなわち0以上の ものに限定する．この場合，線形結合ではなく非負結 合と呼ぶのが一般的である．

ところで，最大化問題を解くときに，一番素直な考 え方はおそらく，よりよい解はないかと探していき，最 良の解を得る方法である．前節で説明した単体法（の ような方法）は，まさにこの方法といえる．一方，最 大値を得るという発想では，次のような方法も考えら れるだろう．最大値について，これ以上は大きくない だろうという値を考え，その値を限界まで小さくする 方法である．（限界まで小さくしたときに，最大値と一 致するかは別問題であるが，）線形計画問題の双対問題 は，この発想を具体化することで得られる．それを問 題(P)を使って説明しよう．

まずは，最大値より大きいだろうという値を見積も らないといけない．手掛かりとなるのは制約式くらい なので，制約式に着目しよう．問題(P)の制約式(1) の両辺を3倍すると次を得る．

6x1+ 3x2≤120.

変数x1とx2が非負であることを前提とすれば，次が 成り立つ．

3x1+ 3x2≤6x1+ 3x2≤120.

これより，問題(P)の最大値は120よりは大きくなら ないことがわかる．さて，同じことを制約式(2)にも 適用できるが，もっと大胆に，たとえば，制約式(1), (2)の辺々を足してしまおう．すると，次を得る．

5x1+ 5x2≤140. (11) 問題(P)の制約を満たす(x1, x2)であれば，この不等 式(11)も満たすことは明らかであろう．ここで，不等 式(11)の両辺を3/5倍すれば，

3x1+ 3x2≤84

を得る．何と，問題(P)の最大値84が出てきた．以上 の手順を，数学的に記述したのが双対問題であり，限

界まで小さくすれば最大値まで得られるというのが，

（強）双対定理と呼ばれるものである．双対定理につい ては，専門書[2]などに任せることとして，双対問題 を作る部分については，以下に，もう少し詳細な解説 をする．

上で行ったのは，ある不等式を3倍するとか，二つ の不等式を足してから全体を3/5倍する（これは，そ れぞれを3/5倍してから足すのと同じ）という操作で ある．これらは，（0倍も含めれば）制約式(1)と(2) に（不等号の向きを変えないために）非負の（変）数 y1, y2をそれぞれかけて，足し合わせることで，

y1(2x1+x2) +y2(3x1+ 4x2)

= (2y1+ 3y2)x1+ (y1+ 4y2)x2

≤ 40y1+ 100y2

という不等式を得ることの具体例といえる．ここで得 られた40y1+ 100y2という値が，問題(P)の最大値 以上の値であるためには，

3x1+ 3x2 ≤ (2y1+ 3y2)x1+ (y1+ 4y2)x2

≤ 40y1+ 100y2

となればよいわけであるが，さらにx1とx2が非負で あることを前提とすれば，x1とx2の係数について，

2y1+ 3y2≥3, (12) y1+ 4y2≥3 (13) が成り立てばよい．非負条件y1≥0, y2≥0と合わせ て，これらが双対問題の制約式となる．双対問題の目 的は，値40y1+ 100y2 をなるべく小さくして，問題 (P)の最大値を探ることであったから，次のようにま とめられる．

(D) minimize 40y1+ 100y2

subject to 2y1+ 3y2≥3, y1+ 4y2≥3, y1≥0, y2≥0.

さて，いまの話の流れで，非負結合（線形結合）を 持ち出すのは，やや蛇足的なところもあるが，いま一 度，双対問題を作る過程を見てみよう．問題(P’)を書 くために導入した行列A =

2 1 3 4

を思い出しても らって，行列Aの行ベクトル[ 2 1 ],[ 3 4 ]を転置し たものを

˜ a1=

2 1

, a˜2= 3

4

と表す．上で述べた，制約式(1)と(2)にy1, y2をそ れぞれかけて，足し合わせるという操作において，変 数x1とx2の係数をまとめるという計算は，ベクトル

˜

a1,a˜2のy1, y2を係数とする線形結合を作ることと同 じである．実際，

y1a˜1+y2a˜2=

2y1+ 3y2

y1+ 4y2

を得るが，第1成分，第2成分はそれぞれ双対問題 (D)の制約式(12)，(13)の左辺に現れるものに他なら ない．ベクトルa˜1とa˜2は行列A^{の転置行列}A^の 列ベクトルであるから，ベクトル

y=

y1

y2

として，

y1a˜1+y2a˜2=Ay

のように書ける．これより，問題(P)を表すのに導入 した行列Aやベクトルb,c,0を使って，双対問題は

(D’) minimize by subject to Ay≥c,

y≥0 と書ける．

双対問題を作る過程を，非負結合でとらえることは，

双対問題を幾何学的に解釈するときに役に立つ．ベク トルa˜1,a˜2 は，それぞれ図1に示された二つの直線 2x1+x2= 40,3x1+ 4x2= 100の法線ベクトルであ る．双対問題は，これら法線ベクトルの非負結合でc 以上のベクトルを作るとき，byを最小にするような 係数y1, y2を求める問題になっている．この辺りの話 について，より詳しくは文献[3]を参照していただき たい．

ところで，以上見てきたように，双対問題は少々技 巧的にして得られる．2節で，ORに現れる式には実 際的な意味をもつものが多いと述べたが，双対問題に 現れる式にも解釈は付けられるだろうか．正直なとこ

ろ，なかなか難しいのであるが，考えてみよう．制約 式(12)，(13)の右辺は単位が円なので，変数y1, y2は，

各原料について，1 ml当たりの金額換算された「何か」

であろう．一つの解釈として，y1, y2はそれぞれ，消費 者に転嫁される原料XとYの価値のようなものとい えるだろうか．消費者はジュースを買うとき，原料の 価値，もう少し具体的に言うならば付加価値を含めた 原料費を負担するものと考えられる．販売者からすれ ば，利益が必要なので，それは販売価格と同じか，そ れ以上である必要があろう．これが，双対問題の制約 式で表されている．消費者にとっては，この負担は最 小であることが望ましいので，最小化問題となる．議 論あるところかと思うが，結論づけるのは難しく，実 際，生産計画問題の双対問題については，探せば色々 な解釈を見つけられる．それらを参考にしていただき たい．その際，「潜在価格」はキーワードの一つである．

5.

対角化と二次関数

一般に，線形計画問題とは，行列やベクトルを使っ て，(P’)や(D’)のように書ける問題をいうのであっ た．それから明らかなように，記述できる問題には限 界がある．特に，最大化や最小化されるものは，変数 同士のかけ算や1以外のべき乗も含まない，いわゆる 一次関数でなければならない．一次関数でないものは 非線形計画問題に分類される．この節では，非線形計 画問題につながる線形代数学の話をしよう．

「非線形=複雑」となるのが一般的なので，「非線形 計画問題=難しい」という気がするかもしれないが，

必ずしもそうではない．解ける最適化問題か否かとい う観点では，「線形か非線形か」よりも「凸か非凸か」

のほうが決定的とされる．

ここで，「凸とは何か」を確認しておこう．ベクトル を変数とし，実数値をとる関数fが凸であるとは，任 意のベクトルx1,x2と0≤α≤1であるような実数 α^{に対して，}

αf(x1) + (1−α)f(x2)

≥f(αx1+ (1−α)x2) (14)

が成り立つことをいう．図2は，凸関数，すなわち式 (14)を満たす関数の例である．内積を使って定義され る関数f(x) =bxについては，内積の線形性から凸 性が直ちに導かれる．実際，

図2 凸関数の例 αf(x1) + (1−α)f(x2)

= αbx1+ (1−α)bx2

= b(αx1+ (1−α)x2)

= f(αx1+ (1−α)x2) (15) のように，式(14)における不等号を等号で満たす．

さて，1変数xの関数f(x)で凸関数といえば，二次 の項x²の係数aが正の二次関数f(x) =ax²+bx+c である．2変数以上の関数の場合の二次関数は，一般 に，行列A,b,cを用いて

f(x) =xAx+bx+c (16) と書ける．このとき，行列 A ^{は対称行列，つまり} A = Aだと思ってよい．なぜなら，たとえば2変 数で，

x1 x2

a b c d

x1

x2

= x1x2

a ^b+c₂

b+c

2 d

x1

x2

が成り立つからである．それでは，2変数以上の二次 関数において，凸か非凸かは何で決まるだろうか．2 変数関数の場合のそれについて考えてみよう．

まず，二次関数が凸か非凸かを議論するとき，式 (16) における bx+c の項は式(15) で見たよう に不等号に影響しないので不要である．したがって，

f(x) =xAxに話を限定する．まず，行列A^の簡単 な例として，

A1= 2 0

0 1

, A2= 2 0

0 0

, A3= 2 0

0 −1

を考えてもらうと，関数fはそれぞれ，

f1(x) = 2x²1+x²2, f2(x) = 2x²1, f3(x) = 2x²1−x²2

となる．行列A2のときのf2は凸だろう．凸関数の和 は凸という事実を用いれば，A1のときは凸関数の和で あるからf1も凸である．一方，A3のときは

x1= 0

−1

, x2= 0

1

, α= 1 2

に対して，式(14)を確かめてもらえば成り立たないこ とから，f3は非凸であることがわかる．正方行列の左 上から右下に向かう対角線上にある成分のことを対角 成分と呼ぶ．対角成分以外の成分がすべて0である場 合，どうやら対角成分がすべて非負であれば凸，負の 成分があれば非凸になりそうである．この予想は正し いのであるが，あとでもう少し厳密に表現しよう．

ところで，どんな対称行列Aも適当な直交行列P

（すなわち，P⁻¹=P）を下記のようにかけることに より，対角成分以外はすべて0となるような行列に変 形できるのであった．

PAP =

λ1 0 0 λ2

.

いわゆる行列の対角化である．対角化により現れる対 角成分λ1, λ2は，行列Aの固有値と呼ばれる値であ る．もちろんながら，上述の行列A1, A2, A3について，

対角化により得られる行列は，それら自身である．さ らに，対称行列Aに対する対角化は，同じ直交行列P を用いたxからx˜への変数変換

x=

x1

x2

=P x˜1

˜ x2

=Px˜ ⇐⇒ x˜=Px

を通じて，関数f(x)にも適用できる．すなわち，

f(x) =xAx

= ˜xPAPx˜

= [˜x1 x˜2]

λ1 0 0 λ2

x˜1

˜ x2

=λ1˜x²1+λ2x˜²2

= ˜f(˜x) を得る．

図3 二次関数の変数変換

これらを踏まえて，関数f(x) =xAxの凸性を論 じよう．上の変数変換は，直交行列による変換なので 座標軸の回転と反転である．直感的ではあるが，図3 も参考にすれば，f^{が凸であれば，}f˜^{も凸であり，そ} の逆も成り立つことがわかる．したがって，f1, f2, f3

のような関数のみを考えればよいのである．対角成分 以外はすべて0であるような行列からできる関数fの 凸・非凸については，先に述べたとおりであり，それ を対角化を通じて，対称行列全般について換言すれば 次のようになる．

関数f(x) =xAxが凸であるためには，対称行 列Aの固有値がすべて非負であること，すなわ ち，半正定値行列であることが必要十分である．

これは，3変数以上の二次関数でも成り立つことである．

以上が二次関数の凸性に関する分類であるが，より 一般の関数の（局所的な）凸性について，テイラー展 開を通して同様の分類が可能である．再び，2変数関 数f(x)を例に挙げる．適当な仮定の下に，f(x)はx0

の周りで，

f(x)

=f(x0) +

∂f

∂x1(x0) ∂f

∂x2(x0)

(x−x0)

+ 12(x−x0)

⎡

⎣ ^∂

2f

∂x2

1(x0) _∂x^∂2f

1∂x2(x0)

∂2f

∂x1∂x2(x0) ^∂_∂x^2f2 2(x0)

⎤

⎦(x−x0)

+R(x) (17)

と書ける．右辺第3項に現れた行列は，関数fのx0

でのヘッセ行列と呼ばれるもので，Hf(x0)と書く．も

図4 f(x, y) = sin(x²+y²)のグラフ

し，f(x)が式(16)のような二次関数であれば，ヘッ セ行列はx0によらずに，Hf(x0) = 2Aである．さて，

式(17)は，xがx0に十分近くて剰余項R(x)の影響 が無視できるようなら関数fはx0の周りで二次関数 のように振る舞うということを意味している（もちろ ん，R(x)の影響の仕方は関数次第なので注意が必要 である）．ということは，x0の周りで「凸」であるた めには，ヘッセ行列Hf(x0)が半正定値であればよい．

一つ例を見てみよう．読みやすさのために，変数は (x1, x2) = (x, y)とし，2変数関数f(x) =f(x, y) = sin(x²+y²)について調べてみよう．

∂f

∂x= 2xcos(x²+y²),

∂f

∂x= 2ycos(x²+y²),

∂²f

∂x²= 2 cos(x²+y²)−4x²sin(x²+y²),

∂²f

∂y²= 2 cos(x²+y²)−4y²sin(x²+y²),

∂²f

∂x∂y=−4xysin(x²+y²)

なので，x0を原点x0 = 0にとったとき，ヘッセ行 列は，

Hf(0) = ∂2f

∂x2(0) _∂x∂y^∂2f (0)

∂2f

∂x∂y(0) ^∂_∂y^2f2(0)

= 2 0

0 2

となる．すでに対角化されていて，対角成分はいずれ も2と非負なので，このヘッセ行列は半正定値である．

したがって，関数f^{は，原点の近くで，「凸っぽい」は} ずである．図4のグラフでそれを確認してもらいたい．

以上はあくまで，x0の近くでの話であったが，ヘッ セ行列の半正定値性は，下記のように（全域的な）凸 性について言及する際にも使える．

（滑らかな）関数f が凸であるためには，各点 でヘッセ行列が半正定値となることが必要十分で ある．

このようにヘッセ行列は，関数が「凸か非凸か」を 議論する際に，重要な役割を果たすものである．問題 を実際に解く際にも重要で，ヘッセ行列は，非線形計 画問題を解く代表的な方法であるニュートン法などで も利用される．これらの詳細については，専門書[2]な どを参照していただきたい．

6.

おわりに

タイトルに関して，「線形代数でわかるOR」が本来 ながらも，「ORでわかる線形代数」とした．線形代数 学にとって，最適化の理論は発展的内容かもしれない が，背伸びをして少し先の話を学ぶことが，理解を深 めることはよくあることかと思う．本稿では，ORで 使われる線形代数学を紹介することを第一義に，やや 後付けではあるが，第二義的には，それを目指した．そ んなこともあって付けたタイトルである．

おわりになってしまったが，釈迦のみなさまには，（読 むなら）温かく読んでいただきたい．

参考文献

[1] 池辺淑子， 線形計画問題：物資の輸送を例として，

オ ペ レ ー ション ズ・リ サ ー チ：経 営 の 科 学 ，54(12), pp. 717–720, 2009.

[2] 田村明久，村松正和，『最適化法』，共立出版，2002.

[3] 鈴木久敏， 双対問題とは?， オペレーションズ・リサー チ：経営の科学，32(6), pp. 309–315, 1987.