Quadratic Programming

Cilj ovoga rada je prikazati problem pronalaženja optimalnog rješenja (ili optimalnih rješenja ukoliko ih ima više) optimizacijskog problema u kojemu je funkcija cilja kvadratna, a ograničenja su dana u obliku linearnih jednadžbi i/ili nejednadžbi. U radu ćemo promatrati uglavnom problem minimizacije, odnosno nastojat ćemo naći točku ili točke globalnog minimuma funkcije cilja na dopustivom području (području određenom nekim danim ograničenjima) te vrijednost funkcije cilja u tim točkama. Na početku rada definirat ćemo kvadratnu funkciju više varijabli, pozitivno semidefinitne i pozitivno definitne matrice, konveksnu funkciju te dati uvjet kada je kvadratna funkcija konveksna. Nadalje ćemo navesti uvjete koje svako optimalno rješenje ovog problema nužno mora zadovoljavati (Karush-Kuhn-Tuckerovi uvjeti) i njihovu primjenu na problem kvadratnog programiranja. U dugom djelu rada upoznat ćemo se s metodom unutarnje točke, kao algoritmom za rješavanje kvadratnog problema optimizacije i opisati Newtonovu metodu za rješavanje sustava nelinearnih jednadžbi na kojoj se navedena metoda i temelji. Međutim, zbog postojanja ograničenja nenegativnosti, Newtonova metoda za generiranje novih procjena rješenja ne može se izravno primijeniti. Stoga je potrebno napraviti prilagodbe u smjeru traženja optimalnog rješenja te ćemo u radu razmatrati tzv. usmjerene Newtonove puteve i iznijeti koncept središnjeg puta. Na kraju rada dat ćemo konkretan primjer za izradu optimalnog portfelja temeljenog na problemu kvadratnog programiranja, nakon čega ćemo provesti detaljnu analizu rješenja danog problema