Period 1

Question 1

What is the definition of a convex set?

Answer 1

A set is convex iff. u, v in X, for all lambda in [0, 1]

lambda x + (1-lambda) v in X

Question 2

When is a set positive semidefinite?

Answer 2

If det(A_k) >= 0 for all k {1, …, n}

Question 3

What is the definition of a cone?

Answer 3

A set is a cone iff.

lambda >= 0, u in X, lambda u in X

Question 4

What is the definition of a Hyperplane?

Answer 4

H = {x in R^n | p^t x = β}, with p in R^2, β in R

Question 5

How to get the direction d in which to search?

Answer 5

d = -∇f(x)

Question 6

What holds when f(x) is convex?

Answer 6

f(x) ≥ f(y) + ∇f(y) (x - y)

Question 7

How to do Dichotomous search?

Answer 7

1. Get interval
2. Get center
3. Take small delta
4. Get l_k = c_k - delta, r_k=c_k+delta
5. If (l_k) > f(r_k) –> min in [l_k, b_k]

If (l_k) min in [a_k, r_k]

If (l_k) = f(r_k) –> min in [l_k, r_k]

Question 8

How many iterations needed for Dichotomous search?

Answer 8

approx 2 log_2((b_1 - a_1)/epsilon)

Question 9

How to do Bisection method (for minimum)?

Answer 9

1. Get [a_1, b_1]
2. Get center c_n = (a_n + b_n)/2
3. If f’(c) < 0 –> min in [c_k, b_k]

f’(c) > 0 –> min in [a_k, c_k]

f’(c) = 0 –> is min

4. repeat

Question 10

How to do Newtons Method (1D)?

Answer 10

1. Get initial guess x^(0)
2. x^(i+1) = x^(i) - f’(x^(i))/f’‘(x^(i))
3. Repeat, this does not always converge

Question 11

How to do Cyclic Coordinate Method?

Answer 11

1. Get inital guess x^(0)
2. Find minimum on x_k for k = 1, …, n (i.e. by setting g(z) = f(x + e_i z))
3. Repeat until close enough

Question 12

How to do Steepest decent?

Answer 12

1. Get initial estimate x^(0)
2. Get the gradient ∇f(x)
3. Go to the direction d = -∇f(x^(k))
4. Do a line search on the function g(z) = f(x + z d), find there the minimum
5. Continue until error is small enough.

Question 13

How to do Newtons Method (1D+)?

Answer 13

1. Get initial guess x^(0)
2. x^(i+1) = x^(i) - (∇^2 f(x^(i)))^-1 ∇f(x^(i))
3. Repeat until close enough.

Question 14

How to do the Conjugate Gradient Method?

Answer 14

1. Get initial estimate x^(0)
2. Get d^(i) = -∇f(x^(k)) + ||f(x^(k))||^2/||f(x^(i-1))\^2 (if i=0, then just regual d)
3. Do line search on g(z) = f(x + z d)
4. Repeat until close enough

Question 15

How fast does the Newton Method converge for a quadratic function?

Answer 15

n (where n is the number of dimentions)

Question 16

How fast does the conjugate gradient method converge for a quadratic function?

Answer 16

n where n is the number of dimentions

Question 17

What is the formula of the barrier method?

Answer 17

f(x) + μ B(x),

with B(x) = sum φ(g_i(x))

With φ(z) is a smooth function, which is bigger then 0 if z <0, and its limit at 0 is inf.

e.g. φ(z) = -1/z

Question 18

How to use the Barrier method?

Answer 18

1. Get an initial point x⁽⁰⁾, this must be in the interior region Ω. Get initial μ⁽⁰⁾.
2. Minimize f(x) + μ B(x) using unconstrained optimization
3. Reduce μ (e.g. half it)
4. Repeat until close enough

Question 19

What is the formula of the Penalty Method?

Answer 19

f(x) + μ α(x), where

α(x) = sum h_i(x) + sum max(0, g_i(x))

Question 20

What is T(y)?

Answer 20

cl(D(y))

Question 21

When is a constraint active?

Answer 21

If g_i(x) = 0

Question 22

How to see if y is optimal using the Geometric form?

Answer 22

-f(y) is in the cone of the constraints.

Question 23

How to test KKT conditions?

Answer 23

Test ∇f(y) = sum λ_i ∇g_i(y) = 0

λ_i g_i(y) = 0 for all 1, …, k

Note equality constraints can just be ignored. Test first if in feasible region.

Question 24

How to create and solve a dual problem?

Answer 24

1. Write the Lagrange formula
2. Create the objective function
3. Find an infomum of x₁, x₂, x₃, … seperately
4. Fill in q(λ)
5. Solve.

Question 25

How to show that a set is a cone?

Answer 25

Create a nonnegative scalar c, if all the elements are still in the first set then it is a cone

Question 26

Does a function have to de differentiable to be convex?

Answer 26

No. e.g. f(x) = |x|