An introduction to constrained non-linear programming

非線形計画問題は，おもに非線形関数で表された目的関数や制約条件を含む連続最適化問題であり，適用範囲が非常に広い一方で，多様な非線形計画問題を効率的に解く汎用的なアルゴリズムを開発することは難しい．今回は，制約つき非線形計画問題の最適性の条件および代表的なアルゴリズムを紹介する．

Transcript

1. 制約つき⾮線形計画問題 ⼤阪⼤学 ⼤学院情報科学研究科 梅⾕ 俊治 2023年7⽉10⽇
2. 等式制約つき最適化問題の最適性条件 • 点 が局所最適解でも とは限らない． • 1本の等式制約を持つ最適化問題では︖ より点 の周りでは制約を と近似できる． • と が平⾏でなければ なので，⽅向 か に進めば⽬的関数を⼩さくできてしまう． 点 が局所最適解ならば と は平⾏，すなわち を満たす が存在する． 2 * と仮定する． は2回連続的微分可能とする． 等式制約つき最適化問題* 局所最適ではない
3. 等式制約つき最適化問題の最適性条件 • 点 が局所最適解でも とは限らない． • 1本の等式制約を持つ最適化問題では︖ より点 の周りでは制約を と近似できる． • と が平⾏でなければ なので，⽅向 か に進めば⽬的関数を⼩さくできてしまう． 点 が局所最適解ならば と は平⾏，すなわち を満たす が存在する． 3 * と仮定する． は2回連続的微分可能とする． 等式制約つき最適化問題* 局所最適
4. 等式制約つき最適化問題の最適性条件 • 最適性の1次の必要条件 点 は局所最適解で は互いに1次独⽴とする*． このとき，以下の条件を満たすベクトル が存在する． • ラグランジュ関数を以下の通り定義すると 最適性の1次の必要条件を満たす と は以下の連⽴⽅程式の解 4 *点 は正則であると呼ぶ．この仮定を1次独⽴制約想定と呼ぶ． ラグランジュの 未定乗数法 局所最適 ではない
5. 等式制約つき最適化問題の最適性条件 • 最適性の1次の必要条件 点 は局所最適解で は互いに1次独⽴とする*． このとき，以下の条件を満たすベクトル が存在する． • ラグランジュ関数を以下の通り定義すると 最適性の1次の必要条件を満たす と は以下の連⽴⽅程式の解 5 *点 は正則であると呼ぶ．この仮定を1次独⽴制約想定と呼ぶ． ラグランジュの 未定乗数法 局所最適
6. 等式制約つき最適化問題の最適性条件 • 最適性の2次の必要条件 点 は局所最適解かつ正則とする．このとき，最適性の1次の必要 条件に加えて以下の条件を満たすベクトル が存在する． ラグランジュ関数のヘッセ⾏列が半正定値であることに対応する． • 最適性の2次の⼗分条件 実⾏可能解 とベクトル が最適性の1次の必要条件に加えて 以下の条件を満たすなら，点 は局所最適解である． 6 制約を違反しない⽅向
7. 不等式制約つき最適化問題の最適性条件 • を満たす制約 の集合 に着⽬する(有効制約)． を満たす⽅向 に進まないと制約を違反する． を満たす⽅向 に進むと⽬的関数値が⼩さくなる． • 最適性の1次の必要条件(KKT条件) 点 は局所最適解かつ正則とする．このとき，以下の条件を満たす ベクトル が存在する． が領域 に 含まれる． 7 不等式制約つき最適化問題 ⽬的関数値を⼩さくする⽅向に進むと 制約条件を違反してしまう 局所最適 ではない
8. 不等式制約つき最適化問題の最適性条件 • を満たす制約 の集合 に着⽬する(有効制約)． を満たす⽅向 に進まないと制約を違反する． を満たす⽅向 に進むと⽬的関数値が⼩さくなる． • 最適性の1次の必要条件(KKT条件) 点 は局所最適解かつ正則とする．このとき，以下の条件を満たす ベクトル が存在する． が領域 に 含まれる． 8 不等式制約つき最適化問題 ⽬的関数値を⼩さくする⽅向に進むと 制約条件を違反してしまう 8 局所最適
9. 不等式制約つき最適化問題の最適性条件 • を満たす制約 の集合 に着⽬する(有効制約)． を満たす⽅向 に進まないと制約を違反する． を満たす⽅向 に進むと⽬的関数値が⼩さくなる． • 最適性の1次の必要条件(KKT条件) 点 は局所最適解かつ正則とする．このとき，以下の条件を満たす ベクトル が存在する． 9 相補性条件 有効でない制約 では 不等式制約つき最適化問題
10. 不等式制約つき最適化問題の最適性条件 • 最適性の2次の必要条件 点 は局所最適解かつ正則とする．このとき，最適性の1次の必要 条件に加えて以下の条件を満たすベクトル が存在する． • 最適性の2次の⼗分条件 実⾏可能解 とベクトル が最適性の1次の必要条件に加えて 以下の条件を満たすなら，点 は局所最適解である． 10 有効制約のみ考慮する
11. 凸計画問題の最適性条件 • 不等式制約つき最適化問題の⽬的関数 および制約関数 は 微分可能な凸関数とする．このとき，実⾏可能解 とベクトル がKKT条件を満たすなら，点 は⼤域最適解である． 点 を任意の実⾏可能解とする．⽬的関数 は凸関数なので KKT条件より 制約関数 は凸関数なので および 点 で ，点 で を満たすので 11 <latexit sha1_base64="cJKU0YeABaEppvLRQLPQqW8NhP8=">AAACzHichVHLShxBFD22SXzFOOpGcNM6GHQz3BETRRAEN1mJr1HBMU13WzMW9ovumkFtZqvgD7hwFcGFSLbJB7gR9y78BHGp4MaFd3oaJBH1FtV16tQ9t071tQJHRorouklr/vDxU0trW3vH584vXZnunuXIr4S2KNi+44erlhkJR3qioKRyxGoQCtO1HLFibc3Uz1eqIoyk7y2pnUCsu2bZkyVpm4opIzNQMeTPuGhGqqaXDTlctNx4u5YyI/qUTkYmSzlKQn8J8inIIo05P3OJIjbgw0YFLgQ8KMYOTEQ81pAHIWBuHTFzISOZnAvU0M7aCmcJzjCZ3eJvmXdrKevxvl4zStQ23+LwDFmpY4iu6JTu6ILO6IYeX60VJzXqXnZ4tRpaERhdB32LD++qXF4VNp9Vb3pWKGEi8SrZe5Aw9VfYDX119/BucXJhKP5Kx3TL/n/RNZ3zC7zqvX0yLxaO3vBjsZfX/1jMXOnZLbcx/3/TXoLl0Vz+e+7b/Fh2eixtaCv6MYhh7to4pvEDcyjwLfv4jT/4q81qSou1WiNVa0o1vfgntL0nO2ilvg==</latexit> u⇤ i gi (x⇤) = 0
12. 双対問題と双対定理 • 不等式制約つき最適化問題のラグランジュ関数 • ラグランジュ乗数 の値を固定した上で， 変数 について を最⼩化するラグランジュ緩和問題を考える． • ラグランジュ緩和問題の最適値を とすると，最⼤ の下界を求めるラグランジュ双対問題が定義できる． • 弱双対定理 不等式制約つき問題の実⾏可能解 と双対問題の実⾏可能解 に 対して が成り⽴つ． 12 原問題の実⾏可能解 に対して
13. 双対問題と双対定理 • 変数 の値を固定した上で，ラグランジュ乗数 について を 最⼤化する問題を考える． • 不等式制約つき最適化問題の最適解 でも成り⽴つので，弱双対定理 と合わせて以下の結果が得られる． 13 * となる制約があると，ラグランジュ乗数 をいくらでも増加できて⾮有界になる． 全ての制約が を満たすとき 最適解 ，最適値 * ओ໰୊ ૒ର໰୊ ऑ૒ରఆཧ 双対ギャップ
14. 双対問題と双対定理 • 鞍点定理 不等式制約つき最適化問題の実⾏可能解 とラグランジュ双対問題 の解 が以下の条件を満たすなら点 と は最適解である． 条件より ⼀⽅で，弱双対定理より よって以下が成り⽴つ． 14 不等号の向きに注意
15. 双対問題と双対定理 • 凸計画問題の強双対定理 不等式制約つき最適化問題の⽬的関数 および制約関数 は 凸関数で， を満たす実⾏可能解 が存在する． このとき，不等式制約つき最適化問題の最適値 と双対問題の 最適値 に対して が成り⽴つ． 15
16. 有効制約法 • 凸2次計画問題は，機械学習や⾦融⼯学など多くの応⽤例を持つだけ ではなく，後述の逐次2次計画法などの部分問題にも現れる． • まずは，等式制約つき凸2次計画問題を考える． • この問題の最適化の(必要⼗分)条件は なので連⽴⼀次⽅程式を解けば最適解が求まる． 16 ラグランジュの未定乗数法 は半正定値
17. 有効制約法 • 現在の解 にて を満たす制約 の集合 のみを考慮した 部分問題を解く⼿続きを繰り返す． • 不等式制約つき凸2次計画問題の最適性の条件 実⾏可能解から開始し，1-3番⽬の条件を満たす点列 を⽣成． 17 凸2次計画問題 は半正定値 部分問題 は現在の解
18. 有効制約法 • 部分問題を解くとその最適解 とラグランジュ乗数 が求まる． • の場合 が元問題の実⾏可能解なら ，そうでなければ線分 上で の最近点を とする． • の場合 なら元問題の最適解． となる制約 が あれば，制約 を取り除いた部分問題を解き直す． 18 元問題の実⾏可能解とは限らない
19. 有効制約法の実⾏例 19
20. ペナルティ関数法 • ⽬的関数とペナルティ関数を⾜し合わせた • を最⼩化する制約なし最適化問題を解いて，ペナルティ重み を • 更新する⼿続きを繰返す． • ペナルティ関数が2次関数だと局所最適解が得られない． • ペナルティ関数が1次関数だと実⾏可能領域の境界で微分可能でない． 20 もしくは 実⾏可能領域 実⾏可能領域
21. バリア関数法 • ⽬的関数とバリア関数を⾜し合わせた • を最⼩化する制約なし⾮線形計画問題を解いて，ペナルティ重み を • 更新する⼿続きを繰返す． • 実⾏可能領域の境界で関数が急峻になり数値的に不安定になる． 21 実⾏可能領域
22. ペナルティ関数法の実⾏例 22
23. 拡張ラグランジュ関数法 • ペナルティ関数法の局所最適解に収束しない，実⾏可能領域の境界 付近で数値的に不安定になる問題を改善する． • ラグランジュ関数 を最⼩化しても， ヘッセ⾏列 は正定値とは限らないため，元問題の局所 最適解は得られない． • ラグランジュ関数に等式制約 に対するペナルティ関数を ⾜し合わせた拡張ラグランジュ関数を最⼩化する． 23 *簡単のためここでは等式制約付き最適化問題を考えることに注意．不等式制約付き最適化問題では， 不等式制約 にスラック変数 を導⼊し，等式制約 に変形する． 等式制約付き最適化問題* 部分問題 ペナルティ重み を⼤きく 取れば は正定値
24. 拡張ラグランジュ関数法 • を元問題の局所最適解*とすると以下が成り⽴つ． さらに，拡張ラグランジュ関数のヘッセ⾏列は より を満たす任意の に対して • ラグランジュ乗数 が に⼗分に近ければ，拡張ラグランジュ関数 を最⼩化することで元問題の局所最適解の良い近似解が得られる． 24 *正確には最適性の2次の⼗分条件を満たす点． は部分問題の局所最適解
25. 拡張ラグランジュ関数法 • ラグランジュ乗数 と固定して，拡張ラグランジュ関数 を について最⼩化する．得られた停留点を とすると ここで，ラグランジュ乗数を と更新すると となり，元問題の最適性の1次の必要条件の⼀部を常に満たす． • ペナルティ重み を増やしつつ， と を交互に更新することで， 最終的に を満たす を求める． 25
26. 拡張ラグランジュ関数法の実⾏例 26
27. 内点法* • 等式制約付き最適化問題の最適性の1次の必要条件に着⽬し， ニュートン法を⽤いて条件を満たす解を求める． • 最適性の1次の必要条件を近似した連⽴1次⽅程式を解いて次の点 を求めた後に，ペナルティ重み を更新する⼿続きを繰り返す． 27 *もとは線形計画問題に対するアルゴリズムとして開発された．これを⾮線形計画問題に拡張することで バリア関数法の問題点を克服するアルゴリズムともなった． 不等式制約付き最適化問題 等式制約付き最適化問題 最適性の1次の必要条件は 連⽴⾮線形⽅程式なので， 近似した連⽴1次⽅程式を解く
28. 内点法 • 等式制約付き最適化問題の局所最適解を とすると以下を満たす*． • 各反復では，ニュートン法を⽤いて現在の点 から最適性の1次 の必要条件を適当な精度で満たす近似解 を求める． • 連⽴1次⽅程式から近似解 を求める⼿続きと，パラメータ を更新する⼿続きを交互に繰り返し，近似的に中⼼パスに沿いつつ 最適性の1次の必要条件を満たす点 に収束させる． 28 * は内点 すなわち を満たす点とする． パラメータ のとき，この条件を 満たす点 が取る軌跡を 中⼼パスと呼ぶ．
29. 内点法 • とすると以下の通り近似できる． • これらを代⼊して を変数とする連⽴1次⽅程式を得る． • 直線探索で ， を満たす適切な ステップ幅 を求める． 29
30. 内点法 • 凸2次計画問題の最適性の1次の必要条件は以下の通り． • を変数とする連⽴1次⽅程式を解く． • 現在の点 が実⾏可能解なら より も実⾏可能となり，上記の連⽴1次⽅程式を解くことで，中⼼パス に⼗分に近い点が求められる*． 30 *内点法は凸2次計画問題に対する多項式時間アルゴリズムであることが知られている． したがって，内点法は線形計画問題に対する多項式時間アルゴリズムでもある． 近似の必要なし 不等式付き
31. 内点法の実⾏例 31
32. 逐次2次計画法 • ニュートン法・準ニュートン法︓⽬的関数 を現在の解 の周り で近似した制約なし凸2次計画問題を部分問題として繰り返し解く． • 逐次2次計画法︓⽬的関数 と制約関数 を解 の周りで近似した凸2次計画問題を部分問題として繰り返し解く． • 不等式制約付き最適化問題の最適性の1次の必要条件は以下の通り． 32 不等式制約付き最適化問題 各反復における部分問題 は正定値
33. 逐次2次計画法 • とすると以下の通り近似できる． • これらを代⼊すると， を変数とする連⽴1次⽅程式が得られる． • これは先の部分問題の最適性の1次の必要条件と⼀致する． 33
34. 逐次2次計画法 • 部分問題の最適解が ならば，現在の解 は元問題のKKT条件を 満たすので終了する． • ならば，メリット関数 に対して直線探索を⾏いステップ幅 を求めて とする． • 逐次2次計画法でも準ニュートン法と同様に，直前の反復の近似⾏列 を更新しセカント条件 を満たす 正定値対称⾏列 を求める． • とおいて準ニュートン法のBFGS公式をそのまま適⽤したい． を満たすとは限らないため の正定値性を保証できない． 34 は適当な パラメータ値
35. 逐次2次計画法 • パウエルの修正BFGS公式 セカント条件を修正した および が成⽴する． 35 は定数
36. 逐次2次計画法の実⾏例 36
37. 参考⽂献 • 茨⽊俊秀，最適化の数学，共⽴出版，2011． • ⽮部博，⼯学基礎 最適化とその応⽤，数理⼯学社，2006． • 福島雅夫，新版 数理計画⼊⾨，朝倉書店，2011． • ⽥村明久，村松正和，最適化法，共⽴出版，2002． • 寒野善博，⼟⾕隆，最適化と変分法，丸善出版，2014． • ⼭下信雄，⾮線形計画法，朝倉書店，2015． • 福島雅夫，⾮線形最適化の基礎，朝倉書店，2001． • ⽥中謙輔，凸解析と最適化理論，牧野書店，1994． • ⾦森敬⽂，鈴⽊⼤慈，⽵内⼀郎，佐藤⼀誠，機械学習のための連続 最適化，講談社，2016． 37
38. 参考⽂献 • D.G.Luenberger, Y.Ye, Linear and Nonlinear Programming (4th ed), Springer, 2016. • S.Boyd, L.Vandenberghe, Convex Optimization, Cambridge University Press, 2004. • J. Nocedal, S.J.Wright, Numerical Optimization (2nd ed), Springer, 2006. • D.P.Bertsekas, Nonlinear Programming (3rd ed), Athena Scientific, 2016. • M.S.Bazaraa, H.D.Sherali, C.M.Shetty, Nonlinear Programming: Theory and Algorithms (3rd ed), John Wiley & Sons, Ltd., 2006. 38