Linear Programming and Convex Optimization
|Hours||3.0 Credit, 3.0 Lecture, 0.0 Lab|
|Prerequisites||MATH 313; or MATH 213 & MATH 215; or instructor's consent.|
|Note||Students are allowed 1 repeat of each C S undergraduate course (all 100-, 200-, 300- or 400-level courses). This includes all students who received any grade including those who withdraw (receive a "W" grade) from a C S course. Students must wait 1 semester/term before being allowed to take a course they have failed twice. Petitions for exceptions to the policy can be completed at cs.byu.edu/undergraduate-handbook/retake-policy-cs-courses/.|
|Programs||Containing C S 412|
Develop a fluency in the mathematical foundations needed to pose optimization problems, including an appreciation for the role of convexity in characterizing solvable problems.
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.
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.
Be able to characterize how to perturb the data of an existing problem so that its solution remains optimal for the new, perturbed problem.
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.