Lecture 17: Interior-Point Methods
Last Time
Unconstrained minimization problem: given a real-valued function $f$ over $\RR^n$, find its minimum $x^*$ (assuming it exists). That is, solve the problem \[ x^*=\arg\min_{x\in \RR^n} f(x). \]- Gradient descent (strong convexity and smoothness) - condition number and update step (good convergence for condition number)
- Newton's method. Second-order gradient descent, Update step. Or really gradient descent in local norm.
- Works really well when Hessians close, a bit less well otherwise.
- Idea - local norm is the best norm makes $f$ locally very well-condition (but not globally)
Solving the LPs via Barrier Method
- Pros and cons of Simplex and Ellipsoid
- New idea: don't deal with constraints explicitly - try to stay away from them - as that's where complexity of simplex comes in
- How to quantify that? Need a potential that measures how close we are to a given constraint
- Barrier: bounded on int of P, goes to infinity to boundary, strongly convex (as that's a good way to do it - add later?)
- How to incorporate barrier trade-off? Just add them together and offset them against our objective function.
- Turned constraint problem to unconstrained one - win!
- logarithmi barrier (figure!) and full objective
- Need normalization. Clearly, want to phase out perturbation $LP(\mu)$ and $y^*(\mu)$.
- How to do that? Optimize with GD/Newton's method?
- Key idea: gradually! Keep always in the sphere of rapid convergence.
- Dynamical system vs. discretization.
- Key questions: when to stop, how many steps needed, how to start?
- compute the gradient - optimality condition, dual solution, complementary slackness
- update step, definition of $\delta$, how many steps based on $\delta$. Condition on $\delta$.
- condition on $s$, derivation of Newton's decrement.
- analysis for min-circulation problem (note - no capacities but can fix that).
- gives fast max flow.
- Beyond: on max flow and my result
- Dikin ellipsoid intuion. John's ellipsoid.
- How to deal with starting point?