RE: [maths] Lagrange Multipliers & Optimal operation of ....

["Hoang Duong Tuan" <tuan@toyota-ti.ac.jp>]

Hi ba'c Ca^u:

La^`n tru+o+'c qua meo ba'c, tui hie^?u la` ba'c muo^'n solve ba`i toa'n
ddo' chu+' tui la.i kho^ng nghi~ ba'c quan ta^m Lagrangian multiplier (LM)
tu+`
quan ddie^?m kinh te^'! Any way, cha('c ba'c cu~ng bie^'t mu.c ddi'ch
cu?a LM la` dde^? ddu+a ca'c ba`i toa'n constrained
ve^` unconstrained (nhu+ ba`i toa'n cu?a ba'c thi` va^~n giu+~ constraints
for integer variables). Sau khi co' lagrangian ro^`i thi` ngu+o+`i ta du`ng
ca'c phu+o+ng pha'p nhu+ Newton, Gauss etc. dde^? ti`m stationary point
(hay co`n go.i la` KKT (Karush-Kuhn-Tucker) point) la` nhu+~ng ddie^?m
tho?a ma~n ddie^`u kie^.n ca^`n (necessary condition) to^'i u+u. Nhu+~ng
ddie^?m na`y chu+a cha('c dda~ locally optimal, la.i ca`ng kho^ng globally
optimal.
Cu~ng du+.a va`o LM ma` ngu+o+`i ta la`m penalty method:
khi ba'c ta(ng lagrangian multiplier thi` se~ force ca'c bie^'n cu?a primal
variable
tho?a ma~n constraint. Phu+o+ng pha'p na`y cu+' sau mo^~i step thi` update
LM (o+? dda^y co`n nhie^`u va^'n dde^` na^?y sinh vi` ta(ng LM to se~ da^~n
to+'i
numerical instability etc.). Chi'nh vi` va^.y ma` tui no'i ra(`ng kho^ng
nha^'t thie^'t
LM pha?i co' bound.
Tre^n dda^y la` vai tro` cu?a LM trong solution method! Ta^'t nhie^n, vi` LM
co'
tu+` ddo+`i ta'm hoa'nh, tru+o+'c khi cu. Ho^` ra ddo+`i ne^n ngu+o+`i ta
to^
ve~ ddu? ca'c kie^?u cho no', nhu+ ca'c anh kinh te^' cha(?ng ha.n. Theo tui
hie^?u ca'c anh kinh te^' quan ta^m dde^'n ca'i saddle point (ddie^?m ye^n
ngu+.a)
cu?a LM, hay no^m na la min-max point. Ta.i ddie^?m na`y, cha('c la`
pseudo-price
(gia' ro?m) cu?a ba'c la` to^'i u+u dda^y. Nhu+ng nhu+ tui dda~ no'i,
thu+o+`ng
chi? ti`m ra ddu+o+.c KKT point (thoa? ma~n necessary condition for min-max)
tho^i. Co`n bound cho ca'i  ddie^?m ye^n ngu+.a na`y thi` tui kho^ng bie^'t
co'
nhu+~ng ai quan ta^m.
Tu+` nhu+~ng ddie^?m ba'c ne^u ra dda^y, tui nghi~ ba'c ne^n ddo.c chu't i't
ve^` duality theory in optimization, no' se~ cho ba'c i't feeling ve^` ma^'y
behavior
va` bounds cu?a LM cha(ng (ngay nhu+ dual problem of LP cu~ng co' ty ty?
economic interpretation).
Ba'c co' the^? ddo.c ma^'y thu+' na`y trong quye^?n cu?a Bertsekas ma`
tui no'i (co' gi` kho' hie^?u thi` khi co' the^? ho?i tui, khi ma't gio+`i
tui se~
gia?i thi'ch). Quye^?n na`y mo+'i ho+n va` co' nhie^`u interesting
interpretation for LM.
Khoa?ng 10 na(m nay, tay Bertsekas na`y mo^~i na(m vie^'t khoa?ng 1-2
quye^?n
sa'ch.
TD

>Cam on Bac Tuan da quan tam den van de cua toi.
>Neu chi can giai primal problem thi co le toi cung khong phai lam phien cac
>bac. Ban chat cua van de la nhu sau.
>Cac bac deu biet Lagrangian multiplier do have a economic intepretation and
>they are sometimes called shadow (pseudo) prices. Ngay nay, nhieu nganh
cong
>nghiep lon nhu electric power industry da va dang duoc cai to va
>decentralised thanh cac cong ty doc lap. Nhu vay hinh thanh cai goi la
>(electricity) competitive market trong do cac thanh vien (participants)
phai
>co strategy sao cho co loi nhat (ton tai va phat trien). Bai toan
>centralised optimisation trong he thong dien tap trung (nha nuoc nam toan
bo
>cac khau: san xuat, truyen tai, phan phoi) se mat y nghia va tro thanh co
>dien. Thay vao do la cac bai toan decentralised coordination, luc nay
>pricing variable (dual variables) tro thanh quan trong va tac dong den
>strategy cua individual participants. Trong literature da thay xuat hien
>market-based control methods mo phong co che dau gia' cua thi truong
>(auction model) va duoc ap dung trong he thong dien, vien thong, v.v...
>Toi cho rang day la mot potential direction and have got some preliminary
>thoughts. Muon vay, truoc tien phai hieu ban chat cua Lagrange multipliers,
>bounds cua no. Khi hieu roi, bac co the mo hinh hoa, optimise ... va play
>with it. It's really interesting I guess.
>Hy vong da lam sang to muc tieu cua van de da neu,
>Regards,
>Cau
>P.s: cho den gio toi van chua tho^ng solution cua Iga. No qua' u+ la toa'n
>ma toi da noi roi, toi la dan non-mathematical. Let me try to read for
>another couple of days.
>Quyen sach ma Bac Tuan gioi thieu khong hieu sao khong co trong library cua
>truong tui ha ? Khong biet no co cung noi dung voi Bertsekas, DP (1982)
>"Constrained optimization and Lagrange multiplier methods", Academic press,
>NY ? Chac phai nho interlibrary Loan thoi !
>
>----- Original Message -----
From: Hoang Duong Tuan <tuan@toyota-ti.ac.jp>
>To: <vnsa@List-Server.net>
>Sent: Monday, 9 August 1999 10:40
>Subject: RE: [maths] Lagrange Multipliers & Optimal operation of ....
>
>
>> Hi ba'c Ca^u: