Goal: The objective of the course is to introduce different classes of optimization problems (linear, quadratic, non-linear, and integer), their mathematical properties, and basic algorithms for solving them.
Textbook:
- Richard W. Cottle and Mukund N. Thapa, Linear and Nonlinear Optimization, ISBN 978-1-4939-7053-7; Springer New York (2017).
- Gerard Cornuejols and Reha Tütüncü, Optimization Methods in Finance. Fourth Printing, Cambridge university press (2013).
- Available at http://web.math.ku.dk/~rolf/CT_FinOpt.pdf
Modeling Language References:
- Some parts of the homework assignments require programming with AMPL. You should familiarize yourself with AMPL (the book below) and NEOS server: https://neos-server.org/neos/
- Robert Fourer, David M. Gay, and Brian W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, Second edition, ISBN 0-534-38809-4
- Available at https://ampl.com/resources/the-ampl-book/
Recommended Background:
This course makes heavy use of linear algebra and matrix operations and assumes that you are comfortable with college-level mathematical reasonings typical of an engineering curriculum. If you are not comfortable with these background materials, either quickly review them or postpone taking the course until you are ready. In addition, this course requires programming with MATLAB or Python. Make sure you are familiar with either MATLAB or Python coding for implementing of algorithms that requires matrix operation in homework assignments.
Tentative Course Plan:
- Linear Programming
- modeling (selected models and as a modeling tool)
- simplex method and modeling language (AMPL)
- duality theory
- Unconstrained Optimization
- optimality conditions and stationarity definition
- basic descent methods
- convexity in unconstrained optimization
- Quadratic Programming
- applied models (least-squares regression, portfolio selection)
- the LASSO estimator and extensions
- a touch of theory
- feasible direction method
- Nonlinear Programming: Foundation
- applied models (logistic regression, LASSO, least squares regression, SVM, etc.)
- convex optimization
- inequality constraints
- duality in nonlinear optimization (weak duality, strong duality, KKT conditions, constraint qualification)
- Nonlinear Programming: Algorithms
- (projected) gradient descent
- coordinate descent algorithm
- using duality in algorithms
- penalty methods
- examples and implementation in machine learning and data analytics applications
- Integer Programming
- IP examples (knapsack, set covering/partition/packing, logical relations)
- basic branch and bound method
- Lagrangian relaxation
Course Requirement and Grading:
- October 13th, 12pm-1:50pm (30%)
- Final exam, Friday December 10th, 11am-1pm (35%)
- Homework assignments (25%)
- Participation (10%)
Homework assignments:
- All homework assignments are due by 11:59pm on the date indicated.
- Homework assignments must be submitted via Blackboard. Only one pdf file should be submitted for each homework assignment. You can submit latex pdf files, word converted pdfs, or scanned images which are converted to pdf format.
- Late homework submissions are not accepted under any circumstances. Start your homework assignments early.
- There will be weekly (sometimes biweekly) homework assignments. The two lowest scored homework assignments will not be considered in your final grade.
- You are encouraged to discuss homework assignments with other students. However, each student is required to submit his/her own personal work.
Class Participation: Class participation is 10% of your entire grade. This grade will be based on the following two criteria:
- Being present in person or in the online lectures; and actively participate in the discussions
- Answering the questions asked by other students in the class Slack channel and participate in the discussions on Slack
Where should you ask your questions?
- If you have a question regarding homework assignments or other parts of the course that you think other students, the TA, or the instructor can answer it, please ask the question in the course Slack channel. This will increase the interactions among all of us during this pandemic time.
- If you have questions regarding your homework assignment’s grades, please email the TA.
- Email the instructor for other inquiries not listed above.
University policies:
- Statement for Students with Disabilities. Any student requesting academic accommodations based on a disability is required to register with Disability Services and Programs (DSP) each semester. A letter of verification for approved accommodations can be obtained from DSP. Please be sure the letter is delivered to your course instructor (or TA) as early in the semester as possible. DSP is located in STU 301 and is open from 8:30am to 5:00pm, Monday through Friday. Website and contact information for DSP:
http://sait.usc.edu/academicsupport/centerprograms/dsp/home_index.html, (213) 740 – 0776n (Phone), (213) 740-6948 (TDD only), (213) 740-8216 (FAX), ability@usc.edu.
- Statement on Academic Integrity. USC seeks to maintain an optimal learning environment. General Principles of academic honesty include the concept of respect for the intellectual property of others, the expectation that individual work will be submitted unless otherwise allowed by an instructor, and the obligations both to protect ones own academic work from misuse by others as well as to avoid using another’s work as ones own. All students are expected to understand and abide by these principles. SCampus, The Student Guidebook, contains the Student Conduct Code in Section 11.00, while the recommended sanctions are located in Appendix A: http://usc.edu/dept/publications/SCAMPUS/gov/. Students will be referred to the Office of Student Judicial Affairs and Community Standards for further review should there be any suspicion of academic dishonesty. The Review process can be found at: http://usc.edu/student-affaris/SJACS/. Information on intellectual property at USC is available at: http://usc.edu/academe/acsen/issues/ipr/index.html.
- Emergency Preparedness/Course Continuity in a Crisis. In case of emergency, when travel to campus is difficult, if not impossible, USC executive leadership will announce a digital way for instructors to teach students in their residence halls or homes using a combination of the Blackboard LMS (Learning Management System), teleconferencing, and other technologies. Instructors should be prepared to assign students a “Plan B” project that can be completed “at a distance”. For additional information about maintaining your classes in an emergency, please access: http://cst.usc.edu/services/emergencyprep.html.