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

["Thai Doan Hoang Cau" <c.thai@ee.unsw.edu.au>]

Hi ca'c ba'c,
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:
>
> Be careful with advices of IgaSon. I don't think that you need such
> references for
> solving your problem.
>
> To IgaSon:  sao ba'c phu+'c ta.p ho'a va^'n dde^` the^', la.i chi? nhu+~ng
> references na(.ng mu`i to'an va` co^? lo^~ xi~ the^'. Ba`i toa'n cu?a ba'c
> Ca^u
> kho' o+? cho^~ co' integer variables (ne^'u kho^ng linearized problem la`
> LP,
> chuye^.n gi` pha?i du`ng Lagrangian multiplier).
> Any way, tui ho^?ng hie^?u ba'c Ca^u ca^`n ma^'y ca'i bounds ddo' la`m
gi`.
> Theo tui chu+a cha('c dda~ co' bounds dda^u. De^~ tha^'y ne^'u ma^'y ca'i
> multipliers ddo' tie^'n to+'i vo^ cu`ng thi` nghie^.m cu?a ba`i toa'n
> Lagrangian
> tie^'n to+'i nghie^.m cu?a ba`i toa'n linearized ddo'.
> Co' quye^?n sa'ch mo+'i va` de^~ ddo.c ma^'y thu+' na`y la`: D.Bertsekas,
> Nonlinear programming, Athena Scientific, 1995. ISBN 1-886529-14-0.
> Cheers,
> tua^'n
>
>
>
> >Dear Iga Nguyen
> >Thanks lot for your kind help in this matter. I'll try to find and read
the
> >references which you have given.
> >Regards,
> >Cau
> >
> >
> >----- Original Message -----
> >From: Iga Nguyen <iga@blue.cft.edu.pl>
> >To: VNSA <vnsa@List-Server.net>
> >Sent: Saturday, 7 August 1999 3:29
> >Subject: Re: [maths] Lagrange Multipliers & Optimal operation of ....
> >
> >
> >> Hi Hoang Cau et al,
> >>
> >> On Thu, 5 Aug 1999, Thai Doan Hoang Cau wrote:
> >>
> >> > Primal problem: min {f(x) : g(x)<=0; h(x) = 0, x E X}  (E: thuo^.c)
> >> > Trong he thong dien, bai toan la mixed integer programming, NP hard
doi
> >voi
> >> > van de hydrothermal coordination va nhung bai toan khac. Tuy nhien,
hay
> >bat
> >> > dau bang bai toan don gian with assumptions of piecewise
linearisation
> >and
> >> > convexity voi f(x) = c'x, g(x) = Ax + B, h(x) = Cx + D trong do c, B,
> D,
> >la
> >> > cac column vector; A, C la matran co corresponding dimensions; g, h
la
> >> > vector cac rang buoc.
> >> > De giai bai toan nay voi kich thuoc lon, nguoi ta thuong dung 2
phuong
> >phap
> >> > kha noi tieng la Lagrangian relaxation (LR) va Benders
decompositions.
> >Trong
> >> > LR, de tranh giai bai toan goc (primal problem) voi cac rang buoc
phuc
> >tap,
> >> > nguoi ta giai its dual problem (doi ngau ?), tuc la
> >> >     min { L: x E X }  voi L = f(x) + mu.g(x) + lambda.h(x)
> >> > with given mu (>=0) , lambda (unrestricted) which are initialised and
> >> > updated by many methods.
> >>
> >> The "Primal Problem" is very well-known problem in the classical
> >> Mathematical Analysis.  Usually it is known as constrained extremum
> >> problem, and it is formulated as following:  X = R^n, F is a
> >> differentiable function from X to R and G is a diff. function from
> >> X to R^m.  Find min/max { F(x) | G(x) = 0 }.
> >>   In general students of 2-nd year univ. must know how to solve
> >> it, at least theoretically, using Lagrange multiplier method.  One has
> >> to solve one vector equation (which is a system of (n+m) scalar
> >> "algebraic" equations) :
> >>
> >>          dF = lambda . dG ;  (1*)     &       G (x) = 0 ;        (2*)
> >>
> >> where lambda is in (R^m)' and dF, dG is a diff. of F, G respectively.
> >>
> >>   Right, the problem is formulated for equality's constraints,
> >> but without a difficulty one can modify it to the case of mixed
> >> constraints (including both equality & inequality).
> >>
> >> Now for fun, one can forget all complicated stupid mathematical symbols
> >> (follow me),  and say: OK, the problem is quite geometrical so why we
> need
> >> as much stupid latin/greece symbols ?:-)  Simply, the problem is to
find
> >> out an extremum of a given function on a given "smooth" manifold.
> >> That's all:-)
> >>
> >> Now let me jump out from the classical analysis to the modern one.
> >> We'll replay the n-dim Euclides space (X) by a normed space,
> >> functional F by functional (non-linear in general), function G by
> >> a function from the normed space to R^m.  The "differentiability"
> >> condition of F, G should be  replayed by Fre'chet's differentiable (ie.
> >> strong differentiable).   We ask for extreme
> >>
> >>        { functional F | G (x) = C, x in X - normed space } ;       (3*)
> >>
> >> It should be understood as a natural generality from a case of
> >> finite constraints to a case of infinite constraints
> >> (more over: uncountable, or with arbitrary cardinal number of
> >>  constraints:-) !!
> >>
> >> In the particular one could choose F as an intergral and gets
> >> uncountable familiar problems, those apperead in App. Math, Phys &
> >> Engeenering ...
> >>
> >> The analogous theorem as in classical case (namely: Lagrange multiplier
> >> rule), was proved firstly by Ljusternik (great Russian mathematician
> >> before & after WW2).  As a matter of fact he required a little more
that
> >> G is continuously Fre'chet differentiable.  So if x is an extreme of F,
> >> then there exists a Lagrange multiplier lambda (in R^m)* such that
> >>
> >>           grad F (x) = lambda . grad G (x) ;
> >> (4*)
> >>
> >>
> >> > Va^'n de^`:
> >> > Cai toi quan tam la da co nghien cuu (strictly mathematical or
> >heuristic)
> >> > nao ve bounds (upper and lower limits) cua mu va lambda chua ? Toi
rat
> >can
> >> > tham khao nhung ket qua nay.
> >> > Mong cac bac da tung quan tam, nghien cuu hay co the advise ve van de
> >nay
> >> > giup do.
> >>
> >> As we have seen, in the classical mathematical analysis, math-people do
> >> not care seriously about Lagrange multipliers, they used it only as
> >> helpful quantities in the calculations .... and what they are really
> >> interested in, is ... constrained extreme :-))
> >>
> >> However,
> >> Look at (1*) or (4*), for simplicity: in the case m =1, these equations
> >> could be viewed as eigenvalue (for (4*) it is nonlinear) problems for
the
> >> operator pair grad F, grad G !!  The eigenvalues are simply the
Lagrange
> >> multipliers !  In fact this intepretation essentially differs
> >> from the ordinary investigation of the stationary points of
> >> L = F - lambda G.
> >>
> >> With the above interpretation, your problem should be reduced to a
> >> problem, which is intensively studied & exploatated, studying a
> >> spectrum (eigenvalues) of a given linear/non-linear operators.
> >>
> >> For some mathematical results in Non-linear Analysis (ie. math analysis
> >> in the normed spaces) about nonlinear eigenvalues problem, see for e.g.
> >>
> >> 1) Fucik, Necas, etc.
> >>     Spectral Analysis of nonlinear Operators, Springer-Verlag 1973.
> >> 2) PALAIS
> >>     Critical Point theory and Minimax principle,
> >>     (Global Analysis) Proc. Sym. Pure Math. Vol 15, 1970.
> >> 3) Rabinowitz (Rocky Mount J. Math. 3, 1973)
> >>    Some aspects of nonlinear eigenvalue problems ....
> >> 4) Nirenberg
> >>    Topics in Nonlinear functional analysis, Courant Inst., NY 1974.
> >> 5) Ambrosetti, Rabinowitz
> >>    Dual variational mathods in critical point theory and applications,
> >>    J. Func. Anal. 14, 1973.
> >>
> >>
> >> etc.
> >>
> >>
> >> Cheers,
> >> Iga
> >>
> >>
> >
> >
> >
>
>