Lecture Time and Location

Wednesday, 6:00-8:50PM. Pearlstein 308.

Instructor

Prof. John MacLaren Walsh. Office: Bossone 203. Telephone: (215) 895-2360. Email: jwalsh@ece.drexel.edu
Office Hours: Thursday 9:00AM-10:00AM. Other times available by email appointment.

Reference Texts

• Linear Optimization and Extensions, 2nd Ed., M. Padberg. Springer-Verlag, 1999.
• Convex Optimization, S. Boyd & L. Vandenberghe. Cambridge University Press, 2004.
• Nonlinear Programming, 2nd Ed., Dimitri P. Bertsekas. Athena Scientific, 1999.

Allof these texts are worth purchasing, in my opinion. If you want a reference, but you must select only one, the last one is the most important one to have. I will post lecture notes and homeworks online which you can work from, but these texts will be extremely handy for any supplemental reading you wish to do.

Course Website

This course has a website: http://www.ece.drexel.edu/walsh/eces811/eces811.html. You will need to check it periodically throughout the semester for information concerning reading assignments, homework assignments, exam information, and projects.

Course Description

This course covers some important results in the theory of mathematical programming and demonstrates them with some engineering applications. Relevant material includes the structure of polyhedra and convex sets, the simplex method, convex functions, convex and affine hulls, the KKT conditions, the Fritz John conditions, duality, and geometric multipliers. While a few of the numerical methods will be discussed, students wishing to become more familiar with numerical methods and optimization software packages are encouraged to also take OPR 992 Applied Mathematical Programming.

Grading Policy

There will be weekly graded homework assignments, a midterm, a final project, and a cumulative final exam. These will count towards the final grade as follows: homework (20%), final project (25%), midterm exam (25%), final exam (30%). If you wish to dispute the grading of a homework/project/exam, you must attach to the homework/project/exam2 a piece of paper outlining your complaint and return it to the instructor within 2 business days after the homework/project/exam is returned. Any disputation of grading which does not follow these guidelines will not be accepted, and may lead to a reduction in your grade.

Rough Outline of Course Content

• Linear Programming
  • Structure of Polyhedra
  • The Simplex Method
  • Passing between representations of polyhedra: Double Descriptions and Reverse Search Methods
• Convex Optimization
  • Convex Sets and Functions
  • Representations of Convex sets. Convex and affine hulls. Carathèodory’s theorem.
  • Convex Programming
    • Karush Kuhn Tucker Conditions
  • Convex Conjugates and Duality
  • Some Basic Numerical Methods
    • Gradient Descent. Conjugate Gradient Descent.
    • Projections Methods. POCS. Bregman Projections.
• Nonlinear Programming
  • Classifying Critical Points of Nonlinear Non-convex Multidimensional Surfaces
    • Saddle, Minimum, Maximum
    • Second Order Conditions
    • Beyond Second Order. Monkey Saddle. Catastrophe theory.
  • Fritz John Conditions
  • Duality and Geometric Multipliers

Lecture Notes & Tentative Course Schedule

• March 30, 2016, April 6, 2016 – Lecture 1 & 2: The structure of polyhedra and the simplex method.
• April 13 & 20, 2016 – Lecture 3: Convex sets, convex functions, & some of their properties.
• April 27, 2016 – Lecture 4: Polyhedral Representation Conversion.
• May 4, 2016 – Midterm Exam: in class.
• May 11, 2016 – Lecture 5: Nonlinear Optimization of Differentiable Functions: The KKT and Fritz John Conditions.
• May 18, 2016 – Lecture 6: Duality and Geometric Multipliers
• May 25, 2016 Lecture 7: Numerical Methods I
• June 1, 2016 – Introduction to Combinatorial Optimization
• June 8, 2016 Final Exam (In Class). Hand in final project.

Assignments

• Homework 1 due April 13 at the beginning of lecture. Solutions.
• Homework 2 due April 26 at the beginning of lecture. Solutions.
• Email an abstract for your final project to Dr. Walsh for review by Wednesday, May 25, 2016.
• Homework 3 due May 28, 2016. Submit via BBlearn site. Solutions.

Exercises (Selected Previous Year’s Assignments & Solutions)

• Structure of Polyhedra. Solutions.
• Standard Form of LP & Simplex Method. Solutions.
• Geometry of Convex Sets. Solutions.