👓

ラグランジュの未定乗数法とはなんぞや

2023/06/08に公開

数理最適化

最適化

tech

自動運転とかで軌跡描く時に出てくる最適化の基礎なので備忘録的にまとめる。

Lagrange Multiplier(未定乗数法)とは？

wiki曰く、コスト関数 $f(x,y)$ を最大化、または最小化させるような $x$ と $y$ を、拘束条件 $g(x,y)=0$ の下で求めるのがゴール。
拘束条件がない場合は $x$ と $y$ それぞれで $f(x,y)$ を偏微分すると極値が求められる。
条件ありの場合はラグランジュ乗数と呼ばれる $λ$ を導入して式を合体。 $x$ 、 $y$ 、 $λ$ の三つで偏微分することで条件内の極値が出せるらしい。証明は難しいので割愛。

例題その1

以下記事の例題が分かりやすかった:
https://manabitimes.jp/math/879

$x^{2} + y^{2} = 1のもとでf(x,y) = 2x + 3yの最大値を求めよ。$

単位円内の $x$ , $y$ で探す。記事の通り値が得られるか実感を得るためにプロットしてみた。

$x$ と $y$ を単位円上で動かすと宙に浮く楕円のようにコスト関数の値(plotのz)が動く。

自動運転とかで使われる例

今はOSQPの方が流行りだがADMMベースのplanningも2022年のpaperなどではある。
OSQPとかADMMとはなんぞやはまたの機会に。
https://arxiv.org/pdf/2011.00462.pdf

参考

先人の記事:

Lagrange Multiplier(未定乗数法)とは？

例題その1

自動運転とかで使われる例

参考

Discussion