Aceastã monografie este expresia unei insatisfacþii pe care am trãit-o în ceea ce priveºte slãbiciunea dezvoltãrilor "pur teoretice" ale algoritmilor de optimizare, priviþi din punctul de vedere al practiþionistului. Ca atare, lucrarea se centreazã pe propunerea ºi justificarea unei noi abordãri a analizei convergenþei ºi complexitãþii algoritmilor de optimizare bazatã pe o conjugare a eforturilor empirice cu cele teoretice din acest domeniu.

În lucrarea "Convergenþa Algoritmilor de Optimizare", Editura Tehnicã - Bucureºti, 2004, am prezentat în detaliu ºi riguros matematic convergenþa metodei Newton pentru optimizare fãrã restricþii, convergenþa metodelor simplex, a elipsoidului ºi a celor de punct interior pentru programarea liniarã, precum ºi a metodelor barierã ºi a planelor de secþiune pentru optimizarea cu restricþii. În acest sens, pentru calculul unei soluþii cu o acurateþe datã, am determinat formule închise care precizeazã numãrul de iteraþii corespunzãtor algoritmilor gradientului descendent ºi respectiv Newton pentru optimizare fãrã restricþii, precum ºi a metodei barierã pentru optimizarea cu restricþii. O analizã detaliatã este dedicatã convergenþei algoritmulor simplex ºi a elipsoidului pentru programarea liniarã. Critica care se poate aduce acestor dezvoltãri teoretice este cã formulele care precizeazã complexitatea acestor algoritmi depind de un numãr de constante, care pentru majoritatea aplicaþiilor practice sunt total necunoscute. Mai mult, pentru optimizarea neliniarã, formulele respective sunt valabile numai pentru anumite tipuri de funcþii care au anumite proprietãþi speciale de convexitate ºi diferenþiabilitate, în speþã funcþii tare convexe, cel puþin de douã ori continuu diferenþiabile cu Hessian funcþie Lipschitz. Dezvoltãrile teoretice privind aceste rezultate s-au obþinut în ipoteze foarte tari care nu se probeazã nici odatã în practicã. Pe lângã acestea, demonstraþiile teoremelor respective sunt complicate, pline de imaginaþie ºi care nu se încadreazã într-un tipar cunoscut. Toate aceste eforturi care se concretizeazã în formule referitoare la complexitatea algoritmului fundamental de optimizare - algoritmul Newton -, ºi a algoritmului barierã pentru optimizarea cu restricþii nu au o valoare practicã, ci doar una conceptualã, reprezentând performanþe intelectuale care arãtã cã pentru cazul funcþiilor considerate algoritmii respectiv converg pãtratic la soluþie dacã punctul iniþial este în imediata vecinãtate a punctului de optim. Evident cã aceste rezultate sunt excepþionale, în sensul cã aratã substanþa domeniului programãrii matematice, de a beneficia de algoritmi bine justificaþi matematic, care cel puþin în anumite situaþii dau o anumitã siguranþã ºi încredere domeniului. Ideea este cã dacã pentru aceste clase de probleme existã algoritmi cu asemenea proprietãþi, atunci este posibil ca performanþele acestora sã nu se degradeze prea mult în ipoteze mai largi.

Scopul monografiei. Efortul depus în aceastã monografie constã în construcþia unei ºtiinþe a empirismului în analiza algoritmilor de optimizare, ca o alternativã la foarte sofisticatele dezvoltãri teoretice ale domeniului. Ideea este cã analiza experimentelor computaþionale controlate, în contextul esenþei algoritmilor, furnizeazã o alternativã serioasã în ceea ce priveºte determinarea complexitãþii algoritmilor de optimizare. Substratul profund este acela al conjugãrii efortului teoretic cu cel empiric, computaþional, cu scopul de a înþelege funcþionarea algoritmilor de programare matematicã.

Structura ºi descrierea monografiei. Monografia este structuratã în cinci capitole. Primul capitol are un caracter introductiv. Pentru început se prezintã câteva opinii privind conceptul de problemã. Se aratã cã aceasta se poate defini ca o chestiune de admisibilitate. Mai mult, în esenþa ei, orice problemã se poate reformula ca una de optimizare. Tot aici se prezintã structura algoritmilor de optimizare. Se aratã cã orice algoritm de optimizare este un sistem dinamic în care starea acestuia este datã de variabilele problemei, iar mãrimea de intrare este lungimea pasului de deplasare. Totodatã se prezintã reformularea problemelor de optimizare neliniarã ca ecuaþii diferenþiale ordinare, precum ºi algoritmi de rezolvare bazaþi pe integrarea acestor ecuaþii. Pentru optimizarea fãrã restricþii se prezintã un algoritm original bazat pe aceastã metodã care este de puterea algoritmului Newton. Capitolul doi are o poziþie cu totul specialã în cadrul acestei monografii. Considerând o lucrare cu acest titlu, - "Teorie versus empirism în analiza algoritmilor de optimizare" -, care în esenþa ei se referã la confruntarea de idei dintre raþionalism ºi empirism, ni s-a pãrut necesar sã facem o incursiune ceva mai detaliatã în profunzimile acestor miºcãri de idei, care au preocupat umanitatea de-a lungul a mai bine de 25 de secole. Cred cã toate concluziile care rezultã din studiul acestor poziþii filosofice poate furniza o justificare ºi o metodologie solidã a conjugãrii eforturilor empirice cu cele teoretice în analiza algoritmilor de optimizare. Problema tratatã în acest capitol este aceea a cunoaºterii. Studiul începe cu atitudinea lui Socrate ºi se terminã cu concluziile lui Kant, de la care încolo se constatã o separare clarã ºi definitivã a filosofiei de ºtiinþele de tip matematic. Poziþiile filosofice prezentate în acest capitol, concluziile care se decanteazã din studiul acestor poziþii, constituie fundamentul dezvoltãrii unei ºtiinþe a experimentelor computaþionale controlate în ceea ce priveºte analiza algoritmilor de optimizare. Se concluzioneazã cã cunoaºterea în general, ºi în particular în domeniul algoritmilor, se fundamenteazã pe empirism, se consolideazã pe raþionalism ºi se verificã prin calcul într-o atitudine scepticã, dubitativã. Capitolul trei prezintã critica raþiunii algoritmilor de optimizare. Aceasta se face separat pentru problemele de optimizare fãrã restricþii de cele de optimizare cu restricþii. Semnificaþia noþiunii de criticã utilizatã în titlul acestui capitol este aceea de întemeiere, de analizã profundã a limitelor convergenþei ºi complexitãþii algoritmilor fundamentali de optimizare: algoritmul Newton pentru optimizare fãrã restricþii ºi respectiv algoritmul barierã pentru optimizarea cu restricþii. Menþionãm faptul cã tratarea numai a metodelor Newton ºi barierã nu constituie o limitare în ceea ce priveºte critica raþiunii algoritmilor de optimizare. Algoritmul Newton pentru optimizare fãrã restricþii ºi respectiv algoritmul barierã pentru optimizare cu restricþii sunt algoritmi fundamentali în programarea matematicã. Toþi algoritmii de optimizare moºtenesc câte ceva din aceºti algoritmi fundamentali. Mai mult, toþi algoritmii de optimizare se structureazã în sensul apropierii proprietãþilor lor de acelea ale algoritmilor Newton ºi barierã. În esenþã, acest capitol este un rezumat, destul de detaliat, a lucrãrii noastre "Convergenþa Algoritmilor de Optimizare", Editura Tehnicã - Bucureºti, 2004. Capitolul patru este dedicat definirii unei ºtiinþe a empirismului în analiza algoritmilor de optimizare. Pentru început se considerã o criticã a testãrii algoritmilor aºa cum vedem cã se face astãzi. Într-adevãr, testarea algoritmilor de optimizare se face foarte formal urmãrindu-se doar punerea într-o luminã favorabilã a algoritmului de testat. Comparaþiile numerice care se fac între algoritmi în fapt se referã la comparaþii ale unor implementãri ale algoritmilor, dar dupã cum ºtim o implementare a unui algoritm, adicã programul de calcul asociat algoritmului, diferã foarte mult de algoritmul în sine. Apoi testarea algoritmilor se face pe un numãr foarte limitat de probleme de optimizare fãrã a se þine seama de esenþa algoritmului. Ideea este cã la ora actualã nu se cunosc generatoare de probleme de optimizare capabile sã elaboreze milioane de probleme pe care eventual sã se facã teste computaþionale. Chiar pentru cea mai simplã problemã de optimizare, programarea liniarã, nu se cunosc generatoare care sã formuleze probleme admisibile. De aceea, în aceastã formã, testarea nu aduce informaþie cu valoare adãugatã în procesul de înþelegere a algoritmului. În continuare, în acest capitol, se prezintã avantajele unei ºtiinþe empirice a algoritmilor, insistându-se asupra esenþei empirismului ºi a particularitãþilor lui în domeniul algoritmilor de optimizare. ªtiinþa empiricã a algoritmilor se defineºte ca ºtiinþa experimentelor computaþionale controlate. Aceasta ne plaseazã în contextul analizei numerice a algoritmilor. Direcþiile de dezvoltare ale unei ºtiinþe empirice a algoritmilor se structureazã în: utilizarea metodelor statistice în studiul rezultatelor empirice ale algoritmilor, utilizarea euristicã a experimentelor computaþionale ºi teoria NP-completitudinii. Capitolul cinci prezintã elementele de bazã ale ºtiinþei experimentelor computaþionale ale algoritmilor de optimizare. În esenþã aceastã ºtiinþã se defineºte ca ºtiinþa experimentelor computaþionale controlate. Este vorba de experimentele computaþionale asociate algoritmilor de optimizare. În acest sens se detaliazã câteva aspecte referitoare la principalele componente ale acestei ºtiinþe: proiectarea sistemului de testare a algoritmului; proiectarea algoritmilor stabili numeric; organizarea unei colecþii de probleme de test care sã evidenþieze toate caracteristicile ºi particularitãþile, numerice ºi structurale, ale clasei de probleme pentru care algoritmul respectiv a fost proiectat; identificarea unor „cazuri particulare" sau a unor „instanþieri particulare deosebite" ale problemei care pun algoritmul în dificultãþi numerice majore; definirea limitelor algoritmului; construcþia unor experimente computaþionale controlate; ºi interpretarea ºi analiza rezultatelor experimentelor computaþionale controlate. Toate acestea constituie subiecte foarte interesante, care au propria lor substanþã ºi care se pot dezvolta de sine stãtãtor. Noi am urmãrit aici doar precizarea conþinutului unei ºtiinþe a experimentelor computaþionale structurat de-a lungul acestor componente. Importanþa unei analize a datelor empirice furnizate de un algoritm de optimizare, în contextul esenþei lui, este ilustratã pe algoritmul simplex din programarea liniarã. În acest sens se defineºte cu precizie esenþa algoritmului simplex ºi apoi în cadrul acestei esenþe din rezultatele privind funcþionarea algoritmului se determinã o formulã închisã care dã numãrul de iteraþii ale acestui algoritm în funcþie de dimensiunile problemei. Ca o concluzie, monografia constituie o propunere privind o nouã abordare a analizei algoritmilor de optimizare, din punctul de vedere al convergenþei ºi complexitãþii, în care dezvoltãrile teoretice sunt conjugate cu eforturile empirice. Menþionãm faptul cã aceastã abordare se poate completa cu studiile privind „tranziþia fazelor" care urmãreºte un import masiv al ideilor din lumea fizicii în lumea algoritmilor de optimizare.

Adresabilitate. Monografia se adreseazã tuturor specialiºtilor interesaþi în construcþia unei filosofii a analizei performanþelor algoritmilor de rezolvare a problemelor de optimizare, din punctul de vedere al convergenþei ºi complexitãþii acestora. În fapt, monografia este o invitaþie de a participa la dezvoltarea ºi consolidarea domeniului programãrii matematice, în sensul identificãrii esenþei algoritmilor de optimizare ºi a scufundãrii acesteia în procesul de analizã a imensului material faptic obþinut din experimentele computaþionale asociate acestor algoritmi. Parcurgerea acestui material necesitã o serie de cunoºtinþe din domeniul filosofiei ºi logicii, precum ºi al algebrei liniare, calculului diferenþial ºi integral, inclusiv analizã convexã.

Mulþumiri. Autorul mulþumeºte Fundaþiei Alexander von Humboldt - Germania pentru generozitatea ºi solicitudinea cu care a ºtiut sã-l sprijine de-a lungul timpului, atât în perioada stagiului de aproape trei ani petrecuþi în câteva Universitãþi din Germania, cât ºi dupã aceea. De asemenea, autorul mulþumeºte celor câþiva colegi ºi prieteni cu care a discutat conþinutul acestei monografii. În acelaºi timp, autorul este recunoscãtor soþiei sale Mihaela ºi copiilor Denisa ºi Cosmin pentru afecþiunea ºi înþelegerea cu care l-au înconjurat ºi sprijinit în efortul de a concretiza o muncã depusã pe parcursul mai multor ani.

Bucureºti,
Septembrie 23, 2004