Exam text content

Optimization Methods Exam, 16.01.2020 Henri Hansen

 

Please answer four out of the following five guestions, on a separate paper. Note that there
are two pages in the exam. No books. non-programmable calculators are allowed.
A Collection of Formulas will be handed. Kaavakokoelma jaetaan.

1. Consider the optimization problem:

min f(z,y) = (x— 22 +472

s:t. ;
m+yYc<I1
(a) Is the feasible set convex?

(b) Is the cost-function convex?

(e) Calculate the optimum and demonstrate that it is a KKT-point.
2. Assume that we have the following linear problem:
min c''x 4
s.t.
Az=b
Tx>0
(a) Suppose that we wish to use the Simplex algorithm. To do so, we need one basic

feasible solution to the LP. Explain how to find one.

(b) Consider the reduced cost & (formula given in the formula sheet). Show (using
algebra), that its component i is egual to the change in the cost function if we
increase the value of the null-variable x; by one. 1.e., assume you have a basic
feasible solution x, and you move from this point, all the while maintaining the
constraint Az = b.

3. Consider the unconstrained problem
min f(z, y) = (2— x)? + 6(y — 2)?

(a) Find the minimum of this function analytically. (Hint: It is not hard, if you really
look at when it can be minimum. Or solve for the zero of the gradient, but that
is going to be hard.

(b) Consider finding the minimum using one of the methods. Start from any point
(other than the optimum) and calculate one iteration. If you use the gradient
method, be sure to formulate the minimization problem solving the step length.

(e) Demonstrate that the function is not convex. (By any means you like.)
Optimization Methods Exam, 16.01.2020 Henri Hansen

4. Let f,g: X > R be two convex functions. Which of the following claims hold? Prove
or disprove (i.e., give an example where the claim is false)

(a) The function af + bg is convex, when a,b € R.
(b) The set (x|f(z) < g(x)) is convex.

 

(e) The function h(x) = max(f(x), g(x)) is convex.
5. Suppose we have a constraint problem
min 2? + Y
s.t.
- m -yc=1
(a) Formulate the KKT-conditions for this problem.

(b) solve the problem either by solving the KKT-eguation or by using Lagrange mul-
tipliers. (Hint: it's not too hard, consider the factors)

(e) What is the minimum of the function?