Math 164 Optimization. Winter 2013, section 3.


For up-to-date infromation check the official course website.
Lectures: MWF 1-1:50 pm in MS 5147
Section: Thursday 1-1:50pm in MS 5147

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.

Homework

(check the CCLE website)

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)

Course syllabus

Lecture Date Book Sections Topic
1 Jan 7 2.2 Fundamentals of Optimization: Feasibility and Optimality
2Jan 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 13Lectures 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.

Homework: