最適制御理論の動向 (1 )坂本実

な道具となるものがある.この資源管理分野への応用を

1.はじめに中心とする，最適制御理論の応用例の解説が，この連載

最適化のための数学的理論，方法は，古典的変分法，
数理計画法，最適制御理論に大別される.これらは，それぞれ独自の発展の歴史をもっている.最近これらの理の 3 つめの主題である.

なお，最近，生物学での最適制御理論の応用を扱った，
興味ある書物 [6 ]が出版された.

論を特にその必要条件について，統一的立場から論ずる，急速に発展しつつあるこの分野全般についての解説を

いわゆる「極値問題の理論」として統合されようとして行なうことは，もちろん不可能なことである.この連載いる.

は比較的紹介の少ない，

この方向の発展のきっかけになったのは，ヅボビツキー (Dubovitskii ，A. Ya)

ソビエトのとミリュチン(Milyutin , A. A) の研究[ 1]であって，多くの研究者がそれを発展させ，応用してきた.特に，ボルチャン
スキー (Boltyanskii ，化して，

V. G) は，これを厳密化，簡潔I テント法 J (ロシア語.

Memog WaMpOB) とソビエトでの研究が紹介されることが特徴といえば，いえないこともないものとなるであろう.記述は，

高等の数学的知識を前提とぜずに，「本質的なことがらを，できるだけ平易に j 書くように努める.

2. 極値問題の理論一一必要条件の一般的理論への道

名づけ，種々の問題に適用している[ 2].

この連載の最初の主題は，この統一的理論を，特に最適制御理論に重心をおいた解説で、ある.

オベレーションズ・リサーチの問題は，すべて広い意

味での，最適化の問題である.最適化の問題は，いうま

現実の問題を解決するために最適性の必要条件を基礎でもなく .OR 以外の，諸科学，技術のあらゆる分野でとする方法を用いるときには，種々の難点が生じること生じる問題である.数学は，がある.十分条件は，必要条件ほどには一般的なものがで，新しく提起された最適化の問題を解決してきた.し開発されてはいないが，最適制御理論では，広い範囲のかし，強力にしかも系統的に研究されるようになったの問題に適用できる方法が，クロトフ (Krotov ，グルマン (Gurman ，B. F) とV.1) によって提案されている [3].

その歴史のあらゆる段階

は，比較的新しいことである.そのような研究が行なわれるようになったのは，経済，経営，

OR.

自動制御な

この方法の解説と応用とがこの連載の 2 つめの主題であどの分野からの要求が高まったことと，電子計算機の出る.

現によって，問題の数値的最終結果を得る強力な手段が最適制御理論，特に，ポントリャーギンの最大値原理

得られたことによるためだといえよう.

が，オペレーションズ・リ+ーチで，そのままの形で用最適化の問題を数学を用いて解決するためには，まずいられることは，工学，経済学に比較して，少ないようで

最初に，それが生じた分野ごとの言葉で記述された問題

ある.ところカ" tことえ li ， コーリン・クラーク (Colin ，を数学の言葉で表現しなければならない.次に，その問

W , Clark) の，漁業資源の有効利用の問題を扱った書

題の解が満たすべき定量的な関係式(最適性の必要条件，

物 [4 ].その書評 [5 ]にみられるように，

OR 研究者

十分条件)を明らかにしなければならない.つづいてなが進出すべき分野のうちに，最適制御理論の方法が有効

すべきことは，解を具体的に求め，作り出すことである.

さかもと

要条件を作り出すことは，とりわけ重要な仕事である.

理論上は，解の存在，一意性も問題とされるが，解の必みのる専修大学

1982 年 1 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(
3
5
)3
5

これについては，広い範囲の問題に適用できる，できる

(
p
r
i
n
c
i
p
l
eofoptimality)に基礎をおく，広い応用範だけ完全な条件を探す方向での多くの研究がなされてき

囲をもっ方法を提案した.この方法は，理論，応用の両た.

面にわたって大きな貢献をなした.

さて，数学的に定式化された最適化の各々の問題を極最適制御の問題の研究での決定的な一歩は，ポントリ

値の問題 (problem of extremals) とよび，それらにャーギン (Pontryagin ， L. S) の最大値原理 (maximum

関する統一的立場から研究する理論を極値問題の理論

principle) の形での極値の必要条件の定式化であった(theory of extremal problems) とよぶことにしよう.

([9J , [10J). この理論を中心として，最適制御理論

極値問題の理論のうちに含めることができるであろう，
古典的変分法 (Calculusof variation) ，等式条件の(theory of optimal control) が形成されることにな
る.ボノレチャンスキー (Bo !t yanskii ，

V. G) がはじめてもとでの関数の最小値(最大値)を求めるラグランジュ

行なったこの最大値原理の証明(1 956 )は，それまでのも(Lagrange , J. 1736-1813)のとは異質で、，まったく新しい方法が用いられた.

の問題では，オイラーの(Euler , L. 1707-1783) 方程式，ラグランジュの乗数法(multiplier rule of Lagrange)とし、った，

最適性の当然のこととして，多くの研究者が，この最大値原理
を，古典的変分法，数理計画法の考えと方法によって証明することが試みた.このことが成功することは，美的必要条件が古くから得られていた.
1939 年のカント価値だけでなく，実用的価値のあることである.つまり，L.V) による，後に，線形計画

最適制御理論の問題に，数理計画法に関して開発された

法 (linear programming) とよばれるようになる問題の多くの計算方法が適用できるようになり，その理論が多研究にしてしまった.これは，ダンチッヒ (Dantig ， G)

くの実際的問題に応用できるようになるわけである.

極値問題の理論の新しい発展段階は，
ロピッチ (Kantrovich ，を中心とする多くの研究者によって完成され，広〈実際

最適制御理論を必要条件の一般理論に組みこむこと上の問題に応用されていることはよく知られたことであに，はじめて成功したのは，すてすこのベたミリュチンとる.極値の必要条件に関する理論，極値問題の理論の第ヅボピツキーであった.彼らは，それまでに知られてい2 段階は，不等式制約条件のもとで，凸関数である目的

た極値の問題での必要条件を特殊ケースとして導き出す

関数を最小化する凸計画法 (convex programming) でことのできる，一般的スキームを作り出すことによっあった.この理論において中心的役割を課したのはキュて，最適化理論の失われていた統一性を回復したのであ1951) でる.彼らの仕事の大きな価値は，このように，すでに研ある.これは，解を具体的に求めるための多くのアルゴ

究されている問題はもちろん，新しく生じるであろう広リズムのよりどころとされた.その考えは，凸でない有い範囲の問題での極値の必要条件を導くための方式を洗限次元の極値の問題にも拡張され，非線形計画法 (non­

練された形に定式化できたことにある.

ーンタッカーの理論 (Kuhn-Tucker

theory ,linear programming) ，数理計画法( mathematical

ボノレチャンスキーは，前述のとおり，この方法を整理，

programming) とよばれる分科が形成されることにな

発展させ，離散最適制御問題，

る.

適用した.ソビエトにおけるこれらの研究とも関連ある

線形，非線形計画法における必要条件を導き出す際のミニ・マックス問題等に類似の方向の研究は，アメリカのノイスタット(Neus­

原理的な考えは「与えられた点、から進むとき，許容領域

tadt , L.W) によってもなされた[ 7](抽象理論である.

を出ずに，目的関数の値が大きくなる方向があるなら歴史的解説も付けられているにば，その点は最小点、ではなし、」とのべることができる.

立に進められたと思われる，凸解析による極値問題の研ズーテンディク (Zautendijk ，

究にロッカ・フエラーによるものがある [8J( これは凸G) によって，その著書(
fMethods of Feasible DirectionsJ , 1960) にまとめられたこの原理は，微分可能な制約条件をもっ有限次元空間での広い範囲の問題に対して，極値の必要条件を定

さらに，これらとは独解析に関する最もすぐれた書物の I つとされている).

3. 極値の問題ーその形式と基本的なクラス
極値問題の理論が対象にするのは，厳密に定式化され式化するために用いられた.
このような有限次元の極値問題の理論，すなわち，数理計画法の理論が発展しているのと時を同じくして，もた「極値の問題 j であることをのベた.ところで，幾何学的図形に関する問題から，ロケットの制御にいたる，

う 1 つのクラスの極値の問題，最適制御の問題 (optimal

さまざまの具体的内容をもっ問題の，共通的な形式はど

control problems) が研究されていた. 1950年代の初め

んなものであろうか?

に，ベルマン (Bellman ，R) は，動的計画法 (dynamic

programming) とよぶ，いわゆる「最適性の原理 j

3
6 (36)

どの極値の問題も，組<f(x) , X, C>
で与えられる.ここに ， f(x) は集合 X の要素に実数値© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

問題 1-3
目的関数(非線形計画法)(ー∞，+∞を含めた)を対応させる写像(関数，汎関数)
であって，目的関数 (objective function)とよばれるものである .X は許容クラス (admissible cI ass) とよば

制約条件

れ，これを定めることによって考察の対象となる空間，

fO(x) →最小X=Rn/i(x)=O， i=l ， … ， p，
gJ(x) 孟 O， j=l ， … ， q:関数の方式などを指定する .C は許容集合( admissible
古典的変分法の問題のクラス;古典的等周問題など，

set) あるいは制約条件 (constraints) あるいは，単に制

幾何学的内容の問題の解決からはじまり，光学，力学に約などとよばれる ， X の部分集合である.

X=C である問題は，制約条件のつかない問題である.

おけるいろいろな変分原理を発見し，自然、科学の言葉と制約条件は，①方程式，②不等式，③集合・要素関係式もなった古典的変分法の問題をいう.ここでは ，のどれか，またそれらのいくつかを具体的に与えること

連続微分可能な，によって定められる.ここで，③は，ある集合を与えて，次元ベクトル関数の族であって ，その要素である z だけを対象とすることを意味する.な

X の距離が，

X は，

実数区間九三 t~三九上で定義された nx=x(t) , y=y(t)E

max I
x
(
t
)‑y(t)1, max Ix(t)1+maxto 孟 S 孟 tl

to~玉 t 亘 t1y(t
)1 等で定義されている.目的関数はto 亘 t 亘 t1

X 上で定義お，①，②，③の形は，内容を変えることなく，互いに1

いれかえることができる.こうして，極値の問題は「条された汎関数(無限に多くの独立変数の関数とも考えら

件 xEG のもとで ， X で定義された関数 f の，れる)である.制約条件は，微分関係式 ，最小値(下限); (または，上限，最大値)を求めよ jと記述される.目的関数の最大化の問題は，

M(x , x(t) ,土 (t) ) 壬 0 ，境界条件 N(x (to)) ， x( ん))孟 0 等で与えられ目的関数

る.例をあげよう，目的関数は，汎関数の記号に改める.

の符号を逆にすることによって，最小化の問題に直すこ

問題 2-1 (古典変分法の最単純問題)とができるので，最小化の問題として記述したが，目的関数 J(x( ・ ))=j:;fo(t， z(札制 t) )dt→最

これからもそのようにする.

この問題の解とは何かを定義しよう .
Xo のある近傍があって，Xo ε X t;こ対し，

f(x) ミ f(xo)J が成立するとき，引をこの問題の局所最適解 (local optimal solution) という.上の不等式で，
Z キ Xo である z に対し ， f(x)>f(x o ) であるとき，近傍
U に Xo 以外の局所最適解はないので ， Xo を狭義の局所
最適解 (strictlocal optimal solution) をいう.また，「すべての zιC に対して .f(x) ミ f(xo)J であるとき，
Xo を大域最適解 (global optimal solution) という.

極値問題の 3 要素が具体化した問題の，その発生，数学的特徴を考慮した，基本的クラスへの分類を行ない，各クラスでの，代表的な問題の例をあげておこう(必ずしも完全な記述ではない).

これは有限個の変数の関数(なめらかな，すなわち，連続微分可能な)を目的関数とするものである.
より具体的な例には次のものがある.
問題 1-1

目的関数

(フェルマ

f" (x) →最小

X=R1: 実数
制約条件なし (C=R1) :問題 1-2
目的関数(ラグランジュ)

制約条件

可能実数値関数}
制約条件叫ん )=xo ， 叫ん )=x 1
ベクトノレ関数 X(t)=(X1(t) ， … ， xη (t) ) の場合は，この問題を「古典変分法のベクトル最単純問題」という.以下の問題の表示では，微分関係式，境界条件は省略して，目的関数だけを書く.
問題 2-2 (ラグランジュ)J(x( ・ ))=j;fO(tpZJ)dt→最小:問題 2-3 (マイヤー; mayer)
J(x( ・)) =/O(x (t o) , x(t J )) →最小:

olza)
問題 2-4 (ボルヅァ; B

数理計画法の(なめらかな)問題のクラス: 2. でのベ

たように，

X ={xlx=x(t) , to 手 t 豆 t 1 ; 連続微分

Iすべての xECnU に対し，

J(x( ・ ))=j:;fO( 仏土)み +g(x( ん)，叫ん))→最小問題 2-5 (等周問題)

目的関数 J(x( ・ ))=[;f0MM→最小

制約条件

j
:
;
g
z
M

最適制御の問題のクラス，動的システムの制御に関係

fO(x) →最小した問題で、あって，システムの入力 U=(U J. ..', U r ) ,X={xlx=(xJ....， Xη) }力(状態 )x=(x J.'..， xη) ，過程 (process) とよぶ対 (u(t) ，出=Rnx(t)) , to 壬 t~五九，

f j (x)=O ， j=l ， 一 ， m:

る. ;C の，制御作用 u(t) を受けておこる，とその評価 J(u( ・ )， x( ・))とに関係す
時間にともなう変化規則は，常微分方程式，差分方程式，偏微分方1982 年 1 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(
3
7
)3
7

程式などの各種の関数方程式の解として与えられる.こA (0 , 0)x

れが，極値の問題としての 1 つの制約条件となる.他の制約条件には ，

x+dx

x

ァ一一一一一一寸

x(t) の大きさの制約，境界条件があるが，本質的なのは制御 u(t) のクラス，

そのとりうる値に関する制約である.ここでは，常微分方程式で記述される対象に限定する.
問題 3-1
目的関数

U

ds、\、

+g(to, x(to) , t
t1
))
dt
1
0X(
制約条件

~i

J(u( ・ )， x( ・))=仁 1 fO (t， X(い μ ))dt
g 十 dx/---→一l

一一ー一ーで..，.

土 =f(t ， x ， u) ， ヂ(to， x (t o) , t
t1
)
)=0
1
0x(

B(
x
" y ,)U 壬 U;u(t) ， [t川11 上の区分的に連続な関数:

微分方程式条件は ， x(t) は[to ， t 1 J で ， u(t) は不連続U

最速降下曲線の問題

図 1

点を除いて，微分可能であって，微分可能なすべての点で，土 (t) =f(t , x(t) , u(t)) が成立することを意味する.

(なお ， u(t) ，[to ， t 1 J は，この区間で高い有限個の，第 l曲線 y=y(x) の，点 (x ， y(x)) から，点 (x+dx ， y(x)+種の不連続点をもっとき，区分的に連続であるという).

dy) までの長さ ds= 、/了五戸平夜耐の闘を通過する時

この問題で，関数 f" 三 1 ， g 三 0 とし，制約条件は同じとして聞は dsj ゾ語函玉J であることを考慮して，得る.

問題 3-2 (最短時間問題)

目的関数 J(u( ・ )， x( ・ ))=j:; 必至 t 1 -t O→最小を，また ，

fO 三 O とし ，

目的関数

J( 計 ))=~:1 Jt+(
y
'
)
2
jJ函
dx→最小

制約条件

y(O)=0, y(x ,) = 仇:この問題は，前述の問題 2-1 に属することは容易にわかる.ここで，次の問題を得る.

曲線のパラメータ表示 x=x(t) ， y=

百 (t) を用いると，パラメータ形式の変分問題が得られる.

問題 3-3 (終端制御問題)
目的関数

問題 A

g を fO に書き改めて(マイヤーらの問題での汎関数の特別なケース)

次の問題を(百 '=dyjdx)

J(u( ・ )， x( ・ )=fO(x( ん))→最小

ところで，具体的内容か同じ問題でも，異なる極値の

もう l つの定式化では，フェルマ (Fermat ， Pierrede ,160 ト 1665) の変分原理「光は時聞が最小になる路を通問題として定式化できるものが多数ある.定式化の例をる」と，光の伝播速度がが =2gy である非同質な媒体に見ることも目的に，そのような例をとりあげよう.

適用して，次を得る.

ガリレオ・ガリレイ

は，著書「対話 j ，(Galileo

Galilei , 1
5
6
4
‑
1
6
4
2
)

1636 年(岩波文庫，

巻，命題 36 ，定理22) で，

r新科学対話 j ，下ことが証明されている.ヨハン・ベルヌウイ(Johan

Bernouilli ,1667-1748) は，

目的関数

t 1 →最小制約条件

土 2+ 金2 三 2gyx(O)=y(O)=0, x( ん )=x"r 円の弦に沿う運動は，その弦を張る弧に沿う運動よりも長時簡を要する jを提起した.

問題 B

1696 年，上の一般化ともいえる次の問題

r 垂直平面の与えられた点 A から点 B まで，y(t 1 )= 仇

光学一力学アナロジーに得られたこの問題は ，f O=I ,

to=O である問題 2-2 である.
さら tこ，ニュートン (Sir I
saac Newton ,

1
6
4
2
‑
1
7
27
)

頂点 u が重力加速度の作用を受けて動くとき，点 B に最の法則「曲線引 x) に沿って運動する質点、には，速度にrachistoｭ
短時間で達するような径路ー最速降下線( B

垂直な力が作用する J にしたがい，質店、の加速度 1 1-，作

chrone) を決定せよ j.

用する力の総和に比例することを考えて，次の，やはりこの問題は，古典変分法の発展の糸口となった問題である.この問題の定式化を行なおう.図 1 のように，座標軸，点、の座標を定め，曲線の方

程式を y=y(x) で表わすことにする.

ガリレオの法則「質点 M の点、 (x ， y(x)) における速度は ，問題 2-2 に属する別の問題が得られる.
問題 C

目的関数

t 1 →最小制約条件

x=u ， 封 =g+v， 土u+ 会v=O

(O ， x) 聞のx(O)= 百 (0)=0 ， x( ム )=x"

曲線引 x) の形には無関係にたて座標 y(x) だけに依存して，、/語玩x) である (g は重力加速度 )j にしたがう.

3
8
)
3
8(

y (t1)= 仇:微分関係式は，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

土= Jyu , 会=イ子V ， u 2 十 v 2 =2g とオベレーションズ・リサーチ

も書ける.こうして，問題 3-2 型の，制御 u. りをも

if
O
(
x
o
)
/
ix

P

っ最適制御問題のクラスの最短時間問題を得る.
最大値原理が最初に証明されたのもやはり「最短時間問題 J であった.(1最適化は，まず時間最適からノ J? ).
ここで，比較のためにも，その自然な形の問題を定式化しておこう.

r 水平なレーノレ上を，摩擦なしに，運動する

トロッコがある.その運動は，ある範囲内で変化させることができる力の作用で制御される.このトロッコを，定められた位置に最短時間で停車させたい.どのように制御すればよいか? J.

f
O=const

トロッコの質量を m. その初期 (t=O) 位置を xo. 初

速度を v o ， 制御の力(けん引力)を u で，

図 2集合{，}o とそのテント K。

トロッコの時刻U t の座標を x(t) で表わそう.ユュ一トンの法則を考

(
x
l
f
O
(
x
)<fO(xo)} とを分離するなめらかな超曲面であ慮して，次を得る.

る(図 2 ).

問題 D

目的関数九→最小
制約条件

小さい値の領域に点 Xo を付加して得られる集合を Q。

mx=u， Ul~五 u;語的としよう.つまり， ρ。 = {
x
o
}n{
x
l
f
O
(
x
)<fO(xo)} とす

x
(
O
)=
x
o
..
i
:(0)=
v
O
.X(t ,) =る.このとき，次の定理が得られる.

土 (t， )=O:

なおこの問題は，たとえば，

rxo が問題 1 ー 2 の最適解であるための，すなわち，[9J.[10J で解かれている.

値をとったのも，必要十分条件は.共通集合{,} On {,}, n …n {,} m関数のクラス一一般形式での X が明確にされていないので，不完全である.ところが，解の存在は，この許容クラスが何であるかに直接的に関係する.また，当初考え)
1(

これらのいずれの定式化は，汎関数が定義されている

関数 fO(x) が C= 仏 n … n {，}m で，点 Xo において最小が，ただ 1 点 Xo だけからなることである j

まず，必要性を証明しよう

Xo が最適解であるとすていたクラスには解が存在しないので，別のクラスに解る.点 x' ε {，}OnC. x' キ Xo が求まるとすれば .fo(x')<

を探すこともある.このことに関しては，後に再び検討

f
O
(
x
o
)
(
x
'E {，}o だから)となり，を行なう.

n {，}m) となり ， Xo が最適解であることに反する.次に，しかもど ε C(= {，}l …

十分性を証明する.共通集合(1)はただ 1 点であるとす

4. 極値問題におけるテント法
一基本定理と適用例
3. でのベたすべての問題を含む広い範囲の問題における最適解の必要条件を導き出す 1 つの理論，方法である

る.このとき ， Xo が最適解でないとすれば，前提に反して，

X'EC 1 で ， fO( ど )<jO (XO).x' キ Xo である点どが存在することになる.
ここで，集合{，}O は点 Xo の近くでは，

内積 ðjO (xo)/テント法の考えを最適制御理論への適用に先だって，結ðx.(x-xo) が，正でないようなすべての点 z からなる果が古くから知られている問題 l ー 2 (3. 参照)を例とし

半空間 (halfspace) Ko と“わずかしか違わなし、"ことてのべよう([ 2J).

に注意しよう(図 2 ).この半空間 Ko は頂点 Xo をもっ

今後は，一般形式 <f(x).X.C> における， C を決定する，個々の方程式，不等式のそれぞれに対応させて，凸錐である.集合 S は，その任意 2 点、 x. y を端点とする線分 aX+(I-a)y.O;玉 a;王 1 を完全に含むとき凸集合
x.yEK ならば .x+y EK

それらを満足する z を集合の形に個々に記述することに(convex set) であるといい ，する.こうして，この問題では，次の集合を導入して，であり ，

C をそれらの共通集合として表現する.

錐 (convex cone) という.これを復習しておこう.

。J= (
x
l
f
J
(
x
)=O}.j=1.

….m.; C= {,}, n …n {,} m.

a ミ O. XES ならば集合仏 (i=l.

aXEK であるものを凸...• m) についてもまったく同様に，点、

Xo がこの問題の最適解であるとして，それが満たすべき

Xo では，凸錐 K t = {
x
lf
i
(
x
o
)
/t
.(
x
‑
x
o
)=O} と“わ条件(必要条件)を導き出すことにする.この点での，勾ずかしか違わな L 、こうして，各 i=O.I. … .m に対し配ベクトル (gradient

v
e
c
t
o
r
)
. ðf/ðx=(ðf/ðx 1•

ðf/ðx n ) はゼロでないとする.

このとき，

点 Xo を通るて，集合仏な点 Xo での，さらに一般化されて「テント Jとよばれる，接錐 (tangent cone) をもっ.テント

関数 jO (x) の等高曲面 ρ =(xlfO(x) =fO(xo)} は，大Kü i ==l ，'.'， m ， は Z の次元 n ~;こ対し ，

きな値の領域 (xlfO(x) >jO (xo)}ことに注意しておこう.これまでのことは，どの極値の1982 年 1 月号と小さな値の領域© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

n-1 次元である

(
3
9
)3
9

問題においても事情は同じであって，問題ごとに，集合ある •仏がちがっており，テント Ki との関係が複雑になるこ

ao+at=O だから，一方のベクトルもゼロでない).つまaO ， Ql のうち少なくとも 1 備はゼロでない(実は，とがあるほが ， K に完全には含まれない場合もある).

り，錐 Ko ， Kt が分離するためには ， ao+at=O であっ次に行なうことは，先の定理を基にして，最適解の必て，不等式 (2) を成立させる，少なくとも 1 個はゼロで要条件を， Ki ， i=O ， 1 ，… ， m を用いて表わすことである.

ないベクトル ，

この考えは，従来の線形化の考えと同じ考えである.そる.

の条件をどのように求めるかを

3 次元の場合について予視してみることにしよう.いま ， Kt と K 2 とが分離

a o, a 1 が存在することが必要(十分)であ錐の個数が 2 個以上の場合にも同様の，次の定理が厳密に証明される.

されておらずに，点、引を通るある半直線 1 で交わって定理 2. R憾の頂点 X o をもっ凸錐 Ko ， Kt … K隅の組いるとする.このときには ， Q。と仏とも交わっていて，が分離されるための必要・十分条件は ， i=O ， … ， m とす

その交わりは，点 Xo における接線が I であるような曲

る (2) を満足し，関係式

線 L であると予想される.そうなると ， X o キ x' ELc ρonQt が求まることになる.つまり，r共通集合(1)が，点 Xo だけからなるためには， Kt と K 2 は分離されていなければならない j と予想される.

(
3)

ao+at+...+a刑 =0を満足する，少なくとも 1 個はゼロでないベクトル ao ，… ， a m が存在することである.
これの定理 1 ，定理がミリュチンとヅボピツキーの結2 個以上の凸錐の分離性について研究

果をボルチャンスキーが発展させたテント法とよばれる

し，テントの概念を厳密化して，次の定理が厳密に証明方法の基本となる定理である.当然，この方法を具体的されている.

な問題での必要条件を導くために用いるには，それに応この方向で定理1. Qo ， Qt'"ρ叫を n 次元ユーグリッド空間 Rη

の，共通点 X o をもっ集合とし

Ko， K1o … ， K隅をそれじた種々の計算的操作を必要とするわけである.

問題 1-2 (ラグランジュ)の問題に戻ろう.この問題

らの集合の点 X o における，少なくとも 1 つは n-1 次元

では ，でない，テントとする.幾式 Qo n
Qt'
" nQ明 ={X o } が成(xo)/òx ・ (x-xo)=O} だから

立するためには，錐 Ko ， K
1
0

Km が分離されていな

Ko={xjòfO(xo)/òx ・ (x-xol 豆 O} ，

Ki={xj fiao=).oòfO(xo)/òx , ).。豆 0; ai= ん Òfi(xol/òx ， i=l ,-, mければならない.
この定理は，幾何学的表現の必要条件を与えているが，実用上は，解析的表現の条件が望まれる.
ようにして得られるであろうかを予想しよう.

これはどの
2 つの錐

とできる.条件 (3) から).ofO(xol/x+).t f1(xol/òx+ ・・ '+).mòfm(x o )

(
4
)

/ x=O

Ko ， Kt があって，これを分離する超平面 F が求まったを得る.このようにして，次のよく知られた次の定理，とする(図 3 ).この超平面に垂直で，逆向きのベクトル

ラグランジュの定数法が得られる.

で，次の条件を満足する 2 つのベクトル ao と向とを選定理 .

Xo が，問題 1-2 (ラグランジュの問題)の最適解であるためには，等式 (4) を満足する少なくとも 1 個

ぶ.

(
2
)

はゼロでない数九…， ).怖が存在しなければならない

i={O , I}. a。と的とは逆向きであるから ， a o + 内 =0 では。豆 O は， (4) が同次方程式であるから本質的ではない).

ai"(X-XO) 孟 0 ， X ε Ki

また ， Òfi(xo)òx ， … ， òfO(xo)/òx が独立であれば，んキ O
であり，ん =1 とできる.
次に，最も単純な，制約条件のない問題 1-1 に，このテント法の考えを適用してみよう.目的関数 fO(x) に対して y=fO(x) としては ， y) 一平面で考える.ぬが最適解であるとする .

Qo={(x ， 百 )jy< 官。 }u (xo , yo) , Qt={(x ， y)jy=f(x)} とおけば ， Xo が最適解であるための必要十分条件は filo nQ ，がただ 1 点 (xo ， Yo) からなる Jであることが前と同様に容易に証明される .

Xo が微分可能であるとする .

f(x) は点

Qo , Ql に対する ， Ko , K1

は ， Ko={(x ， y)l-a o ・ (x-xo ， y‑Yo)>O }，ただし α。=(0 , 1); K 1 ={( 九百) j a l ・ (x-Xo ， 百 -Yo)=O} ，
図 3

40 (40)

錐 Ko ， Kt の分離

ただし，

a1=(-f' (xo) , 1) で与えられることは容易にわかる(図© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

x2

y

C

ーーーーー一一ーー f' (0)

λ， e ，

一。

寸lk

争

似m一一

o=
it--

。

ニx

ニ"0

Z

λ， e ，

図 4

1

Y=f(x) の最小化

f(x) ， x. ミ 0， x 2 ミ O の最小化

図 54).等式 (4) は ， ao+ 引 =(0 ，ー 1) +(-f'(xo) ，1) =O と適用例の概略をのべた.次回は，これを準備として，最なり ，適制御理論の問題への適用例をのべることから始める.

f' (xo)=O を得る.こうして，テント法の考えによって，微積分で良く知られている結果(フェルマーの文献(ロシア語原書には本をつける)

定理 H ぬが ， f(x) の最小値を与える点であるためには，

f(x) が点 Xo で微分可能であるとき ， f'(xo)=0' でなけ

題.

ればならなし、」を得た.

もう 1 つ，問題 1-3 の，特殊ケースである問題
問題 1_3'

目的関数

f(x. ， x 2 ) →最小

x. ミ 0 ， x 2 ;:;:;0

この点で成立すべき関係(必要条件)を導く.この問題では，次を得る(図 5 ).
。o={xo} n{xlf(x)<f(xo) }， Q.={xlx. 註 O }，点 Xo で，ベクトノレ f'(x)=(ðf(x)/ðx t,

法，数理科学の進歩，

30, No. 3(183)(1975) , 3
‑
5
5

1
9
7
3

[4J ColinW.Clark:Mathematical Bioeconoｭ
mics‑Theoptimalmanagemento
frenewable
resources一，羽Tiley-Interscience[5] 竹内啓: [4J の書評，リサーチ J ，

f(x)/ x2)

1979年 6 月号，

1
9
7
6
.3
5
2P

I オベレーションズ・

3
8
1[6]巌佐庸:生物の適応戦略.サイエンス社，
1981がゼロでないとして

Ko={xlao(x‑xo)>O}, K;={xla;(x-xo) ミ O }， i=
1 ， 2 として ，I 計算数学と物理数学 J 5, No.3(
1965) , 395‑453*[2J ボルチャンスキー:極値問題におけるテント

ナウカ，

へのテント法の適用を行なおう ， xo=(XO.， X02) が，このQ2={xlx 2 孟 O}

ミリュチン:制約条件付極値間*[31: クロトフ，グルマン. .最適制御の方法と問題.

f: 凹関数
制約条件

問題の最適解であるとして，*[1J ヅボピツキー，ao=-).of'(xo) , a.= ん el ， a2= ん e2 ， e.=(I ，0) ， e2=(0 ， 1) ， んミ 0 ， i=0 ， 1 ， 2 を得る( (3) 参照).等式 (4)ao+a. 十 a 2 =0 から ， ðf(xo)/ðx.=)..( ミ 0) ， ðf(x o )/ðx 2 =[7] Lucien W. Neustadt

Optimization‑Atheory of Necessary Conditions , Princeton
UniversityPress , 1
97
6[8J R.TyrrellRockafellar;ConvexAnalysis ,PrincetonUniversityPress , 1
970，( 2(;:;:;0) となる.結局，IX O が問題 1- 3'の最適解であるための必要条件は，

f(xo)/ðx. , f(xo)/ðx 2 のいずれも非負で，どちらか 1[9J ポントリャーギン他，関根訳:最適過程の数学
的理論，総合図書，

1
9
6
7[IOJ ボノレチャンスキー，坂本訳. .最適制御の数学的つはゼロではない J

方法(新版)，総合図書，

を得る.

1
9
7
4

最適昔話j御の問題でなく，数理計画の問題へのテント法
1982 年 1 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(
41)41