Tentin tekstisisältö

MAT-41120 Matemaattinen optimointiteoria 1
SSÄyyt Tentti 22.5.2006

Tentissä saa käyttää kirjallista materiaalia oman valinnan mukaan.
1. Tarkastellaan standardimuotoista primaali-duaaliparia
(LP) — min Tx (DP) — max bu
ehdoilla Ax=b, ehdoilla Aru<c,
x>0, u vapaa.

Tutki, ovatko seuraavat väitteet tosia vai epätosia. Anna lyhyt perustelu tai vastaesimerk-
ki.

a. Jos primaalilla on useita optimikantoja, niin ne ovat degeneroituneita.
b. Duaalitehtävän optimiarvo on suurempi kuin primaalitehtävän optimiarvo.

c. Oletetaan, että 97p 3 (, mutta primaalilla ei ole äärellistä optimia. Rajoitusyhtälön
Ax = b oikea puoli voidaan muuttaa sellaiseksi, että (LP):llä on äärellinen optimi.

 

2. Kirjoita seuraavan LP-probleeman duaali. W
min cPx
ehdoilla Aix < by,
Ayx = bo,
A3x> b3;
x>0,

missä A; € R”"*", i=1,2,3. Sievennä mahdollisimman yksinkertaiseen muotoon.

3. Oletetaan, että f : R* > R on konveksi ja jatkuvasti derivoituva. Oletetaan edelleen,
että x* on probleeman

min f(x

min 769
optimipiste, mutta y € R” ei ole optimipiste. Osoita, että d = x* — y on f:n vähenemis-
suunta pisteessä y.

4. Tarkastellaan probleemaa
(*) min f(x)
ehdoilla —4x=b.
a. Onko piste x = [3, —3]" probleeman KT-piste, kun
Fz,y) = (e D?+(y— 37, A=[11], b=0?
b. Olkoon x* probleeman (*) KT-piste ja oletetaan, että matriisin A vaakarivit ovat

lineaarisesti riippumattomia. Osoita, että pisteessä x* Lagrangen kerroinvektoreita A on
tarkalleen yksi.