【Convex Optimization Basics - YouTube】
【Convex Sets】Some properties:
- The empty set ? and ?d are both convex.
- Preserved by scaling and translation.
- Intersections of convex sets are convex.
- Any local minimum is a global minimum.
- Where it exists, the Hessian is positive semi-definite.
- Level sets are convex.
- a·f(x) + b·g(x) is convex for convex f,g and a,b > 0.
- max(f(x), g(x)) is convex for convex f(x) and g(x).
【Convex Optimization Terminology】
- optimization variable
- objective / cost function
- inequality constraints
- equality constraints
- optimal value
- optimal point
【Why Convex Optimization?】
- Contains various types of problems, e.g., many ML and OR tasks.
- Repeatability: different runs give the same results.
- Some convex problems can be solved in polynomial time
- However, lots of important problems aren‘t convex: neural networks, k-means, most Bayesian inference.
The max-min inequality: the max of the minima ≤ the min of the maxima
【Convex Optimization】Convex Optimization Basics