EEweb Home     ::     Graduate Courses     ::     Undergraduate Courses     ::     My Home

Course Description Form

Course number and title: EE236C Optimization Methods for Large-Scale Systems
Credits: 4
Instructor(s)-in-charge: Not offered in 2011-12
Course type: Lecture
Required or Elective: A Signals and Systems course.
Course Schedule:
Lecture: 4 hrs/week
Outside Study: 8 hrs/week
Office Hours: 2 hrs/week
 
Course Assessment:
Homework: Several assignments.
Project Reports: 1 project.
Exams: 1 final examination.
 
Grading Policy: Typically, 20% homework, 30% project, 50% final.
Course Prerequisites: EE236B
Catalog Description: Theory and computational procedures for decomposing large-scale optimization problems: cutting-plane methods, column generation, decomposition algorithms. Techniques for global continuous optimization: branch-and-bound methods, reverse convex programming, bilinear and biconvex optimization, genetic algorithms, simulated annealing. Introduction to combinatorial optimization.  
Textbook and any related course material:
C. Papadimitrou, Combinatorial Optimizations: Algorithms and Complexity.
M.R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.
 
Course Website
Topics covered in the course:
Definition and examples of combinatorial optimization problems, including Traveling Salesperson, max-clique, and satisfiability problems.
Introduction to Computational complexity and Turing Machines. The definitions of time and space complexity.
Definitions of the computational complexity classes, P and NP.
Polynomial-time reductions and the notion of NP-Completeness.
Examples of NP-Complete problems.
Results on approximating NP-complete problems.
Linear programming formulations of combinatorial optimization problems, and the case of Totally Unimodular constraint matrices.
Polynomial-Time algorithms for Max-flow, matching, and related problems.
LP relaxation for NP-complete problems and the application of Chernoff bound.
Convex programming and SDP relaxations for NP-complete problems and obtaining approximate solutions.
Will this course involve computer assignments? NO Will this course have TA(s) when it is offered? NO

:: Last modified: September 2011 by C. Chiuco ::

Copyright © 2003 UCLA Electrical Engineering Department. All rights reserved.
Please contact eeweb@ee.ucla.edu for comments or questions for the website.