Course Description: Fundamentals of optimization. Linear
programming: basic solutions, simplex method, duality theory.
Unconstrained optimization, Newton's method for minimization. Nonlinear
programming, optimality conditions for constrained problems.
Prerequisite: course 115A (linear algebra). Not open for credit to
students with credit for Electrical Engineering 136.
This course is not about model building and practical application, it will be concerned primarily with the mathematical aspects of optimization with rigorous treatment --- definitions, theorems, proofs and purely mathematical examples. Section 1.7 of the textbook presents some practical applications of the topics that will be covered and is recommended as a side reading.
Instructor: Greta Panova
e-mail: panova (at) math.ucla.edu
Office: Math Sciences 6334
Office Hours: Monday 3-5 (except holidays), Wednesday 3-4.
Teaching Assistant: Wenying Gan
wgan at ucla.edu, MS 3921, Office hours: Thursday 11-12, 3-4.
Texbook: Linear and Nonlinear Optimization , 2nd edition, by Igor Griva, Stephen G. Nash, Ariela Sofer.
Grading scheme: Final exam 60%. Midterm 25%. Homework 15%.
Final letter grade will be determined relative to all students' scores (so-called "curve"). There will be no make-up exams. Homework will be listed below weekly and will be due in the beginning of lecture on. (after Section) No late homework will be accepted, instead your two lowest homework grades will not be counted towards your final grade.
Exams: The midterm will be on Wednesday, February 13, in class
and will cover the material from Lectures 1-13. There will be a
comprehensive final exam, the date is determined by the Registrar's Office
and will be announced later. For both exams you'd need only a pen (or
pencil) and your Bruin card, i.e. no books, notes, paper,
calculators, phones or other electronic devices will be allowed.
Practice sample exams will be uploaded here in advance.
1. Due Friday Jan 18:
To be handed in for grading: Chapter 2.2 problem 2.3 (page 47), Chapter 2.3 problem 3.12 (page 53), Chapter 3.1 problem 1.3(i) and problem 1.1 only for x_b =(3,0,1)^T (page 82).
Recommneded problems for exercise: Chapter 2.2 -- 2.1, 2.4; Chapter 2.3 -- 3.1,3.20; Chapter 3.1 -- 1.1 (for the remaining values of x), 1.2, 1.3(iv).
2. due Friday Jan 25 in class:
for grading: Chapter 4.1 problems 1.1(iv) and (vi), Chapter 4.2 problem 2.3 (hint: use only 2 excess/slack variables); Chapter 4.3 -- for the linear program from Chapter 4.2, 2.3 determine all basic solutions and which of them are feasible, problem 3.12, problem 3.17(i)(ii).
For exercise (not to be handed in): Chpater 4.1 -- 1.2, 1.4; Chapter 4.2 -- 2.2, 2.5; Chapter 4.3 -- 3.7, 3.9, 3.16.
3. due Friday Feb 1.
For grading: Chapter 4.3: Chapter 4.3 problems 3.2, 3.3, 3.17(iii); Chapter 4.4: problem 4.4, problem 4.5, problem 4.6 (find only one representation, no need for 3).
For exercise: 4.3.9; 4.3.4; 4.3.8; 2.3.18; 4.4.1; 4.4.3; prove that the set S of all points which are convex combinations of k points w_1,...,w_k is a convex set.
4. due Friday Feb 8.
For grading: Chapter 5.2, problems 2.2(ii), 2.4, 2.9(ii)(iii)(iv)(you can solve it for n=4 instead of general n); Chapter 6.1 - problem 1.4 (no need to simplify) and 1.6; Chapter 6.2 - problem 2.15(i).
For exercise: 5.2.2((iv)(v), 5.2.7, 5.2.10; 6.1.1, 6.1.3, 6.1.7;
6.2.3, 6.2.4, 6.2.7, 6.2.8, 6.2.10, 6.2.15(ii) ,6.2.19
Note: The material from 6.1 and 6.2 will be covered on Monday and Wednesday, most of the exercise problems from 6.2 are not "due" next Friday, but are meant for midterm exercise.
Homework 5, due February 22.
For grading: Chaapter 2.6, problems 6.4, 6.5; Chapter 2.7, [roblem 7.10 -- starting with the point y_0=(1,1) apply Newton's method for one step to find the next point y_1 and calculate f(y_1) to 3 decimal places; Chapter 11.2 -- problem 2.10(i)(ii) (answer only the first question, about the minimizer), problem 2.13(i)
For exercise: 2.6.6, 2.7.1, 2.7.5, 11.2.3,11.2.9
Homework 6, due March 1.
For grading: Chapter 11.3 problems 3.3 (do 2 iterations), 3.6; Chapter 3.2 problems 2.1(ii)(iii), 2.2
For exercise: 11.3.2, 11.3.4 (no need to find rate of convergence), 3.2.3, 3.2.4, 3.2.5
Homework 7, due Friday March 8.
For grading: Chapter 14.2, problems 2.2(vi), 2.6, 2.10; Chapter 14.3 problem 3.3 ("perturbed problem" refers to the problem with constraints "Ax=b+delta")
For exercise: 14.2.1, 14.2.7, 14.2.12, 14.2.14, 14.2.16; 14.3.1
Homework 8, due Friday March 15 by 1pm (sharp!)
For grading: Chapter 14.4, problem 4.2 (find the local minimizers only) (20 points), 4.4(i) (10 points), 4.10 (10 points).
For exercise: Show that ( (2+sqrt(7))/3, 0) is a local minimizer in Example 14.13 (page 499), 14.4.1, 14.4.6, 14.4.8 (hint: first express x_n through the remaining variables and convert the problem to an inequality constrained one)
|1||Jan 7||2.2||Fundamentals of Optimization: Feasibility and Optimality|
|2||Jan 9||2.3 (without 2.3.1)||Convexity.|
|3||Jan 11||3.1||Linear constraints: basic concepts.|
|4||Jan 14||4.1||The geometry of linear programming (introduction).|
|5||Jan 16||4.2||The standard form (of linear programming -- LP).|
|6||Jan 18||4.3||Basic solutions and extreme points in LP.|
|Jan 21||---||Holiday: Martin Luther King, Jr|
|7||Jan 23||4.3||Basic solutions and extreme points in LP. (continued)|
|8||Jan 25||4.3, 4.4||Extreme points (continued). Representation of solutions in LP.|
|9||Jan 28||4.4, 5.2||Representations of linear constraints (continued).|
|10||Jan 30||5.2||The simplex method.|
|11||Feb 1||5.2, 6.1||The simplex method (continued). The dual LP problem.|
|12||Feb 4||6.2||Duality theory.|
|13||Feb 6||6.2.1 and 6.2.2||Complementary slackness.|
|Feb 8||A.7.1, B.4, 2.3.1, 2.6||Gradient, Hessian and Jacobian. Derivatives and convexity. Taylor series.|
|14||Feb 11||2.7, 2.7.1||Newton's method for (systems of) nonlinear equations.|
|15||Feb 13||Lectures 1-13||Midterm.|
|16||Feb 15||11.2||Unconstrained optimization, optimality conditions.|
|Feb 18||---||Holiday: Presidents' Day|
|17||Feb 20||11.3||Newton's method for minimization|
|18||Feb 22||3.2||Null and range spaces.|
|19||Feb 25||B.7, 14.2||Linear equality constrained problems.|
|20||Feb 27||14.2||Optimality conditions for linear equality constraints.|
|21||Mar 1||14.3||Lagrange Multipliers and the Lagrange function I.|
|22||Mar 4||14.3, 14.4||The Lagrange multiplier and the Lagrange function II. Linear inequality constrained problems.|
|23||Mar 6||14.4||Optimality conditions for linear inequality constraints.|
|24||Mar 8||14.4||Optimality conditions for linear inequality constraints. (continued)|
|25||Mar 11||14.5||Optimality conditions for nonlinear constraints.|
|26||Mar 13||14.5||Optimality conditions for nonlinear constraints.(continued)|
|27||Mar 15||14.5||Optimality conditions for nonlinear constraints. (continued)|
|End.||Mar 21, 3-6pm||Lectures 1-27||Final Exam.|