NUMERICAL OPTIMISATION
ASSIGNMENT 8
MARTA BETCKE
KIKO RUL·LAN
EXERCISE 1
Consider a problem to minimise the function
min
x
f(x) =
1
2
xTGx + cTx
subject to the constraint
Ax ≤ b,
where G ∈ Rn×n symmetric positive semidefinite, A ∈ Rm×n, c ∈ Rn, b ∈ Rm.
(a) State the KKT conditions for this problem. [20pt]
(b) Rewrite the constraint using a vector of slack variables y ∈ Rm, y ≥ 0 and give the corresponding
KKT conditions. [20pt]
(c) Formulate the dual to the problem in (b) and discuss its properties. [20pt]
EXERCISE 2
Solve the following constraint minimisation problem:
min
(x,y)
f(x, y) = (x− 2y)2 + (x− 2)2, x− y = 4.
(a) Formulate the KKT system. [20pt]
(b) Solve the KKT system with a method of your choice. Explain briefly your approach. [20pt]
Remark. Submit your solutions via Turnitin. This submission should not be longer than 4 pages.