Exam text content

Optimization Methods Exam, 01.03.2018 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. Calculators are allowed.
A Collection of Formulas will be handed. Kaavakokoelma jaetaan.

1. Consider the optimization problem:
min f(z,y) = x? + y?
s.t.
mP4+Y<1
(a) Is the feasible set convex, and is the function convex? (Prove or disprove)
(b) Find the KKT-points of the problem. Is one of them a minimum?
2. Consider the linear problem:
min 2 = 21 + 222 — 23
s.t.
T1—x29—%3>2
271 + 22 +373 < 1
T1,T2,73 > 0
(a) Transform the problem into the standard format
(b) Find the dual of the problem (either directly or from the standard form; your
choice)
3. Assume that we have a linear problem:
min cr
s.t.
Az=b
7>0
(a) Suppose we construct the dual and find that the dual is infeasible. What can we
say about the original problem?

(b) Suppose that we wish to use the Simplex algorithm. To do so, we need one basic
feasible solution to the LP. Explain a method for finding a basic feasible solution.

(e) Suppose we run the dual simplex algorithm and find a point u that is a feasible
solution to the dual. What can we say about possible solutions of the original
problem?
Optimization Methods Exam, 01.03.2018 Henri Hansen
4. Consider the unconstrained problem

min f(2,y) = x —y+2xy+22? + 7?

(a) Suppose we run a minimization algorithm to find a local minimum, starting from
the point g = (1,5). Pick any of the methods discussed during the course to
find a minimum. (I suggest the Newton method, but feel free to use any of the
others), and compute at least two other points from the iteration (i.e. x; and 22).

(b) How would you determine, after reaching a result, whether the point you found
is a local mininum?

(c) How would you determine if it is a global minimum?
5. Let f : X + R be convex. Which of the following claims hold? Prove or disprove (i.e.,
give an example where the claim is false)
(a) The function f(x)? is convex.
(b) The set f(z) < b is convex for every b € R.
(c) I KC X is a closed and bounded convex set and f is differentiable in K, then

 

min f(x)

has the solution z* such that Vf(a*) = 0.