Math 320: Algorithm Design and Optimization 1

Title

Algorithm Design and Optimization 1

(3:3:0)

F

Prerequisite

Math 290, Math 313, Math 314, Math 341; concurrent with Math 321, Math 334, Math 344

Description

A treatment of algorithms used to solve these problems. Specific topics include Complexity and Data, Approximation Theory, Recursive Algorithms, Linear Optimization, Unconstrained Optimization, Constrained Optimization, Global Optimization.

Desired Learning Outcomes

Prerequisites

Math 290, Math 313, Math 314, Math 341; concurrent with Math 321, Math 334, Math 344

Minimal learning outcomes

Students will have a solid understanding of the concepts listed below. They will be able to prove many of the theorems that are central to this material. They will understand the model specifications for the optimization algorithms, and be able to recognize whether they apply to a given application or not. They will be able to perform the relevant computations on small, simple problems. They will be able to describe the optimization and approximation algorithms well enough that they could program simple versions of them, and will have a basic knowledge of the computational strengths and weaknesses of the algorithms covered.

1. Complexity and Data
• Asymptotic Analysis
• Combinatorics
• Graphs and Trees
• Complexity (P, NP, NP Complete)
2. Approximation Theory
• Interpolation and Splines
• Stone-Weierstrass Theorem
• Bezier Curves
• B-Splines
3. Recursive Algorithms
• Difference Calculus, including Summation by Parts
• Simple linear recurrences
• General linear recurrences
• Generating functions
4. Linear Optimization
• Problem Formulation
• Simplex Method
• Duality
• Applications
5. Unconstrained Optimization
• Steepest Descent
• Newton
• Broyden
• Applications
6. Constrained Optimization
• Equality Constrained, Lagrange Multipliers
• Inequality Constrained, KKT Condition
• Applications
7. Global Optimization
• Interior Point Methods
• Genetic Algorithms
• Simulated Annealing

Textbooks

Possible textbooks for this course include (but are not limited to):