\documentclass{article} \usepackage{me} \usepackage{amssymb} \usepackage{amsfonts} \setlength{\parindent}{0pt} $\newcommand\vol{{\mbox{vol}}}$ $\newcommand{\RR}{\mathbb{R}}$

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?