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

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

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
>>
>>
>
>
>