Optimal-Control
These are solution for the algorithm course of Princeton
Table of Contents
- Lecture 1: Dynamics Review
- Lecture 2: Dynamics Discretization and Stability
- Lecture 3: Optimization Pt. 1
- Lecture 4: Optimization Pt. 2
- Lecture 5: Optimization Pt. 3
- WordNet
- Seam Carving
- Baseball Elimination
- Boggle
- Burrows Wheeler
- Contact
Lecture 1: Dynamics Review
Lecture 2: Dynamics Discretization and Stability
To Transform from continuity to discretization, some methods are following:
1. Discret-time sim/dynamics
2. Stability of discrete-time system
3. Forward/Backward Euler
Forward Euler(Emplicit): add energy.
Backward Euler(Impicit): add dampping, use in game and physical simulation.
- Impilicit methods are often "more" stable than explicit counterparts
- For forward simulation, solving implicit equation can be more expensive
- In many "direct" traj opt methods, they're not any more expensive to use
4. Zero/First-order hold on controls
Lecture 3: Optimization Pt. 1
1. Notation
- Given
$f(x):\mathbb{R}^2\rightarrow\mathbb{R}$ $$\frac{\partial{f}}{\partial{x}}\in\mathbb{R}^{1\times n}$$ is a row vector
Giving
because
We will also define:
2. Root Finding
-
given
$f(x)$ , find$x*$ such that$f(x*)=0$ -
- example: equilibrium point of continuous-time dynamics
-
Closely realted fixef point such that
$f(x*)=x*$ -
- example: equilibrium for disrete-time dynamics
-
Fixed point solution method
Newton's method(better than the above)
- Fit a linear appr0ximation to
$f(x)$ :$$f(x+\Delta{x})\approx f(x)+\frac{\partial{f}}{\partial{x}}\Delta{x}$$ - Set approximation to zero and solve for
$\Delta x$ :$$f(x)+\frac{\partial{f}}{\partial{x}}\Delta{x}=0 \qquad \Longrightarrow \qquad \Delta{x}=-(\frac{\partial{f}}{\partial{x}})^{-1}f(x)$$ - Apply correction:
$$x \leftarrow x+\Delta{x}$$ - Repeat until convergence
Take-Away Message
- Quadratic convergence
- Can achieve machine precision
- Most expensive part: solving linear system
- Can impreove complexity by taking advantage of preblem structure
3. Minimization
convert it to root finding problem
Take Away Message:
- Newton is a local root-finding method. Will converge to the Cloest Fined point to the initial guess (min, max or saddle)
sufficient conditions
4. Regularization
use some tricks to fix the decent, and go downhill
Lecture 4: Optimization Pt. 2
1. Line Search
Genernal intuition
- Often
$\Delta{X}$ step from Newton is too big and overshoots the minimization - To fix this check
${f(x+\Delta{x})}$ and "backtrack" until we get a "good" reduction - Many stratagics exist
- A simplest effective one is "Armijo rule"
- Make sure step agrees with linearization within some tolerance.
Take Away Messages
- Nweton with simple, cheap modifications(" globalization strategies") is extremely effetive at finding local minima.
2. Constrained Minimization
2.1 equality constraints
First-Order Necessary Conditions
- Need
${\nabla f(x)=0}$ in free directions - Need
$c(x)=0$ 
- Any non-zero component of
${\nabla f}$ must be in normal to the constraints surface/manifold${\nabla{f}+ \lambda \nabla{c}=0}$ for some${\lambda \in \mathbb{R}}$ , where${\lambda}$ is "Lagrange multipliter"/"Dual variable"
In genral:
-
Based on this gradient condition, we define:
$L(x,\lambda)=f(x)+\lambda^{T}c(x)$ , where${L}$ denotes the "Lagrangian" -
Such that:
$$\nabla_{x}L(x,\lambda)=\nabla{f}+(\frac{\partial{c}}{\partial{x}})^T\lambda=0$$ $$\nabla_{\lambda}L(x,\lambda)=c(x)=0$$
We can solve this with Newton:
Gauss-Newton Method:
- We often drop the second-order "constraint " term for its expensive to compute
- Called "gauss-newton"
- Slightly slower converagence than full newton(more itterations) but much cheaper per itteration
Take away message:
-May still need to regularize
2.2 Inequality constraints
- In general, these methods for now with the privious ones for mixed equility/inequality constraints
First-Order Necessary Conditions:
- $\nabla f = 0 $ in the free directions
$c(x) \geq 0$
KKT Conditions:
Intuition:
- If constraint is "active"
$\lambda > 0$ (same as equality case) - If constraint is "inactive"
$\lambda = 0$ (same as unconstrainted) - Complementerity encodes "on/off" switching
Algorithms:
- Mush harder than equality case
- can't directly apply Newton to KKT
- Many options will trade offs
Active-Set:
- Have some way of guessing active/inactive constraints
- Just solve equality-constrainted problems
- Very fast if you can guess well
- Very bad otherwise
Barrier/Interier-POINT
-
Replace inequalities with "barrier function" in objective that goes to infinity at constraint boundary.
$${min \quad f(x)}$$ $$s.t.\quad c_i(x)\geq 0$$ convert the above to the fllowing：$$min_{x} f(x)-\sum^{m}_{i=1}\frac{1}{p}log(c_i(x))$$ -
Gold standard for small~medium convex problems
-
Requies lots of tricks/hacks for non-convex problems
Penalty
-
Replace inequality with objective term to pernalize violations
$${min \quad f(x)}$$ $$s.t.\quad c_i(x)\geq 0$$ convert the above to the fllowing：$$min f(x)+\frac{p}{2}[min(0,C(x))]^{2}$$ -
Easy to implement
-
Has issues with numerical ill-conditioning
-
Difficult to achieve high accuracy
Lecture 5: Optimization Pt. 3
Penalty Method
- Replace inequalities with objective term that penalizes violations:
$$\min_{x} \quad f(x)$$ $$s.t. \quad c(x)\geq0$$ The above can be rewritten:$$\min_{x} \quad f(x)+\frac{p}{2}[min(0,c(x))]^2$$ - Easy to implement
- Large penalties->ill-conditioning
- Difficult to achieve high accrracy
1 Augmented Lagrangian
- Add Lagrange nultiplter estimate to penalty method:
$$\min_{x} L_p(x,\hat{\lambda})=f(x)-\hat{\lambda}^{T}c(x)+\frac{P}{2}[min(0,c(x))]^2$$ -Update$\hat{\lambda}$ by "off loading" penalty into multiplier at each iteration - Repeat until convergence
$\min_{x} \quad L_p(x,\hat{\lambda})$ $\hat{\lambda}\leftarrow max(0,\hat{\lambda}-pc(x))$ $p \leftarrow \alpha p \quad (optinal)$
- Fixed ill-conditioning of penalty method
- Convergencs fast(super linear)
- Works well on non-linear problems
2 Quadratic Programs
- Very useful in control
- Can be solved very fast
3 Regularization+duality
- We might line to trun this into :
$$\min_{x}\quad f(x)+P_{\infty}(c(x)), P_{\infty}(c(x))\geq 0$$ - Practically terrible, but we can get the same effect by solving:
$$\min_{x} \quad \max_{\lambda} \quad f(x)+\lambda^Tc(x)$$ - Whatever
$c(x)\neq 0$ , inner problem blows up - Similarly for inequalities!
$$\min_{x} \quad f(x)$$ $$s.t. \quad c(x) \geq 0$$ trun this into:$$\min_{x}\quad f(x)+P_{\infty}(c(x)), P_{\infty}^{+}(c(x))\geq 0$$ we can get the same effect by solving:$$\min_{x} \quad \max_{\lambda\geq 0} \quad L(x,\lambda)=f(x)+\lambda^Tc(x)$$ - Asside for convex problems, we can switch the order of min/max and get the same answer(duality). Not true ub general.
- Interpretation: KKT conditions define a sddle point in
$(x,\lambda)$ - KKT system should have
$dim(x)$ positive eigenvalues and$dim(\lambda)$ negative eigenvalue at an optimum. Called "Quasi-definite"
When rugularizing a KKT system, the lower-right block should be negative:
- Exapmle: -still heve overshoot -> need line search
Merit Function
- How do we do a lone search on a root-finding problem?
find
-
Define a scalar "merit function"
$P(x)$ that measures distance from a solution -
standard Choices!
$$P(x)=\frac{1}{2}c(x)^{T}c(x)=\frac{1}{2}||c(x)||^2_2$$ $$P(x)=\Vert c(x)\Vert_1 \quad (any \quad norm \quad works)$$ -
Now just do Armijo on
$P(x)$ $$\alpha=1$$ $$while\quad P(x+\Delta x)>P(x)+c\alpha\nabla P(x)^T\Delta{x}$$ $$\qquad \alpha \leftarrow c\alpha$$ $$end$$ $$\qquad x \leftarrow x+ \alpha \Delta x$$ $ -
How about constrained minimization?
$$min_{x}\quad f(x)$$ $$s.t.\quad c(x)\geq 0$$ $$s.t.\quad d(x)= 0$$ turn into:$$L(x,\lambda,\mu)=f(x)-\lambda^{T}c(x)+\mu^{T}d(x)$$ -
Lot's of options for merit function:
Take away message:
-
$P(x)$ based on KKT residual is expensive - Exessively large constraint penalty can cause problems
- AL methods come with a merit fuction for free