Lagrange Multiplier

by allenlu2007

Lagrange Multiplier 是在學微分求最大值或最小值之後的另一個 topic.

這是另一個 Lagrange 的貢獻。主要是用來處理 optimization problem 中的 constraint 問題。

以 2-D 為例: consider the optimization problem

maximize

f (x, y)

subject to

g (x, y) = c

標準解法是定義 Lagrange function (or Lagrangian)

\Lambda(x,y,\lambda) = f(x,y) + \lambda \cdot \Big(g(x,y)-c\Big),

然後解以下聯立方程式: 三個 equations, 三個未知數 (第三個 equation 就是 constraint)

$\nabla_{x,y,\lambda} \Lambda(x , y, \lambda)=0.$

到底 Lagrange 如何”神來一筆” 引入 lambda 和 Lagrange function 之前對我來說是謎。

幾何解釋

其實如何求解的關鍵在於下圖 (Figure 2): 在最大值時 f(x, y) 和 g(x,y)-c 在 Figure 1 (3D) and Figure 2 (2D contour plot) 是相切。同時兩者的 normal direction (gradient direction) 是 parallel!

$\nabla_{x,y} f = - \lambda \nabla_{x,y} g$ , Lambda 基本上只是 scaling constant.

NewImage

Figure 1: Find $x$ and $y$ to maximize $f (x, y)$ subject to a constraint (shown in red) $g (x, y) = c$ .

NewImage

Figure 2: Contour map of Figure 1. The red line shows the constraint $g (x, y) = c$ . The blue lines are contours of $f (x, y)$ . The point where the red line tangentially touches a blue contour is our solution. Since $d 1 > d 2$ , the solution is a maximization of $f (x, y)$ .

把以上 equations (包含二個 equations and 三個變數) 再加上 constraint;

同時濃縮在一個方程式就得到

$\nabla_{x,y,\lambda} \Lambda(x , y, \lambda)=0.$

這個方法可以推廣到 multiple constraints at higher dimensions.

allenlu2007