Week 9 Flashcards
Constrained Optimization
What are descent direction?
Any direction that reduces the function. Descent direction is the property of function f(x) - objective function
from taylors series : f(x+nd) ~ f(x) +nd gradient(f(x)) and dgradient(f(x)) < 0 implies, d is a descent direction.
What is a feasible direction?
Any direction that takes to a point that is feasible (satisfying the constraint g(x)<=0) (for some step-size).
It is the property of the constraint function g(x)
What is the necessary condition for a point to be optimal solution? (for <=0 constraint)
grad(f) = -lambda . grad(g(x) where lambda is any positive scalar
where lambda is called a lagrange multiplier
What is the necessary condition for a point to be optimal solution? (for <=0 constraint)
grad(f) = -lambda . grad(g(x) where lambda is ANY scalar
where lambda is called a lagrange multiplier
What are lagrange multipliers?
What is a projected gradient descent algorithm?
What are Convex Constraint Sets?
What is Convexity?
What are convex set?
What are Hyper planes? Are they convex sets?
What are half spaces?
What are properties of convex sets?
- Intersection of convex sets is a convex set
What is a convex combinations?
What is a convex hull?
What are convex function?
Any function f is a convex function where the epigraph(f) is a convex set.
Alternate defn: f(lambda .x1 +(1-lambda) x2) <= lambda (f(x1) + (1-lambda)f(x2)
3rd Defn: Assume f is differntiable, f is convex if and only if f(y) = f(x) + (y-x)transpose . Grad(f(x))
4th defn: f is twice differentiable.
