|
HU Credits:
3
Degree/Cycle:
2nd degree (Master)
Responsible Department:
Computer Sciences
Semester:
2nd Semester
Teaching Languages:
English and Hebrew
Campus:
E. Safra
Course/Module Coordinator:
omri weinstein
Coordinator Office Hours:
Teaching Staff:
Prof. Weinstein Omri
Course/Module description:
This course will cover advanced algorithms for solving Linear Programming, from the Simplex method and Ellipsoid to Interior-Point Methods (IPMs), Self-Concordant Barrier functions, and Energy-based analysis of IPMs.
In the second part of the course we will explore fast approximate LP solvers using variants of the Multiplicative-Weight Updates method (MwU), including the Frank-Wolfe algorithm, Clarkson’s algorithm, MaxFlow (CKMST) and properties of the Energy Potential function.
Course/Module aims:
Learning outcomes - On successful completion of this module, students should be able to:
Research project + Seminar-style presentation.
Attendance requirements(%):
70
Teaching arrangement and method of instruction:
Course/Module Content:
•LP Rounding + Applications
•Convex Duality and the
Frenchel Dual.
• The Simplex & Ellipsoid
algorithms.
• (Quasi-)Newton Methods &
convergence for SC
functions.
• Interior-Point Methods
• Energy-based potential
Analysis (Perturbing the
central path)
• The Multiplicative Weight Updates Method (PST/Clarkson/Frank-Wolfe)
• (Time permitting:) Acceleration via Linear Coupling
Required Reading:
Convex Optimization,
S. Boyd
Additional Reading Material:
Yin-Tat Lee’s course “Optimization and Geometry” in UW
Grading Scheme :
Essay / Project / Final Assignment / Home Exam / Referat 70 %
Presentation / Poster Presentation / Lecture/ Seminar / Pro-seminar / Research proposal 30 %
Additional information:
|
