Legendre Transform

by allenlu2007

數學上有很多的 transformation, 有些是比較抽象。但應用在工程上的大多比較 physically intuitive, 或者有幾何上的意義。前者如 Fourier transform (time domain vs. frequency domain); 後者如 bilinear transform (complex vs. polar, used in Smith chart); 或是 Laplace transform (pole and zero plot).

本文 focus on Legendre transform, 意即 f(x) — L –> g(p ) 把 x domain 上的 f(x) transform 成 p domain 上的 g(p )

Legendre transform 有兩個前提 (i) f 必須是 convex function (f”>0 開口向上); (ii) Legendre transform 關注 local behavior.

和 Fourier transform 比較: f(t) –> F(f) 把 time domain 的 f(t) transform 成 frequency domain 的 F(f).

Fourier transform 的前提是 (i) (int f) 積分必須存在, 要不然就要引入 delta function; (ii) Fourier transform 關注 global behavior 而非 local behavior.  區部的 behavior 並無法告訴我們包含什麼 frequency.  (更正確但 hand waving 來說, local t 附近 dt 的 information, 只能告訴我們 f >> 1/2*pi*(dt) 的 information).  

 

Legendre Transform 幾何詮釋

前提:

NewImage

對於 (x, f(x)) 可以定義唯一切線,斜率為 p, 截距為 -g.  Legendre transform 即是 g(p ).

以 f(x) = x^2 為例:  f'(x) = 2x;  f”(x)=2 > 0 開口向上。

對 (x, f(x)) 的斜率為 f'(x) = 2x = p  ==> x = p/2  

 

重點是要找 p=f'(x) 的反函數   x = f’^-1(p ) !!   因為 f(x) 是 convex, f'(x) 是遞增,所以反函數存在。

但不一定有簡單的 solution 如上式。

截距為 f(x) = px – g  ==>  g(p) = px – f(x) ==> g(p ) = p*p/2 – (p/2)^2 = p^2/4

In summary:   x^2 — L –>  p^2/4

NewImage

有趣的是,如果把 g(p ) 在做一次 Legendre transform:

f(x) = x^2/4 ; f'(x) = x/2 = p;  f”(x) = 1/2 > 0

x = 2p,  g(p ) = px – f(x) = p(2p) – (2p)^2/4 = p^2

 

In summary:  p^2/4 — L –> x^2    兩次 Legendre transform 會回到原點。

 

再次強調, Legendre transform 是基於微分的反函數,所以需要微分遞增或是 convex function!

因些 Legendre trasform 的特性也類似反函數。(如下)

 

對稱性:  L(f(x)) = f*(p ) and  L(f*(p )) = f(x)   (反函數的反函數是自己)

除了對稱性外,還代表 Legendre transform 不會 loss information.

All information about a convex function is stored in the y-intercepts of its tangent lines.


f(x) + f*(s) = x*s   where s = df(x)/dx   and x = df*(s)/ds    f’^(-1) = f*’  (反函數 = Legendre transform 微分) 

Multi-dimension 寫法

F(x) <==>  G(s)   via Legendre transform

G(s) + F(x) = <s, x>

where x(s) = dG(s)/ds  (∇ of G(s))

where s(x) = dF(x)/dx   (∇ of F(x))

 

Scaling: for a > 0,

f(x) = a \cdot g(x) \Rightarrow f^\star(p) = a \cdot g^\star\left(\frac{p}{a}\right)

f(x) = g(a \cdot x) \Rightarrow f^\star(p) = g^\star\left(\frac{p}{a}\right).

Translation,

 f(x) = g(x) + b \Rightarrow f^\star(p) = g^\star(p) - b

 f(x) = g(x + y) \Rightarrow f^\star(p) = g^\star(p) - p \cdot y

 

倒數 (非反函數)?

 f(x) = g^{-1}(x) \Rightarrow f^\star(p) = - p \cdot g^\star\left(\frac{1}{p}\right)

 

另外是否有兩函數的和 (sum) 的 Legendre transform 公式?

f(x) <==>  f*(s)   where s = f'(x)  and x = f’^-1(s)  (反函數)

g(x) <==> g*(s) where s = g'(x)  and x = g’^-1(s)  (反函數)

f(x) + g(x) <==>  ??

It turns out there is no simple answer to sum of two functions.

主要是 (f+g)’^-1 ≠ f’^-1 + g’^-1 !!

 

 

另類 Legendre Transform 幾何詮釋

剛好在上述 reference 看到另一個幾何詮釋。也許 author unaware 這也是 Legendre transform 的幾何詮釋。

假設 state 的座標是 q (charge), co-state 的座標是 e (voltage).  

如果存在 e=Φ(q) 以及反函數 q=Φ^-1(e):  (this imply Φ is monotonic increasing or decresing)

Wiki: Continuous 反函數存在條件: A continuous function f is one-to-one (and hence invertible) if and only if it is either strictly increasing or decreasing

可以定義 energy (state) function W(q) = ∫edq; and co-energy (co-state) function W*(e) = ∫qde.  

兩塊面種加起來: W(q) + W*(e) = e*q.    Legendre transform 就是 co-energy (co-state) function, 也就是 shaded  部份的面積 (i.e. 積分).   BTW, co-state function 和 co-energy function 的單位因此相同。

那原來的 convexity requirement 呢?  其實隱含在 Φ(q) 反函數之中。

因為 e=Φ(q) 的導數必為全正或全負才能保証 q=Φ^-1(e) 存在。因此 W(q) 保証是 convex or concave (因為二階導是全正或全負。

其實上述的定義也是如何求 Legendre transform 的 procedure: 

1. 先做 dW(q)/dq = e = Φ(q)   (之前的幾何詮釋是鈄率,現在的幾何詮釋是 (e, q) 的 nonlinear function.

2. 下一步 (i) 用比較難的 approach, 先求 q = Φ^-1(q), 再做積分 W*(e) = ∫qde.  或是 (ii) 用簡單的 approach, W*(e) = e*q – W(q)!

  NewImage

一些例子:

1.  以 W(q) = q^2/2 為例:  dW(q)/dq = e = Φ(q) = q  因此是線性對稱關係。可以推論 W*(e) = e^2/2

2.  Scaling and translation 應可由以上的幾何得出。

這個幾何詮釋對我似乎更有感覺。

 

 

 

General Legendre Transform

Legendre transform 可以推廣到 non-differentiable function 或是 multi-dimension case (但仍必須是 convex function)

 

Non-differential function case.  重點是用 sup 取代斜率。

Let I ⊂ R be an interval, and f : I → R a convex function; then its Legendre transform is the function f* : I* → R defined by

f^*(x^*) = \sup_{x\in I}(x^*x-f(x)),\quad x^*\in I^*

with domain

I^*= \left \{x^*:\sup_{x\in I}(x^*x-f(x))<\infty \right \} ~.

The transform is always well-defined when f(x) is convex.

 

接下來是推廣到 multi-dimension.  x = (x1, x2, … xn).   

x* = (df/dx1, df/dx2, .., df/dxn) = ∇ f(x)

切線變成切面

截距 (scaler) 仍然是切面在 (x1, x2, ..xn) = (0, 0, ..0) 時的截距值。

x * x* = <x, x*> inner product

 

The generalization to convex functions f : X → R on a convex set X ⊂ Rn is straightforward:f* : X* → R has domain

X^*= \left \{x^*:\sup_{x\in X}(\langle x^*,x\rangle-f(x))<\infty \right \}

and is defined by

f^*(x^*) = \sup_{x\in X}(\langle x^*,x\rangle-f(x)),\quad x^*\in X^*   ~,

where \langle x^*,x \rangle denotes the dot product of x* and x.

The function f * is called the convex conjugate function of f.

 

Example 1: A general quadratic n-dimension curve

NewImage

 

NewImage

 

Example 2: A general linear function

Linear function (affine) 並非 strictly convex. 但可以用一個 curvature ~ 0 的 parabola 來近似。

其實用第二種幾何更容易了解。

NewImage 

 

Example 3: (Example 1 is a special case where A = A’A and y=0

NewImage

NewImage

 

Example 4: (exponential and log)

f(x) = x log(x) with x ∈ R and x > 0 and p ∈ R

注意 f'(x) ~ log(x) 因此反函數是 exp(p), exp(p) 的積分仍是 exp function. 

NewImage

 

 

Legendre transform 到底有什麼用?

A. Optimization applications

Legendre transform 把 f(x) 轉到斜率、截距 domain, 雖然保留 all information (assuming f is convex function), 到底提供什麼 physical insight?

A.1 unconstraint optimization solution: 很顯然 unconstraint optimization problem 的最小值是在斜率p=0, 同時最小值就是截距。

i.e.  -f*(p=0) 就是最小值!!  

但如何找對應的 xmin? 有兩種方式:

(a)  p(x) = df/dx  => p(xmin) = df/dx = 0 解 xmin

在 strictly convex 情形下基本上有唯一解。

(b)  f(x) + f*(p ) = x*p

xmin 對應 p=0  => f(xmin) + f*(p=0) = 0

=> f(xmin) = -f*(p=0) 可用來解 xmin

 

For R^n dimension, the generalization is straightforward.  

x* = (df/dx1, df/dx2, ..) = ∇ f(x)

f(x) + f*(x*) = <x, x*>

找最小值時斜率 (gradient) 為 0:

(a) x* = ∇ f(xmin) = 0 –> n equations 解 xmin

f(xmin) + f*(x*=0) = <xmin, x*> = 0

(b) f(xmin) = -f*(x*=0) 得到最小值

 

一般來說, (a) 比較簡單且好解,因為微分後的 function 階數比較低。另外在 R^n 情況下: (a) 是 n equations 解 n variables. (b) 只有 1 equation 解 n variables; 

 

順便 check 如果 f(x+b)=g(x) 最小值 ==> -g*(p ) = -f*(p )+p*b  => -g*(p=0) =  -f*(p=0)

x translation 不改變 f 的最小值。

f(x)+b=g(x) ==> -g*(p ) = -f*(p )+b

y translation f 最小值是原值 + b

同樣 x scaling 不改變 f 最小值,y scaling scale f 最小值。

 

A.2 Constraint optimization 

f(x)  under h(x) = 0 where x is a R^n vector.  Both f(x) and h(x) are convex function

f(x) -> f*(s)  ;  h(x) -> h*(s)    

在有 constraint 情況下,標準解法是 Lagrange multiplier (參考 Lagrange multiplier 文)

∇ f(x) = λ * ∇ h(x)  and h(x)=0

 

是否可用 Legendre transform?  有三種方式:

Method 1 (n-1 components): Reduce component, h(x) 中的 one component 被其他 n-1 components 替換。

Method 1 確定可得到 Legendre transform 見下文。即使 h(x) 非 convex function 應該也 ok?

 

Method 2 (n component): Full component, h(x) = f(x)+ λ g(x); λ 是 constant, 可由 Lagrange multiplier 找出。

  ∇ h(x) = 0  => ∇ f(x)+ λ ∇ g(x) = 0 等同於 Lagrange multiplier

convex + convex 應該是 convex (how about h(x) is not convex?),但 two function sum 的 Legendre transform 並沒有 close form.  不確定是否有 close form.

Method 3 (n+1 component): λ 視為第 n+1 component, h(x, λ) = f(x)+ λ g(x)

  ∇ h(x, λ) = 0  =>  ∇ f(x)+ λ ∇ g(x) = 0  and g(x)=0  等同於 Lagrande multiplier 加上原來 constraint.

 

 

Method 2  

Method 3. 不確定是否 h(x, λ) = f(x)+ λ g(x) 是否 convex?  是否存在 Legendre transform.  以及 Legendre transform 是否有意義。

 

Method 1. Reduce component 基本上得到的結論就是 Lagrange multiplier.  最後的 Legendre transform of reduced component 可以用以下的公式得到。

NewImage

NewImage

 h(x) = 0 的 constraint 可以消滅一個 variable (至少 conceptually, 實際上不一定有 close form)

NewImage 

 仔細觀察 (4) and (5), 當 i = a 時 pa = 0.  因些 (5) 可以改為:

                                NewImage           (6)

 換言之,h(x)=0 的 constraint 讓 unconstraint 的 (p1, p2, …, p(a-1), pa) 變為 (p1′, p2′, .., p'(a-1), 0).

     where p1′ = p1 – Φ ∂h/∂x1,   p2′ = .., … , p’a=0

 Constraint 讓一個 dimension 消失了!  注意替換不同的 xa (corresponding p’a=0) 會得到不同的 Φ 和 g(p’).

 實務上由 (5) or (6) 算 g(p’) 非常費工。

 除了所有的偏微分,還必須先求所有 p’i ( eq (4) ) 的反函數 xi。最後再代入 (5) or (6).

 

 事實上找 minimum 並不用算出 g(p’) 只要找 p’i = 0  ==> ∂ f / ∂ xi  * ∂ h / ∂ xa = h f / ∂ xi  * ∂ f / ∂ xa  for all i.

 基本上這就是 Lagrange multiplier 的變形! ( ∇ f(x) = λ ∇ h(x) )

 可以看出 Φ(xmin) = λ  注意替換不同的 xa 會得到不同的 Φ, 但 Φ(xmin) = λ always true regardless xa.

 上述方式應可以推廣到 multiple constraints. 在此不推導。

 

Example:  f(x, y) = 1/2(x^2 + y^2)   —- (1)     h=x+y-4=0   —- (2)

p = (u, v) = (x, y)  => g(u, v) = 1/2(u^2 + v^2) => unconstraint fmin = g(u=0,v=0) = 0

Constraint by (2) brutal force way:

NewImage

p’=0 ==> (xmin, ymin, fmin) = (2, 2, 4) as expected

 

From (6) Φ = ∂ f/∂ y  / ∂h/ ∂y  = y

NewImage

Same as brutal force way.

  結論是: 解 optimization 問題時,不要真的求 Legendre transform, 而是解 p=0 即可。如果是 constraint optimization, 就解 p’=0 (相同於 Lagrange multiplier).

 

 Method 2

Optimization condition:

Df + λ Dg = 0   plus  g(x)=0

D(f + λ g) = 0

g(x) = 0    g(x) + g*(x*) = <x, x*>  ==> g*(x*) = <x, x*>

?? 是 f*(x*=0) (no, this is no constraint)  ==> g*(x*) = 0 ==> no, stationary point 不是原點,應是兩者 normal parallel

==> f*(x*) = k g*(x*) 但 g*(x*) = <x, x*> ==>  f*(x*) = k <x, x*>

 

 

B. Physics applications

Legendre transform 最常被 quote 的例子是在力學以及熱力學。

特別是在 link two variables 時 (兩個 variables 不需是 independent. 事實上大多是 dependent.

主要的引入 Legendre transform 原因我相信也是解 optimization problem.

 

E.g.  Lagrangian   int L  -> minimize   after Legendre transform   dH =0 (H is not explicitly t dependent)  H conservation.  轉換 optimization 問題變成守恆量 or 不變量 (invariant) 問題 (?)

以上 Lagrangian <-> Hamiltonian  可以推廣到 optimal control (?) 把 extensive variable 轉為 intensive variable (conjugate variable) for better control.

可以參考 Noether’s Theorem 如下:

 

(ii) If  f = f(y, y’) = L(p, q) without explicitly t dependence (t symmetry), p ∂L/∂p – L(p, q) = const = H

   解釋:  (t, H) :  t symmetry 轉換成 H invariant   (Variation minimum play what role?  是 key role, 是先決條件。舉例而言,如果有磨擦力以下的 Euler-Lagrange equation 不能滿足 equation 如下)

How about (q, p)?  q symmetry –> p invariant

How about (phi, angular momentum)?

 

NewImage

 

The Legendre transform is linked to integration by partspdx = d(px) − xdp.

Let f be a function of two independent variables x and y, with the differential

df = {\partial f \over \partial x}dx + {\partial f \over \partial y}dy = pdx + vdy .

Assume that it is convex in x for all y, so that one may perform the Legendre transform in x, with p the variable conjugate to x.   Since the new independent variable is p, the differentials dx and dy devolve to dp and dy, i.e., we build another function with its differential expressed in terms of the new basis dp and dy.  We thus consider the function g(py) = f – px  so that

dg = df - pdx - xdp = pdx + vdy - pdx - xdp = -xdp + vdy
x = -\frac{\partial g}{\partial p}
v = \frac{\partial g}{\partial y}.

The function g(py) is the Legendre transform of f(xy), where only the independent variable x has been supplanted by p.  

以上 Wiki 的定義 g(p, y) = f – px 和之前 Legenedre transform 相反 ( g(p, y) = px – f ).  因些之後的 dg, x, v 都要加個負號。

 

Hamilitonian of New particle and Einstein particle

 

Lagrangian and Hamiltonian

一個有名的例子是 Lagrangian 經由 Legendre transform 後變成 Hamiltonian

L(v,q)=\tfrac{1}2\langle v,Mv\rangle-V(q),

視 q 為 fixed constant, L(v) 是 convex function of v.  

 Legendre transform 後

 p = ∂L/∂v = mv (generalized momentum).  The Legendre transform of Lagrangian 變成 Hamiltonian

 H(p, q) = p v – L(v, q)

H(p,q)=\tfrac 12\langle p,M^{-1}p\rangle+V(q). 

 同時可以得到 Hamilitonian 的 equations of motion.

 

  v to p transform 看來 trivial, 好像沒做什麼事。其實對應是 1/2v^2 – a <–> 1/2 p^2 + a

 剛好在 parabola v = p,  如果非 parabola (如相對論 particle 或 optimal control u=f(q, v, t)) v <> p

 但 optimal concept 仍然 apply

 

 minimize 一個 free particle 的 Lagrangian path integral : min   int L = int (1/2 v^2 – a)

轉成 p 之後

 

比較文言文的說法:

“the Legendre transform of a Lagrangian function constructs an invertible map between solutions of an n-dimensional second-order equation of motion and a flow on a 2n-dimensional symplectic manifold,” 

 比較白話文的說法 (roughly):

在 Lagrangian 的詮釋中, v 是因變數 (?); 經過 Legendre transform 後,p 做為自變數(?).  以 (p, q) 為座標的 phase plot 可以清楚描述 dynamic system. 

 

Lagrange Multiplier and Legendre Transform

之前提到 (physics) Lagrangian 經過 Legendre transform 後變成 Hamiltonian.  (p, q) 可視為 independent variables 用在 phase diagram 完全描述 dynamic system.  不過尚未提到 equations of motion (Euler-Lagrange equation) 如何從 n 個 2nd order equations 變為 2n 個 1st order equations.  (TBA)

我們先討論比較簡單的例子: Lagrande multiplier.  如前文

consider the convex optimization problem

maximize f(xy)
subject to g(xy) = c.

f(x, y) 是 convex function, assuming f(x, y) = 1/2 (x^2 + y^2) ==>  f*(p, q) = 1/2 (p^2 + q^2) 

(p, q) 決定了 f(x, y) 的 normal direction

g(x, y) 是 convex function, 同樣 g(x, y)-c=0  ==> g*(p, q)+c = 0 (??) 

 

Duality: Primal dual, gap

 

Lagrange multiplier interpretation

wiki Lagrange multiplier: generalized force

 

NewImage

f(s)={bsT=cTotherwise
Advertisements