C S 412
Linear Programming and Convex Optimization
Computer Science
College of Physical and Mathematical Sciences
Course Description
Optimization, problem formulation, and solution algorithms, including simplex and interior point methods. Applications from control, data mining, finance, game theory, learning, network flow, operations research, and statistical estimation.
When Taught
Contact Department
Grade Rule
Grade Rule 8: A, B, C, D, E, I (Standard grade rule)
Min
3
Fixed
3
Fixed
3
Fixed
0
Other Prerequisites
or instructor's consent.
Title
Mathematical Foundations
Learning Outcome
Develop a fluency in the mathematical foundations needed to pose optimization problems, including an appreciation for the role of convexity in characterizing solvable problems.
Title
Simplex Method
Learning Outcome
Develop a fluency with the Simplex Method as a solution technique to Linear Programming problems. Understand how it exploits the linear nature of the problem to yield good average-case performance while failing to be efficient in the worst-case.
Title
Sensitivity Analysis
Learning Outcome
Be able to characterize how to perturb the data of an existing problem so that its solution remains optimal for the new, perturbed problem.
Title
Applications
Learning Outcome
Explore the role of Linear and Convex Programming in a variety of applications, including 1) Finance, 2) Game Theory, 3) Regression, and 4) Computer Networking.
Title
Interior Point Methods
Learning Outcome
Develop a fluency with interior point methods for solving Linear Programming problems and understand how these solutions may be extended to solve nonlinear, convex optimization problems.
Title
Duality Theory
Learning Outcome
Understand the meaning of weak and strong duality and their role in the design and verification of algorithmic solutions to optimization problems.
