Lösning till Tentamen TMA946/MAN280 Optimeringslära 020826

1a) Vi skriver om problemet på standardform och får med s_{1} och s_{2} som slack-

variabler

minimera z = −x_{1} − 2x_{2}
då  x_{1} − x_{2} − s_{1} = 1,
x_{1} + x_{2} + s_{2} = 2,
x_{1}, x_{2}, s_{1}, s_{2} ≥ 0.

Observera att vi har bytt tecken på målfunktionen då vi hade ett maximeringsproblem. Vi ser ingen uppenbar tillåten bas, därför tar vi och inför en artificiell variabel, vilket ger FASI problemet

minimera w =  a
då  x_{1} − x_{2} − s_{1} + a = 1,
x_{1} + x_{2} + s_{2} = 2,
x_{1}, x_{2}, s_{1}, s_{2}, a ≥ 0.

Vi väljer a, s_{2} som vår bas. Vi beräknar reducerade kostnaden, vilken ges av

c̄^{T} = c_{N}^{T} − c_{B}^{T}B^{−1}N

vilket för oss blir

[0 0 0] = [1 0] [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}1 & −1 & −1 \\ 1 & 1 & 0 \end{matrix} ] = [−1 1 1]

Vi ser att inkommande variabel blir x_{1}

Viu beräknar

y = B^{−1}A_{ink} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}−1 \\ 1 \end{matrix} ] = [ \begin{matrix}−1 \\ 1 \end{matrix} ]

samt

b̂ = B^{−1}b = b = [ \begin{matrix}1 \\ 2 \end{matrix} ] .

Utgående ges av

argmin_{i,y_{i}>0} \frac{b̂_{i}}{y_{i}}

vilket ger att a blir utgående. Ny bas blir x_{1}, s_{2}, med basmatris

B = [ \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ] , B^{−1} = [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ]

Då alla artificiella variabler utgått ur basen vet vi att basen är tillåten. Vi tittar nu på originalproblemet för att hitta en inkommande variabel.

Vi har

c̄^{T} = c_{N}^{T} − c_{B}^{T}B^{−1}N

vilket blir

[−2 0] − [−1 0] [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ] [ \begin{matrix}−1 & 1 \\ −1 & 0 \end{matrix} ] = [−3 − 1]

Den inkommande variabeln blir x_{2}.

P.S.S. som tidigare beräknas

\begin{aligned}y = B^{−1}A_{ink} & = [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ] [ \begin{matrix}−1 \\ −1 \end{matrix} ] = [ \begin{matrix}−1 \\ 2 \end{matrix} ] \\ b̂ = B^{−1}b & = [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 2 \end{matrix} ] = [ \begin{matrix}1 \\ 1 \end{matrix} ] \end{aligned}

Den utgående variabeln blir basvariabel 2 dvs. s_{2}. Ny bas blir x_{1}, x_{2} med basmatris

B = [ \begin{matrix}1 & −1 \\ 1 & 1 \end{matrix} ] , B^{−1} = \frac{1}{2} [ \begin{matrix}1 & 1 \\ −1 & 1 \end{matrix} ]

Vi har

c̄^{T} = c_{N}^{T} − c_{B}^{T}B^{−1}N

vilket blir

[0 0] − [−1 − 2]\frac{1}{2} [ \begin{matrix}1 & 1 \\ −1 & 1 \end{matrix} ] [ \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ] = \frac{1}{2}[1 3]

Vi kan se att basen är otpimal, ty vi har c̄ ≥ 0.

1b) Lösningen är unik. c̄ > 0 innebär att målfunktionsvärdet ökar om vi väljer en slackvariabel som inkommande. Vidare är basen icke-degenererad, dvs. det finns endast en bas som ger den givna optimala punkten, vilket vi ser på att b > 0. Därmed vet vi att

(a) Att z ökar om vi ökar en inkommande variabel från 0.

(b) Att ett basbyte verkligen innebär att den inkommande får ett värde större än 0.

2. Index

i Materialtäkt, i = 1 är grustag 1, i = 2 är grustag 2 och i = 3 är

bergstäkt. m material, m = 1 är flis, m = 2 är makadam och m = 3 är sand. n vägverkets lager nummer 1 och 2.

Variabler:

x_{i} mängd brutet material i respektive materialtäkt y_{m} ton flis från anläggning till respektive lager. z_{m} ton flis från restlagret till respektive lager. v_{m} ton sålt material. w ton makadam som körs genom krossen.

Målfunktion, summa av kostnader för transport, minus intäkter för försäljning

min ∑_{i=1}^{3} x_{1}p_{i} + ∑_{m=1}^{2} y_{m}g_{m} + ∑_{m=2}^{2} z_{m}h_{m} − ∑_{m=2}^{3} v_{m}d_{m}

Inte överskrida kapacitet in i kross

t_{1} ≥ x_{3} + w

Inte överskrida kapacitet in i sikt

t_{2} ≥ x_{1} + x_{2}

Makadam som inte körs i kross skall säljas

w + v_{2} = k_{2}x_{3} + a_{2}(x_{1} = x_{2})

Sand skall säljas

v_{3} = k_{3}x_{3} + a_{3}(x_{1} + x_{2}) + l_{3}w

Flis skall transporteras bort

y_{1} + y_{2} = k_{1}x_{3} + a_{1}(x_{1} + x_{2}) + l_{1}w

Vi får inte överskrida restlagrets kapacitet

z_{1}z_{2} ≤ q

Vi skall uppfylla vägverkets behov

h_{n} = z_{n} + y_{n}, n = 1, 2,

3. Låt B vara den bas vi har innan pivoteringssteget i uppgiften. Vi betraktar problemet P̄, som är en modifiering av det ursprungliga problemet P.

I P̄ har vi tagit bort variabeln x_{i}. Då x_{i} var den enda tänkbara inkommande variabeln i det ursprungliga problemet har vi att B är en optimal bas till P̄, med optimalt värde z̄. Varje tillåten lösning till det ursprungliga problemet sådan att x_{i} = 0 är även en lösning till P̄. Därför kan det inte existera en tillåten lösning x till P med x_{i} = 0 sådan att c^{T} < z̄. Då en optimal lösning till P har ett värde lägre än z (ty det icke genererade steget ger oss en tillåten lösning med värde lägre än z) vet vi att varje optimal lösning måste ha x_{i} > 0.

4a) Lets write down the 1st and 2nd order optimality conditions

\{ \begin{matrix}3x_{1} + (1 + a)x_{2} − 1 = 0 \\ 3x_{2} + (1 + a)x_{1} − 1 = 0 \end{matrix} ⇔  (1st)

if

a = −4 ⇒ no solutions

a = 2 ⇒ \{ \begin{matrix}x_{1} − arbitrary \\ x_{2} = \frac{1}{3} − x_{1} \end{matrix} (i.e. mult. solutions.)

a ≠ −4

a ≠ 2 ⇒ \{ \begin{matrix}x_{1} = \frac{1}{4+a} \\ x_{2} = \frac{1}{4+a} \end{matrix}

( \begin{matrix}3 & 1 + a \\ 1 + a & 3 \end{matrix} ) ≥ 0 ⇔ \begin{matrix}g − (1 + a)^{2} ≥ 0 \\ a^{2} + 2a − 8 ≤ 0 \\ −4 ≤ a ≤ 2 \end{matrix}  (2nd - necessary)

To summerise: for any b iff −4 < a < 2 both 1st and 2nd order necessary and sufficient conditions for optimality are satisfied at the unique point (\frac{1}{4+a}, \frac{1}{4+a})^{t}.

If a = −4 ⇒ first order nec. conditions are violated ∀x_{1}x_{2}. If a > 2 or a < −4 ⇒ 2nd order nec. conditions are violated ∀x_{1}, x_{2}. If a = 2 ⇒ take x_{2} = \frac{1}{3} −x_{1} → f(x_{1}, λ_{2}) = \frac{3}{2}(x_{1}^{2} +x_{2}^{2})+3x_{1}x_{1} −(x_{1} +x_{2})+6 = const(b) for any x_{1} ∈ ℝ ⇒ cannot be an unique min! ■

b) f(x) = x^{4/3}

f′(x) = \frac{4}{3}x^{1/3}

f′′(x) = \frac{4}{9}x^{−2/3} (x ≠ 0)

Take x_{0} ≠ 0

x_{1} = x_{0} − \frac{4}{3}x_{0}^{1/3} · (\frac{4}{9}x_{0}^{−2/3})^{−1} = x_{0} − 3x_{0} = −2x_{0}
x_{2} = −2x_{1} = (−2)^{2}x_{0}
⋮
x_{k} = (−2)^{k}x_{0}, which diverges for any x_{0} ≠ 0.

The reason is the unboundedness of the second derivative near the optimal solution, so that we cannot use the corresponding convergence result! (in fact, the function is not twice differentiable at x^{∗} = 0).

c) The direction d is a descent direction, if (d, ∇f) = d^{t}∇f < 0.

Therefore,

[−(I + E(x))∇f(x)]^{t}∇f(x) = −∇f^{t}(x)(I + E(x))∇f(x) < 0

This is true, if for any x we can guarantee that I + E(x) is positive definite matrix, i.e. if all the eigenvalues of I + E(x) are positive, or all roots of

(( \begin{matrix}det(I + E(x) − λI) \\ det(E(x) − (λ + 1)I) \end{matrix} are positive.

The latter is true, if all eigenvalues of E are greater than −1.

5a) The problems (1) and (2) are equivalent, because the objective functions are the same, and 0 are the feasible sets because

∀i : h_{i}(x)0 ⇔ ∀i : (h_{i}(x))^{2} = 0 ⇔ ∑_{i=1}^{m}(h_{i}(x))^{2} ≤ 0

Let’s write the 1st order necessary optimality conditions for the both problems

P(1) : { h_{1}(x) = 0 ; ⋮ ; h_{m}(x) = 0 ; ∇f(x) = ∑_{i=1}^{m} μ_{i}∇h_{i}(x) ; some μ_{1} … μ_{n} vs. P(x) { h_{1}(x) = 0 ⋮ h_{m}(x) = 0 ∇f(x) = μ · ∑_{i=1}^{m} h_{i}(x)∇h_{i}(x) ≡ 0! some μ ≤ 0 [because h_{i}(x) = 0∀i]

I.e., if ∇(x) ≠ 0 at some locally optimal solution for the problem (1), the optimality conditions for the problem (2) are not satisfied. The simplest example is

\begin{matrix}min x \\ s.t. x = 0 \end{matrix}

with the only feasible [& thus optimal] point x = 0 at which the gradient of obj. f − n is 1 ≠ 0.

The reason for such a huge difference between the two equialent problem for mulations is the even if the LICQ holds at some x^{∗} feasible for P(1), ∇(∑_{i=1}^{∞}(h_{i}(x^{∗}))^{2}) = 0, i.e. LICQ is violated! Furthermore, Slater CQ cannot hold for (2), because

∑_{i=1}^{m}(h_{i}(x))^{2} ≯ 0∀x.

b) min_{x=inℝ^{n}} max{f_{1}(x), f_{2}(x)} is equivalent to the following (differentiable) problem:

\begin{matrix}min_{(x∈ℝ^{n},z∈ℝ)}z \\ s.t. & \{ \begin{matrix}f_{1}(x) − z ≤ 0 \\ f_{2}(x) − z ≤ 0 \end{matrix} & | \begin{matrix}μ_{1} \\ μ_{2} \end{matrix} \end{matrix}

Let’s write the optimality conditions for the latter problem:

f_{1}(x) ≤ z  (1)
f_{2}(x) ≤  (2)
μ_{1} ≥ 0  (3)
μ_{2} ≥ 0  (4)
μ_{1}(f_{1}(x) − z) = 0  (5)
μ_{2}(f_{2}(x) − z) = 0  (6)
\begin{matrix}1 − μ_{1} − μ_{2} = 0 & (7) \\ μ_{1}∇f_{1}(x) + μ_{2}∇f_{2}(x) = 0 & (8) \end{matrix} | derivative wrt z

derivative wrt x

I.e., if (x^{∗}, z^{∗}) is global min ⇒ nec. conditions are satisfied. (Slater CQ holds)

⇒ ∃μ_{1}, μ_{2} : \begin{matrix}μ_{1} ≥ 0, μ_{2} ≥ 0 & (3 & 4) \\ μ_{1}∇f_{1}(x^{∗}) + μ_{2}∇f_{2}(x^{∗}) = 0 & (8) \\ μ_{1} + μ_{2} = 1 & (7) \end{matrix}

Since z^{∗} = max{f_{1}(x^{∗}), f_{2}(x^{∗})] (otherwise it would’nt be a global min.)

⇒ from (1), (2), (3), (4), (5) and (6) we conclude that μ_{i} = 0 if f_{i}(x) < max{f_{1}(x^{∗}), f_{2}(x^{∗})}, i = 1, 2 [i.e., if f_{i}(x^{∗}) − z < 0].

6. S ⊂ ℝ^{n} är en konvex mängd om

\begin{matrix}x, y ∈ S \\ λ ∈ [0, 1] \end{matrix} \} ⇒ λx + (1 − λ)y ∈ S

f : ℝ^{n} ↦ ℝ är en konvex funktion om

\begin{matrix}x, y ∈ ℝ^{n} \\ λ ∈ [0, 1] \end{matrix} \} ⇒ f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y)

Låt epif = {(x, α) ∈ ℝ^{n=1}|f(x) ≤ α}.

Antag att f är konvex. Låt (x, α_{1}) och (y, α_{2}) vara två punkter i epif. Betrakta punkten λ(x, α_{1}) + (1 − λ)(y, α_{2}), λ ∈ [0, 2] Då gäller att

\begin{aligned}f(λx + (1 − λ)y) & ≤ λf(x) + (1 − λ)f(y) \\ & ≤ λα_{1} + (1 − λ)α_{2}, \end{aligned}

dvs λ(x, α_{1}) + (1 − λ)(y, α_{2}) ∈ epif. Alltså är epif konvex.

Antag att epif är konvex. Låt (x, α_{1}) och (y, α_{2}) vara två punkter i epif. Då ligger ockå (λ ∈ [0, 1])λx + (1 − λ)y i epif, och alltså gäller att f(λx + (1 − λ)y) ≤ λα_{1} + (1 − λ)α_{2}. Men detta är ekvivalent med att f är konvex.

7a) En differentiarbar funktion är konvex om

f(y) ≥ f(x) + ∇f(x)^{T} (y − x), ∀x, y ∈ ℝ^{n}.

Alltså gäller att

∇f(x)^{T} (y − x) ≤ f(y) − f(x) ∀x, y ∈ ℝ^{n}.

f är uppenbart psuedokonvex, för om vänsterledet är ≥ 0 måste högerledet också vara det.

Motexempel mot omvändningen: f(x) = x^{3}.

b) Antag att för x^{∗} ∈ x gäller att

∇f(x^{∗})^{T} (x − x^{∗}) ≥ 0, ∀x ∈ X.

Om f är pseudokonvex följer omedelbart att f(x) ≥ f(x^{∗}) ∀x ∈ X, dvs x^{∗} är ett globalt minimum.