Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AstronomieBiofizicaBiologieBotanicaCartiChimieCopii
Educatie civicaFabule ghicitoriFizicaGramaticaJocLiteratura romanaLogica
MatematicaPoeziiPsihologie psihiatrieSociologie


PROBLEMA COMPLEMENTARITATII

Matematica

+ Font mai mare | - Font mai mic




CUPRINS



CAP.1.PROBLEMA COMPLEMENTARITATII

1.1.Introducere 4

1.2.Importanta problemei complementaritatii si rolul

calculatorului in rezolvarea ei 7

1.3.Notatii 10

1.4.Conurile complementare 12

1.5.Problema complementaritatii liniare 14

1.6.Aplicatii 15

1.6.1.Programarea liniara 15

1.6.2.Programarea patratica 17

1.6.3.Jocuri de doua persoane 18

1.6.4.Alte aplicatii 19

1.7.Clase de matrici 20

1.8.Algoritmi pentru rezolvarea problemei

complementaritatii liniare 21

1.8.1.Bazele 22

1.8.2.Operatii pivot 24

1.8.3.Baza initiala 26

1.8.4.Proprietatile bazele 27

1.8.5.Bazele complementare admisibile aproape

adiacente 28

1.8.6.Regula pivotului complementar 28

1.8.7.Incheierea 29

1.9.Exemple numerice 30

1.10.Conditii 35

1.11.Alti algoritmi 35

1.12.Rezumat al rezultatelor teoretice 36

1.13.Probleme nerezolvabile 36

1.14.Problema complementaritatii neliniare 37

1.15.Metode de calcul a punctelor fixe 38

CAP.2.PROBLEMA COMPLEMENTARITATII IN

PROGRAMAREA PATRATICA

2.1.Restrictii ecuatii 41

2.2.Metoda multiplicatorilor Lagrange 53

2.3.Metoda multimii active 58

2.4.Proprietati avansate 65

2.5.Probleme speciale de programare patratica 68

2.6.Pivotarea complementara si alte metode 72

2.7.Exercitii 81

BIBLIOGRAFIE   

Capitolul 1

Problema complementaritatii

1.1.Introducere

Fie Rn un spatiu vectorial euclidian de dimensiune n.Fie M o matrice patratica de rang n si q un vector coloana in Rn.Se considera problema:sa se gaseasca w1,..,wn,z1,…,zn cu proprietatille:

w-Mz=q, w 0, z 0 si wizi=0 pentru toti i

Ca un exemplu concret,fie

2 1 -5

n=2 M= q=

1 2 -6

Pentru acest caz,problema asociata ce trebuie rezolvata este:

w1 -2z1-z2 = -5

w2-z1-2z2= -6 (1.1)

cu variabilele w1,w2,z1,z2 0 si w1z1=w2z2=0

Probleme de acest fel,cunoscute sub denumirea de problemele complementaritatii liniare (P.C.L.) ,se pot intalni in programarea liniara,programarea patratica,in teoria jocurilor si in numeroase alte domenii.Problema (1.1) poate fi scrisa si sub forma de ecuatie vectoriala:

1 0 -2 -1 -5

w1 +w2 +z1 +z2 = (1.2)

2 1 -1 -2 -6

w1,w2,z1,z2 0 si w1z1=w2z2=0    (1.3)

Pentru orice solutie care satisface (1.3),cel putin una dintre variabilele din perechea (w1,z1) trebuie sa fie egala cu zero,deoarece w1z1=0.Analog si pentru perechea (w2,z2).O metoda de rezolvare pentru aceasta problema este:se alege cate o variabila din fiecare pereche (w1,z1),(w2,z2) si se egaleaza aceste variabile cu valoarea zero in sistemul de ecuatii (1.2).Variabilele ramase in sistem se numesc variabile active.Dupa eliminarea variabilelor nule din (1.2),daca sistemul obtinut are o solutie in care varibilele active sunt nenegative,aceasta va fi solutie pentru (1.2),(1.3).

Fig.1. Pos ,

-1 -2

Notam cu (q1,q2) vectorul constant (-5,-6) din (1.2).Alegem w1,w2 ca variabile cu valoare zero.Rezulta ca variabilele active sunt z1,z2.Dupa

inlocuirea w1,w2=0 in (1.2),sistemul obtinut este:

-2 -1 -5 q1

z1 +z2 = = =q (1.4)

-1 -2 -6 q2

z1 0 , z2

Sistemul redus (1.4) are o solutie daca si numai daca vectorul q poate fi

-2 -1

exprimat ca o combinatie liniara nenegativa de vectorii si

-1 -2

-2 -1

Multimea tuturor combinatiilor lineare nenegative de vectori si

-1 -2

reprezinta un con in spatiul de coordonate q1 si q2 ,ca in Fig1.Daca vectorul

-5

dat q= se afla in acest con. Atunci P.C.L.(1.1) are o solutie in care

variabilele active sunt z1 , z2 si w1=w2=0.

Verificam daca punctul (-5,-6) se afla in acest con si daca solutia pentru (1.4) este (z1 , z2 )=(4/3,7/3) si rezulta ca solutia pentru (1.1) este

(w1,w2 , z1 , z2 )=( 0,0,4/3,7/3).

Conul din Fig.1 se numeste conul complementar asociat P.C.L (1.1).Conurile complementare sunt generalizari ale claselor de sferturi de cerc sau ale claselor de ortanti.

P.C.L. (1.1) este de ordin 2.Intr-o P.C.L. de ordin n vor fi 2n variabile.Problemele de ordin 2 pot fi rezolvate prin trasarea tuturor conurilor complementare si verificarea daca vectorul q se afla in aceste conuri.Pentru rezolvarea problemelor de ordin mai mare avem nevoie de algoritmi eficienti si calculatoare care pot obtine solutii folosind acesti algoritmi.

1.2.Importanta problemei complementaritatii si

rolul calculatorului in rezolvarea ei

Exemplu:

Fie K suprafata poliedrala convexa hasurata ca in Fig.2.Fie P puctul de coordonate (-2,-1).Se cere sa se gaseasca punctul K cel mai apropiat de P (se considera dinstanta euclidiana ).Probleme de acest fel apar foarte des in inginerie si in aplicatiile cercetarii operationale.

Fiecare punct din K poate fi exprimat co o combinatie convexa de puncte de extrem (sau puncte unghiulare) A,B,C,D, i.e.,coordonatele puctelor generale din K sunt (l l l l l l l l ) unde li satisfac l l l l =1 si li 0 pentru toti i.Astfel problema gasirii punctului din K cel mai apropiat de P este echivalenta cu rezolvarea problemei:

inf

l poate fi eliminat din aceasta problema prin inlocuirea lui cu expresia l l l l Prin simplificare, se obtine problema patratica:

inf (-66,-54,-20)l lT l

4 16 8

pentru -l l l -1 si l

unde l

.Se va arata in sectiunea 1.61. Programarea patratica ca rezolvarea acestui program este echivalenta cu rezolvarea unei P.C.L..

u1 34 16 4 1 l

u2 - 16 34 16 1 l = -54

u3 4 16 8 1

v1 -1 –1 -1 0 Y1 1

toate variabilele

u1,u2,u3,v1,l l l ,y1

si

u1l =u2l =u3l =v1y1=0

Daca ( u1, u2, u3, v1, l l l y1) este o solutie a acestei P.C.L.,fie l l l l si x=( l l l l l l l ) este punctul din K cel mai apropiat de P.

In sectiunea 1.6. Aplicatii se arata ca toate problemele de programare liniara si problemele de programare patratica convexa pot fi transformate in P.C.L. .Astfel de P.C.L. pot fi rezolvate prin algoritmul pivot complementar tratat in sectiunea 1.8 .Algoritmi pentru rezolvare P.C.L.

Fif.2. Problema distantei minime.

Totusi , majoritatea aplicatiilor practice ale P.C.L. conduc la probleme de ordin mare . Este practic imposibil de rezolvat manual asemenea probleme de ordin mare si devine esentiala folosirea calculatorului . De asemenea, este importanta dezvoltarea algoritmilor pentru rezolvarea P.C.L.,ceea ce conduce la programe mai eficiente pentru calculator.

Programarea liniara detine un vast numar de aplicatii .In prezent, variante ale metodei simplex sunt folosite frecvent pentru solutionarea programelor liniare intalnite in aplicatiile vietii reale .Un studiu experimental a aratat ca algoritmul pivot complementar pentru rezolvarea P.C.L. (vezi sectiunea 1.8.Algoritmi pentru rezolvarea P.C.L.) este net superior metodei simplex pentru rezolvarea programelor liniare .Este posibil ca in viitorul apropiat , programele pentru calculator ce rezolva P.C.L. sa fie deseori folosite pentru rezolvarea problemelor programarii liniare .

In sectiunile 1.6.Aplicatii, 1.8.Algoritmi pentru rezolvarea P.C.L. si 1.10.Conditii se arata ca algoritmul pivot complementar pentru rezolvarea P.C.L. poate fi folosit pentru rezolvarea problemelor liniare ,problemelor patratice convexe si problemelor de jocuri bimatriciale .Astfel P.C.L. asigura o teorie generala pentru studierea tuturor acastor tipuri diferite de probleme .

De asemenea, s-a aratat ca argumentele folosite in algoritmul pivot complementar pentru rezolvarea P.C.L. pot fi generalizate si aceste generalizari au condus la algoritmi care pot calcula aproximativ punctele fixe Brower si Kakutani .Pana acum ,singura si cea mai mare contributie a problemei complementaritatii este probabil intelegerea si dezvoltarea algoritmilor de calcul a punctelor fixe (vezi sectiunea 1.15.Metode de calcul a punctelor fixe).

In matematica ,teoria punctului fix este foarte mult dezvoltata , dar absenta unor algoritmi eficienti pentru calculator ale acestor puncte fixe au impiedicat pana acum toate incercarile de aplicare ale acestei importante teorii in problemele vietii reale .Impreuna cu dezvoltarea acestor noi algoritmi ,teoria punctului fix si-a gasit numeroase aplicatii in programarea matematica ,in economia matematica si in numeroase alte domenii.

1.3.Notatii

Fie D o matrice .Vectorul coloana j al matricei D se noteaza cu D.j.

DT reprezinta transpusa matricei D. I repezinta matricea identica .

Exemplu1:


Fie n=3 ,atunci I= 0 1 0 si I.3 = 0

0 0 1 1

Daca este o multime de vectori coloana din Rn Pos reprezinta multimea tuturor vectorilor din Rn care pot fi exprimati ca o combinatie liniara nenegativa de E.1,…,E.k , i.e. ,

Pos=.


0

Exemplu 2: Pos , este ortant nenegativ din R2 (vezi Fig.3).


2 -2

Exemlu 3:Pos , este conul hasurat din Fig.4.

1 -2

Pentru orice r,er este vectorul coloana din Rr ale carui elemente sunt egale cu 1.

Exemplu 4: e3 =( 1,1,1)T


1 0

Fig. 3.Pos ,

0 1


-2 2

Fig.4.Pos. ,

-2 1

1.4.Conul complementar

Se da M o matrice patratica de ordin n.Pentru a obtine C(M), clasa conurilor complementare corespunzatoare lui M, perechea de vectori coloana (I.j,-M.j) se numeste perechea complementara de vectori j,1≤j≤n.

Se alege un vector din perechea (I.j,-M.j) si se noteaza cu A.j. Multimea ordonata de vectori (A.1,…,A.n) se numeste multimea complementara de vectori.Conul Pos( A.1,…,A.n) se numeste conul complementar din clasa C(M).In total sunt 2n conuri complementare.

Exemplu 5:Fie n=2 si M=I.In acest caz clasa C(I) este chiar clasa ortantilor

din R2 (vezi Fig.5).

In general pentru orice n,C(I) este clasa ortantilor din Rn.Astfel clasa

conurilor complementare este o generalizare a clasei ortantilor.

Exemplul 6: n=2 si M= . Vezi Fig.6.

Exemplu 7: n=2 si M= .Vezi Fig.7.

1 0

Fig.5. Conurile complementare cand M=

0 1

Fig.6. Conurile complementare cand M=

Fig.7. Conurile complementare cand M=

1 -2

1.5.Problema complementaritatii liniare

Fiind date M o matrice patratica de ordin n si vectorul coloana qIRn,P.C.L (q,M) este sa se gaseasca conul complementar in C(M) care sa contina punctul q, adica sa se gaseasca multimea complementara de vectori (A.1,…,A.n) astfel incat :

(i)        A.j I , pentru 1≤j≤ n si

(ii)     q poate fi exprimat ca o combinatie liniara de vectorii (A.1,…,A.n).

Aceasta este echivalenta cu gasirea lui wI Rn,zIRn satisfacand

n n

∑ I.jwj -∑ M.jzj=q

j=1 j=1

wj≥0, zj≥0 ( pentru toti 1≤j≤ n)

si wj=0 sau zj=0 (pentu toti 1≤j≤n)

Cu ajutorul matricelor se mai poate scrie astfel:

w-Mz=q (5.5)

w≥0 z≥0 (5.6)

wjzj=0 (pentru toti j) (5.7)

n

Datorita relatiei (5.6), conditia (5.7) este echivalenta cu wjzj=wTz=0

j=1

si aceasta conditie este cunoscuta sub denumirea de restrictia complementaritatii .Deci P.C.L.(q,M) consta in gasirea lui w IRn,z I Rn ce satisfac (5.5),(5.6),(5.7).

Pentru orice solutie a P.C.L.(q,M) ,daca una dintre variabilele din perechea (wj,zj) este pozitiva , cealalta trebuie sa fie zero.De aceea perechea (wj,zj) se numeste pereche complementara de variabile si fiecare variabila

din aceasta pereche este complementara celeilalte.

Aplicatii

1.6.1. Programarea liniara

Se stie ca orice problema de progamare liniara poate fi scrisa sub forma canonica ( simetrica ).

inf CTx

pentru Ax≥ b (6.8)

x≥0

Presupunem ca A este o matrice de rang m ×N.Daca x este o solutie optima pentru problema (6.8), atunci exista vectorul dual y I Rm si vectorii liberi

u x

vIRm, uI RN astfel incat … si … sa satisfaca:

v y


u 0 -AT x cT

v A 0 y -b (6.9)

u x u T x

… ≥0, … ≥0, si … … =0

v y v y


u x

Si reciproc daca … si …

v y

satisfac toate conditiile din (6.9),atunci x este solutie optima pentru problema (6.8).

Observatie:In (6.9) toti vectorii si matricile sunt scrise sub forma

u    extinsa (separata). De exemplu …

v

este vectorul (u1,…,un,v1,…,vm)T.Daca n= m+N,

u x 0 -AT cT

w = … , z = … , M = …………… , q= …

v y A 0 -b

Problema (6.9) este vazuta ca o P.C.L. .Solutia problemei liniare (6.8) poate fi obtinuta si prin rezolvarea P.C.L. (6.9) .

1.6.2.Programarea patratica

Se considera problema de programare patratica

Inf

pentru Ax≥b (6.10)

x≥0

unde A este o matrice de rang m×N si D este o matrice simetrica patratica . x I Rn reprezinta punctul Karush-Kuhn-Tucker pentru problema (6.10),daca exista vectorul yIRmsi vectorii liberi uIRN, v I Rm astfel incat ( x, y, u, v) sa satisfaca:

u D -AT x cT

v A 0 y -b (6.11)

u x u T x

… ≥0, … ≥0, si … … =0

v y v y

atunci (6.11) este o P.C.L. .Din Teorema Karush-Kuhn-Tucker partea de necesitate daca x reprezinta punctul de minim local pentru (6.10) ,atunci x este punct Karush-Kuhn-Tucker .Daca D este o matrice pozitiv semidefinita, atunci (6.10) se numeste problema de programare patratica convexa,si, in acest caz din Teorema de suficienta Krush-Kuhn-Tucker se deduce ca fiecare punct Krush-Kuhn-Tucker este solutie optima pentru (6.10).Rezolvand P.C.L. (6.11) se obtine punctul Krush-Kuhn-Tucker pentru(6.10) si daca D este matrice pozitiv semidefinita, aceasta reprezinta solutia optima pentru (6.10).

1.6.3.Jocuri de doua persoane

La fiecare joc, jucatorul I alege una dintre cele m optiuni ale sale din multimea posibila si independent,jucatorul II alege una dintre cele N optiuni ale sale din multimea posibila.Intr-un joc, daca se intampla ca jucatorul I sa aleaga optiunea i ,si jucatorul II sa aleaga optiunea j, atunci jucatorul I pierde

suma a'ij$ si jucatorul II pierde suma b'ij$,unde A'=(a'ij) si B=(b'ij) sunt matricile de pierdere date .

Daca a'ij+b'ij=0 pentru toti i si j , jocul se numeste jocul cu suma nula, si in acest caz este posibila dezvoltarea conceptului de strategie optima,

pentru joc folosind Teorema Von Neumann minimax.Jocurile care nu sunt jocuri cu suma nula sunt numite jocuri cu suma nenula sau jocuri bimatriciale.In jocurile bimatriceale este dificil de definit o strategie optima.Totusi,in acest caz strategia perechiide ehilibru se poate defini si problema de calculare a strategiei perechii de echilibru poate fi transformata intr-o P.C.L.

Presupunem ca jucatorul I isi alege optiunea i cu probabilitatea xi.Vectorul coloana x=(xi)I Rm defineste complet strategia jucatorului I .Analog , fie vectorul y=(yi)I RN probabilitatea de strategie a jucatorului II.Daca jucatorul I adopta strategia x , si jucatorul II adopta strategia y , pierderile jucatorului I sunt xT A' y si pierderile jucatorului II sunt xTB'y.

Perechea de strategie ( x, y) reprezinta perechea de echilibru daca un jucator nu beneficiaza de dreptul sau de a-si schimba strategia , in timp ce celalalt jucator isi pastreaza strategia din perechea ( x, y) neschimbata , i.e., daca

xA' y≤xA' y (pentru toti vectorii probabili xIRm)

xB' y≤ xB' y (pentru toti vectorii probabili yIRN)

Fie α, β numere pozitive arbitrare astfel incat ai j =a'i j +α>0 si bi j =b'i j+β>0 pentru toti i,j: Fie A=(ai j), B=(bi j).Se considera P.C.L.


u 0 A ξ -em

v BT 0 -eN (6.12)

u u T

… ≥0, … ≥0, si … … =0

v η v η

vezi partea 1.3.Notatii pentru definirea lui em,eN.S-a aratat ca daca ( u, v, η) este solutie pentru P.C.L.(12), atunci x = ξi) si

y = ηi) reprezinta strategiile perechii de echilibru pentru jocul initial.

1.6.4.Alte aplicatii

P.C.L este folosita pentru studiul problemelor din analiza plastica de structura, din comportarea rezistentei neelastice la incovoiere a grinzilor din beton armat, din suprafata de separatie pentru lagarela de sustinere, pentru studiul modelelelor financiare si numeroase alte domenii.

1.7.Clase de matrici

Vom defini cateva clase de matrici pe care le vom folosi in studiul P.C.L Fie M o matrice patratica de rang n.

M este o matrice pozitiv definita daca:

n n

yTMy =Σ Σ yi mi j yj>0 pentru toti 0≠y Rn

i=1 j=1

2.M este o matrice pozitiv semi-definita daca:

yTMy ≥0 pentru toti y IRn

3. M este o matrice copozitiva daca:

yTMy ≥0 pentru toti y≥0

4.M este o matrice plus copozitiva daca este o matrice copozitiva si daca

yT(M+MT)=0 pentru toti y≥0 cu proprietatea yTMy =0

5. M este o P_ matrice daca toti determinantii principali ai matricei M sunt pozitivi.

6.M este o Q_matrice daca P.C.L. (q,M) are solutie pentru toti q I Rn

1.8.Algoritmi de rezolvare a P.C.L.

P.C.L de ordin 2 pot fi rezolvate prin trasarea (desenarea) tuturor conurilor complementare in planul determinat de q1,q2 asa cum s-a discutat in 1.1.Introducere.

Exemplu 8

Fie q= si M=

1 -2

si se considera P.C.L.(q,M).

Clasa conurilor complementare corespunzatoare acestei probleme este in Fig.7

Tabelul 8.13.

w1

w2

z1

z2



q

w1,w2,z1,z2≥0, w1z1=w2z2=0

q se afla situat in doua conuri complementare Pos(- M.1,I.2) si Pos(-M1,-M.2). Aceasta implica ca multimile variabile active (z1,w2) si (z1,z2) conduc la solutia P.C.L.

Inlocuind w1=z2=0 in (8.13) si rezolvand sistemul ramas pentru valorile variabilelor active (z1,w2) se obtine solutia (z1,w2)=(2,1). Astfel (w1,w2,z1,z2)=(0,1,2,0) este solutia P.C.L considerate. Analog , inlocuid w1=w2=0 in (8.13) si rezolvand sistemul pentru valorile variabilelor active (z1,z2) se obtine o a doua solutie (w1,w2,z1,z2)=(0,0, 7/3,2/3 ) pentru P.C.L. considerata.

Exemplu 9 :

Fie q= si M=

1 -2

si se considera P.C.L.(q,M).Clasa conurilor complementare corespunzatoare acestei probleme este trasata in Fig.7.Se verifica ca q nu se afla in nici un con complementar.Rezulta ca aceasta P.C.L. nu are solutie.

S-a discutat in 1.1.Introducere ca metoda de mai sus poate fi aplicata doar pentru P.C.L. de rang 2.Pentru rezolvarea P.C.L. de ordin mai mare,vom descrie algoritmul pivot complementar care foloseste operatii liniare pentru sistemul de ecuatii (5.5).

Pentru P.C.L. (5.5),(5.6),(5.7) daca q≥0,atunci w=q,z=0 este o solutie si problema este rezolvata.Deci presupunem ca q<0.

1.8.1.Bazele

Variabila artificiala z0,asociata vectorului coloana -en (vezi sectiunea 1.3.Notatii),este introdusa in sistemul (5.5) pentru a obtine o baza admisibila.Folosind forma tabelara,sistemul (5.5) devine:

Tabelul 8.14.

w

z

z0

I

-M

-en

q

w≥0 z≥0 z0≥0

In fiecare etapa a algoritmului folosim o baza care oste o submatrice patratica nesingulara de ordin n a matricei coeficient din (8.14).Vectorii coloana din baza sunt numiti vectori coloana de baza si variabilele din (8.14) asociate vectorilor sunt numite variabile de baza.Vectorii coloana ramasi in tabel se numesc vectori coloana secundari(nebazici) si variabiabilele asociate lor sunt variabile secundare.

Solutia pentru (8.14) corespunzatoare unei baze date se obtine prin egalarea tuturor variabilelor secundare cu zero si rezolvarea sistemului de ecuatii liniare ramas din (8.14) cu valorile variabilelor de baza.Baza este o baza admisibila daca valorile tuturor variabilelor de baza din solutie sunt nenegative.Algoritmul foloseste doar baze admisibile.

Cand baza este transformata in matricea identica (prin aplicarea operatiilor necesare sau prin inmultirea la dreapta a intregului tabel din (8.14) cu inversa bazei), (8.14) este transformat in tabelul canonic asociat bazei.Variabilele de baza asociate lui I.r din tabelul canonic sunt numite r_variabile de baza, sau variabile de baza din linia r a tabelului canonic.

Toti vectorii coloana din tabelul canonic sunt numiti vectori coloana actuali.Fie q vectorul actual constant din dreapta.Atunci q este vectorul valorilor variabilelor de baza pentru solutia corespunzatoare acestei baze, q≥0 daca baza reprezinta o baza admisibila.

1.8.2.Operatii pivot

Prima etapa folosita in algoritm este etapa pivot care reprezinta si etapa principala a algoritmului simplex folosit pentru rezolvarea problemelor liniare.

La fiecare etapa a algoritmului ,baza se schimba prin introducerea in baza a unui vector coloana secundar.Variabilele din (8.14) asociate acestui vector se numesc variabile de intrare.Vectorul lor coloana actual se numeste coloana pivot pentru aceasta schimbare a bazei.

In solutia pentru (8.14),asociata la noua baza,toate variabilele secundare,diferite de variabilele de intrare,vor fi egalate cu zero.

Deoarece baza pentru (8.14) este formata din n vectori coloana,atunci cand o noua coloana este introdusa in baza,unul dintre vectorii coloana prezent in baza va trebui eliminat.Eliminarea vectorului trebuie facuta dupa o anumita regula numita:testul raportului minim(criteriul de iesire din baza) in terminologia programarii liniare.Acest criteriu garanteaza ca noua baza obtinuta dupa etapa pivotului este admisibila.

Vom analiza pe scurt acest criteriu de iesire din baza. Singurele variabile ale caror valori din solutie se schimba la aceasta etapa sunt variabilele de intrare si variabilele de baza actuale.Presupunem ca valoarea variabilei de intrare este schimbata de la valoarea actuala 0 la o valoare oarecare nenegativa, .Valorile variabilelor de baza se determina in functie de astfel incat noua solutie sa satisfaca conditiile egalitatii din (8.14).

Spre exemplu sa presupunem ca variabilele de baza actuale sunt

y1,y2 ,…,yn cu yr variabilele de baza ale liniei r si fie xs variabilele de intrare.[Variabilele din (14) sunt w1,w2,…,wn;z1,z2,…,zn;z0.Exact n dintre aceste variabile sunt variabile de baza actuale.Pentru usurinta, presupunem ca aceste variabile de baza sunt notate cu y1,y2 ,…,yn ].Dupa rearanjarea variabilelor din (8.14),daca este necesar,forma canonica (8.14) a bazei prezente este de forma:

Tabelul Variabile

de baza

y1    … yi … yn xs Alte

variabile

Vectorul constant din dreapta

y1

yn

… 0 a1s

.

ans

q1

qn

Deoarece toate variabilele secundare ,altele decat xs,vor fi egalate cu zero,noua solutie este:

xs

y1 = q1 - a1sλ (8.15)

yi = qi - aisλ

yn = qn - ansλ

toate celelalte variabile=0

Exista doua posibilitati:

1.Coloana pivot poate fi nepozitiva,i.e., a is≤0 pentru toti 1≤i≤ n .In acest caz solutia pentru (8.15) ramane nenegativa pentru toti λ≥0.Cum λ ia valori de la 0 la ∞ ,aceasta solutie traseaza o semidreapta nemerginita(sau o frontiera nelimitata) a multimii bazelor admisibile pentru (8.14).Daca se intampla acest lucru,algoritmul se incheie.

2.Exista cel putin o intrare pozitiva in coloana pivot.In acest caz,daca solutia (8.15) ramane nenegativa,valoarea maxima pe care o poate lua λ este θ=min( qi / ais : I astfel incat ais >0).

Acest θ este numit raportul minim in aceasta etapa pivot.Daca θ= qr / ars atunci yr devine egal cu zero in solutia pentru (8.15) cand xs=θ.Astfel yr este eliminat din vectorul de baza si xs devine variabila de baza r in locul lui.Linia r este numita linia pivot pentru aceasta etapa pivot.

Pivotarea consta in transformarea coloanei pivot in I.r prin operatii liniare.Aceasta conduce la tabelul canonic asociat noii baze si la terminarea etapei.

Deoarece ia valori de la 0 la in (8.15),schimbam solutia de la aceasta etapa la solutia din (8.14) asociata noii baze.Aceste doua solutii sunt puncte extreme adiacente ale multimii de solutii admisibile pentru (8.14) si segmentul de linie care le uneste este o margine.

1.8.3.Baza initiala

Variabila artificiala z0 a fost introdusa in (8.14) pentru a obtine o baza admisibila pentru inceperea algoritmului.

Identificam linia t astfel incat qt=min(qi : 1≤i≤n).Deoarece am presupus q<0,atunci qt<0.Atunci cand un pivot este format in (8.14) cu vectorul coloana z0 ca si coloana pivot si linia r ca linia pivot,vectorul constant din dreapta devine un vector nenegativ.Tabelul rezultat este tabelul canonic asociat bazei in care variabilele de baza sunt w1,…,wt-1,z0,wt+1,…,wn.Aceasta este baza initiala pentru inceperea algoritmului.

1.8.3. Proprietatile bazelor

Baza initiala satisface urmatoarele proprietati:

1.Exista cel putin o variabila de baza din fiecare pereche complementara de variabile (wj,zj ).

2.z0 este variabila de baza in ea.Contine exact o variabila de baza din fiecare (n-1) perechi complementare de variabile si ambele variabile din perechea complementara ramasa sunt secundare.

O baza admisibila pentru (8.14) care contine exact o variabila de baza din fiecare pereche complementara(wj,zj) se numeste baza complementara admisibila.Solutia admisibila pentru (8.14) corespunzatoare bazei admisibile complementare este o solutie pentru P.C.L.

O baza admisibila pentru (8.14) care satisface cele doua proprietati de mai sus se numeste baza complementara admisibila apropiata.Toate bazele obtinute in algoritm ,cu posibila exceptie a bazei finale,sunt baze complementare admisibile apropiate.Daca la o anumita etapa a algoritmului se obtine o baza complementara admisibila, atunci ea reprezinta baza finala si algoritmul se incheie.

1.8.5.Bazele complementare admisibile aproape adiacente

Fie (y1,…,yj-1,z0,yj+1,…,yn) un vector de variabile de baza complementara admisibila apropiata pentru (8.14),unde yiI pentru fiecare i≠j.In aceasta baza ambele variabile din perechea complementara sunt variabile secundare. Bazele complementare admisibile apropiate adiacente pot fi obtinute doar prin alegerea ,ca variabile de intrare, ori alui wj,ori a lui zj .Astfel ,pentru fiecare baza complementara admisibila apropiata sunt exact doua posibilitati pentru obtinerea bazelor complementare admisibile apropiate adiacente.

Initial,in baza complementara admisibila apropiata,atat wt cat si zt sunt variabile secundare.In tabelul canonic asociat bazei initiale ,vectorul coloana actual wt poate fi verificat ca fiind -en ,care este <0.Deci baza complementara admisibila apropiata initiala este in final o semidreapta complementara apropiata.

Deci ,este o unica metoda de obtinere a unei baze complementara admisibila apropiata adiacenta:prin alegerea lui zt ca variabila de intrare.

1.8.6.Regula pivotului complementar

Pentru toate etapele ulterioare este un singur mod de a continua algoritmul si anume:se alege ca variabila de intrare, complementara variabilei care tocmai a iesit din baza.Aceasta se numeste regula pivotului complementar.

Principala proprietate a drumului generat de algoritm este urmatoarea:fiecare solutie de baza admisibila obtinuta in algoritm contine doua margini complementare apropiate.Am ajuns la aceasta solutie urmand o astfel de margine si plecam prin cealalta margine.Astfel, algoritmul continua intr-o maniera unica.

1.8.7.Incheierea

Sunt exact doua moduri de terminare a algoritmului:

1.La o anumita etapa a algoritmului,z0 poate parasi vectorul de baza si astfel se obtine o baza admisibila complementara.Solutia pentru (8.14) corespunzatoare acestei baze finale este o solutie pentru P.C.L. (5.5),(5.6),(5.7).

2.La o anumita etapa a algoritmului ,coloana pivot poate fi nepozitiva (problema discutata la partea 1.8.2.Operatiile pivot) si in acest caz algoritmul se termina cu o raza(semidreapta).

Aceasta se numeste terminatie raza.Cand acest lucru se intampla,algoritmul nu poate rezolva P.C.L.

Exemple numerice

Exemplu 10:

Se considera urmatoarea P.C.L.:

w1

w2

w3

w4

z1

z2

Z3

z4

q

wi≥0 , zi≥ 0 , wi zi =0 pentru toti I

Introducem variabila artificiala z0 si tabelul devine:

w1

w2

w3

w4

Z1

z2

z3

z4

z0

q

Deoarece cel mai mare numar negativ qi este q3=-9,atunci pivotul se afla in coloana vectorului z0 si cea de-a treia linie este linia pivotului.Elementul pivot este incercuit in tabel.Operatiile pivotului conduc la tabelul canonic asociat bazei initiale.Variabilele de baza sunt scrise in ordine in coloana din partea stanga.

Variabile de baza

w1

w2

w3

w4

z1

z2

Z3

z4

z0

q

raport

w1

w2

z0

w4

La fel ca in sectiunea 1.8.5.Baze complementare admisibile apropiate adiacente,alegem pe z3 ca variabila de intrare.Vectorul coloana z3 devine coloana pivot.Raporturile discutate in sectiunea 1.8.2.Operatiile pivot sunt introduse in coloana din dreapta.Cel mai mic raport este pe linia a patra.Astfel linia pivot este a patra linie.Elementul pivot este incercuit.w4 iese din vectorul de baza si este inlocuit cu z3.

Variabile de baza

w1

w2

w3

w4

z1

z2

Z3

z4

z0

q

raport

w1

w2

z0

z3

Deoarece w4 nu a iesit din vectorul de baza ,complementul sau,z4 este variabila de intrare pentru urmatorul pas.Coloana lui z4 este coloana pivot.Elementul pivot este incercuit .w1 iese din vectorul de baza.

Variabile de baza

w1

w2

w3

w4

z1

z2

Z3

z4

z0

q

raport

z4

w2

z0

z3

Deoarece w1 a iesit din baza,complementul sau,z1 este noua variabila de intrare.Acum w2 iese din vectorul de baza.

Variabile de baza

w1

w2

w3

w4

z1

z2

Z3

z4

z0

q

raport

z4

z1

z0

z3

Deoarece w2 a iesit din vectorul de baza ,complementara sa,z2 este variabila de intrare.Acum z0 iese din vectorul de baza.

Variabile de baza

w1

w2

w3

w4

z1

z2

z3

z4

z0

q

z4

z1

z2

z3

Deoarece baza actuala este o baza complementara admisibila,algoritmul se termina.Solutia corespunzatoare este:

variabilele secundare w1,w2,w3,w4=0

vectorul de baza z4=1,z1=2,z2=1,z3=3

si reprezinta solutia pentru P.C.L.

Exemplu 11:

Se considera urmatoarea P.C.L.:

W1

w2

w3

z1

z2

z3

q

wi≥0 , zi≥ 0 , wi zi =0 pentru toti i

Tabelul cu variabila artificiala z0 este:

w

W

w

z

z

z

z

q

Tabelul canonic initial este:

Variabile de baza

w1

w2

w3

z1

z2

z3

z0

q

Raport

z0

w2

w3

Variabile de baza

w1

w2

w3

z1

z2

z3

z0

Q

z0

w2

z1

Variabila de intrare este z3.Coloana pivot este nepozitiva.Deci algoritmul se opreste aici printr-o terminatie raza.Algoritmul nu poate rezolva P.C.L.

1.10. Conditii

S-a aratat ca algoritmul pivot complementar pentru rezolvarea P.C.L. ofera o solutie pentru problema,daca aceasta solutie exista,chiar daca M este o matrice nenegativa cu admiteri diagonal pozitive,sau o P-matrice,sau o matrice pozitiv semidefinita,sau o matrice plus copozitiva,sau daca M apartine altor clase speciale de matrici nediscutate aici.

Programarea liniara si programarea patratica convexa pot fi rezolvate cu acest algoritm folosind forma P.C.L. discutata in sectiunea 1.6.Aplicatii.Algoritmul pivot complementar poate oferi o solutie pentru P.C.L. (5.5),(5.6),(5.7), chiar daca M nu se afla in nici una din aceste clase de matrici,dar in acest caz este posibil ca algoritmul sa se opreasca cu o terminatie raza ,chiar daca exista o solutie pentru P.C.L.

1.11.Alti algoritmi

S-a dezvoltat un nou algoritm special care,atunci cand a fost combinat cu algoritmul pivot complementar din sectiunea 1.8.Algoritmi pentru rezolvarea P.C.L.,a oferit o solutie pentru P.C.L.asociata unui joc bimatricial.Algoritmii bazati pe pivotarea principala sunt disponobili si sunt folositi atunci cand M este pozitiv semidefinita.Algoritmii care folosesc metode sistematice au fost de asemenea dezvoltati.

Singurele metode prin care se dezvolta P.C.L. cand M este o matrice oarecare sunt algoritmii enumerativi.Chiar atunci cand M apartine unei clase speciale de matrici,singurii algoritmi care pot genera multimea tuturor solutiilor unei P.C.L. sunt tot algoritmii enumerativi_tip.




1.12. Rezumat al rezultatelor teoretice

In problema complementaritatii liniare (q,M),daca M este fixata,problema are o solutie unica pentru fiecare qIRn daca M este o P_matrice,i.e.,clasa conurilor complementare C(M) partitioneaza Rn (precum clasa ortantilor), daca M este o P_matrice.Pentru anumite conditii puse lui M s-a aratat ca problema poate avea un numar par de solutii pentru toti qIRn sau un numar impar de solutii pentru toti qIRn.Se cunosc mai multe astfel de rezultate.Proprietatile problemei complementaritatii liniare pentru M, apartinand unei clase speciale de matrici sunt studiate foarte mult.

1.13.Probleme nerezolvabile

Un algoritm pentru o problema este un bun algoritm daca numarul calculelor necesare este limitat superior de un polinom de grad n,ordinul (sau marimea ) problemei.

Se cunosc algoritmi eficienti pentru testarea unei matrici daca este pozitiv definita sau pozitiv semidefinita.Acesti algoritmi se bazeaza pe operatii liniare pentru matrici si sunt trecuti in cartile despre algebra liniara.

Pana acum nu se cunosc algoritmi buni pentru testarea unei matrici patratice oarecare daca este copozitiva ,plus copozitiva,o P_matrice sau o Q_matrice.De asemenea ,pentru o matrice oarecare , nu sunt cunoscute conditii simple necesare si suficiente pentru a fi o Q_matrice.

Obtinand o solutie pentru o P.C.L.,vrem sa aflam daca aceasta solutie este unica sau daca mai exista alte solutii alternative.Daca aceste solutii alternative exista,vrem sa le calculam.Algoritmii enumerativi disponibili in prezent ,care pot raspunde la aceste intrebari si care pot rezolva P.C.L. cand M este o matrice oarecare,nu sunt foarte eficienti cand n este mare.

In plus ,exista un mare numar de probleme teoretice nerezolvate cu privire la proprietatile conurilor complementare si la proprietatile teoretice ale matricei asociate la P.C.L.

1.14.Problema complementaritatii neliniare

Fie f(z)=(f1(z),…,fn(z))T Rn un vector de functii , zRn.Problema ce trebuie rezolvata

z≥0

f(z)≥0

n

f(z)Tz=∑zIfI(z)=0

i=1

se numeste problema complementaritatii neliniara.Daca f(z)=Mz+q aceasta devine o P.C.L.Numeroase rezultate ale conditiilor necesare si suficiente pentru existenta unei solutii a problemei complementaritatii neliniare se poate transforma intr-o problema de calcul a punctelor fixe Kakutani (vezi sectiunea urmatoare) a unui punct din harta multimilor(vezi urmatoarea sectiune) definite pe Rn .Algoritmi pentru calcularea acestor puncte fixe,folosind idei asemanatoare cu cele discutate in algoritmul pivot complementar pentru rezolvarea P.C.L.,au fost dezvoltati si sunt discutati foarte pe scurt in sectiunea urmatoare.

Metode de calcul a punctelor fixe

Se considera o harta careia i se asociaza o submultime F(x)IRn pentru fiecare punct xIRn.O astfel de harta se numeste harta multimii de puncte.Un punct fix Kakutani din aceasta harta este punctul yIRn care satisface yIf(y).

Recent s-au dezvoltat algoritmi pentru calaculul eficient al acestor puncte fixe.Acesti algoritmi folosesc triangularile din Rn.O triangulare este o partitie a lui Rn in simplexuri.Fiecare simplex din Rn este acoperirea convexa a n+1 puncte numite vertexuri.Fiecare vertex are asociata o eticheta din multimea .Etichetarea se face astfel incat daca se gaseste un simplex,dintre cele care au vertexuri cu etichete distincte,fiecare punct din acel simplex este o aproximare a punctului fix.Problema se reduce la gasirea acelui simplex din triangulare care are vertexuri cu etichete diferite.Deoarece fiecare simplex are exact n+1 vertexuri,multimea etichetelor asociate vertexurilor unui simplex etichetat diferit trebuie sa fie .Astfel de simplexuri se numesc simplexuri etichetate complet.

Algoritmul incepe cu construirea unui simplex special care este etichetat aproape complet,i.e.,vertexurile acestui simplex au etichete diferite intre ele,cu exceptia unei singure perechi de vertexuri care au aceeasi eticheta.Spre exemplu,multimea de etichete asociate vertexurilor din simplexul de inceput poate fi .Etichetele asociate vertexurilor unui simplex etichetat aproape complet satisfac urmatoarele proprietati:

1.O singura eticheta apare exact de doua ori.

2.O singura eticheta din multimea lipseste.

Proprietatile triangularii folosite asigura faptul ca fiecare simplex atichetat aproape complet are cel putin doua simplexuri adiacente care sunt etichetate complet sau aproape complet.Simplexul de inceput are un singur simplex adiacent etichetat aproape complet si algoritmul poate fi folosit.Toate simplexurile obtinute de-a lungul algoritmului vor fi etichetate aproape complet cu exceptia ultimului care va fi etichetat complet.Am ajuns la un simplex pornind de la un simplex adiacent etichetat aproape complet.Simplexul mai are un singur simplex adiacent care este etichetat aproape complet sau este etichetat complet si algoritmul continua.Astfel metoda urmeaza o cale unica si clara care se termina cu un simplex etichetat complet.

Este evidenta asemanarea dintre algoritmul de obtinere a simplexurilor etichetate aproape complet si dintre algoritmul pivot complementar de obtinere a bazelor aproape complementare pentru rezolvarea P.C.L.

S-a aratat ca problemele programarii neliniare (restictionate sau nu) pot fi transformate in probleme de calcul a punctelor fixe.Algoritmii pentru calculul punctelor fixe au o larga aplicabilitate in programarea matematica si aplicatiile ei.

Capitolul 2

Problema complementaritatii

in programarea patratica

2.1.Restrictii ecuatii

Asemeni problemei de programare liniara,o alta problema de optimizare care poate fi rezolvata printr-un numar finit de pasi este problema de programare patratica (P.P.).Pentru aceasta problema functia obiectiv f(x) este patratica si functiile de restrictie ci(x) sunt liniare.Astfel problema consta in gasirea unei solutii x* pentru:

Inf    (1.1)

Sau in forma canonica:

Inf

Unde q(x)=(1/2)xTGx+gTx , gIRn,G matrice simetrica.

Ca si in programarea liniara,problema poate fi fara solutie admisibila sau poate avea solutie infinita;totusi aceste posibilitati sunt detectate promt in algoritmi,astfel in general se presupune ca solutia x* exista.Daca matricea hessiana G este pozitiv semi-definita atunci x* este solutie globala;in plus , daca G este pozitiv definita atunci x* este unic.Aceste proprietati rezulta din convexitatea (stricta) a lui q(x) si deci (1.1) este o problema de programare convexa.Cand hessiana G este nedefinita ,atunci pot apare solutii locale care nu sunt globale si calcularea unei astfel de solutii nu este importanta (vezi Sectiunea 2.4).Un algoritm eficient pentru P.P. trebuie sa fie destul de complex,astfel se realizeaza mai intai un calcul simplificat al structurii de baza si apoi se amplifica acest calcul.In primul caz se arata in Sectiunea2.1 si 2.2 cum se rezolva problemele cu restrictii ecuatii.Generalizarea acestor idei ,in cazul restrictiilor inecuatii ,se face prin intremediul unor strategii de multimi active si sunt descrise in Sectiunea 2.3.Proprietati mai avansate ale algoritmului P.P.,in care se foloseste matricea hessiana nedefinita si care permite rezolvarea eficienta a unui set de probleme, sunt date in Sectiunea 2.4.Probleme de P.P. cu o structura speciala ,cum ar fi cele care au doar restrictii marginite sau cele care apar din problemele patratelor minime, sunt tratate in Sectiunea 2.5.Pentru rezolvarea unei probleme de P.P. se foloseste ades forma tabelara modificata a metodei simplex din programarea liniara.Aceasta rezolvare este descrisa in Sectiunea 2.6 si a ajuns sa fie exprimata in termeni de problema complementaritatii liniare.Este descrisa echivalenta dintre aceste metode si metodele multimii active,precum si motivele pentru care este preferata ultima deducere.

Programarea patratica difera de programarea liniara prin faptul ca este posibil sa avem anumite probleme (altele decat un sistem de n×n ecuatii) in care nu sunt restrictii inecuatii.De aceea aceasta sectiune studiaza cum sa afli o solutie x* a problemei cu restrictii ecuatii

Inf (1.2)

unde q(x)=(1/2)xTGx+gTx

Presupunem ca sunt m≤n restrictii astfel incat bIRm si A este o matrice n×m si contine vectorii coloana ai ,iIE.Presupunem ca A are rangul m;daca restrictiile sunt cosistente aceasta se poate obtine prin inlaturarea restrictiilor dependente, desi pot fi dificultati numerice in recunoasterea acestei situatii.Aceasta presupunere afecteaza existenta si unicitatea multiplicatorilor Lagrange * si calcularea acestora.

O metoda directa de rezolvare a problemei (1.1) este aceea de a folosi restrictiile pentru a elimina variabilele.Daca matricile

x1 A1 g1 G11 G12

x= A= g= G=

x2 A2 g2 G21 G22

Sunt definite ,unde x1 IRm si x2 I Rn-m atunci ecuatiile (1.1) devin

AT1x1+AT2x2=b si sunt gata rezolvate (prin eliminarea gaussiana) inlocuind x1 cu x2; aceasta se scrie convenabil astfel:

x1=A-T1(b-AT2x2) (1.3)

Inlocuind in q(x) problema devine :inf (x2), x2 I Rn-m, unde (x2) este functia patratica:

Ψ(x2)=(1/2)xT2(G22-G21A-T1AT2-A2A-11G12+A2A-11G11A-T1AT2)x2

. +xT2(G21-A2A-11G11)A-T1b+(1/2)bTA1-1 G11 T1b

+xT2(g2-A2A-11g1)+gT1A-T1b (1.4)

Exista si este unic un x2* minim daca hessiana Ψ este pozitiv definita caz in care x2* se obtine prin rezolvarea sistemului liniar Ψ (x2) =0.Apoi x1* se obtine prin substitutie in (1.3).Vectorul multiplicatorului lagrange λ* este definit prin g*=Aλ*, unde g*= q(x*), si poate fi calculat prin rezolvarea primei divizari g*1=A1λ*.Din definitia lui q(x) din (1.2),g*=g+Gx* deci o expresie explicita pentru λ* este:

λ*=A1-1(g1+G11x1*+G12x2*) (1.5)

Exemplu de rezolvare a unei probleme prin aceasta metoda:

Inf (1.6)

Pentru eliminarea lui x3,ecuatiile se scriu sub forma:

x1+2x2= 4+x3

x1-x2= -2-x3

si sunt gata rezolvate prin eliminarea Gaussiana ,obtinand:

x1=0-(1/3)x3, x2=2+(2/3)x3 (1.7)

x1

Se verifica usor ca aceasta solutie corespunde cu (1.3) cu X1=

1 1 x2

X2=(x3), A1= si A2=[-1 1].

2 -1

Inlocuind (1.7) in q(x) din (1.6) se obtine

(x3)=(14/9)x32+(8/3)x3+4 (1.8)

2 0

Care corespunde cu (1.4) cu G11 =

0 2

G12=GT21=0,G22=[2] si g=0.Matricea hessiana din (1.8) este [28/9] care este pozitiv definita, deci minimul este obtinut prin =0 si x3*=-6/7. Inlocuind inapoi in (1.6) se obtine x1*=2/7 si x2=10/7.Sistemul g*=A * devine :

2 1 1

si rezolvand primele 2 linii avem *1=8/7 si *2=-4/7,si aceasta este valabila cu a treia linie.

Eliminarea directa a variabilelor nu este singura metoda de rezolvare a (1.2) si nici cea mai buna.O metoda de eliminare generalizata este posibila in care se face initial o transformare liniara a variabilelor.

Fie Ysi Z matrici de n×m, respectiv de n×(n-m) astfel incat [Y:Z] este nesingulara si in plus fie ATY=I si ATZ=0, YT fiind privita ca inversa generalizata la dreapta a matricei A astfel incat o solutie a ATx=b sa fie data de x=Yb.Totusi ,aceasta solutie nu este unica in general si alte puncte admisibile sunt date de x=Yb+ , unde este spatiu coloana nul din A.

Acesta este spatiu liniar

(1.9)

care are dimensiunea n-m.Matricea Z are coloane z1,z2 ,…,zn-m liniar independente in acest spatiu nul si de aceea pot fi vectori de baza pentru spatiu nul.Adica ,pentru orice punct admisibil x orice corectie admisibila poate fi scrisa astfel:

n-m

=Zy= ∑ziyi (1.10)

i=1

unde y1,y2,…,yn-m sunt componente (sau variabile reduse)ale fiecarei directii a coordonatei reduse(vezi Fig. 1).Astfel fiecare punct admisibil x poate fi scris sub forma:

x=Yb+Zy (1.11)

Fig.1:Coordonatele reduse pentru regiunea admisibila

Aceasta poate fi interpretat (Fig.2) ca un pas de la origine la punctul admisibil Yb,urmat de o corectie admisibila Zy pentru a ajunge la punctul x.Astfel (1.11) ofera o metoda de eliminare a restictiilor ATx=b in termeni ai vectorului variabilelor reduse y care are n-m elemente,fiind astfel o generalizare a (1.3).Inlocuind in q(x) obtinem functia patratica redusa

(y)=(1/2)yTZTGZ y+(g+GYb)TZy+(1/2) (g+GYb)TYb (1.12)

Daca ZTGZ este pozitiv definita ,atunci exista un punct de minim unic y* care (din (y)=0) rezolva sistemul liniar

(ZTGZ)y=-ZT(g+GYb) (1.13)

x* se obtine prin inlocuire in (1.11).Matricea ZTGZ din (1.12) se numeste matricea hessiana redusa si vectorul ZT(g+GYb) se numeste vectorul gradient redus.Se observa ca g+Gyb= q(Yb) este vectorul gradient al lui q(x) pentru x=Yb (la fel cum g este q(0)), deci derivatele reduse se obtin print-o operatie matriciala cu ZT.In plus , inmultind cu YT la g*=A * se obtine ecuatia

*=YTg*=YT(Gx*+g) (1.14)

care poate fi folosita pentru a calcula multiplicatorii lagrange.Expresiile explicite pentru x* si * in termenii datelor originale sunt:

x*=Yb-Z(ZTGZ)-1ZT(g+Gyb) (1.15)

si

*=YT(g+Gx*)

=(YT-YTGZ(ZTGZ)-1ZT)g

+YT(G-GZ(ZTGZ)-1ZTG)Yb (1.16)

Aceste formule nu vor fi folosite direct dar sunt folositoare pentru a arata relatia cu metoda alternativa a multiplicatorilor Lagrange pentru rezolvarea problemelor P.P. cu restrictii ecuatii, considerate in Sectiunea 2.2.

Anumite metode depind de alegera lui Y si alui Z si pentru construirea acestor matrici Y si Z cu proprietatile corecte este descrisa in continuare o procedura generala.Totusi , o alegere particulara este factorizarea matricei A.Aceasta se poate scrie astfel:

R R

A=Q =[Q1 Q2 ] =Q1R (1.17)

0 0

Unde Q este de dimensiune n×n si este ortogonala, R este de dimensiune m×m si superior triunghiulara si Q1 si Q2 sunt de dimensiune n×m,respectiv

n×(n-m).Alegerile

Y=A+T=Q1R-T, Z=Q2 (1.18)

se observa ca au proprietatile corecte.In plus vectorul Yb din (1.11) si Fig.2 se observa ca este ortogonal pe multimea restrictiilor si directiile coordonatelor reduse zi sunt reciproc ortogonale.Solutia x* se obtine ca mai sus prin punere in ecuatie si rezolvand (1.13) pentru y* si apoi inlocuind in (1.11).Yb este calculat din substitutia dinainte in RTu=b urmata de Yb=Q1u.

Fig.2:Eliminarea generalizata intr-un caz special

Multiplicatorii * din (1.14) sunt calculati prin substitutia

R *=QT1g* (1.19)

Planul se datoreaza lui Gill si Murray (1974) si se va face referire la el sub denumirea de metoda factorizarii ortogonale.

Exemplu de aplicare a metodei pentru problema (1.16) .Matricile respective sunt:

5 8 1

Y=(1/14) 4 -2 Z= -2

-1 4 -3

1/√6 4/√21 1/√14 √6 -√6/3

A= 2/√6 -1/√21 -2/√14 0 √21/3

Vectorul Yb=(1/7)(2,10,-6)T, g=0 si GYb=2Yb,ZT(g+Gyb)=0.Rezulta ca y*=0 si x*=Yb=(1/7)(2,10,-6)T . De asemenea g*=g+Gyb=(2/7) (2,10,-6)T si *=(8/7,-4/7)T si aceste rezultate sunt egale cu cele obtinute prin eliminarea directa.

Un algoritm general pentru calcularea matricelor Y si Z este urmatoarea: se alege o matrice oarecare V de dimensiune n×(n-m) astfel incat [A:V] este nesingulara.Fie matricea inversa exprimata astfel:

YT

[A:V]-1= (1.20)

ZT

unde Y si Z sunt de dimensiune n×m,respectiv n×(n-m).Apoi urmeaza YTA=I si ZTA=0 astfel incat aceste matrici sa fie potrivite pentru folosirea lor in metoda eliminarii generalizate.Metoda rezultata poate fi interpretata ca o metoda care foloseste o transformare liniara cu matricea [A:V].Metodele descrise la inceput pot fi cazuri particulare ale acestui algoritm.Daca se alege

0

V= (1.21)

I

atunci egalitatea

A1 0 -1 A1-1 0 YT

A2 I -A2A1-1 I ZT

ofera expresiile pentru Y si Z.Se verifica usor ca in acest caz metoda se reduce la metoda eliminarii directe.Alternativ, daca se alege

V=Q2 (1.23)

unde Q2 este definita de (1.17),atunci se obtine metoda factorizarii ortogonale de mai sus.Egalitatea

R-1Q1T

[A:V]-1=[Q1R:Q2]-1= (1.24)

Q2T

poate fi exprimata sub forma

A+

[A:V]-1= (1.25)

V+

unde A+=(ATA)-1AT si ,in acest caz,(1.14) poate fi scris astfel:

*=A+g* (1.26)

De fapt pentru orice Y si Z,exista un unic V datorita relatiei (1.20).Totusi,daca Z este dat si Y este arbitrar,atunci V poate fi ales mai usor; acest lucru este discutat in Sectiunea 2.6.Generalizarea din (1.20) nu este tocmai cea mai potrivita ; este preferabil sa nu construim pe Y si Z ,ci sa generam indirect aceste matrici prin factorizarea [A:V] ; in particular , forma simpla (1.21) si (1.22) poate fi avantajoasa pentru probleme mai mari.

O alta metoda care poate fi descrisa in aceasta Sectiune este metoda gradientului redus a lui Wolfe(1963).Folosind termenii din metoda multimii active (Sectiunea 2.3),matricea V este formata din vectorii normali ai restrictiilor inactive care anterior au fost active.Asfel , cand o restrictie devine inactiva ,coloana ai din A este transferata in V asfel incat [A:V]-1 trebuie sa fie recalculata si numai linia de divizare trebuie repozitionata.Cand o restrictie inactiva devine activa,vectorul de intrare ai inlocuieste o coloana din V.Alegera coloanei este arbitrara si poate fi facuta astfel incat [A:V] sa fie bine determinata.Acest schimb de coloane este analog cu cel din programarea liniara.

Alte metode pentru P.P pot de asemenea folosi acesti termeni.Murray (1971) ofera o metoda in care matricea Z este construita si pentru care

ZTGZ=D (1.27)

unde D este matrice diagonala.In aceasta metoda coloanele din Z pot fi

interpretate ca directii conjugate si sunt legate de matricea (Z^) din metoda de factorizare ortogonala prin Z=Z^L-1.Din aceasta cauza metoda prezinta in primul rand informatii despre matricea inversa dar poate fi nesigura pe motive de stabilitate.Totusi , are avantajul ca solutia pentru (1.13) devine triviala si nu este necesara o retinere a elementelor matricei ZTGZ.Se poate considera metoda Beale (1959) (vezi Sectiunea 2.6) prin care se pot selecta directiile de cautare cunjugate din liniile matricei [A:V]-1.In acest caz matricea V se formeaza din diferenta gradientilor (j) din iteratiile anterioare.Totusi si aceasta metoda are unele dezavantaje.

Nu este usor sa faci alegera cea mai buna dintre aceste metode,deoarece aceasta depinde de tipul problemei si de faptul ca metoda poate fi considerata o parte a metodei multimii active pentru restrictii inecuatii (Sectiunea 2.3).In plus, in Sectiunea 2.2 sunt descrise alte metode importante.Totusi,metoda factorizarii ortogonale este avantajoasa deoarece calcularea lui Z implica operatii cu matrici ortogonale elementare care sunt foarte stabile numeric.De asemenea ,aceasta alegere (Z=Q2) ofera cea mai buna posibila marginire

k(ZTGZ)≤k(G) (1.28)

a numarului conditie k(ZTGZ).Nu se poate spune ca ofera cel mai bun k(ZTGZ), asa cum sustineau in mod eronat Gill si Murray (1974).Intr-adevar o modificare triviala a metodei Murrey(1971) cu D=I permite sa fie calculata matricea Z pentru care k(ZTGZ)=1.De fapt semnificatia acestui numar conditie este nesigura deoarece poate fi schimbat prin scalarea liniilor si coloanelor simetrice din ZTGZ ,fara modificarea propagarii erorii.Relatia (1.28) indica faptul ca k(ZTGZ) nu poate fi arbitrar mare.Totusi aceasta concluzie poate fi obtinuta si cu alte metode care folosesc pivotarea.Pe de alta parte , o alegere arbitrara a lui V care face coloanele lui Z aproape dependente,poate induce cresteri neplacute a erorilor de rotunjire.

2.2.Metoda multiplicatorilor Lagrange

O cale alternativa de obtinere a solutiei x* pentru problema (1.2) si a multiplicatorilor * asociati este prin metoda multiplicatorilor Lagrange.Functia lagrangeian devine:

L(x, )=(1/2)xTGx + gTx - T(ATx - b) (2.1)

si conditiile pentru punct stationar devin:

x L=0: Gx + g - A

x L=0: ATx - b =0

care pot fi rearanjate sub forma de sistem liniar

G -A x g

= - (2.2)

-AT 0 b

Matricea coeficient este denumita matricea lagrangeian si este simetrica,dar nu este pozitiv definita.Daca inversa exista si se scrie sub forma

G -A -1 H -T

-AT 0 -TT U

atunci solutia pentru (2.2) este

x*= -Hg+Tb (2.4)

*=TTg-Ub    (2.5)

Aceste relatii sunt folosite de Fletcher(1971) pentru rezolvarea problemei cu restrictii ecuatii (3.1) care provin din metoda multimii active.Deoarece b=0 in acest caz doar matricile H si T trebuie retinute.Expresiile explicite pentru H,T si U ,cand G-1 exista, sunt :

H=G-1-G-1A(ATG-1A)-1ATG-1

T= G-1A(ATG-1A)-1 (2.6)

U= -(ATG-1A)-1

si sunt gata verificate prin inmultiri ale matricei lagrangeian si a inversei sale.Murtagh si Sargent (1969) sugereaza metode pentru restrictii liniare care folosesc aceasta reprezentare prin retinerea matricelor (ATG-1A)-1 si

G-1.Totusi nu este necesar pentru ca G-1 sa existe si pentru ca matricea lagrangeian sa fie nesingulara.Nici una dintre aceste de mai inainte nu este recomandata in practica deoarece pot fi potentiale probleme de stabilitate.De fapt, daca Y si Z sunt definite de (1.20), atunci o expresie alternativa pentru inversa matricei lagrangeian este:

H=Z(ZTGZ)-1ZT

T=Y- Z(ZTGZ)-1ZTGY (2.7)

U=YTGZ(ZTGZ)-1ZTGY-YTGY

Acestea pot fi verificate folosind relatiile obtinute din (1.20).Astfel se considera ca pentru calcularea lui Y si Z in orice metoda de eliminare este esentiala o cale subtila de factorizare a matricei lagrangeian din metoda Lagrange.Ecuatiile (2.7) demonstreaza ca matricea lagrangeian este nesingulara daca si numai daca exista Z astfel incat matricea ZTGZ

este nesingulara.In plus, x* este minim local unic daca si numai daca ZTGZ este pozitiv definita datorita conditiilor de ordin 2 aplicate functiei patratice (1.12).

Aceste reprezentari diferite ale inversei matricei lagrangeian se folosesc in doua tipuri diferite de metode care au fost propuse pentru rezolvarea problemelor (2.4) si (2.5).In general este metoda spatiului nul in care Y , Z si ZTGZ = LLT se presupune ca exista.Metoda spatiului nul este asociata cu reprezentarea (2,7) care este folosita pentru a modul de rezolvare a (2.4) si (2.5).Expresiile intermediare sunt simplificate acolo unde este posibil si operatiile de inversare cu matrici triunghiulare sunt indeplinite de substitutii.De fapt, aceasta ofera metoda eliminarii generalizata din Sectiunea 1.1.Exista numeroase metode diferite de spatii nule legate de diferite moduri de alegere a lui Y si Z si sunt discutate in Sectiunea 1.1.O abordare alternativa este metoda spatiului imagine care necesita ca matricea hessiana sa fie pozitiv definita si foloseste factorii Choleski G=LLT.Metoda spatiului imagine este asociata cu reprezentarea (2.6).Folosind factorii Choleski putem sa rearanjam relatia (2.6) si se observa ca produsul L-1A apare frecvent.Recent, metodele spatiului imagine se bazeaza pe folosirea L-1A astfel incat:

R

L-1A=[Q1:Q2] =Q1R

0

si matricile din (2.6) au forma determinata

H=L-T(I-Q1Q1T)L-1

T=L-TQ1R-T

U= -R-1R-T

Gill (1984) ofera o astfel de metoda in care Q1(dar nu Q2) si R sunt explicit actualizate.Goldfarb si Idnani (1983) au o metoda inrudita in care introduc matricea S=L-TQ si in care retin si actualizeaza pe S si R .Evident formulele de mai sus permit inlocuirea lui L-TQ1 cu S1: se poate ca metoda sa fie imbunatatita doar prin retinera si actualizarea lui S1 si a lui R.Algoritmul se poate numi metoda retinerii minime deoarece actualizeaza doar matricea R, inlocuind Q cu produsul L-1AR-1 in formulele de mai sus.Trnsformarea ridica la patrat numarul conditie al problemei si acest lucru nu se doreste.Metoda spatiului imagine este des folosita cand factorul Choleski al matricei G este dat apriori si nu trebuie sa fie calculat.Operatiile folosite pentru aceste metode sunt favorabile cand sunt doar cateva restrictii pentru problema.

Urmeaza operatii cu privire la structura inversei din (2.3).In primul rand TTA=I astfel incat TT este inversa la stanga generalizata a matricei

A.Daca ZTGZ este pozitiv definita ,atunci H este pozitiv semi-definita cu rangul n-m.Se verifica ca HA=0 astfel ca proiecteaza orice vector v in multimea restrictiilor (din ATHv=0).Daca x(k) este este un punct oarecare admisibil atunci ATx(k)=b si g(k)=g+Gx(k) este vectorul gradient al lui q(x) in x(k).Folosind apoi (2.6) putem rearanja (2.4) si (2.5) astfel incat

x*=x(k) - Hg(k) (2.8)

*=TTg(k) (2.9)

Ecuatia (2.8) are o relatie apropiata cu metoda Newton si arata ca H contine curbura corecta pentru regiunea admisibila si poate fi privita ca o matrice hessiana inversa redusa.De aceea aceste formule pot defini o metoda de proiectie relativa la matricea G (pozitv definita); daca G este inlocuita cu I atunci H=AA+=P care este o matrice de proiectie ortogonala.De fapt se poate stabili ca H=(PGP)+, inversa generalizata a matricei hessiane de proiectie.

Se pot folosi metode (atribuite initial lui Bunch si Parlett (1971)) pentru factorizarea unei matrici generale simetrice nesingulare.Aceasta include si calcularea factorilor LDLT ai matricei lagrangeian, unde D este matrice diagonala.De aceea,aceasta ofera un mijloc stabil de rezolvare a (2.2), in special pentru probleme in care G este nedefinita.Totusi, metoda ignora matricea nula care exista in (2.2) si astfel nu profita destul de structura.De asemenea , deoarece este inclusa pivotarea,factorii nu sunt foarte potriviti pentru a fi actualizati in metoda multimii active.Pe de alta parte,matricea lagrangeian este nesingulara daca si numai daca A are rangul intreg,deci metodele de eliminare generalizata, care formeaza matricele Y si Z in mod rezonabil atunci cand A are rangul intreg , nu pot fi instabile datorita factorizarii matricei lagrangeian atat timp cat ZTGZ este pozitiv definita.Astfel ,metodele stabile de eliminare generalizata sunt cele preferate.

Un alt mijloc de rezolvare a sistemului Lagrange (2.2) este acela de a factoriza dinainte matricea lagrangeian.Mai intai se calculeaza factorii LDLT ai matricei G care este stabila atat timp cat G este pozitiv definita.Apoi acesti factori sunt folositi pentru a elimina divizarile diagonale (-A si -AT) in matricea lagrangeian.Divizarea 0 se schimba in -ATG-1A care este negativ definita si astfel poate fi factorizata ca -ˆLˆDˆLT cu ˆD>0.De aceea factorii rezultati L D LT ai matricei lagrangeian sunt dati de

L D

L= D= (2.10)

BT ^L -D^

unde B este definita de LDB= -A si este deja calculata de substitutia dinainte.Pentru a evita pierderea preciziei in formarea ATG-1A,ˆL si ˆD sunt calculate cel mai bine prin formarea matricei D-1/2L-1 si factorizarea ei in QˆD1/2 .Metoda este foarte avantajoasa in cazul in care G are o anumita structura care poate fi exploatata si cand numarul de restrictii m este mic .Nu este absolut sigur ca metoda este stabila cu privire la erorile de rotunjire, in special cand G este aproape singulara , dar metoda este folosita cu succes.Cerinta ca G sa fie pozitiv definita este importanta,totusi,o alta calculare a factorilor LDLT poate sa nu fie posibila sau poate fi instabila.Metoda este echivalenta cu metoda spatiului imagine descrisa mai sus.

2.3.Metoda multimii active

Majoritatea problemelor de P.P. include restrictii inegalitati si astfel pot fi exprimate sub forma data de relatia (1.1).Aceasta sectiune descrie modul in care metodele pentru rezolvarea problemelor cu restrictii ecuatii pot fi generalizate sa rezolve probleme cu inegalitati cu ajutorul metodei multimii active .Cea mai folosita este metoda multimii active primale si cea mai mare parte a sectiunii este dedicata acesteia.Este descrisa in cazul in care matricea hessiana G este pozitiv definita ceea ce asigura ca solutia sa fie punct de minim global unic si astfel unele potentiale dificultati sa fie evitate.

Pe parcursul acestei sectiuni este posibil sa consideram metoda multimii active duale ,desi aceasta se aplica doar in cazul in care G este pozitiv definita.

In metoda multimii active primale anumite restrictii ,indexate de multimea activa A , sunt privite ca egalitati pe cand celelalte sunt temporar neluate in seama si metoda aranjeaza aceasta multime pentru a identifica corect restrictiile active ale solutiei preoblemei (1.1).Deoarece functia obiectiva este patratica este posibil sa fie m (0≤m≤n) restrictii active,spre deosebire de programarea liniara unde m=n.La iteratia k se cunoaste punctul admisibil x(k) care satisface restrictiile active ca egalitati,adica aiTx(k)=bi,iIA.Pentru aiTx(k)>bi,i A.Fiecare iteratie incearca sa localizeze solutia problemei egalitatii (P.E.) in care apar doar restrictii active.Cel mai convenabil este sa schimbam originea in x(k) si sa cautam o corectie δ(k) care rezolva

inf (1/2)δTGδ+δTg(k)

δ (3.1)

pentru aiTδ=0 , iIA

unde g(k) este definita prin g(k)=g+Gx(k) si este q(x(k)) pentru functia q(x) definita in (1.1).Aceasta reprezinta de fapt problema scrisa sub forma (1.2),deci poate fi rezolvata prin orice metoda descrisa in Sectiunea 2.1 si Sesctiunea 2.2.Daca δ(k) este admisibila cu privire la restrictiile ce nu se afla in A , atunci urmatoarele iteratii sunt x(k+1)=x(k)(k) .Daca nu , atunci o linie de cautare este facuta in directia lui δ(k) pentru a gasi cele mai bune puncte admisibile.Acest lucru poate fi exprimat prin definirea solutiei problemei (3.1) si cautarea directiei s(k) si alegerea pasului α(k) pentru a rezolva

bi- aiTx(k)

(k) =min 1, min ————— (3.2)

I:i IA aiTs(k)

aiTs(k)<0

astfel incat x(k+1)=x(k)+ (k)s(k).Daca (k)<1 in (3.2) atunci o noua restrictie devine activa , definita de indicele ( sa spunem p) care atinge minimul din (3.2) si acest indice este adaugat la multimea activa A.

Daca x(k) (adica =0) rezolva P.E. curenta atunci este posibila calcularea multiplicatorilor ( sa spunem (k)) pentru restrictiile active asa cum este descris in Sectiunea 2.1 si 2.2.Vectorii x(k) si (k) satisfac apoi toate conditiile de ordin intai pentru probleme cu restrictii inecuatii,exceptand conditiile dual admisibile ,adica i≥0 ,iI I.Astfel se testeaza daca i(k) iIA(k)∩I; daca da , atunci conditiile de ordin intai sunt suficiente pentru a asigura solutia globala de vreme ce q(x) este convexa.Astfel, exista un indice ,q,qIA(k)∩I astfel incat q(k)<0.In acest caz , putem reduce q(x) prin devenirea lui q restrictie inactiva.Astfel q este eliminat din A si algoritmul continua ca mai inainte cu rezolvarea P.E. rezultata (3.1).Daca exista mai multi indici pentru care q(k)<0 atunci se alege q rezolvand

min i(k) (3.3)

i IA∩I

Aceasta alegere este destul de buna si convenabila si este folosita foarte des.

Pentru a rezuma algoritmul , daca x(1) este un punct admisibil dat si A=A(1) este multimea activa corespunzatoare, atunci metoda multimii active primale este definita astfel:

(a) Pentru k=1 : se da x(1) si A.

(b) Daca =0 nu rezolva (3.1) se trece la pasul (d).

(c) Se calculeaza multiplicatorii Lagrange (k) si se rezolva (3.3);

daca q(k)≥0 algoritmul se termina cu solutia x*=x(k),altfel se

elimina q din A.

(d) Se rezolva (3.1) pentru s(k). (3.4)

(e) Se gaseste (k) pentru rezolvarea (3.2) si x(k+1)=x(k)+ (k)s(k).

(f) Daca (k) <1, se adauga p la A.

(g) k=k+1 si se trece la pasul (b).

In Fig.3.1 este ilustrata metoda pentru o problema de P.P. simpla .Pentru aceasta problema de P.P. restrictiile sunt marginile x≥0 si restrictia generala aTx≥b.

Fig 3:Metoda multimii active primale pentru o problema patratica simpla

La x(1) marginile x1≥0 si x2≥0 sunt active si astfel x(1) ( =0) rezolva P.E. curenta (3.2) .Calcularea arata ca restrictiile x2≥0 au multiplicator negativ si astfel devin inactive si doar x1≥0 este activa.P.E. corespunzatoare este acum rezolvata de x(2) (sau = x(2)-x(1)) care este admisibil si astfel devine urmatoarea iteratie.Calcularea lui indica faptul ca restrictia x1≥0 are multiplicatorul negativ si devine astfel inactiva, lasand multimea A vida.P.E. corespunzatoare este acum rezolvata de x′ care este admisibil si directia de cautare s(2)= x′- x(2) este calculata din (3.1) si o cautare liniara

de-a lungul lui s(2) prin rezolvarea (3.2) il da pe x(3) ca cel mai bun punct admisibil.Restrictia generala aTx≥b devine activa pentru x(3) si astfel este adaugat in A.Deoarece x(3) nu rezolva P.E. curenta , multiplicatorii nu sunt calculati, dar in schimb este rezolvata P.E. si x(4) este urmatoarea iteratie.Calcularea multiplicatorilor lui x(4) indica faptul ca x(4) este solutia problemei de P.P. cu inegalitati si algoritmul se termina.

In general,algoritmul se poate termina la fiecare pas (k)≠0 , caz in care q(x) se reduce la fiecare iteratie.Este o consecinta a (3.2) faptul ca vectorii ai,iIA , sunt independenti ;deci P.E. in (3.1) este tot timpul bine definita.Demonstrarea terminarii se bazeaza pe faptul ca este un sir de iteratii care rezolva P.E. curenta .(Doar cand (k)<1 in (3.2) , x(k+1) nu este solutie pentru P.E.In acest caz un indice p este adaugat la A .Aceasta se poate intampla de cel mult n ori, caz in care x(k) este vertex si astfel rezolva P.E. corespunzatoare).Deoarece numarul de P.E. este finit si deoarece fiecare x(k) din sir este solutia globala unica pentru o P.E. si pentru ca q(x(k)) este monoton descrescatoare , inseamna ca algoritmul trebuie sa se incheie.Aceasta demonstratie este gresita atunci cand se iau pasi de marime zero si q(x(k)) nu este descrescatoare; in acest caz algoritmul poate fi ciclic prin intoarcerea la o multime activa anterioara din sir.Aceasta este cauza de degenerare in multimea restrictiilor.Pentru valoarea (k)=1(pentru care s(k) rezolva (3.1)) restrictiile inactive devin active.Teoretic, este posibil ca ciclarea sa fie evitata,dar in practica sunt unele dificultati si majoritatea algoritmilor ignora faptul ca poate apare degenerarea.

Metoda multimii active primala necesita un punct admisibil initial x(1); acesta poate fi aflat ; se calculeaza un vertex admisibil(poate include unele pseudo-restrictii) care devine punctul admisibil x(1) cerut.Elementele matricii A pentru multimea activa pot fi folosite in algoritmul principal.O posibilitate alternativa care evita folosirea punctului admisibil este aceea de a influenta faza 1 a functiei cost prin adaugarea unui multiplu vq(x) a functiei patratice .Pentru un v suficient de mic, problema poate fi rezolvata

intr-o singura faza.Aceasta duce la studiul unor metode asemanatoare P.P. pentru problema

min (x) =q(x)+║l(x)-1 (3.5)

(pentru restrictii inecuatii l(x)≥0),unde l(x)=ATx-b si a‾=max(-a,0).Este posibila aici utilizarea unei metode ale multimii active care difera de (3.4) in mai multe privinte.Una ar fi aceea ca, cautarea liniara (3.2) este shimbata la cautarea unui minim pentru (3.5).O alta diferenta este aceea ca pentru conditiile de ordin intai pentru (3.5) multiplicatorii care exista satisfac 0≤ i≤1.Astfel testul (3.3) este schimbat astfel incat sa aleaga q ca multiplicator care incalca cel mai mult aceste conditii.De asemenea, restrictiile inactive au multiplicatorii corespunzatori ori 0 ori 1 dupa cum li(x)>0 sau <0.P.E. care este rezolvata este:

min q(x) - ∑ ili(x)

x i A (3.6)

pentru li(x)=0, i IA

si tehnicile din Sectiunea 2.1 si 2.2 sunt din nou relevante,impreuna cu metodele de actualizare potrivite.

In Sectiunea 2.6 sunt descrise relatiile dintre metoda multimii active (3.4) si unele metode derivate ca extensii ale programarii liniare.Variantele posibile ale (3.4) care au fost sugerate includ inlaturarea mai multor restrictii ( cu i(k)<0) din A la pasul (c ) sau modificarea pasului (b) astfel incat sa fie acceptata o solutie aproximativa a P.E.Ambele posibilitati induc multimi active mai mici.Goldfarb (1972) dovedeste ca astfel este avantajos.Modificarea , in care se inlatura mai mult de o restrictie , creeaza unele dificultati pentru P.P. nedefinita asociata cu cerinta de a mentine stabili factorii matricei de curbura ZTGZ.

O metoda mai recenta pentru P.P. convexa este sugerata de Goldfarb si Idnani (1983) si poate fi interpretata ca metoda multimii active duale .Prin aceasta metoda este calculata o secventa de vectori x, care satisface conditiile Kuhn-Tucker ,cu exceptia admisibilitatii primale.Initial x= -G-1g este minimul fara restrictii a functiei patratice,A=Ĝ si =0 este un vertex in spatiul dual.O iteratie majora a metodei consta in urmatorii pasi:

(i)        Se alege q astfel incat restrictia q este neadmisibila in (1.1) si se adauga q la A.

(ii)     Daca aq I atunci se elimina din A indicele restrictiei inegalitatii care va deveni pozitiva la pasul (iii).

(iii) Mergi la solutia P.E.

(iii)           Daca orice i↓0, iIA∩I atunci se inlatura I din A si se va merg la (iii).

Iteratia majora este completa cand solutia P.E. este gasita la pasul (iii).Iteratiile majore se continua pana cand se recunoaste admisibilitatea majora la pasul (i) (x este solutia optima) sau pana cand nici un indice potrivit din A ce trebuie eliminat,nu este gasit la pasul (ii) (P.P.este neadmisibila).O problema de P.P. nemarginita nu poate sa apara deoarece G este pozitiv definita.Daca problema de P.P., care este duala problemei (1.1) este setata (organizata), atunci metoda lui Goldfarb si Idnani este echivalenta cu metoda multimii active primale,fiind aplicata acestei probleme duale si este instructiv sa comparam proprietatile acestor metode ale multimii active primale si duale .Desi metoda lui Goldfarb si Idnani cauta si inlatura irealizarile primale,nu este necesar cazul in care o restrictie primala ramane realizabila odata ce devine realizabila.Proprietatea de terminare a metodei este asigurata de faptul ca fiecare iteratie mareste atat functia obiectiv primala, cat si functia obiectiv duala.Admisibilitatea dualei este mentinuta.

Avantajul metodei este acela ca se poate deja folosi de disponibilitatea factorilor Cholescki ai matricei G.Metoda este mai eficienta cand sunt doar cateva restrictii active ca solutie si ai avantajului unei bune estimari a lui A.Nu este posibila degenerarea restrictiilor i≥0,iII.Singura dificultate cauzata de degenerare in restrictiile primale apare aproape de solutie.Proprietatile nefavorabile ale metodei includ si lipsa de generalizare, in faptul ca matricea G trebuie sa fie pozitiv definita.La fel si in cazul in care vor apare dificultati atunci cand G este rau conditionata de exemplu ,pot apare elemente si erori de rotunjire mari in vectorul x=-G-1g.Totusi, Powell(1985) sustine ca aceste dificultati pot fi depasite.Metoda este mai mult asociata cu folosirea metodei spatiului imagine pentru rezolvarea P.E..Este posibil sa fie dezvoltate alte metode numite metode dual-primale

pentru P.P. convexa care permit ambele irealizari primale si duale si care au pasi similari cu cei din metodele de mai sus.Transformarea unei probleme de P.P. intr-o problema de complementaritate liniara, cum este descrisa in Sectiunea 2.6, poate fi privita ca o marire a numarului de metode dual-primale.

O proprietate importanta a oricarei metode de multimi active priveste eficienta solutiei P.E. (3.1) atunci cand sunt efectuate schimbari asupra multimii A .Ca si in programarea liniara este posibil sa evitam refactorizarea matricei Lagrange la fiecare iteratie si in schimb sa actualizam factorii oricand se face o schimbare in A.

2.4.Proprietati avansate

Un algoritm modern pentru P.P. ar trebui stabilit pentru o aplicatie mai larga decat cele considerate pana acum; ar trebui sa rezolve problema de P.P. nedefinita si ar trebui sa nu permita utilizatorului sa poarte dinainte informatia eficienta de la o calculare anterioara a P.P., atunci cand o secventa de probleme trebuie rezolvata.Aceste extinderi sunt luate in considerare in aceasta sectiune.P.P. nedefinita se refera la cazul in care nu se cere ca hessiana G sa fie pozitiv definita, deci adesea va fi nedefinita, desi sunt incluse si cazurile negativ si pozitiv semi-definita.Pentru P.P. cu restrictii ecuatii nu apar dificultati si exista o solutie unica globala daca si numai daca matricea hessiana redusa ZTGZ este pozitiv definita.Totusi, cand sunt prezente inegalitati si se exclude cazul pozitiv semi-definit, este posibil sa existe solutii locale care nu sunt globale.Problema de optimizare globala este foarte dificila astfel ca algoritmii sunt folositi pentru gasirea unei solutii locale.De fapt, o modificare a metodei multimii active este folosita doar daca garanteaza gasirea unui punct Kuhn-Tucker pentru care hessiana redusa ZTGZ este pozitiv definita.Daca i*>0, i II*, atunci aceste conditii sunt suficiente pentro o solutie locala.Totusi , daca exista i*=0, iI I*, atunci este posibil ca metoda sa gaseasca un punct Kuhn-Tucker care nu este o solutie locala.In acest caz, de obicei exista mici perturbari arbitrare ale preoblemei (a) care fac punctul Kuhn-Tucker o solutie locala sau (b) care fac punctul sa nu mai fie un punct Kuhn-Tucker astfel ca metoda multimii active sa continuie sa gaseasca o solutie locala mai buna.Totusi, desi este teoretic posibil ca aceste situatii sa apara , in practica este imposibil si ,de obicei, algoritmul gaseste o solutie locala (adesea globala).

Dificultatea principala din rezolvarea problemei nedefinite de P.P. apare in mod diferit.Posibilitatea exista pentru o alegere arbitrara a lui A astfel ca matricea hessiana redusa care rezulta ZTGZ poate fi nedefinita astfel incat factorii sai LDLT pot sa nu existe sau pot fi instabili cu privire la propagarea de rotunjire.(De sigur , daca G este pozitiv definita , atunci nu apar probleme pentru ZTGZ).Intr-o oarecare masura, metoda spatiului nul evita aceasta dificultate.Initial x(1) este un vertex astfel ca spatiul nul (1.9) are dimensiunea zero si dificultatea nu apare.De asemenea daca ZTGZ este pozitiv definita pentru multimea A data si o restrictie este adaugata la A,atunci noul spatiu nul este o submultime a celei dinainte, astfel ca noua matrice ZTGZ are cu o dimensiune mai putin si este si pozitiv definita.

Deci dificultatea apare la pasul (c) din (3.4).In acest caz x(k) rezolva P.E. actuale si ZTGZ este pozitiv definita.Totusi, cand un indice de restrictie q este inlaturat din A , dimensiunea spatiului nul creste si se adauga in plus la Z o coloana.Aceasta cauzeaza in plus o linie si o coloana ce trebuie adaugate la ZTGZ si este posibil ca matricea ce rezulta sa nu fie pozitiv definita.Calcularea noilor factori LDLT este doar pasul obisnuit pentru extinderea factorizarii Choleski, dar cand ZTGZ nu este pozitiv definita noul element din D este ori negativ ori zero.Aceasta impica faptul ca , corectia (k) care este un punct stationar al (3.1) nu mai este minima, astfel ca trebuie aleasa directia de cautare s(k) la pasul (d) pentru (3.4).Deoarece x(k) nu este

punct Kuhn-Tucker , directiile de cautare admisibile exista si orice astfel de directie poate fi aleasa pentru s(k) .O posibilitate este sa se considere linia cauzata de cresterea slabirii restrictiei q la x(k) .Asfel bq este schimbat in bq+ si din (2.4) directia de cautare ce rezulta este s(k)=Teq , coloana din T corespunzatoare restrictiei q.De fapt atunci cand D are un element negativ aceasta este echivalenta cu alegerea s(k)= - (k) unde (k) este punctul stationar din (3.1) pentru problema actualizata.In acest caz , unitatea pasului (k)=1 in (3.2) nu mai are semnificatie.Astfel , modificarea ceruta in (3.4) cand D are un element negativ este sa alegem s(k)= - (k) la pasul (d) si sa rezolvam (3.2) pentru a obtine (k) la pasul (e).Daca D are un element zero poate fi inlocuit de - ,unde >0 este neglijabil.Aceasta cauzeaza ca s(k) sa fie foarte mare , dar dimensiunea lui s(k) nu are importanta pentru rezolvarea (3.2).Este posibil ca (3.2) sa nu aiba solutie;acesta este modul in care o solutie nemarginita a P.P. nedefinita este indicata.Se poate vedea ,prin calcul ,ca nu exista nici o dificultate reala,daca se fac schimbarile de mai sus.Situatia in care D are un singur element negativ este doar temporara ,de vreme ce algoritmul continua prin adaugarea restrictiilor,reducand dimensiunea spatiului nul, pana cand solutia unei P.E. este gasita, caz in care matricile ZTGZ si D sunt pozitiv definite.Singura posibilitate nefavorabila este aceea ca nu este marginit elementul negativ din D.Astfel, cand acest element este calculat , eroarea de rotunjire care rezulta poate fi semnificativa.De aceea Gill si Murray (1978) sugereaza ca aceasta posibilitate este monitorizata si daca se observa un element negativ mare ,atunci factorii sunt recalculati in alta etapa.

O posibilitate alternativa care evita aceasta problema de rotunjire este urmatoarea: cand se determina o restrictie q ca la pasul (c ), atunci poate fi lasata in A ca o pseudo-restrictie.Vectorului din dreapta bq I se permite sa creasca la bq+α si urmeaza directia de cautare s(k)=Teq descrisa mai sus.Daca o noua restrictie p devine activa in linia de cautare, atunci p este adaugat la A si procesul continua.Doar cand solutia unei P.E. se gaseste intr-o secventa a liniei de cautare, atunci indicele q este inlaturat din A.Aceasta abordare are avantajul ca toate matricile hessiene reduse ZTGZ care sunt calculate sunt pozitiv definite.Dezavantajul este ca apar situatii degenerate aditionale cand vectorul de intrare apde la pasul (f) din (3.4) este dependent de vectorii ai,i A q.Aceasta apare cel mai evident cand se face schimbarea de la un vertex la altul, ca in programarea liniara.Un posibil remediu este sa avem formule pentru a actualiza factorii matricei Lagrange cand se face un schimb de indici ai restrictiilor din A (ca in metoda simplex din programarea liniara).O idee de acest fel este folosita de Fletcher (1971) si ar trebui practicata cu metode mai stabile ,dar inca nu a fost investigata.

O alta trasatura importanta a algoritmului P.P. este aceea ca ar trebui sa permita informatiei sa fie trecuta dinainte de la o calculare anterioara a P.P. atunci cand problema a fost perturbata doar de o mica cantitate .Aceasta este un exemplu de programare parametrica.In acest caz ,poate fi avatajos sa se rezolve o P.E. initiala cu multimea activa A dintr-o calculare anteriora a P.P.Punctul ce rezulta x(1)va rezolva noua problema de P.P.Daca A este neschimbata atunci Z trebuie recalculata in majoritatea metodelor si daca si G este neschimbata, atunci ZTGZ nu se schimba ,astfel ca factorii sai trebuie recalculati.Sunt totusi unele potentiale dificultati.Daca A se schimba , atunci ar putea sa-si piarda rangul si astfel pot apare dificultati de rotunjire.In problemele de P.P. nedefinite , daca se schimba A sau G atunci s-ar putea ca

ZTGZ sa nu mai fie pozitiv definita.Totusi, sunt solutii posibile pentru aceste dificultati, fara sa abandonam incercarea de a folosi o multime activa anterioara.O alta posibilitate este aceea ca solutia intiala x (1) a P.E. este neadmisibila in raport cu anumite restrictii i A .In acest caz este preferabil sa nu incercam sa gasim un vertex admisibil.O idee mai buna este sa inlocuim vectorii din dreapta bi ai restrictiilor incalcate cu bi +θ si sa gasim solutia problemei de P.P. cu θ↓0 .O abordare alternativa se bazeaza pe folosirea unei functii de penalitate exacta cum este descrisa in (3.5).

Un alt aspect al programarii parametrice este in gasirea sensibilitatii solutiei asociata schimbarilor lui g si b.Rata rezultata prin schimbarea lui x* si λ* se obtine prin inlocuire in (2.4) si (2.5) si efectul asupra lui q(x*) prin folosirea definitiei lui q(x) din (1.1).Se observa ca dq/dbi este apropiat de λi*.Aceste estimari pot fi invalide daca exista multiplicatori pentru care

i*=0,i II*.

2.5.Probleme speciale de programare patratica

In unele cazuri problemele de P.P. au o structura speciala care este utilizata cu scopul de a obtine o mai buna eficienta sau stabilitate.Anumite posibilitati sunt descrise in aceasta sectiune.Un caz important apare atunci cand singurele restrictii din problema sunt marginile

li≤xi≤ui , i=1,2,…,n (5.1)

unde orice ui sau -li poate fi ∞ si li≤ui.Astfel vectorii ai sunt ħei si este posibil ca P.E. sa fie exprimata (dupa ce se permuta variabilele astfel incat marginile active sa fie primele m variabile) sub forma:

I m 0 m

A=Y= Z=V= (5.2)

0 n-m I n-m

si ZTGZ=G22 (vezi definitia dinainte (1.3)).Astfel nu este nevoie ca Z sa fie calculata si acest lucru poate fi folosit in metode speciale cu un anumit scop.Singura actualizare necesara este pentru factorii LDLT ai matricei ZTGZ.De asemenea , din (1.14) multiplicatorii (k) la solutia unei P.E. sunt chiar elementele corespunzatoare lui g(k) in raport cu Y de mai sus.O alta proprietate a acestei probleme este ca nu poate apare degenerarea in restrictii.De asemenea nu sunt dificultati pentru P.P. nedefinita in folosirea metodei a doua (bazata pe pseudo-restrictii) descrisa in Sectiunea 2.4.Singura formula de schimbare care se foloseste este aceea pentru inlocuirea unei margini inferioare pentru xi cu marginea superioara si vice versa ,ceea ce este trivial. Pseudo-restrictiile sunt importante pentru calcularea unui vertex initial pentru problema, in special daca ui si -li sunt mari.Metode pentru aceasta problema sunt date de Fletcher si Jackson (1974) si de Gill si Murray (1976).Metoda de mai tarziu actualizeaza o

G22 G12

factorizare partiala a matricei

G21 G11

Acum este de preferat sa actualizam factorii LDLT ai matricei G22 cum s-a aratat mai sus.

Un alt caz special al P.P. apare atunci cand G este o matrice diagonala pozitiv definita.Prin scalarea variabilelor,functia obiectiv poate fi scrisa cu G=I astfel

q(x)=(1/2)xTx+gTx (5.3)

Problema ce rezulta se numeste problema distantei minime deoarece solutia x* pentru (1.1) poate fi interpretata ca punctul admisibil cel mai apropiat de punctul x= -g (dupa ce se scrie (5.3) ca (1/2)║x+g║22 si se ignora termenii constanti ).Din nou este potrivita metoda cu un scop special , deoarece alegerea Z=Q2 este avantajoasa pentru ZTGZ=ZTZ=I.Astfel nu trebuie facuta nici o pregatire speciala pentru actualizarea factorilor ZTGZ si sunt necesare doar operatiile de actualizare pentru Z, pentru care pot fi folosite formulele lui Gill si Murray(1978).Deoarece G este pozitiv definita , nu apare nici o dificultate speciala.

Mai apare un alt caz special al P.P. atunci cand problema este sa se gaseasca solutia celor mai mici patrate pentru ecuatiile liniare

Bx=c (5.4)

Unde B est de p×n si cI Rp,asociat la restrictiile din (1.1).In acest caz functia obiectiv este suma patratelor definite atfel:

q(x)=(Bx-c)T(Bx-c) (5.5)

Este posibil sa continuam ca la metoda standard cu G=BTB si g= -BTC, dupa ce impartim prin doi si omitem termenii constanti.Totusi, se stie ca forma explicita BTB dintr-o calculare patratica liniara minima cauzeaza aparitia 'efectului patratic' prin care se pot pierde doua sau mai multe figuri semnificative ,atat cat este necesar.De aceea este din nou avantajos sa avem o rutina scop speciala care evita dificultatea.Aceasta se poate realiza prin actualizarea factorilor matricei BZ.Astfel:

U

BZ=P =P1U (5.6)

este definita, unde P este p×p ortogonala, U este (n-m)×(n-m) superior triunghiulara, P1 este formata din primele n-m coloane ale lui P.Urmeaza ca UT U sa fie factorizarea Choleski a ZTGZ (=ZTBTBZ) si astfel poate fi folosita pentru rezolvarea (1.3) sau (3.1).

In sfarsit, un caz special al P.P. pentru cele mai mici patrate foloseste doar marginile variabilelor considerate.Este posibil sa se introduca o metoda suplimentara cu scop special, asemanatoare cu cele descrise mai sus , in care, folosind (5.2) si (5,6) B este scris [B1:B2] si factorii P1U ai lui B2 sunt folositi pentru rezolvarea P.E.O posibilitate alternativa este sa se transforme problema intr-o problema de distanta minima folosind duala Wolfe.De exemplu , problema de P.P.:

Inf.(1/2)xTBTBx+gT

x (5.7)

pentru x≥0

devine:

sup (1/2) xTBTBx+gTx - Tx (5.8)

x,

pentru BTBx+g-

(5.10)

Eliminand din (5.8) , folosind (5.9) si scriind Bx=u se obtine problema distantei minime:



Inf (1/2)uTu

u (5.11)

pentru BTu≥-g

Sistemul poate fi rezolvat prin metoda descrisa mai sus,obtinand solutia u*.Solutia x* pentru (5.7) poate fi aflata si prin alta metoda.Se aplica pentru (5.11) transformarea duala si se observa usor ca duala pentru (5.11) este (5.7) si astfel vectorul x este vectorul multiplicativ pentru restrictiile din (5.11).Astfel xi*=0 daca i corespunde unei restrictii inactive la solutia pentru (5.11).Mai mult,este disponibila o factorizare a coloanelor lui B corespunzatoare restrictiilor active astfel incat elementele ramase ale lui x* pot fi determinate din Bx*=u*.Astfel, problemele celor mai mici patrate marginite pot fi reduse la probleme de distanta minima si vice versa.

2.6.Pivotarea complementara si alte metode

Un numar de metode pentru P.P. au fost sugerate ca extensii ale metodei simplex pentru programarea liniara.Cea mai noua metoda este algoritmul Dantzig-Wolfe (Danzig 1963) care rezolva conditiile Kuhn-Tucker pentru P.P.

Inf.(1/2)xTGx+gTx

x (6.1)

pentru ATx≥b , x≥0

Itroducand multiplicatorii pentru restrictiile ATx≥b si pentru marginile x≥0 se obtine functia Lagrange:

L(x, )=(1/2) xTGx+gTx- T(ATx-b)- Tx    (6.2)

Definim variabilele ecart r =ATx-b si conditiile Kuhn-Tucker devin:

-Gx+A =g

r-ATx= -b (6.3)

,r,x, Tx=0 , rT

Metoda presupune ca G sa fie pozitiv definita, care este conditia suficienta pentru ca orice solutie pentru (6.3) sa rezolve (6.1).Sistemul (6.3) poate fi exprimat si sub forma :

w-Mz=q (6.4)

w≥0, z≥0, wTz=0

p x G -A g

w= , z= , M= ,q= (6.5)

r l AT 0 -b

Astfel se obtine problema complementaritatii liniare (P.C.L.) si se mai pot exprima in acest fel probleme din teoria jocurilor sau din problemele de calculare a valorilor marginite.Metoda Dantzig-Wolfe pentru rezolvarea (6.3) ofera metoda pivotarii principale pentru rezolvarea problemei (6.5) si este prezentata in continuare.Totusi, toate metodele pentru rezolvarea (6.4) au unele proprietati comune.Acestea efectueaza operatii liniare asupra ecuatiilor de la (6.4) intr-o maniera apropiata cu problema liniara.Astfel ambele variabile w si z sunt rearanjate ca variabile bazice (B) si nebazice (N): xB si xN.La o etapa generala, se poate folosi reprezentarea tabelara

xB

[I:A^] =b^ (6.6)

xN

a ecuatiilor din (6.4) si variabelele au valorile xB=b^ si xN=0.Se alege pentru a fi marita o variabila xq, q N si efectul asupra lui xB din (6.6) este dat de

xB = b^ -a^qxq (6.7)

unde a^q este coloana din A^ corespunzatoare variabilei xq .Un element xi, iIB devine zero cand xq=bi^/aiq^.Aceasta determina ca unele variabile xp sa devina zero si astfel p si q sunt interschimbate intre B si N ca in programarea liniara.Tabelul este apoi rearanjat prin efectuarea operatiilor liniare care reduc coloana veche xq a tabelului la un vector unitate.Algoritmul se termina cand b^≥0 si cand solutia este complementara,adica zi IB <=> wi IN si zi IN<=> wi IB, pentru toti i.

Metoda de pivotare principala este initializata de xB=w,xN=z,A^= -M si b^=q.Aceasta este complementara si deci algoritmul se termina daca b^≥0.Daca nu,exista un element xt IB pentru care bt^<0 (daca exista mai multi se alege elementul cel mai negativ).

Tabelul 6.1: Tabelul pentru metoda de pivotare principala

B

p

p

r1

x1

x2

l

b^

p

p

r1

x1 p

p

x1

r1

x2 r1

p

x1

x2

l p

l

x1

x2

Se alege apoi variabila complementara xq IN pentru a fi marita (xt si xq sunt complementare daca (xt si xq ) pot fi identificate ca (wi,zi) sau (zi,wi) pentru un anumit i).Efectul asupra variabilelor de baza se observa cu ajutorul relatiei (6.7).Atat timp cat toate variabilele nenegative din B raman nenegative,atunci xq se mareste pana cand xt↑0.Apoi xq si xt sunt interschimbate in B si N si tabelul este actualizat; tabelul rezultat este tot complementar ,astfel ca iteratia poate fi repetata . Se poate intampla ca atunci cand xq este marit , variabila de baza xp↓0.In acest caz se realizeaza o interschimbare pivot pentru a obtine un tabel necomplementar.La urmatoarea iteratie , complementara lui xp se alege pentru a fi marita .Daca aceasta cauzeaza ca xt↑0 , atunci este restabilita complementaritatea si algoritmul poate continua ca mai sus.Totusi, un xp diferit poate deveni zero, caz in care se repeta aceeasi operatie de crestera a complementarei.Excluzand degenerarea , fiecare iteratie mareste xt astfel ca o eventuala complementaritate este restabilita.Un exemplu de aplicare a metodei pentru problema de la Sectiunea 2.7. este dat in Tabelul 6.1.Metoda Dantzing -Wolfe difera printr-un singur aspect de metoda de pivotare principala si anume prin faptul ca permite variabilelor de baza corespunzatoare variabilelor λ si π din (6.3) sa ramana negative in timpul cautarii. Metoda Dantzing -Wolfe este ilustrata in Tabelul 6.2 si se pot observa diferentele dintre Tabelul 6.1.Nu este dificil de aratat ca metoda Dantzing -Wolfe este echivalenta cu metoda multimii active primala (3.4).O solutie complementara este echivalenta cu solutia unei P.E. si alegerea celui mai negativ xt este analog cu (3.3).Cazul cand xt↑0 este acelasi cu alegerea α(k)=1 in (3.2) si cazul xp↓0 este echivalent cu α(k)<1 cand o restrictie inactiva devine activa in linia de cautare.Aceste proprietati se pot observa in Tabelul 6.2.Rezolvarea problemei prin forma tabelara are avantajul simplitatii pentru o problema mica si poate oferi un algoritm compact pentru aplicatiile pe calculator.Totusi,forma tabelara este dezavantajoasa: nu exploateaza eficient factorizarea matricei Lagrange si in shimb este esentiala actualizarea matricei inverse care poate fi instabila numeric.Variabilele ecart pentru toate inegalitatile sunt necesare , astfel ca tabelul poate fi largit.Se rezolva doar o forma restrictionata (6.1) a problemei P.P. si metoda poate esua pentru P.P. nedefinita.Astfel,in general, se prefera un algoritm modern pentru metoda multimii active.

Tabelul 6.2: Tabelul pentru metoda Dantzig -Wolfe

B

p

p

r1

x1

x2

l

b^

p

p

r1

x1 p

x1

p

r1

x2 r1

x1

p

x2

l p

x1

l

x2

Un algoritm diferit pentru rezolvarea problemei complementaritatii liniare (6.4) ete atribuit lui Lemke (1965).In aceata metoda tabelul este extins prin adaugarea in plus a unei variabile z0 si a coloanei corespunzatoare -e= -(1,1,…,1)T la A^.Problema (6.4) este initializata de xB=w, xN=( z0 ,z), A^=(-e,-M), b^=q si valorile variabilelor sunt xN=0 si

xB=b^.Daca b^≥0 atunci aceasta este solutia; altfel se mareste z0 in (6.6) pana cand toate variabilele w sunt nenegative.Algoritmul incearca acum sa reduca z0 la zero.Efectul pasului initial este sa conduca o variabila (xp) la zero (corespunzatoare celui mai negativ qi).Apoi xp si z0 se interschimba in pasul pivot si complementul lui xp este marit la inceputul celei de-a doua iteratii.In general, se interschimba la pasul pivotului variabila ce trebuie marita si variabila care se reduce la zero.Apoi urmatoarea variabila ce trebuie marita este complementara celei ce trebuie redusa la zero.Algoritmul se termina cand z0 devine zero, ceea ce da o solutie pentru (6.4).Un exemplu de metoda aplicata problemei de la Sectiunea 2.7. este dat in Tabelul 6.3.O observatie despre metoda este ca includerea termenului z0 face ca fiecare tabel din metoda sa fie o solutie a problemei in forma modificata (6.1) in care g este inlocuit de g+z0e si b de b- z0e.Astfel metoda Lemke poate fi privita ca o solutie a programarii parametrice pentru (6.1) in care solutia este gasita ca parametrul z0 ↓0.Pasul la care πi↓0 sau λi↓0 corespunde unor margini sau restrictii active ce devin inactive cand z0 este micsorat.Pasul la care xi↓0 si ri↓0 corespunde unor margini sau restrictii inactive ce devin active.Un avantaj al algoritmului Lemke este ca nu necesita tehnici speciale pentru rezolvarea degenerarii.O forma a algoritmului Lemke fara variabila

z0 apare daca este o anumita coloana mq≥0 in M asfel incat mjq>0 cand qj<0.Apoi este posibil un pas initial pentru a-l mari pe zq , care face din (6.6) pe w≥0.Apoi algoritmul continua ca mai sus si se termina cand se obtine complementaritatea (vezi Sectiunea 2.7.).

Exista o forma generala mai interesanta a problemei P.C.L.Problema L1 a P.P. la care se face referire in (3.5) poate fi de asemenea exprimata folosind un tabel de P.C.L., dar cu margini inferioare si superioare pentru ambele variabile primale si duale.

Tabelul 6.3:Tabelul pentru metoda Lemke

B

p

p

r1

z0

x1

x2

l

b^

p

p

r1

z0 p

z0

p

r1

x1 p

z0

x1

r1

x2 r1

z0

x1

x2

l z0

l

x1

x2

O tehnica mai noua pentru P.P. este metoda Beale care a fost dezvoltata tot ca o extindere a programarii liniare.Totusi, metoda poate fi descrisa pe scurt ca o metoda a multimii active in felul urmator.Se considera metoda multimii active pentru programarea liniara aplicata pentru a minimiza o functie patratica.Daca linia de cautare k se termina prin gasirea unei restrictii minime, atunci diferenta dintre gradienti γ(k)=g(k+1)-g(k) este schimbata cu restrictiile normale in matricea A.Dupa o secventa de pasi in care restrictiile sunt inlaturate din A efectul este ca directia de cautare s(k+1) este ortogonala cu vectorii γ(1),…, si deci si conjugata cu s(1),…,s(k).Asfel se introduce posibilitatea de terminare patratica.Din pacate, daca o restrictie inactiva anterioara devine apoi activa, secventa de directii conjugate este rupta.Pentru a se restabili aceasta, metoda Beale necesita anumite iteratii neproductive in care vectorii irelevanti γ(j) sunt inlaturati din matricea A.Posibilitatea de rearanjare a tabelului pentru a evita aceste iteratii a fost studiata de Benveniste (1979).Metoda devine apoi apropiata de metoda Murray (1971)care de asemenea recurge la directii conjugate.Cu cat este actualizata inversa matricei , cu atat mai mult se prefera factorizarea stabila descrisa in Sectiunea 2.1.Relatiile dintre metoda multimii active,metoda Dantzig -Wolfe,metoda Bale si altele sunt discutate mai pe larg de Goldfarb(1972).

2.7.Exercitii

7.1Pornind de la x(1) =0, sa se ilustreze pasii din metoda multimii active primale pentru rezolvarea urmatoarei probleme de P.P.

inf x12-x1x2+x22-3x1

x

pentru x1≥0

x2≥0

-x1-x2≥-2

Verificati echivalenta metodei cu metoda Dantzig-Wolfe. (Tabelul 6.1,Tabelul 6.2 ).

7.2.Stabiliti problema complementaritatii liniare aparuta la problema 7.1 si aratati ca satisface conditiile de aplicabilitate pentru forma modificata a metodei Lemke.( Tabelul 6.3).

Bibliografie

1.C.Zidaroiu si S.Stefanescu,'Cercetari operationale'.

2.Albert G. Holzman,'Operations Research Methodology'.

3.R.Fletcher, 'Practical methods of optimization'.









Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 801
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2020 . All rights reserved

Distribuie URL

Adauga cod HTML in site