Convex Optimisation

Question 1

What is a convex function?

Answer 1

A function 𝑓(𝑥) is convex if for any two points
𝑥1 and 𝑥2 and any 𝑡 ∈ [0,1], the inequality 𝑓(𝑡𝑥1 + (1−𝑡) 𝑥2) ≤ 𝑡𝑓(𝑥1)+(1−𝑡) 𝑓(𝑥2) holds. Example: 𝑓(𝑥) = 𝑥2
.

Question 2

What defines a convex set?

Answer 2

A set 𝑆 is convex if the line segment joining any two points in 𝑆 entirely lies within 𝑆.

Question 3

What is a convex optimization problem?

Answer 3

A convex optimization problem seeks to minimize a convex function over a convex set.

Question 4

How does the gradient descent algorithm work in convex optimization?

Answer 4

Gradient descent iteratively adjusts parameters in the direction opposite to the gradient of the function at that point to find the local minimum, which is also the global minimum in convex problems.

Question 5

Describe Newton’s Method in the context of convex optimization.

Answer 5

Newton’s Method uses both the first and second derivatives to find a better approximation of the minimum faster by considering the curvature of the function.

Question 6

What is the purpose of line search in optimization algorithms?

Answer 6

Line search determines the optimal step size in a given direction to efficiently decrease the objective function and ensure convergence.

Question 7

What defines a good descent direction in optimization methods?

Answer 7

A good descent direction is identified using local information to ensure it leads to a decrease in the function value. Methods like gradient descent use the negative gradient as the descent direction.

Question 8

What are common challenges faced by the gradient descent method?

Answer 8

Challenges include slow convergence on flat surfaces, getting stuck at saddle points, and the need for careful step size selection to avoid overshooting.