Computer Science
 

Linear Programming and Convex Optimization

Linear Programming and Convex Optimization
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.
C S
412
 Hours3.0 Credit, 3.0 Lecture, 0.0 Lab
 PrerequisitesC S 312 & MATH 313; or instructor's consent.
 NoteStudents are allowed only 1 retake of C S 412. This includes students who have failed or withdrawn (received a "W" grade). If after 1 retake, a student needs to retake the course again, the student must wait 1 semester/term before being allowed to take any C S course and must follow the petition process at cs.byu.edu/retake-policy. This policy does not apply to classes dropped before the add/drop deadline. Petitions for exceptions to the policy can be completed at cs.byu.edu/retake-policy.
 Taught 
 ProgramsContaining C S 412
Course Outcomes: 

Mathematical Foundations

Develop a fluency in the mathematical foundations needed to pose optimization problems, including an appreciation for the role of convexity in characterizing solvable problems.

Simplex Method

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.

Duality Theory

Understand the meaning of weak and strong duality and their role in the design and verification of algorithmic solutions to optimization problems.

Interior Point Methods

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.

Sensitivity Analysis

Be able to characterize how to perturb the data of an existing problem so that its solution remains optimal for the new, perturbed problem.

Applications

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.