Universit a tea din Bucure³ti [631602]

Universit a tea din Bucure³ti
F a cul t a tea de Ma tema tic  ³i Inf orma tic 
ELEMENTE DE OPTIMIZARE
CONVEX€
Co ordonator ³tiinµic,
Conf. univ. dr. Cristian Niculescu
Absolv en t,
Vlad Cristian Munte an

Bucure³ti
2020

Cuprins
Rezumat / Abstract 4
Rezumat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
In tro ducere 6
Scurt Istoric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Optimizare matematic  . . . . . . . . . . . . . . . . . . . . . . . . 8
Optimizare con v ex  . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Programare liniar  . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Elemen te de optimizare con v ex  13
F uncµii con v exe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Probleme de optimizare con v ex  . . . . . . . . . . . . . . . . . . . . 18
Problema primal  ³i dual  de optimizare con v ex  . . . . . . . . . . 22
Aplicaµii – estim ri statistice 23
Estimarea distribuµiei parametrice . . . . . . . . . . . . . . . . . . . 23
Estimarea distribuµiei non-parametrice . . . . . . . . . . . . . . . . 24
Limite Cheb yshev ³i Chemo . . . . . . . . . . . . . . . . . . . . . 25
Bibliograe 26
P ostfaµ  27
3

Rezumat / Abstract
Rezumat
4

Abstract
5

Introducere
Conceptul de optimizare este, în prezen t, bine înr d cinat ca principiu ce
se a  la baza analiz rii m ultor decizii complexe ³i probleme de repartiz ri.
A cest concept ofer  deseori o simplicare incon testabil  a op eraµiilor de cal-
cul, tratând problema cu o eleganµ  losoc , greu de con trazis. Utilizând
losoa optimiz rii, individul ab ordeaz  o problem  ce admite o ip otez  com-
plex , incluzând selecµia de v alori a un ui n um r de v ariabile in terdep enden te,
concen trându-³i toat  atenµia asupra un ui singur obiectiv menit s  cuan tice
p erformanµa ³i s  m soare calitatea deciziei.
În prezen ta lucrare ne v om axa asupra elemen telor de optimizare con v ex ,
care reprezin t  cel mai studiat domeniu din clasele de probleme neliniare.
A ceste elemen te includ programarea liniar  ³i structuri de optimizare ca ³i
caracteristic  a acesteia. Exemple de situaµii care conduc la aceast  structur 
sun t r spândite p este tot prin aceast  lucrare, iar aceste exemple ar trebui
s  a jute la sublinierea faptului c  probleme practice p ot  deseori structu-
rate în aceast  form . Ne in tereseaz  dezv oltarea, analiza ³i compararea de
algoritmi în rezolv area problemelor de optimizare.
Exist  la ora actual  sucien te c rµi despre programarea liniar  ³i programa-
rea neliniar  care se axeaz  asupra form ul rii, mo del rii ³i aplicaµiilor, pre-
cum ³i sucien te c rµi care acop er  noµiuni de teorie a optimiz rii con v exe,
a meto dei punctului in terior ³i analiza complex  asupra acesteia. Lucrarea
de mai jos se dore³te a  o com binaµie în tre aceste dou  categorii, o lucrare
despre optimiz ri con v exe generale care se fo cuseaz  p e problema form ul rii
³i a mo del rii.
6

Scurt Istoric
În timp ce matematica optimiz rii con v exe a fost studiat  înc  de la începutul
secolului trecut, câtev a dezv olt ri recen te asupra acestui domeniu au stim u-
lat in teresul faµ  de acesta. Prima este recunoa³terea meto delor punctului
in terior, dezv oltat  în anii 1980 p en tru a rezolv a probleme de programare
liniar , care p oate  folosit  ³i la rezolv area de probleme de optimizare con-
v ex . A ceste meto de noi ne p ermit s  rezolv  m an umite tipuri noi de clase
de probleme de optimizare con v ex , precum programele semidenite ³i pro-
gramele conice de ordin ul al doilea, aproap e la fel de simplu ca programele
liniare.
A doua dezv oltare este reprezen tat  de descop erirea faptului c  problemele
de optimizare con v ex  (care dep ³esc programele liniare ³i ale "celor mai
mici p trate") sun t mai predominan te în practic  decât se credea în trecut.
Începând cu an ul 1990, m ulte aplicaµii au fost descop erite în domenii pre-
cum: Automatizarea sistemelor de con trol (de exemplu gestionarea tracului
urban al v ehiculelor), Pro cesarea semnalelor, T ransp orturi ³i telecom unicaµii
(în cadrul managemen tului companiilor aeriene prin logistica mo dului de a
obµine bun uri sau destinaµii la cel mai mic cost), Design de circuit electric,
Mo delare ³i analiz  de date, Statistic  ³i Finanµe (de exemplu, determinarea
³i calcularea p ortofoliilor de activ e în mo d ecien t, p en tru a calcula preµu-
rile nanciare ³i p en tru a determina strategiile comerciale ale fondurilor de
in v estiµii). Optimizarea con v ex  ³i-a g sit v aste aplicaµii în optimizarea com-
binatorial  ³i optimizarea global  a, unde este folosit  a p en tru a g si limite de
v alori optimale, precum ³i soluµii apro ximativ e. În aceea³i m sur  se crede
c  m ulte alte aplicaµii ale optimiz rii con v exe sun t înc  nedescop erite.
Exist  o serie în treag  de a v an ta je în ceea ce priv e³te recunoa³terea sau for-
m ularea problemelor ca o problem  de optimizare con v ex . A v an ta jul primar
este c  o problem  p oate  ap oi rezolv at  foarte ecien t folosind meto da
punctului in terior sau alte meto de sp eciale de optimizare con v ex . A ceste
meto de sun t sucien t de sigure p en tru a putea  înglobate în tr-un program
de prelucrare ³i analizare de date sau c hiar în tr-un sistem automatic de con-
trol. Exist , de asemenea, ³i a v an ta je teoretice sau conceptuale de a form ula
o problem  în tr-o problem  de optimizare con v ex . De exemplu, problema
dual , are deseori o in terpretare in teresan t  asupra problemei originale ³i con-
duce spre o meto d  ecien t  de rezolv are. Se crede c  optimizarea con v ex 
este un topic sucien t de imp ortan t astfel încât oricine folose³te matematic 
computaµional  ar trebui s  cunoasc  m car bazele acestui domeniu.
7

Optimizare matematic 
O problem  de optimizare matematic , sau, p e scurt, problem  de optimi-
zare are urmatoarea form :
(
minf0
fi6bi;i= 1;:::;m
(1.1)
Aici, v ectorul x= (x1;:::;xn) este v ariabila de optimizare a problemei, func-
µiaf0:Rn!R este funcµia obiectiv, funcµiile f0:Rn!R;i= 1;:::;m , sun t
funcµiile de restricµie, ³i constan tele b1;:::;bm sun t limitele p en tru restricµii.
Un v ector xse n ume³te "optim" sau "soluµie optim  a problemei" (1.1)
dac  are cea mai mic  v aloare de optimizare din tre toµi v ectorii care satisfac
restricµiile: p en tru orice z cuf1(z)6b1;:::;fm(z)6bm a v emf0>f0(x) .
În general, lu m în calcul familiile sau clasele de probleme de optimizare,
caracterizate de forme particulare ale funcµiilor restrictiv e. Ca ³i exemplu,
problema de optimizare (1.1) este den umit  "program liniar" dac  funcµiile
de optimizare ³i restricµiile f0;:::;fm sun t liniare, adic  satisfac:
fi(x+y) =fi(x) +fi(y) ,8x;y2Rn³i8;2R
(1.2)
Dac  problema de optimizare n u este liniar , se den ume³te program neliniar.
Lucrarea aceasta este despre clasa problemelor de optimizare n umit  "pro-
bleme de optimizare con v ex ". O problem  de optimizare con v ex  este una
în care atât funcµia de optimizare, cât ³i cea restrictiv   sun t con v exe, adic 
satisfac inegalitatea:
fi(x+y)6fi(x) +fi(y) ,8x;y2Rn³i8;2R
cu+= 1 ,>0 ,>0 .
(1.3)
8

Comparând (1.3) cu (1.2), putem observ a faptul c , în acest caz, con v exi-
tatea este mai general  decât liniaritatea: inegalitatea înlo cuie³te egalitatea
care este mai restrictiv  , iar inegalitatea se p streaz  doar p en tru an umite
v alori ale lui  ³i . Astfel, µinând con t de faptul c  orice program liniar
este, de fapt, o problem  de optimizare con v ex , putem v edea optimizarea
con v ex  ca p e o generalizare a program rii liniare.
Optimizarea problemei (1.1) reprezin t  o abstractizare a problemei de alegere
a soluµiei cele mai bune p en tru v ectorul care apartine Rn. V ariabila x re-
prezin t  alegerea f cut , restricµiile fi(x)6bi reprezin t  cerinµele obligatorii
care limiteaz  p osibilele alegeri, iar v aloarea funcµiei obiectiv f0(x) reprezin t 
"costul" alegerii lui x . O soluµie a problemei de optimizare (1.1) corespunde
unei alegeri care are cost minim (sau utilitate maxim ) comparativ cu toate
celelalte v alori care resp ect  cerincµele obligatorii.
Menµionasem mai sus despre imp ortanµa problemelor de optimizare con v ex 
în domeniul Financiar (precum ³i în alte domenii) ³i doresc s  dezv olt puµin
noµiunea de "optimizar e a p ortoiului" . Aici, c ut m cea mai bun  cale de
a in v esti capital în tr-un set de n activ e. V ariabila xi reprezin t  in v estiµia
în activul i , deci v ectorul x2Rndescrie alo carea global  a v alorilor p este
setul de activ e. Restricµiile p ot reprezen ta limite ale bugetului de in v estiµie,
precum ³i o v aloare minim  ³i sucien t  acceptat  sub form  de v enit de p e
urma p ortofoliului. Obiectivul sau costul acestei funcµii p oate  o m surare
a riscului general sau a v ariaµiei câ³tigului sau pierderii rezultate în urma
p ortofoliului. În acest caz, problema de optimizare (1.1) corespunde alo c rii
capitalului în p ortofoliu care minimizeaz  riscul, prin tre toate celelalte p osi-
bile alo c ri care mai îndeplinesc condiµiile stricte.
P en tru ma joritatea aplicaµiilor practice, optimizarea matematic  este folosit 
ca un instrumen t a jut tor în luarea de decizii, proiectarea sistemelor sau
op erarea acestora. A cestea supra v egheaz  pro cesele, v eric  rezultatele ³i
mo dic  problema unde este necesar. A ceast  luare de decizii µine direct con t
de acµiunile sugerate de problema de optimizare, de exemplu prin vinderea
³i cump rarea de activ e p en tru obµinerea p ortofoliului optim.
9

Optimizare con v ex 
O problem  de optimizare con v ex  are urmatoarea form :
(
minf0
fi6bi;i= 1;:::;m
(1.4)
unde funcµiile f0;:::;fm:Rn!R sun t con v exe, adic  satisfac:
fi(x+y)6fi(x) +fi(y) ,
8x;y2Rn³i8;2R cu+= 1 ,>0 ,>0
Nu exist , în general, o form ul  analitic  p en tru solucµia problemelor de op-
timizare con v ex , dar sun t m ulte meto de ecien te de a le rezolv a. Amin tim
aici "Meto da punctelor in terioare" ³i "Meto da Simplex" care obµin rezultate
foarte bune în practic . V om v edea cum meto da "Punctelor in terioare" p oate
rezolv a problema (1.4) în tr-un n um r de pa³i aat mereu în in terv alul 10-100.
Cu toate acestea, n u putem înc  susµine c  rezolv area general  de probleme
de optimizare con v ex  este o tehnologie bine pus  la punct (precum proble-
mele de programare liniar ). În ultimii ani, cercetarea meto delor punctelor
in terioare p en tru probleme generale de optimizare neliniar  con v ex  este p e
o pan t  ascenden t , dar înc  n u s-a stabilit care meto d  este cea mai bun .
F olosirea optimiz rii con v exe este, cel puµin la niv el conceptual, asem n –
toare cu programarea liniar . Dac  reu³im s  form ul m o problem  ca o
problem  de optimizare con v ex , atunci o putem rezolv a ecien t, la fel ca p e
o problem  liniar . Se p oate spune c hiar c  o problem  practic  este rezol-
v at  în prop orµie ma joritar  în momen tul în care o reducem la o problem 
de optimizare con v ex . Desigur, recunoa³terea unei funcµii con v exe p oate 
dicil , dar, dep ³it  aceast  pro v o care, rezolv area problemei este direct .
10

Programare liniar 
Cele mai cunoscute dou  sub clase ale optimiz rii con v exe sun t "Meto da celor
mai mici p trate" ³i "Programarea Liniar ". În rândurile care urmeaz , v om
amin ti câtev a no ctiuni despre programarea liniar , cea în care atât obiecti-
vul, cât ³i restricµiile sun t liniare:
(
minfTx
aT
ix6bi;i= 1;:::;m
(1.5)
Aici, v ectorii c, a1;:::;am2Rn³i scalariib1;:::;bm2R sun t parametrii pro-
blemei care denesc funcµiile obietiv ³i restricµiile aferen te.
Soluµia programelor liniare n u dispune de o form ul  analitic  simpl , dar
exist  o v arietate semnicativ   de meto de ecien te p en tru rezolv area acestor
programe, incluzând aici Meto da Simplex a lui Dan tzig. De³i n u putem res-
trânge n um rul op eraµiilor necesare rezolv  rii acesor programe la un n um r
exact, putem folosi limite (prin meto da "Punctelor in terioare") care ofer  o
acurateµe impresionan t  asupra n um rului de op eraµii necesar.
Unele aplicaµii ne conduc direct la programe liniare de forma (1.5) – sau la
una din tre n umeroasele forme standard. Altele, în sc him b, n u au o form ul 
standard a program ului liniar, dar p ot  transformate în tr-un program liniar
ec hiv alen t folosind tehnici p e care le v om discuta mai am n unµit în capitolele
care urmeaz .
Amin tim aici un exemplu practic, din viaµa de zi cu zi ³i un exemplu consa-
crat, "Problema apro xim rii a lui Cheb yshev".
Problema dietei
O diet  s n toas  conµine m n utrienµi diferiµi în can tit µi cel puµin egale cu
b1 , …,bm . Putem compune aceast  diet  alegând can tit µile non-negativ e x1 ,
…,xn cu n mânc ruri diferite. O unitate din can titatea de mâncare j conµine
o can titate aij de n utrienµi i ³i are un cost ck . V rem s  determin m cel mai
mic cost p en tru dieta care satisface cerinµele n utriµionale. Problema p oate 
form ulat  ca un PL de forma:
11

8
><
>:mincTx
Ax<b
x<0:
Multe alte v ariaµii ale acestei probleme p ot  form ulate sub form  de PL. De
exemplu, dac  vrem ca o can titate exact  de n utrienµi s  fac  parte din dieta
noastr  (care pro duce o restricµie liniar  de egalitate), sau putem impune o
limit  sup erioar  a can tit µii de n utrienµi, în plus faµ  de limita inferioar  de
mai sus.
Problema apro xim rii a lui Cheb yshev
minmaxi=1;:::;kjaT
ixbij
(1.6)
Aici, x2Rneste v ariabila, iar a1;:::;ak2Rn,b1;:::;bk2R sun t parametrii
care sp ecic  instanµa problemei. Obiectivul este s  m sur m dimensiunea
termeniloraT
ixbi , iar p en tru acest lucru, folosim maxim ul v alorilor absolute.
Observ  m un lucru imp ortan t, an ume faptul c  funcµia obiectiv din problema
apro xim rii lui Cheb yshev n u este diferenµiabil . Astfel, problema p oate 
rezolv at  prin rezolv area urm torului program liniar:
8
><
>:mint
aT
ixt6bi;i= 1;:::;k
aT
ixt6bi;i= 1;:::;k
(1.7)
cu v ariabilele x2Rn³i t2R .
•inând con t de faptul c  programele liniare sun t rezolv ate de-a gata, pro-
blema apro xim rii lui Cheb yshev este ³i ea rezolv at .
12

Elemente de optimizare convex 
F uncµii con v exe
Mai jos, v om considera V spaµiu v ectorial 2R ,AV o subm ulµime di-
ferit  de zero ³i funcµii denite p e m ulµimea A cu v alori în R , unde R=
R[f1;+1g .
Deniµie:
FieAV o subm ulµime nevid , con v ex  ³i F:A!R . F uncµia F se n u-
me³te con v ex  dac  p en tru ecare u, v 2 A ³i ecare 2(0;1) are lo c:
F(u+ (1)v)6F(u) + (1)F(v) ,
(1.8)
atunci când expresia din mem brul drept este denit . F se n ume³te conca v  
dac  – F este con v ex .
Observaµie:
Relaµia (1.8) n u are expresia din mem brul drept denit  atunci când F (u) =
– F (v) =1 .
T e or ema 1 privind c ar acterizar e a unei funcµii c onvexe:
Fie A V o subm ulµime nevid , con v ex  ³i F : A!R . F uncµia F este
con v ex  dac  ³i n umai dac  oricare ar  n n um r natural, oricare ar 
u1;:::;un2A ³i oricare ar  1;:::;n2R+ astfel încâtPn
i=1i= 1 are
lo c:
F (Pn
i=1iui)6Pn
i=1i F(ui) ,
(1.9)
atunci când expresia din mem brul drept este denit . Dac  F : V!R este
o funcµie con v ex , atunci p en tru ecare a2R m ulµimilefuj F(u)6ag ³i
fuj F(u)<ag sun t m ulµimi con v exe.
13

Observaµie:
Consider m funcµia F :R!R , denit  prin F (u) =3pu . P en tru ecare a
2R , m ulµimilefu2Rj F(u)6ag ³ifu2Rj F(u)< ag sun t con v exe, dar
funcµia F n u este con v ex . A³adar, recipro ca armaµiei an terioare n u este
adev  rat .
Deniµie:
P en tru orice funcµie F : V!R , m ulµimea
dom F =fu2Vj F(u)<+1g
(2.0)
se n ume³te domeniul efectiv al lui F . Domeniul efectiv al unei funcµii con v exe
F : V!R este o m ulµime con v ex .
Considerând o funcµie F : A!R , unde A V este nevid , îi putem aso cia
funcµia F : V!R , denit  prin:
F (u) =(
F(u); dac  u2A
F(u); dac  u=2A
(2.1)
Pr op oziµie:
F uncµia F : V!R este con v ex  dac  ³i n umai dac  A  V este m ulµime
con v ex  ³i F : A!R este funcµie con v ex .
Demonstr aµie.
Fie u, v2 A ³i2(0;1) . F ind con v ex  rezult  c  F(u+(1)v)6 F (u)
+(1) F (v) = F (u) + (1) F (v). Dac u +(1)v =2A rezult  c 
F(u+(1)v) = +1 ceea ce con trazice relaµia an terioar . T rebuie a³adar
ca p en tru ecare u, v 2 A ³i ecare 2(0;1) s  aib  lo c u+ (1)v2A ,
ceea ce înseamn  c  A este m ulµime con v ex .
14

P en tru u, v2A ³2(0;1) rezult  c  u+ (1)v2A ³i are lo c
relaµia F(u+ (1)v) = F(u+ (1)v)6 F (u)+(1) F (v) =
 F (u)+(1) F (v), ceea ce înseamn  c  F este funµie con v ex .
Fie u, v2 V ³i2(0;1) . Dac  u ³i v2 A, atunciu+ (1)v2A ³i
are lo c F (u+ (1)v) =F(u+ (1)v)6F(u) + (1)F(v) =
 F (u)+(1) F (v). Dac  cel puµin un ul din tre punctele u ³i v n u aparµine
lui A, atunci  F (u)+(1) F (v) = +1 ³i are lo c relaµia F(u+ (1)v)6
 F (u)+(1) F (v) ceea ce ne asigur  c  F este funcµie con v ex .
P e baza prop oziµiei an terioare putem considera func{tiile con v exe denite p e
tot spaµiul V.
Deniµie:
Numim funcµie indicatoare a m ulµimii AV funcµiaA:V!R denit 
prin:
A(u) =(
0; dac  u2A
+1; dac  u=2A
(2.2)
Pr op oziµie:
Mulµimea A este con v ex  dac  ³i n umai dac  A este o funcµie con v ex .
Demonstr aµie.
P e baza relaµiei (1.8) v a trebui s  ar t m c  oricare ar  u, v 2 V ³i oricare
ar 2(0;1) are lo c:A(u+ (1)v)6A(u) + (1)A(v) . Dac 
u2A ³iv2A atunciu+ (1)v2A ³iA(u+ (1)v) = 0 . Datorit 
faptului c  A(u) = 0 ³iA(v) = 0 , relaµia are lo c. Dac  cel puµin un ul din-
tre punctele u ³i v n u aparµine lui A, atunci A(u) + (1)A(v) = +1 ,
iar relaµia are lo c ³i în acest caz, ceea ce ne asigur  c  A este funcµie con v ex .
15

Fie u, v2 A ³i2(0;1) . Din faptul c  A este funcµie con v ex  rezult 
c A(u+ (1)v6A(v) = 0 ceea ce implic  c  A(u+ (1)v) = 0 ,
ec hiv alen t cu u+(1)v2A . A³adar m ulµimea A este o m ulµime con v ex .
P e baza prop oziµiei an terioare, studiul m ulµimilor con v exe se reduce la stu-
diul funcµiilor con v exe. Analiz m în con tin uare funcµiile con v exe care p ot lua
v aloarea1 .
Pr op oziµie:
Fie F : V!R o funcµie con v ex . Dac  exist  u 2V astfel încât F (u)
=1 , atunci p e orice semidreapt  din V care pleac  din u funcµia F este
iden tic  +1 sau exist  un punct v p e acea semidreapt  astfel încât în tre u
³i v funcµia F s  ia v aloarea1 , iar de la v încolo s  ia v aloarea +1 .
Demonstr aµie.
Consider m o semidreapt  oarecare din V care pleac  din u ³i presupunem
c  exist  p e aceast  semidreapt  un punct v astfel încât F (v) >1 . Ale-
gem un punct arbitrar w 2 [u, v],w6=u ³iw6=v . Exist  atunci 2(0;1)
astfel încât w = (1)u+v . P e baza relaµiei (1.8) obµinem c  F (w) =
F(v+ (1)u)6 F (v)+(1) F (u) =1 , ceea ce implic  c  F (w) =
1 .
Alegem un punct arbitrar w' p e semidreapta care pleac  din u ³i trece prin
v astfel încât w' =2 [u, v]. Presupunem c  F (w') < +1 . Rezult  în acest caz
c  v2 [u, w'] ³i exist , a³adar, 2(0;1) astfel încât v = (1)u+w0. P e
baza relaµiei (1.8) are lo c F (v) = F (w0+ (1)u)6 F (w') + (1) F (u)
=1 . Punctul v a fost ales astfel încât F (v) >1 , ceea ce ne conduce
la o con tradicµie. P en tru ecare punct w' ales în mo dul de mai sus are lo c
F (w') =1 .
16

Deniµie:
Despre o funcµie con v ex  F : V!R spunem c  este proprie dac  n u ia în
niciun punct v aloarea 1 ³i n u este iden tic  +1 .
Deniµie:
Numim epigraf al unei funcµii F : V!R m ulµimea:
epi F =f(u;a)2VXRj F (u)6ag
(2.3)
Observaµie:
Epigraful reprezin t  m ulµimea punctelor din V X R situate deasupra gra-
cului lui F . Proiecµia m ulµimii epi F p e V este dom F . Imp ortanµa epigrafului
în studiul funcµiilor con v exe este dat  de urm torul rezultat.
T e or ema 2
F uncµia F : V!R este con v ex  dac  ³i n umai dac  epi F este o m ulµime
con v ex .
Demonstr aµie.
Fie (u, a) ³i (v, b) dou  puncte arbitrare din epi F ³i arbitrar din (0, 1).
Se obµine atunci F(u+ (1)v)6 F (u) + (1) F (v)6a+ (1)b
ceea ce implic  faptul c  (u+ (1)v ,a+ (1)b)2epi F ec hiv alen t cu
(u;a) + (1)(v;b)2epi F . A³adar, epi F este m ulµime con v ex .
Consider m u ³i v arbitrare din V ³i 2(0;1) .
17

Probleme de optimizare con v ex 
Probleme de optimizare
F olosim urmatoarea notaµie p en tru a descrie problema g sirii lui x care mi-
nimizeaz f0x din tre toµi x -ii care satisfac condiµiile: fi(x)60 ,i= 1;:::;m
³ihi(x) = 0 ,i= 1;:::;p :
8
><
>:minf0(x)
fi(x)60;i= 1;:::;m
hi(x) = 0;i= 1;:::;p:
(1.8)
Spunem despre x2Rnc  este variabila de optimizar e ³i despre funcµia f0 :
Rn!R c  este funcµia obiectiv. Inegalit µile fi(x)60 se n umesc condiµii
de inegalitate, iar funcµiile coresp onden te fi :Rn!R se n umesc funcµiile
condiµiilor de inegalitate. Ecuaµiile hi(x) = 0 se n umesc condiµii de egalitate,
iar funcµiile hi :Rn!R sun t funcµiile condiµiilor de egalitate. Dac  n u
exist  condiµii ( i.e. , m = p = 0) spunem despre ea c  este f r  restricµii.
Mulµimea punctelor p en tru care atât obiectivul, cât ³i toate restricµiile func-
µiilor sun t denite,
D=Tm
i=0 domfi\Tp
i=1 domhi ,
se n ume³te domeniul problemei de optimizare (1.8). Un punct x2 D este fe-
zabil dac  satisface condiµiile fi(x)60 ,i= 1;:::;m ³ihi(x) = 0 ,i= 1;:::;p .
Problema (1.8) este fezabil  dac  exist  cel puµin un punct fezabil, ³i nefe-
zabil  dac  n u exist  niciun punct fezabil. Mulµimea punctelor fezabile se
n ume³te set fezabil.
Punctul optim pal problemei (1.8) se dene³te astfel:
p= infff0(x)jfi(x)60;i= 1;:::;m;h i(x) = 0;i= 1;:::;pg .
Fiep=1 . Dac  problema este nefezabil , a v em p=1 , iar dac  a v em
punctele fezabile xk cuf0(xk)!1 cu k!1 , atuncip=1 ³i spunem
despre problema (1.8) c  este f r  limit  inferioar .
18

Puncte de optim ³i de optim lo cal în problemele de optimizare
Spunem despre xc  este un punct optim (sau c  este soluµie p en tru pro-
blema (1.8)), dac  xeste fezabil ³i f0(x) =p. T otalitatea punctelor optime
se n ume³te "m ulµime optim ", descris dup  cum urmeaz :
Xopt=fxjfi(x)60;i= 1;:::;m;h i(x) = 0;i= 1;:::;p;f 0(x) =pg .
Dac  exist  un punct optim p en tru problema (1.8), spunem ca v aloarea op-
tim  a fost atins , iar problema este rezolv abil . Dac  Xopt n u conµine niciun
elemen t, spunem c  v aloarea optim  n u a fost atins  (acest lucru este mereu
v alabil când problema este f r  limit  inferioar ). Spunem despre un punct
fezabil x c  este optim lo cal dac  exist  un R > 0 astfel încât:
f(x) =infff0(z)jfi(z)60;i= 1;:::;m;h i(z) = 0;i= 1;:::;p;kzxk26Rg ,
sau, în alte cuvin te, x rezolv   problema de optimizare:
8
>>><
>>>:minf0(z)
fi(z)60;i= 1;:::;m
hi(z) = 0;i= 1;:::;p
kzxk26R
cu v ariabila z . T ermen ul de "optim global" este uneori folosit p en tru a înlo-
cui "optim" ³i a putea face diferenµa în tre "optim lo cal" ³i "optim".
Dac  x este fezabil ³i fi(x)<0 , spunem c  restricµia inegalit µii cu n um rul
"i"fi(x)60 este activ   în x . Dac fi(x)<0 , spunem c  restricµia fi(x)60
este inactiv  . (În cazul restricµiilor de egalitate, toate punctele fezabile sun t
activ e).
Exemple:
f0=1
x:p= 0 , dar v aloarea optim  n u este atins ;
f0(x) =log x:p=1 unde problema are optim innit;
f0(x) = xlog x:p=1=e este atins în punctul optim (³i unic) x= 1=e ,
19

unde problemele de optimizare f r  restricµii de mai sus au v ariabila x2R
³i domf0=R++ .
Probleme de optimizare con v ex  în forma standard
O problem  de optimizare con v ex  are urm toarea form :
8
><
>:minf0(x)
fi(x)60;i= 1;:::;m
aT
ix=bi;i= 1;:::;p
(1.9)
undef0;:::;fm sun t funcµii con v exe. Comparând (1.9) cu forma standard a
problemelor de optimizare (1.8), cea con v ex  are trei cerinµe necesare în plus:
 F uncµia obiectiv trebuie s  e con v ex ;
 F uncµiile restricµiilor de inegalitate trebuie s  e con v exe;
 F uncµiile restricµiilor de egalitate hi(x) =aT
ixbi trebuie s  e ane.
Pr oprietate a 1:
Setul de puncte fezabile a unei probleme de optimizare con v ex  este con v ex,
deoarece se a  la in tersecµia domeniului problemei:
D=Tm
i=0 domfi ,
care este un set con v ex, cu m ulµimea m (con v ex ) de subniv ele fxjfi(x)60g
³i p hip erplanefxjaT
ix=big .
Observaµie!
Putem presupune c  ai6= 0 : dac ai= 0 ³ibi= 0 p en tru an umiµi "i", atunci
cea de-a "i" restricµie de egalitate p oate  ³tears . Dac  ai= 0 ³ibi6= 0 ,
cea de-a "i" restricµie de egalitate n u este consisten t , iar problema este ne-
fezabil . Deci, în tr-o problem  de optimizare con v ex , minimiz m funcµia
obiectiv con v ex  p este o m ulµime con v ex .
20

Puncte de optim lo cal ³i global în probleme de optimizare con v ex 
O proprietate fundamen tal  a problemelor de optimizare con v ex  este c 
orice punct de optim lo cal este ³i punct de optim global. P en tru a putea
v edea acest lucru, s  presupunem ca x este punct de optim lo cal p en tru pro-
blema de optimizare con v ex , adic  x e fezabil ³i
f0(x) =infff0(z)j z fezabil;kzxk26Rg ,
(2.0)
p en tru un R > 0. S  presupunem acum c
ua x nu este punct de optim global, adic  exist  un y fezabil astfel încât
f0(y)<f 0(x) . Eviden tkyxk2>R , deoarece, în caz con trar, f0(x)6f0(y) .
Fie z denit de urm toarea ecuaµie:
z= (1)x+y; =R
2kyxk2.
Ap oi a v emkzxk2=R
2< R , ³i, datorit  con v exit µii m ulµimii fezabile, z
este fezabil. Din con v exitatea lui f0 a v em:
f0(z)6(1)f0(x) +f0(y)<f 0(x) ,
care con trazice (2.0). Prin urmare n u exist  y fezabil cuf0(y)<f 0(x) , adic 
x este punct de optim global.
21

Problema primal  ³i dual  de optimizare con v ex 
22

Aplicaµii – estim ri statistice
Estimarea distribuµiei parametrice
23

Estimarea distribuµiei non-parametrice
24

Limite Cheb yshev ³i Chemo
25

Bibliograe
26

Postfaµ 
BUCURE“TI,
Septem brie 2020
27