NPTEL Phase II :: Computer Science and Engineering

Untitled Document

COURSE OUTLINE

Introduction. Mathematical Background, including convex sets and functions. Need for constrained methods in solving constrained problems.

Unconstrained optimization: Optimality conditions, Line Search Methods, Quasi-Newton Methods, Trust Region Methods. Conjugate Gradient Methods. Least Squares Problems.

Constrained Optimization: Optimality Conditions and Duality. Convex Programming Problem. Linear Programming Problem. Quadratic Programming. Dual Methods, Penalty and Barrier Methods, Interior Point Methods.

COURSE DETAIL

Sl.No.	Topics	No.of Hours
1	Introduction: Optimization, Types of Problems and Algorithms	1
2	Background: Linear Algebra and Analysis	2
3	Convex Sets and Convex Functions	4
4	Unconstrained Optimization: Basic properties of solutions and algorithms, Global convergence	2
5	Basic Descent Methods: Line Search Methods, Steepest Descent and Newton Methods	2
6	Modified Newton methods, Globally convergent Newton Method.	2
7	Nonlinear Least Squares Problem and Algorithms	2
8	Conjugate Direction Methods	1
9	Trust-Region Methods	1
10	Constrained Optimization: First Order Necessary Conditions, Second Order Necessary Conditions, Duality, Constraint Qualification	6
11	Convex Programming Problem and Duality	2
12	Linear Programming: The Simplex Method, Duality and Interior Point Methods, Karmarkar's algorithm	6
13	Transportation and Network flow problem	1
14	Quadratic Programming: Active set methods, Gradient Projection methods and sequential quadratic programming	3
15	Dual Methods: Augmented Lagrangians and cutting-plane methods	2
16	Penalty and Barrier Methods	2
17	Interior Point Methods	1

PREREQUISITES

Linear Algebra and Differential Calculus.

REFERENCES

David Luenberger and Yinyu Ye, Linear and Nonlinear Programming, 3rd Edition, Springer, 2008.
Fletcher R., Practical Methods of Optimization, John Wiley, 2000.

ADDITIONAL READINGS

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.