16745: Dynamic Optimization
Spring 2015
Instructor: Chris Atkeson, cga at cmu
TA: Sasanka Nagavalli snagaval at andrew
MW 34:20 NSH 3002
Events of Interest
Last year's course

Jan 12: Introduction to the course.
Goal: Introduce course.
This years emphases is TO BE DETERMINED
Possibilities:

Low level parallelization of quadratic programming (QP) across N cores on one
machine.

Robust control.

Jan 12: Function Optimization Example
Goal: Introduce you to a useful tool, MATLAB
and its optimization subroutines, and show you how to use them on an example.
Robotics: redundant inverse kinematics.
Using Matlab's fminsearch and fminunc.
Using Matlab's fminsearch and fminunc, with
desired posture.
Using Matlab's fmincon.
Relationship of Jacobian approach to gradient descent.

Jan 14:
Function optimization using
first and
second
order gradient methods.
Goal: Review gradient descent approaches.
A nice chapter on function optimization techniques:
Numerical Recipes in C, chapter 10
(2nd or 3rd edition, 2nd edition is electronically available for free
under Obsolete Versions):
Minimization or Maximization of Functions,
This material from any other numerical methods book is also fine.
Resources:
Matlab fminunc,
Numerical Recipes,
GSL,
AMPL,
NEOS,
software list 1,
Useful
software guide,
gradient method,
line search,
conjugate gradient,
conjugate gradient v2,
quasiNewton/variable metric methods, and
Newton's method.

Jan 19: No Class

Jan 21: Nongradient ("derivativefree") function optimization methods:
Goal: Review nongradient approaches.
hill climbing
(including
local search,
local unimodal sampling,
pattern search,
random search,
random optimization),
Nelder Mead/Simplex/Amoeba method,
Matlab fminsearch,
simulated annealing,
fit surfaces (for example
Response Surface Methodology (RSM),
Memorybased Stochastic Optimization, and
Q2),
evolutionary algorithms,
genetic algorithms,
and ...
Paper:
Derivativefree optimization: A review of algorithms and comparison of software implementations by Luis Miguel Rios and Nikolaos V. Sahinidis,
Book: Introduction to DerivativeFree Optimization

Jan 2126:
Covariance Matrix Adaptation Evolution Strategy.
See also Hansen web page.
Example1,
Ex2,
Ex3,
Ex4.

Jan 26: Constraints.
Soft/hard constraints, penalty functions,
Barrier functions,
Lagrange Multipliers,
Augmented Lagrangian method,
Interior point methods vs. Simplex methods vs. soft constraint methods,

Jan 2628:
Quadratic Programming and
Sequential quadratic programming,
Matlab fmincon.
SNOPT,
CVXGEN

Jan 28: Automatic differentiation

Jan 28: Dynamics and Numerical Integration
Continous time, discrete time. Euler integration, Forward and inverse dynamics. Linearization.

Feb x: Formulating trajectory optimization as function optimization.
Examples of formulating a trajectory optimization problem
as a function optimization problem:
Case Studies In Trajectory Optimization: Trains, Planes, And Other
Pastimes,
Robert J. Vanderbei
Example use of AMPL
A free trial version of AMPL is available from here.
AMPL is also available for remote use through the Neos Server.
Click on SNOPT/[AMPL Input] under Nonlinearly Constrained Optimization.
Example use of Matlab: pend1xu,
pend1u,
pend1x
Spacetime Optimization: Witkin paper text
Witkin paper figures

Feb x:
Use of splines in trajectory optimization.
Cubic Hermite spline.
Useful.
Example 1,
Collocation,
Pseudospectral X.

Feb x:
Policy optimization I: Use function optimization.
What is a policy?
Known in machine learning/reinforcement learning as policy search or refinement, ...
slides
See examples in CMAES section for policy optimization.

Feb x: Ways to robustify function optimization:
Problems: How choose method?, more of an art than a science, local minima, bad answers, discontinuities, redundant/rank deficient constraints,
bad scaling, no formulas for derivatives, you are lazy, computational cost.
Techniques: Levenberg Marquardt,
Trust regions,
line search,
scaling and preconditioning, regularize parameters, soft constraints,
sparse methods,
Continuation Methods,
Paper on continuation methods,
Hand of God, allow constraint violations, add extra constraints,
Matlab recommendations

Feb x:
Dynamic Programming.
Bellman equation,
slides

Feb x:
Linear Quadratic Regulator,
Riccati Equation,
Differential Dynamic Programming

Feb x: Receding Horizon Control (a.k.a. Model Predictive Control (MPC)).

Feb x: Ways to reduce the curse of dimensionality
slides

Feb x: Policy Optimization II: Optimization using modelbased gradients
slides

Feb x: Robustness using Linear Matrix Inequalities
Robustness to parametric uncertainty in the linear(ized) model.
I can't find a good reference on robustness using linear matrix inequalities,
but here is a tutorial on LMIs

Feb x: Robustness
Robustness to random disturbances, varying initial conditions, parametric
model error, structural modeling error such as
high frequency unmodelled dynamics,
and model jumps (touchdown and liftoff during walking, for example).
Monte Carlo trajectory/policy optimization.

Feb x: Robustness: Policy Optimization with Multiple Models.
MonteCarlo, DP, and DDP approaches to Multiple Models.

Feb x:
State Estimation,
Uncertainty Propagation:
Gaussian Propagation (like Kalman Filter),
Unscented (like Unscented Filter), Second Order Kalman Filter (See Kendrick below).
Review of Gaussians slides
State estimation slides
Matlab Kalman filter example
and
minimum jerk trajectory subroutine.
Example mobile robot Kalman filter slides

Feb x:
Dual Control.
Simple example.
Information state DP.

March x: Local Approaches to Dual Control/Stochastic DDP
Information state trajectory optimization.
Stochastic Control for Economic Models,
David Kendrick, Second Edition 2002.

March x: Robustness and state estimation:
Example of bad interactions, Loop Transfer Recovery (LTR),
A paper on the topic,
Policy optimization approaches.

March 911: No Class

March x: Other ways in trajectory optimization to handle contact:
Posa, Tedrake,
Posa video
Erez, Todorov

March x: Avoiding obstacles: CHOMP
STOMP

March x: Sampling based methods: RRT,
slides
Projected RRT,
RRT*
slides
LQRRRT*
Random Sampling DP

March x: A*like algorithms: R*

March x: Reinforcement Learning: Model free policy optimization.
Kober, J.; Peters, J. (2011). Policy Search for Motor Primitives in Robotics, Machine Learning, 84, 12, pp.171203

March x: Comparison of various RL methods: CMAES, CEM, PI2.
Freek Stulp and Olivier Sigaud. Path Integral Policy Improvement with Covariance Matrix Adaptation. In Proceedings of the 29th International Conference on Machine Learning (ICML), 2012.

March x: Adaptive Control

March x: Learning From Demonstration

April x: Inverse Optimal Control
Sergey Levine, Vladlen Koltun. Continuous Inverse Optimal Control with Locally Optimal Examples. ICML 2012

April x:
Trajectory optimization based on integrating the dynamics:
calculus of variations,
EulerLagrange equation,
Pontryagin's minimum principle,
HamiltonJacobiBellman equation,
costate equations,
shooting methods,
multiple shooting methods,
KarushKuhnTucker conditions

April x:
Continuation Methods,
Metaoptimization,
Learning during optimization

Apr. 27: Project presentations

Apr. 28: Project presentations

May. xx: Final Projects Due
Other topics

Learning Heuristic Functions

SIMD parallelism
How do GPUs and other forms of SIMD parallelism affect optimization
algorithm design?
Assignments

Assignment 0 (Due Jan. 18): Send CGA email:
Who are you?
Why are you here?
What research do you do?
Describe any optimization you have done (point me to papers or
web pages if they exist).
Any project ideas?
What topics would you especially like the course to cover?
Be sure your name is obvious in the email, and you mention the course
name or number. I teach more than one course, and a random email from
robotlover@cs.cmu.edu is hard for me to process.