gradient descent and iterative stuff

Question 1

iterative method (basic):

Answer 1

x(k+1)=xk+akpk, starting with an educated guess x0, f(x(k+1))<=f(xk), tryna get it to converge to x*

Question 2

step length:

Answer 2

ak in the iterative method, pretty sure it’s usually a constant

Question 3

search direction:

Answer 3

pk in the iterative method, gradient (derivative) of a function
pk=-∇f(xk)

Question 4

how to choose step length optimal:

Answer 4

a minimiser of the function a->φ(a):=f(xk+apk) (so φ’(a)=0 and rearrange for a)

Question 5

sufficient decrease condition:

Answer 5

f(xk+apk)<=f(xk)+ca⟨∇f(xk),pk⟩=:l(a) with c in (0,1)
aka armijo condition, always used only sometimes with others

Question 6

wolfe condition:

Answer 6

φ’(a)>=dφ’(0), d in (c,1)

Question 7

armijo-goldstein condition:

Answer 7

ak should satisfy f(xk)+(1-c)ak⟨∇f(xk),pk⟩<=f(xk+akpk)

Question 8

backtracking:

Answer 8

pick a large a (like 1) and decrease it until it satisfies the required conditions

Question 9

vector convergence:

Answer 9

for all ε>0 there exists some N such that for all n>=N, ||xn-x*||<ε (for a sequence of vectors {x1,…,xn})

Question 10

linear convergence:

Answer 10

assume a sequence of vectors {xk}, k>=0, converges to x* - it’s linear if there exists an r in (0,1) such that for sufficiently large k, ||x(k+1)-x||<=r||xk-x|| - r is called the rate

Question 11

superlinear convergence:

Answer 11

assume a sequence of vectors {xk}, k>=0, converges to x* - it’s superlinear if lim(k->∞)||x(k+1)-x||/||xk-x||=0

Question 12

convergence with order p:

Answer 12

assume a sequence of vectors {xk}, k>=0, converges to x* - it converges with order p>1 if there is a constant M>0 such that for sufficiently large k, ||x(k+1)-x||<=M||xk-x||^p - p=2 is called quadratic convergence