close

Вход

Забыли?

вход по аккаунту

?

О принципе аппроксимации допустимого множества в методах внутренних и внешних штрафов.

код для вставкиСкачать
BeCTHHK CTI6ry. Cep . 10,2006,
Y.LI:K 519 .68
5I. H. 3a6omU'I-t, H. A .
BbIll .
2
<PY1W'H
o IIPIIHIJ;IIIIE AIIIIPOKCIIMAIJ;1I1I ,n;OIIYCTIIMOrO MHO)l(ECTBA
B METO,n;AX BHYTPEHHIIX H BHEIIIHIIX IIITPA<I>OB
BBe,n;eHHe. MeTO,LI, lIlTpa<pHbIX <PYHKIIHM YHHBepCaneH H npocT B peanH3aIIHH, 'IeM npH­
[1- 5J 60JIee 30 JIeT. He OCJIa6eBaeT K HeMy HHTepec H B
[4- 9J iIOCB.HIIIeHO OIIeHKaM TO'IHOCTH pelIleHH.H B MeTO­
lIlTpa<poB. B OTJIH'IHe OT HHX B [1OJ ,LI,JI5I pelIleHH5I C 3a,LI,aHHOM
BJIeKaeT BHHMaHHe HCCJIe,LI,OBaTeJIeM
nOCJIe,LI,Hee BpeM.H
[5J.
MHoro pa60T
,LI,ax BHYTpeHHHx H BHelIlHHX
TO'IHOCTbIO 3a,LI,a'IH BbIIIYKJIOrO nporpaMMHpOBaHH5I MeTO,LI,OM lIlTpa<pHbIX <PYHKIIHM 6bIJIO
npe,LI,JIO)KeHO HcnOJIb30BaTb lIlTpa<pHble <PYHKIIHH, nOCTpoeHHble He no ,LI,OnYCTHMOMY MHO­
)KeCTBY, a no MHO)KeCTBY, aIInpOKCHMHpYIOIIIeMY ero H3HYTpH. TaM)Ke npHBe,LI,eH anropHTM,
Kpl':lTepHeM OCTaHOBKH KOToporo CJIY)KHT <paKT nOna,LI,aHH5I TO'IKH MHHHMYMa BcnOMOraTeJIb­
HOM <PYHKIIHH B Pa3HOCTb ,LI,OnYCTHMoro MHO)KeCTBa Hero annpoKcHMaIIHH.
AnnpOKCHMa­
IIH5I CTPOHTC5I TaKHM 06Pa30M, ~IT06bI BKJIIO'IeHHe 3TOM TO'IKH B ,LI,OnYCTHMoe MHO)KeCTBO
rapaHTHpOBaJIO 3a,LI,aHHYIO TO'IHOCTb no <PYHKIIHoHany pelIleHH.H HCXO,LI,HOM 3a,LI,a'IH.
[11 J
B
HCnOJIb30BanHCb Pa3JIH'IHble cnoco6bI annpoKcHMaIIHH ,LI,OnycTHMoro MHO)KeCTBa.
B HaCT05lIIIeM pa60Te oCJIa6JIeHbI YCJIOBH5I, HanaraeMble Ha U;eJIeBYIO <PYHKIIHIO H orpa­
HH'IeHH5I.
B
MHO)KeCTBa.
'IaCTHOCTH, CH5ITO YCJIOBHe BbIIIYKJIOCTH IIeJIeBOM <PYHKIIHH H ,LI,OnYCTHMoro
TaK)Ke npe,LI,JIaraeTC5I anropHTM C annpoKcHMaIIHeM ,LI,OnYCTHMoro MHO)KeCTBa
B MeTO,LI,e 6apbepHblx <PYHKIIHM.
IIocTaHoBKa 3a,n;aQH.
fi(X)
,LI,JI5I
paHCTBe
YCJIOBHe p-annpoKcHMHpyeMocTH.
i E I = {I, 2, ... , m}
Rn.
f(x),
IIycTb <PYHKIIHH
onpe,LI,eJIeHbI H HenpepbIBHbI B n-MepHOM eBKJIH,LI,OBOM npOCT­
,l1;JI5I JII06oro 'IHCJIa
A onpe,LI,eJIHM
MHO)KeCTBO
D (A)
= {x
: x E R n , 9 (x)
O}, r,LI,e g(x) = max{fi(x),i E I}. C'IHTaeTC5I, 'ITO MHHHMYM <PYHKIJ;HH f(x)
D(O) ,LI,OCTHraeTC.H H Ka)K,LI,bIM JIOKanbHbIM MHHHMYM 51BJI5IeTC5I rJI06anbHbIM.
+A~
Ha MHO)KeCTBe
IIOJIO)KHM
1* = min{f(x),x E D(O)}.
> 0 HaMTH TO'IKY x'
Tpe6yeTc5I no 3a,LI,aHHOMY 'IHCJIY c
BCIO,LI,Y ,LI,anee npHMeM, 'ITO MHO)KeCTBO
x E R,g(x)
D(O)
EX;
(1)
= {x
E D(O) : f(x) -
1*
Y,LI,OBJIeTBOp5leT yCJIOBHIO CJIeMTepa, T. e.
~ c}.
{x :
< O} i- 0.
<p(X) onpe,LI,eJIeHa B R n, 'IHCJIO A
M(A) = {x : x ERn, <p(x) ~ A} He nYCTO, G - 3a,LI,aHHOe B Rn
M(A) n G i- 0 H, KaK 06bI'IHO , p(x, M(A)) = inf Ilx - yll·
,l1;anee 6Y,LI,eM C'IHTaTb, 'ITO <PYHKIIH5I
TaKOBO, 'ITO
MHO)KeCTBO
MHO)KeCTBO,
xEM{>.)
Onpe,n;eJIeHHe. IIycTb
npH
t
> 0 H a(O)
= O.
a(t) -
HenpepbIBHM nOJIO)KHTeJIbHM Hey6bIBaIOIIIa.H <PYHKIIH5I
<I>YHKIIHIO
V;(x)
= {<p(X)
a(p(x, M(A)))
+A
'i/x E M(A) n G,
'i/x E G \ M(A)
(p, a, A)-annpoKcHMHPYIOIIIeM CHH3y 3a,LI,aHHYIO <PYHKIIHIO <p(x),
<p(x) - (p, a, A)-aIInpOKcHMHPyeMoM CHH3y Ha MHO)KeCTBe G, eCJIH
6Y,LI,eM Ha3bIBaTb
V;(x)
© .H. 11.
22
3a6oTHH, 11. A. Cl>yKHH , 2006
~
<p(x), 'i/x E G.
(2)
a <PYHKIIHIO
(3)
B
[11]
nO,LI,06HOe nOH.HTHe 6bIJIO HCnOJIb30BaHO npH
6bIJIH ,LI,OKa3aHbI
<PYHKll,HH
1)
CJIe,LI,yIO~e YCJIOBH.H
= 13 . t, 13 >
aCt)
(p, 13, A)-annpOKcHMHPyeMocTH
O.
TaM)Ke
CHH3Y ,LI,JI.H BblIIYKJIOH
<p(x):
nycTb <PYHKll,H.H
<pC x)
onpe,LI,eJIeHa, HenpepbIBHa H .HBJI.HeTC.H BblIIYKJIOH Ha BblIIYKJIOM
G n M(A) OrpaHH'ieHO, H CYlll,eCTByeT TOqKa
X E G TaKa.H, 'iTO <p(X) < A. TOr,LI,a HaH,LI,eTC.H qHCJIO 13 = j3(A) > 0 TaKoe, 'iTO ,LI,JI.H <PYHKll,HH
'I/J (x), onpe,LI,eJIeHHOH YCJIOBHeM (2) npH aCt) = 13 ·t, 13 > 0, 6Y,LI,eT BbIIIOJIH.HTbC.H HepaBeHCTBO
(3);
2) nycTb <PYHKll,H.H <pC x) .HBJI.HeTC.H HenpepbIBHOH. H BblIIYKJIOH Ha Rn. ECJIH <PYHKll,H.H
<p (x) .HBJI.HeTC.H (p, 13, A) -annpoKcHMHPyeMoH CHH3Y Ha G eRn, TO <PYHKll,H.H x(x) = T<p(X),
MHO)KeCTBe
G eRn,
,LI,JI.H 'mCJIa A MHO)KeCTBO
o < T ~ 1, .HBJI.HeTC.H (p, Tj3, N)-annpoKcHMHPyeMoH CHH3Y Ha G npH N
~ A.
(p, 13, A)-annpoKcHMHPyeMbIe <PYHKll,HH .HBJI.HIOTC.H (p, a, A)-annpoKcHMHPye­
O,LI,HaKO KJIaCC (p, a, A)-annpoKcHMHPyeMbIx <PYHKll,HH., KaK 6Y,LI,eT nOKa3aHO HH)Ke ,
O'ieBH,LI,HO,
MbIMH.
3HaqHTeJIbHO umpe.
TeopeMa 1. llycm'b <PY'H'K'4U.R <p(x) .R6.1£.RemC.R '1Wa3U6'btny'K.I£OU 6 Rn. T02aa a.l/,.R .1£'/06020
A 'HaUaemc.R ma'Ka.R 'Henpep'bt6'Ha.R, nO.l£O;)ICume.l£'b'Ha.R U 'Hey6'bt6a'/O'l1I;a.R no t > 0 <PY'H'K'4U.R
aCt), "{mo a.l/,.R <PY'H'K'4uu 'IjJ(x), onpeae.Ae'H'Hou YC.l£06ueM (2), 6yaem 6'btnO.l£'H.Rm'bC.R 'Hepa­
6e'HCm60 (3).
BbI6epeM npOH3BOJIbHO TO'iKY x ¢ M(A). ITYCTb pr(x) - npo­
x Ha MHO)KeCTBO M(A). ITo onpe,n;eJIeHHIO KBa3HBbIIIYKJIOCTH, <p(tx + (1 ­
t)pr(x)) ~ max{<p(x), <p(pr(x))} ,LI,JI.H JII06oro t E [0,1]. TaK KaK <p(x) > A, <p(pr(x)) = A,
T O <p(tx + (1 - t)pr(x)) ~ <p(x) , HJIH, 'iTO TO )Ke caMoe, <p(pr(x) + t(x - pr(x))) ~ <p(x).
TaKHM 06Pa30M, <PYHKll,H.H <p(pr(x) + t(x - pr(x))) He y6bIBaeT no t E [0,1].
TaK KaK
T O'iKa pr(x) .HBJI.HeTC.H npOeKll,HeH JIl060H TO'iKH pr(x) + t(x - pr(x)), t ~ 0, TO <PYHKll,H.H
i.p(pr(x) +t(x-pr(x))) He y6bIBaeT no t Ha OTpe3Ke [0, t'] npH JII060M tl > O. Tor,LI,a <PYHKll,H.H
,l1;oKa3aTeJIbCTBo.
eKll,H.H TO'iKH
.
aCt)
nOJIO)KHTeJIbHa H He y6bIBaeT no
y ¢ M(A)
.1106oH TO'iKe
x - pr(x)
= x9!M(oX)
mm <p(pr(x) + t II X t> O.
ITOCTPOHM <PYHKll,HIO
= x9!M(oX)
min <p(pr(x) + Ily - pr(Y)1111
X -
( )11)
pr x
~ <p(pr(y)
'IjJ(x)
(3).
= a(p(x,M(A))) + A.
B
~ y - prey)
+ Ily - pr(Y)IIIIY _ pr(Y)II) = <p(y).
TaKHM 06Pa30M, YKa3aHa <PYHKll,H.H, onpe,LI,eJIeHHa.H YCJIOBHeM
eTC.H HepaBeHCTBO
A
,LI,JI.H Hee BepHo
x - pr(x) 'IjJ (y)
( )11) -
pr x
(2),
,LI,JI.H KOTOPOH BbIIIOJIH.H­
TeopeMa ,LI,OKa3aHa.
TeopeMa 2. IIycm'b <PY'H'K'4U.R <p(x) .R6.1£.RemC.R pa6'HOMep'H0 6'btny'K.I£OU 6 Rn C MOaY.l£eM
6btnY'K.I/,OCmu b(t). T02aa a.l£.R .1£'/06020 A O'Ha (p, a, A)-annp0'KCUMupyeMa C'HU3Y 6 Rn npu
aCt) = b(t).
,l1;oKa3aTeJIbCTBO. BbI6epeM npOH3BOJIbHO TOQKY Xo ¢ M(A). ITYCTb xp - npoeK­
lUHI TO"<IKH Xo Ha MHO)KeCTBO M(A). ,LI,JI.H paBHOMepHO BblIIYKJIbIX <PYHKll,HH BbIIIOJIH.HeTC.H
HepaBeHcTBo
[12,
c.
221]
r~e 8<p(x p ) - cy6,n;H<p<pepeHll,HaJI <PYHKll,HH <p(x) B TO'iKe xp. ,l1;oKa)KeM, 'iTO CYlll,eCTByeT
T aKOH BeKTOp
d
E 8<p(x p ) ,
"<ITO
Cd, Xo - x p)
~
o.
,l1;eHcTBHTeJIbHO, eCJIH 6bI 3TO 6bIJIO He TaK,
23
(C,XO-Xp) < 0, M3 KOTOpOrO CJIe,n;yeT,
<p(X) B TO'-lKe Xp. IIPOTMBOpe'-lMe
MMeeT MeCTO B CMJIY TOrO, '-ITO Xo fj. M(A) M <p(aXO + (1- a)xp) > <p(xp) ,n;JIfi JIIo6oro a> O.
TaKMM 06Pa30M, ,n;JIfi HeKOToporo c' E o<p(xp) rrOJIY'-IMM <p(xo) ~ o(llxo - xpll) + <p(xp).
TaK KaK TO'-lKa Xo BbI6paHa M3 MHO)KeCTBa Rn \ M (A) npOM3BOJIbHO M <p(x p) = A, TO
HepaBeHCTBO <p(x) ~ o(p(x, M(A)) + A) BbIllOJIHfleTCfI ,n;JIfi JIIo6oro x fj. M(A). TeopeMa
TO ,n;JUI BCeX c
'-ITO
Xo - Xp
E O<p(Xp) BbIllOJIHflJIOCb
6bI HepaBeHCTBO
flBJIfleTCfI HarrpaBJIeHMeM y6bIBaHMfI <PYHKll,MM
,n;OKa3aHa.
ECTecTBeHHo, paBHOMepHO BbIllYKJIafi <PYHKll,MfI flBJIfleTCfI KBa3MBbIllYKJIOH, M CYlll,eCTBO­
BaHMe ,n;JIfi Hee
TeopeMe
2
(p, 0", A)-annpoKcMMMPYIOlll,eH
<PYHKIJ;MM CJIe,n;yeT M3 TeopeMbI
YKa3aH JIerKO peaJIM3yeMbIH crroco6 BbI60pa <PYHKIJ;MM
1.
O,n;HaKo B
O"(t).
AJII'OPHTM Ha OCHOBe IIITpa<pHoH <PYHKD;HH, nocTpoeHHoH no nOI'pY)I{eHHoMY
MHO)l{eCTBY· IIYCTb
= (Yl,Y2, ... ,Ym),Y E Rm,R:;;"
P(y) TaK, '-ITO
Y
orrpe,n;eJIMM <PYHKIJ;MIO
YE
R~
===}
P(y)
= 0,
Y fj.
R~
= {y: Yi:::;
===}
O, Vi
= 1, ... ,m}.
P(y) > o. B
Rm
(4)
V(x) = P(h(x) +p,··.,fm(x) +p) M A(a) = {x ERn: V(x):::; a,a ~ O}.
(4), JIerKO 3aMeTMTb, '-ITO V(X) = 0 rrpM x E A(O) M V(X) > 0 npM x fj. A(O).
IIPM P > 0, TaK KaK A(O) = D(p), MHO)KeCTBO A(O) .HBJIfleTCfI rrOrpY)KeHHbIM B D(O),
T. e. D(O) .HBJIfieTC.HOKpeCTHOCTbIO MHO)KeCTBa A(O).
0603Ha'-lMM
"Y'-IMTbIBMI
BCIO,n;y ,n;aJIee 6y,n;eM rrpe,n;rrOJIaraTb, '-ITO BbIIlOJIHeHbI yCJIOBMfI:
a) <PYHKIJ;MfI
f(x)
y,n;OBJIeTBOpfieT Ha MHO)KeCTBe
D(O)
YCJIOBMIO JIMrrllmIJ;a C KOHCTaHTOH
Lj
6) CYlll,eCTByeT TaKoe '-IMCJIO
O"(t)
<PYHKIJ;MfI
g(x)
A' < 0, '-ITO rrpM Bcex A E [A', 0) M rrpM HeKoTopoH <PYHKIJ;MM
(p, 0", A)-arrrrpoKcMMMPyeMoM CHM3Y B Rn·
flBJIfieTC.H
BBe,n;eM BcrrOMOraTeJIbHYIO <PYHKll,MIO
F(x, C) = f(x) + CV(x), C > 0, (5)
M MHO)KeCTBO aprYMeHTOB ee MMHMMYMa
X(C)
= Argmirr{F(x,C),x ERn}. (6)
x(C) 0603Ha'-lMM TO'-lKM MHO)KeCTBa X(C)j TO'-lKM x* E Argmin{f(x),x E
D(O)},xp E Argmin{f(x),x E D(P)}.
TeopeMa 3. llycm'b "tUC.l/,O p E (0, min{ O"(c!L), -A'}) . T02aa 'Hepa6e'HCm60 f(x) - 1* < c
61JtnO.l/,'H.R,emc.R, a.l/,.R, .l/,106ou mo"t'X:u X E Q, 2ae Q = {x E Rn : f(x) :::; fp} n D(O), fp = f(x p).
,LI;oKa3aTeJIbCTBO. IIYCTb Xo - rrpOeKIJ;MfI TO'-lKM x* Ha MHO)KeCTBO D(p). TaK KaK
f(x*) :::; f(x) :::; f(xo), TO
f(x) - f(x*) :::; f(xo) - f(x*).
(7)
IIocpe,n;CTBOM
g(X) .HBJIfleTCfI (p, 0", A)-arrrrpoKcMMMPyeMoM CHM3y rrpM Bcex A > A',
TO g(X*) ~ O"(llx* - xoll) - p. Tor,n;a, B CMJIY g(X*) :::; 0 M YCJIOBMH
O"(llx* - xpll) :::; p < O"(cl L). 113 Hey6bIBaHMfI O"(t) rro t CJIe,n;yeT
TaK KaK <PYHKll,M.H
-p > A'
M
x* fj. D(p),
TeOpeMbI, MMeeM
Ilx* - xoll < ciL. f(x) y,n;oBJIeTBOpfieT Ha D(O) yCJIOBMIO
(8), nOJIy'-lMM fo - f(x*) :::; Lllxo -x*11 < c .
«I>YHKIJ;MfI
BeHCTBO
TeopeMa ,n;OKa3aHa.
24
(8)
JIMrrIllMIJ;a, rro3ToMY,
Tor,n;a, B CMJIY
(7),
Y'-lMTbIBafi Hepa­
MMeeM
f(x) - 1* < c.
CJIe,n;CTBHe
1. Ec.l/,u J.I/,.R
C > 0 8'bmO.l/,'H.RemC.R X(C) E D(O), mo J(x(C))­
'He~OmOp020
1* < c.
).l;oKa3aTeJIhCTBO. TaK KaK
J(X(C)) :::; Jp.
Torp;a X(C) E
CJIep;CTBl1e p;OKa3aHO.
Q,
J(X(C)) -
MOHOTOHHO Hey6hIBaIOm;a51 <PYHKll,l151 OT C, TO
a P;JI51 TaKOll TO':lKl1 Tpe6yeMoe HepaBeHCTBO BhIIIOJIH51eTC51.
ITo onpep;eJIeHl1IO MHO)KeCTBa
X;, eCJIl1 npl1 HeKOTopOM p > 0 BhIIIOJIH51eTC51 HepaBeHCTBO
JP - 1* :::; c, TO Q eX;
11 JII06a5i TO':lKa x E Q 6yp;eT c-OnTl1MaJIhHOll. O,n;HaKO Ha npaKTl1Ke
BhI':Il1CJIeHl1e BeJIl1':1l1HhI JP B 3aBl1Cl1MOCTl1 OT p He npom;e, ':IeM pemeHl1e 3ap;a':l11 (1).
TeopeMa
3 n03BOJI51eT Oll,eHl1Th Pa3HOCTH JP -
J*.
TO':lHee, C ee nOMOm;hIO MO)KHO YKa3aTh
3Ha':leHl1e napaMeTpa p, npl1 KOTOPOM p;OCTl1raeTC51 BKJIIO':IeHl1e
Q C
X;.
ITpl1Me':laTeJIhHO, ':ITO B TeopeMe Oll,eHKa pemeHl151 He 3aBl1Cl1T OT cnoco6a HaXO)K,ll;e­
Hl151
X E Q.
ECJIl1)Ke 3ap;a':lY Ml1Hl1M113all,1111 <PYHKll,l1l1
J(x)
Ha MHO)KeCTBe
D (P)
pe­
maTh MeTop;OM BHemHl1X mTpa<pOB C nOMOm;hlO TaKOll BcnOMOraTeJIhHOll <PYHKll,l1l1, ':ITO
p(x(C),D(P)) - - - t 0, TO Hallp;eTC51 TaKoe C > 0, ':ITO x(C) E D(O). A no CJIep;CTBl1IO
C--too
3 3TO paBHOCl1JIhHO BKJIIO':IeHl1IO x( C) E X;.
TeopeMa 4. IIycm'b ifJy'H~v,uu J(x), V(x) - JuifJifJepe'Hv,upyeM'b£J
K TeopeMe
ny~.I/,a.RJ cy~ecm8yem ifJy'H~V,U.R a-I (.) J
~ ifJy'H~v,uu
o6pam'Ha.R
ifJy'H~V,U.R V(x) - 8'b£­
a (t) J U 0 < p :::; -)..'. T02Ja
'Hepa8e'Hcm80
La-I(p)
C :::; V(x(C))
8'bmO.l/,'H.Remc.R J.I/,.R 8cex C > 0
ma~uxJ ~mo
).l; 0 K a 3 aTe JI h C T B O. ITyCTh
x(C) E D(O) .
Xo - npOeKll,l151 TO':lKl1 x(C)
Ha MHO)KeCTBO
D(p).
AHaJIOrl1':1HO p;OKa3aTeJIhCTBY TeopeMhI 3 nOJIy':ll1M a(llx(C) -xoll) :::; p. TaK KaK cym;ecTByeT
o6paTHa51 K a(t) <PYHKll,l151, TO a(t) B03paCTaeT no t. OTCIOp;a CJIep;yeT Ilx(C) - Xo II :::; a-I (p).
Torp;a, Y':ll1ThIBa5i, ':ITO
V(xo)
= 0, BepHO HepaBeHCTBO
V(x(C)) - V(xo) ;;::: V(x(C))
TaK KaK
x(C)
~
D(P),
TO Ilx(C) - xoll
+ Ilx(C) -
> O.
(9)
xoll- a-I(p).
(9)
Pa3p;eJIl1M o6e ':IaCTl1 HepaBeHCTBa
Ha
Ilx(C) - xoll:
V(x(C)) - V(xo)
Ilx(C)-xoll
V(x(C)) - a-I(p) ~ 1
1
+
;;:::
Ilx(C)-xoll
~ +
(V(x(C)) -
a-I(p)) _
a-I(p)
-
(10)
V(x(C))
a-I(p)'
X = x(C)+t(x(C)-xo), t;;::: O. OTcIOp;ax(C) = t~1 xo+ t~1 x. TaK KaK <PYHKll,l151 V(x)
BhIIIYKJIa51, TO V(x(C)) :::; t~1 V(xo) + t~1 V(x) 11 V(x) - ~(x(C)) ;;::: V(x(C)) - V(Xo). Torp;a
10)
V(x)-V(x(C)) ~ ~
e V(x(c)+t(x(C)-xo))-V(x(C)) ~ V(x(C))
C Y':leToM (
HaxOP;l1M tllx(C)-xoll ~ (T- l (p) ,T. .
tllx(C)-xoll
~ --:=trP)
ITyCTh
npl1 JII06hIX t ;;:::
O.
CJIep;OBaTeJIhHO,
av(x(C))
a x~C)-xo
IIx C)-xoll
r
= t~~O
ITOJIY':ll1M IIV'(x(C))11 ;;:::
V(x(C)
88~{~lC21
II'" C)-"'oll
TO':lKe
tllx(C) -
;::
~~1{~))'
rp;e
xoll
V'(x(C)) -
~
~
V(x(C))
a-I(p) .
rpap;l1eHT <PYHKll,l1l1
V(x)
B
x(C).
1:13 onpe,n;eJIeHl151 x(C) BhITeKaeT,
L(T~
C·- 11f'{x{C))11
11 . -
+ t(x(C) - xo)) - V(x(C))
':ITO rpap;l1eHT
F'(x(C), C)
= J'(x(C))+CV'(x(C)) = 0
1IV'(x(C))II ' :::; V(x(C))' TeopeMa p;OKa3aHa.
25
CJIe,n;CTBHe 2. IIycm'b
JocmuzaemcJ£ npu J/,106o.M
C
a = max{a
:
A(a) c D(O)}. TozJa B'X:J/,lO"te1-tUe x(C) E D(O)
-1( )
L
~ ~.
A(a) M D(O) MMeIOT HeKOTOPYIO
g(z) = 0 M V(z) = a. TaK KaK HaMfJ,eTCH MHfJ,eKC s E I TaKOM ,
'"ITO fs(z) = 0, TO npH p > 0 BeKTOp (II (z) + p, ... , fm(z) + p) (j. R;. 113 (4) CJIefJ,YeT, '"ITO
P(1I (z) + p, ... , fm(z) + p) > O. TorfJ,a, no onpefJ,eJIeHHIO, a = V(z) > O.
ITYCTb BCIOfJ,Y fJ,aJIee '"IHCJIO C > 0 TaKoe, '"ITO V(x(C)) = a. TaK KaK a > 0 H <PYHK­
U;HH V(x(C)) HenpepbIBHa no C > 0, TO '"IHCJIO C CYI1J,eCTByeT H KOHe'"lHO. ITo TeopeMe 4
npH p :s; -A' fJ,JIH '"IHCJIa C BblIIOJIHHeTCH 'HepaBeHcTBo C :s; L(T~l(p). 113 HeB03paCTaHHH
<PYHKU;HM V(x(C)) no C > 0 BbiTeKaeT, '"ITO V(x(C)) :s; a fJ,JIH Bcex C ~ C. 9TO 03Ha'"laeT,
L~-l(~,
'"ITO BKJIIO'"IeHHe x(C) E A(a) c D(O) fJ,OCTHraeTCH npM JII060M C ~ ~. CJIefJ,CTBHe
,LI;o K a3 aTe JI b CT B O. O'"leBMfJ,HO, rpaHMU;bl MHO)KeCTB
06ru;yIO TO'"lKY Z, B KOTOPOM
fJ,OKa3aHO.
Ha 3TOM CJIefJ,CTBHH H TeopeMe
AJIrOpHTM
1.
(0 , min {at! ), - A'} ),
3afJ,aeTCH
3
OCHOBaH
,
TO'"lHOCTb peIlleHHH
HaTypaJIbHOe '"IHCJIO
N.
c
> O.
Bbl6HpaIOTcH
'"IHCJIO
p E
3afJ,aIOTCH TO'"lKa Ha'"laJIbHOrO npH6JIH)KeHHH
L~-l(~,
E Rn
H
B03paCTa~I1J,aH <PYHKU;HH
1
h(·) TaKaH, '"ITO h(l) ~ 0, heN) ~ ~, rfJ,e 0 - (-)­
<PYHKU;HH, 06paTHaH K aCt). ITOJIaraeM k = 1.
1. Bbl'"lHCJIHeM Ck = h(k).
2. Bbl6MpaeM MeTOfJ, A k , o6eCne'"lHBaIOI1J,MM HaXO)KfJ,eHHe 6e3YCJIOBHOrO MHHMMYMa <PYHK­
U;MM F(Ck,X).
3. MeTOfJ,OM Ak OTblCKMBaeM x(Ck) = arginf{F(Ck,x) , x ERn}.
4. ECJIH x(Ck) E D(O), TO npOU;ecc OKOH'"IeH H X(C k) HBJIHeTCH c-peIlleHMeM 3afJ,a'"lH
HaxO)KfJ,eHHH (1). l1Ha'"le 3aMeHHeM k Ha k + 1 H nepeXOfJ,HM K n. 1.
TeopeMa 5. YCJl,OBUe n . 4 aJ/,zopum.Ma 1 B'btnOJl,1-tUmCJ£ "tepea 'X:01-te"t1-toe "tUCJl,O k' :s; N
umepa'Ll;uu. IIpu amo.M x( Ck') E X; .
,LI;oKa3aTeJIbCTBO. ITo CJIefJ,CTBHIO K TeopeMe 4, TO'"lKa x(CN ) E D(O), T. e. YCJIOBHe
Xo
npepbIBaHHH Bbl'"lMCJIeHMM BblIIOJIHMTCH '"Iepe3
TeopeMe
3,
BblIIOJIHHeTCH HepaBeHCTBO
k'
:s;
f(x(Ck,)) -
N
HTepaU;HM.
1* < c.
ITPH Bbl60pe Ha nOfJ,rOTOBMTeJIbHOM Illare aJIrOpHTMa
L~-l(~,
~
, '"ITO rapaHTHpyeT BKJIIO'"IeHHe
Q
x(Cr) E D(O).
TorfJ,a, no CJIefJ,CTBMIO K
TeopeMa fJ,OKa3aHa.
N
=
1
nOJIY'"IHM
heN)
= h(l)
~
9TO 03Ha'"laeT p e IlleHHe C 3afJ,aHHOM
TO'"lHOCTbIO HCXO,lI,HOM 3afJ,a'"lM 3a OfJ,HY MTepaU;MIO MeTOfJ,a IllT pa<p0B. Ho, K CO)KaJIeHHIO, nofJ,06HbIM Bbl60p '"IHCJIa
HblX <PYHKU;HM
N
F(x, C1 )
npMBOfJ,HT K nJIOXOM 06YCJIOBJIeHHOCTH MaTpMU;bI BTOPblX npOH3BOfJ,­
B 06JIaCTH peIlleHHH. ECJIH npH 3TOM TO'"lKa Ha'"laJIbHOrO npH6JIH)Ke­
F(x, Cr) Bbl6paHa fJ,OCTaTO'"lHO fJ,aJIeKO
x(Cr) E X(C1 ) 6YfJ,eT, nO-BHfJ,MMOMY,
MefJ,JIeHHO CXOfJ,HI1J,MMCH. IT03TOMY u;eJIeC006pa3HO CTPOHTb cepHIO <PYHKU;MM F(x, C k ). MH­
HHMH3au;HIO <PYHKU;HH F(x, Ck) CJIefJ,yeT Ha'"lHHaTb H3 TO'lKH X(C k - 1 ). TaK KaK <PYHKU,HH
x( C) HenpepbIBHa no C > 0, TO npH fJ,OCTaTO'"lHO 6JIM3KHX 3Ha'"leHMHX Ck H Ck-l MO)KHO
O)KHfJ,aTb 6JIH30CTb TO'"leK x(C k) H x(Ck-d.
BeJIH'"IHHa norpY)KeHHH P H K03<P<PHIJ;MeHT IllTpa<pa C Bbl6MpaIOTCH B aJIrOpHTMe 1 Ha
OCHOBe napaMeTpa L M <PYHKU;HH aCt) , KOTopble B npaKTHKe MO)KHO JIHilib ou;eHHTb. C JIefJ,OBa­
TeJIbHO, K03<P<PHU;HeHT C 6YfJ,eT, O'"leBHfJ,HO, CHJIbHO 3aBbIIlleHHbIM, M BKJIIO'"IeHHe x( C) E D(O)
MO)KeT fJ,OCTMraTbcH npH C < C. 113 3THX co06pa)KeHMM B n. 4 aJIrOpMTMa 1 KpHTepHeM
OCTaHOBKH BbI6paHo BKJIIO'"IeHHe x(C) E D(O), a He YCJIOBHe k = N.
l1MeeTcH 60JIbillOM npOH3BOJI Bbl60pa HeOTpMu;aTeJIbHOM B03paCTaIOI1J,eM <PYHKu;HH h(k),
3afJ,aIOllI,eM npaBMJIO H3MeHeHHH IllTpa<pHoro napaMeTpa C B 3aBHCHMOCTH OT HOMepa HTepa­
U;HH k. ECJIH B npaKTMKe Tpe6yeTcH YCTaHOBHTb MYJIbTMnJIHKaTMBHblM 3aKOH YBeJIM'"IeHMH C,
HMH B MeTOfJ,e 6e3YCJIOBHOM MHHHMH3aU;HH <PYHKU;MM
OT MHO)KeCTBa
26
X(Cr),
TO npou;ecc HaXQ)KfJ,eHHH TO'"lKH
TO MO)KHO rrOJIO)KI1Tb
~
'-ITO rrpl1 3TOM C k -
l
=
ECJII1 B aJIrOpl1TMe
TO'-IHO rrOJIO)KI1Tb
f-L
= J1."t-k'
h(k)
~
h(k-l)
1
I1MeeM
Tor,n,a
I
~.
f.
r,n,e BeJII1'-II1Ha
C TaKafl,
HeKoTopbI:i1 MHO)KI1TeJIb. JIerKo 3aMeTI1Tb,
'-ITO
h(N)
~
O"(t)
h(k)
= _
eN
k
(gl )--,;r=r
11
h(1)
G1 ,
TO ,n,OCTa­
= Gl .
11 BbI60pa Ha rro,n,rOTOBI1TeJIbHOM 3Tarre aJIrOpl1TMa
OTCIO,n,a
G
HI1Tb HepaBeHCTBOM
>1-
= f-L.
= (g) N:'l.
O"-l(p)
f-L
Tpe6yeTcfI flBHO 3a,n,aTb Ha'-IaJIbHbI:i1 K03<pqm~l1eHT
B CI1JIY B03paCTaHI1f1 <PYHK~1111
p ~ O"(f),
r,n,e
~
V(x(C))
LO"-l(p)
_
a
= a.
~
Lf
-_a
c
= -=:-,
a
To eCTb YCJIOBl1e
h(N) ~ Lu~l(p)
MO)KHO 3aMe­
;i-.
AJIrOpHTM Ha OCHOBe 6apbepHoH <PYHKD;HH.
llpl1MeHI1M rrpl1H~l1rr arrrrpOKCI1Ma­
~1111 ,n,orrYCTI1MOrO MHO)KeCTBa ,n,JIfi rrOCTpOeHI1f1 aJIrOpl1TMa 3a,n,aHHo:i1 TO'-IHOCTI1 B MeTo,n,e
6apbepHbIx <PYHK~I1:i1. ,II;JIfi 3Toro I1CrrOJIb3yeTcfI BbmYKJIM 6apbepHafi <PYHK~I1f1
b(x), orrpe­
193].
llYCTb bdD(O) - rpaHI1~a MHO)KeCTBa D(O), intD(O) = D(O) \ bdD(O). BCIO,LI,y Ha intD(O)
<PYHK~I1f1 b( x) KOHe'-IHa, HerrpepbIBHa 11 HeOTpl1~aTeJIbHa, ,n,JIfi JII060:i1 6eCKOHe'-IHo:i1 rrOCJIe­
,n,OBaTeJIbHOCTI1 TO'-IeK {Xi}, rrpI1Ha,n,JIe)KaIll,I1X intD(O) 11 CXO,n,flIll,I1XCfI K TO'-IKe 113 bdD(O),
rrpe,n,eJI lim b(Xi) = +00.
,n,eJIeHHafi CJIe,n,yIOIlI)1:M 06pa30M
[4,
c.
t-+oo
,II;orrOJIHI1TeJIbHO K YCJIOBI1f1M a) 11 6) rroTpe6yeM BKJIIO'-IeHl1e
X* C bdD(O),
{x E D(O) : f(x) ~ /*}.
llYCTb B(a) = {x E Rn : b(x) ~ a},a ' = min{a : D(P) C B(a)}.
B(a')} - /* ~ fp - /*, r,l1;e fp = min{f(x) , x E D(O)}.
r,n,e
X*
=
min{f(x),x E
Tor,l1;a
Ha 3T0:i1 o~eHKe OCHOBaH CJIe,l1;YIOIll,l1:i1 rrpI1H~l1rrl1aJIbHbI:i1
AJIrOpHTM 2.
3a,l1;aIOTCfI Tpe6yeMafi TO'-IHOCTb c > 0 HaXO)K,l1;eHI1f1 (1), '-II1CJIO P E
(0, min{ 0"( f), -N}). BbI6l1paIOTCfI rrOCJIe,l1;OBaTeJIbHOCTb {Td~o -+ 0, Tk > 0, '-II1CJIO a ~ a /.
llOJIaraeTCfI k = O.
1. HaxO,l1;I1TCfI Xk E Argmin{F(x,Tk),X ERn}, r,l1;e F(X,Tk) = f(x) + Tkb(X).
2. ECJII1 Xk ¢ intB(a) , TO BbI'-II1CJIeHI1f1 OCTaHaBJII1BaIOTCfI, 11 TO'-IKa Xk rrpl1HI1MaeTCfI
B Ka'-IeCTBe c-OrrTI1MaJIbHOrO peIIIeHI1f1 3a,l1;a'-Il1 (1). I1Ha'-Ie CJIe,l1;yeT rrepe:i1TI1 K rr. 1 rrpl1 k,
3aMeHeHHOM Ha k + 1.
TeopeMa 6. HauaemcJl, ma'lwu 'HO.M.ep N, "tmo e nOCAeaoeame.!l,'b'HOCmU {xd, nocmpo­
e'H'HOU no a.f/,20pum.M.Y 2, mo"t'lw XN ¢ intB(a). IIpu 3mO.M. XN E X;.
,II; 0 K a 3 aTe JI b C T B O. llpe,D,llOJIO)KI1M OT rrpOTI1BHoro, '-ITO )J;JIfi JII060ro k TO'-IKa
Xk E intB(a). Tor,l1;a, B CI1JIY 3aMKHY~OCTI1 MHO)KeCTBa B(a), TO'-IKa x' = lim Xk E B(a).
k-+oo
llo TeopeMe CXO,l1;I1MOCTI1 MeTO,l1;a 6apbepHbIx
<PYHK~I1:i1 (CM., Harrpl1Mep,
x' E X*, a rro ,l1;OrrOJIHI1TeJIbHOMY YCJIOBI1IO x' E bdD(O).
Ho B(a) rrorpY)KeHO B D(O), TaK KaK D(O) cO,l1;ep)KI1T OTKpbIToe
g(x) < O}, CO,l1;ep)KaIII,ee B(a). CJIe,l1;OBaTeJIbHO, B(a) n bdD(O) = 0.
llOJIY'-IeHHOe rrpOTI1BOpe'-Il1e ,l1;OKa3bIBaeT cyII~ecTBOBaHl1e HOMepa
[4,
c.
194]) TO'-IKa
MHO)KeCTBO
N,
{x E Rn :
rrpl1 KOTOPOM
xN ¢
intB(a).
,II;aJIee BbI6epeM TO'-IKY
x E Argmin{f(x),x E B(a)}.
B(o:/) c B(a) 11
TaK KaK
a
~
a',
TO, B CI1JIY
BbmYKJIOCTI1 6apbepHo:i1 <PYHK~I1I1,
f(x) ~ min{f(x),x E B(a /)}.
27
ITo onpe.n,eJIemno, T09KH MHHHMYMa
f(x)
+ TNb(x).
b(x) :::;; a, b(XN)
f(x) - 1* :::;; min{f(x) : x
TaK KaK
B
F(XN , TN) :::;; F(x,TN).
OTCIO.n,a
f(XN)
+ TNb(XN)
:::;;
,n;JI.H y.n,06CTBa npe06pa3yeM 3TO HepaBeHCTBO K BH)J.y
2
aJIrOpHTMe
~ a, TO b(x) E B(a')} - 1*
HCnOJIh3yeTC.H
b(XN) :::;; 0 H f( XN) :::;; f(x).
Tor.n,a
f(XN) - 1* :::;;
:::;; fp - 1* :::;; c. TeopeMa .n,OKa3aHa.
BeJIH9HHa a', Oll,eHHTh KOTOPYIO MO)KHO, JIHUlh
HaJIara.H
.n,onOJIHHTeJIhHhle YCJIOBH.H Ha 6aphepHYIO <PYHKlI,HIO. ITpHBe.n,eM 3.n,eCh Oll,eHKY .n,JI.H HaH6o­
JIee pacnpocTpaHeHHoM B JIHTepaTy pe <PYHKlI,HH
s(tI, t2, ... , t m )
b(x)
=
s(- h(x)' - !2(x) , ... , - ,Jx))'
r.n,e
- nOJIO)KHTeJIhHa.H B03paCTaIOllI,a.H <PYHKlI,H.H no KaJK.n,OM nepeMeHHoM.
JIeMMa 1. Bep1w 'Hepa8e'HCm80 s(~,~, ""~) ~
a'.
x' E Argmax{b(x), x E D(P)}.
D(p) C B(b(x')) . CJIe.n,OBaTeJIbHO, C O.n,HOM CTOPOHhI, no onpe.n,eJIeHHIO a', BepHO
HepaBeHCTBO b(x') ~ a'. C .n,PyroM CTOPOHhI, x' E D(p), a D(P) C B(a'). Tor.n,a x' E B(a')
H b(x') :::;; a'. IT03TOMY CYllI,eCTByeT T09Ka x' E D(p), B KOTO'P OM b(x') = a'.
ITo onpe.n,eJIeHHIO MHO)KeCTBa D(P), HepaaeHCTBO fi(X') :::;; -p BepHO .n,JI.H Bcex i = 1, .. , m.
OTcIO.n,a H H3 B03paCTaHH.H <PYHKlI,HH s(h, t 2 , •.• , t m ) BbITeKaeT
,n; 0 K a 3 aTe JI h C T B o.
BhI6epeM npOH3BOJIhHO
Tor.n,a
JIeMMa .n,OKa3aHa.
TaKHM 06Pa30M, eCJIH B aJIrOpHTMe
a
~ s( 1,1, ...,1),
p
P
P
1
Ha no.n,rOTOBHTeJIhHOM 3Tane BhI6HpaTh BeJIH9HHY
TO Tpe6yeMoe HepaBeHCTBO
a
~ a'
6y.n,eT BhITIOJIH.HThC.H.
Summary
Zabotin Ya. 1., Pukin I. A . On the principle of the feasible set approximation for the methods
of penalty and barrier functions.
This article proposes a nonlinear programming problem algorithm based on the principle of the
feasible set approximation. This principle is applied here for algorithm development on the method
of penalty functions.
r.
1. E6mywen?Co 10.
LIHCJIeHHbIe MeTO,11,bI peilleHH5I 3a,11,a'l HeJIHHeHHOro rrporpaMMHpOBaHHlI
/ / )KypH. BbI'lHCJIHT. MaTeMaTHKH H MaT. <pH3HKH. 1976. T. 16, N~ 2. C. 307-324.
2. BaCU.lI,'be6 <P. n. , K06a"l, M. O. 0 perYJI5IpH3~ HeKoppeKTHblx 3KCTpeMaJIhHbIX 3a,11,aQ C
HcrrOJIb30BaHHeM illTpa<pHb1x H 6apbepHblx <PYHKII,HH/ / BecTH. MOCK. YH-Ta. Cep . BMK. 1980.
N~
2. C. 29-35.
3. C?Capun B.
Jl.. 0 CKOPOCTH CXO,LI,HMOCTH MeTO,11,a 6apbepHblx <PYHKII,HH / / MeTO,11,bI orrTHMH3a­
II,HH H paCrr03HaBaHHe 06pa30B B 3a,lJ,a'lax rrJIaHHpOBaHH5I. M. : YHIJ; AH CCCP, 1980. C. 27- 36.
4. E6mywen?Co 10.
MeTO,11,bI peilleHH5I 3KCTpeMaJIbHbIX 3a,LI,a'l H HX rrpHMeHeHHe B cHcTeMax
OrrTHMH3~H. M .: HaYKa, 1982. 432 c .
5. )KaGan B.
LIHCJIeHHble MeTO,11,bI JIHHeHHoro H HeJIHHeHHOro rrpOrpaMMHpOBaHH5I (BcrroMo­
raTeJIbHble <PYHKlI,HH B YCJIOBHOH orrTHMH3all,HH). M.: HaYKa, 2002 . 160 c.
6. EpeMun 11. 11. MeTO,11, «illTpa<poB» B BbIIIYKJIOM rrporpaMMHpOBaHHH / / ,LI;OKJI. AH CCCP.
r.
r.
1967. T. 173, N~ 4. C. 748- 751.
7. )KaGan B. r. 0 HeKOTopblX Oll,eHKax K03<p<pHlI,HeHTa illTpa<pa B MeTO,11,ax TO'lHbIX illTpa<pHbIX
<PYHKII,HH / / )KYPH. Bbl'lHCJIHT. MaTeMaTHKH H MaT. <pH3HKH. 1984. T. 24, N~ 8. C. 1164- 1171.
28
8. Cyxape6 A. r., Tu,.M,OX06 A. B., qJeaOp06 B. B. Kypc MeTO,Ll,OB onTHMH3~H. M.: HaYKa,
1986. 328 c.
9. Kaaapo6 C. A. Ou;eHKH 6Jlli30CTH peIllemm 3KCTpeMaJIbHbIX 3a,Ll,aQ B MeTO,Ll,e IllTpa<pHhIx
<PJHKu;mt / / M3B. BY30B. MaTeMaTHKa. 1978. N! 9. C. 40-48 .
10. 3a6omu'H. H. H., qJy.,.U'H. H. A. 06 O,Ll,HOH MO,LJ,H<pHKau;HH C,LI,BHI'a IllTpa<poB ,lVIa 3a,n;aQ He.1m­
HeHHoro npOrpaMMHpOBaHHH /I M3B. BY30B. MaTeMaTHKa. 2000. N! 12. C.49-54.
11. 3a6omu'H. H. H., (JJy.,.U'H. H. A. AJIrOpHTMbI B MeTO,Ll,e IllTpa<pOB C anrrpoKcHM~eH ,LI,onyc­
THMoro MHO)l{eCTBa / / M3B. BY30B . MaTeMaTMKa. 2004. N! 1. C. 36-47.
12. Bacu'//''be6 B. fl. "tfMCJIeHHbIe MeTO,LJ,bI p,eIlleHHH 3KCTpeMaJIbHbIX 3a,n;a'l. M.: HayKa, 1988.
552 c.
Документ
Категория
Без категории
Просмотров
3
Размер файла
3 972 Кб
Теги
внешний, внутренние, допустимое, множества, принципы, штрафов, метода, аппроксимация
1/--страниц
Пожаловаться на содержимое документа