Przykªadowe kolokwium wykªadowe z Metod i Algorytmów Optymalizacji Imi¦ . . . . . . . . . . . . Nazwisko . . . . . . . . . . . . . . . . . . Nr indeksu . . . . . . . . .

Odpowied¹

Punktacja

poprawna

1

brak odpowiedzi

0

bª¦dna

-0,5

UWAGA: W pust¡ kratk¦ po lewej stronie ka»dej odpowiedzi nale»y wpisa¢ sªowo:

TAK, je»eli odpowied¹ jest poprawna,

NIE, je»eli odpowied¹ jest bª¦dna,

lub pozostawi¢ puste miejsce, je»eli nie znamy odpowiedzi na to pytanie.

1) Niech D ⊂ n

R , Int D 6= ∅, f : D → R klasy C2 na Int D, x0 ∈ Int D oraz f osi¡ga w x0 maksimum lokalne, wówczas na pewno

∇f (x0) = 0 n,

R

Hf (x0) jest ujemnie okre±lona,

∃ r > 0 ∀ x ∈ K(x0, r) \ {x0} f (x) < f (x0).

2) Niech f : n

R → R korecywna i ci¡gªa, wtedy na pewno

f osi¡ga minimum globalne,

f osi¡ga ±cisªe minimum lokalne,

lim

1

= +∞.

k

f (x)

xk→+∞

3) Niech D ⊂ n

R

wypukªy, f : D → R wypukªa na D. Wówczas na pewno f jest ±ci±le wypukªa na D,

−f jest wkl¦sªa na D,

epi f jest wypukªym podzbiorem

n

R .

4) Niech U ⊂ n

R otwarty, wypukªy, f : U → R klasy C2 na U , taka, »e Hf (x) jest dodatnio okre±lona dla ka»dego x ∈ U . Wtedy na pewno

f osi¡ga ±cisle minimum globalne w ka»dym punkcie krytycznym f , f jest wypukªa na U ,

∀ (x, y ∈ U, x 6= y)

f (x) + ∇f (x), y − x < f (y).

5) Niech dany b¦dzie

(g(t

Qm

1, . . . , tm) = Pn

c

(t

i=1 i

j=1

j )αij

→ min

(GP )

gdzie t1, . . . , tm > 0.

Przez (DGP ) oznaczamy problem dualny do (GP ). Wówczas na pewno je»eli t? jest rozwi¡zaniem (GP ), a δ? jest rozwi¡zaniem (DGP ), to g(t?) ≤ v(δ?).

je»eli (DGP ) nie jest zgodny, to (GP ) nie ma rozwi¡zania,

wektor (δ1, . . . , δn) taki, »e Pn δ

α

i=1

i = 1, Pn

i=1

ij δi = 0, j = 1, . . . , m oraz δ1 = −δ2, jest wektorem dopuszczalnym dla (DGP ).

6) Niech x

n

0 ∈ R , r > 0 oraz kx0k > r. Wtedy na pewno K(x

n

0, r) jest wypukªym podzbiorem w R ,

mo»na zastosowa¢ twierdzenie o podpieraniu do punktu x0 i zbioru K(0 n, r), R

mo»na zastosowa¢ twierdzenie o oddzielaniu do punktu x0 i zbioru K(0 n, r).

R

7) Niech dany b¦dzie problem wypukªy

f(x) → min









przy ograniczeniach

(P )

g



1(x) ≤ 0, g2(x) ≤ 0, . . . , gm(x) ≤ 0,







x ∈ C.

Zaªó»my, »e funkcja MP (·) ma niepust¡ dziedzin¦ - DMP . Wówczas na pewno funkcja MP (·) jest ci¡gªa,

∀ z1, z2 ∈ DMP

z1 ≤ z2 ⇒ M P (z2) ≤ M P (z1),

M P = M P (0 m ).

R

8) Niech dany b¦dzie superzgodny problem wypukªy (P ) postaci takiej jak w pytaniu 7). Zaªó»my, »e x? ∈ C jest rozwi¡zaniem dla (P ). Wówczas na pewno

gi(x?) ≤ 0, i = 1, . . . , m,

h

i

∃ λ? ∈

m

m

R

∀ x ∈ C ∀ λ ∈ R L(x?, λ) ≤ L(x?, λ?) ≤ L(x, λ?) ∧ λ?g

,

i i(x?) = 0, i = 1, . . . , m

∃ λ? ≥ 0 (x?, λ?) jest punktem siodªowym dla lagran»janu (P ).

9) Niech dany b¦dzie problem wypukªy (P ) postaci takiej jak w pytaniu 7), który posiada wektor wra»liwo±ci λ.

Wtedy na pewno

∀ z ∈

m

R

M P (z) ≥ M P − λ, z,

je»eli funkcja MP (·) jest ró»niczkowalna w 0 m, to λ = ∇MP (0 m), R

R

je»eli λ1 = 0 oraz e1 nale»y do dziedziny MP (·), to MP = MP (e1).

f(x) → min





10) Niech U ⊂ n

R

otwarty, f, g : U → R klasy C1 na U. Niech dany b¦dzie problem przy ograniczeniu



g(x) = 0, x ∈ U.

Wówczas na pewno

ka»dy wektor dopuszczalny dla powy»szego problemu jest regularny, je»eli x? jest lokalnym minimum i punktem regularnym dla powy»szego problemu, to istnieje λ ≥ 0 taki, »e

∇f (x?) + λ∇g(x?) = 0 n,

R

je»eli x? jest lokalnym minimum i punktem regularnym dla powy»szego problemu, to istnieje λ ∈ R taki,

»e ∇f(x?) + λ∇g(x?) = 0 n.

R