## Topic outline

• ### General

Content
Convexity, linear programming, the simplex method, optimality conditions for nonlinear programming with and without constraints, basics of duality theory.

Teacher:
Zhou, Yishao, together with Berggren, Tomas

Textbook:

Nonlinear Programming - Theory and Algorithms, by Mokhtar Bazaraa, Hanif Sherali, C.M. Shetty, Wiley 2006, (3rd edition).

Time and place:
The lectures will be held on Tuesdays and Fridays from 8.30 to 11.15, starting 5 November, in room 34, house 5, Kräftriket.

Final exam date: January 8, 2015

• ### Day 1, Nov. 4

Lecture: 8.30-10.15

Introduction with basic terminologies and some important problems: a soft start.
Text: BSS Chapter 1
Exercises: 1.1.

• ### Day 2, Nov. 7

Lecture: 8.30-11.15

Convex sets: Convex hulls, Weierestrass's Theorem, the closest-point theorem, Hyperplanes, support sets at a boundary points, separatopn of a convex set and a point two convex sets. Polyhedral sets, extreme points and extreme directions. (Brain storming)
Text: BSS p.40-72.
Exercises: BSS 2.6, 2.7, 2.13,
2.46, 2.47.

• ### Day 3, Nov. 11

Exercise Session, 8.30-11.15

2.1, 2.3, 2.6, 2.8*, 2.12*, 2.15*, 2.21, 2.24, 2.46, 2.49*, 2.50*, 2.53.

If there is time left we'll discuss *-marked problems.

• ### Dag 4, Nov. 14

Lecture: 8.30-10.15, Exercise session 10.30-11.15.

Important properties with convex sets and convex functions.
Text: BSS 3.1, 3.3.
Exercises: BSS 3.1-3.5, 3.12-3.15, 3.39.

• ### Day5, Nov. 18

Lecture 8.30-10.15.

Local and global optima, feasible directions, descent directions.
Text: BSS 3.2, 3.4.
Exercises: BSS 3.26, 3.27, 3.29, 3.51, 3.54.

Exercise session 10.30-11.15

We discuss subgradients and do an exercise BSS 3.27 at Exercise session.

• ### Day 6, Nov. 21

Lecture, 8.30-11.15

Some necessary and sufficient conditions for optimality.  The KKT conditions: optimal problems with inequality constraints.
Text: BSS 4.1, 4.2.
Exercises: BSS 4.1, 4.2,4.4,4.6,4.7, 4.9, 4.12, 4.33.

• ### Day 7, Nov. 25

Exercise session, 8.30-11.15

Some of the following problems from BSS: 3.2, 3.3, 3.11, 3.14, 3.15, 3.26, 3.29, 3.45, 4.6, 4.7,4.9, 4.12, 4.15, 4.27a,b, 4.30, 4.31,4.33.

• ### Day 8, Nov. 28

No class.  Self-study and catch up.

• ### Day 9, Dec. 2

Lecture 8.30-10.15, Exercise session, 10.30-11.15

Lagrange relaxation
Text: K
Exercises: (K)

• ### Day 10, Dec. 5

Lecture 8.30-11.15

Lagrange duality
Text: BSS 6.1, 6.2
Exercises: BSS 6.10, 6.11(a,(b),6.13, 6.15, 6.23.

• ### Day 11, Dec. 9

Exercise session, 8.30-11.15 (TB)

6.10, 6.11(a)(b), 6.13, 6.15, 6.16, 6.17, 6.23, 6.24, 6.26*, 6.27, 6.29(a,b,c),d*

• ### Day 12, Dec. 12

Lecture, 8.30-11.15

Linear programming, recap on extreme points and basic solutions, the simplex method. Two-phase method, Duality in LP.
Text: BSS 2.7
Exercises: BSS 2.23,2.24,2.36,2.34,2.35,2.36,2.39, 2.41, 2.42, 4.10.

• ### Day 13, dec. 16

Exercise session, 8.30-11.15  (TB)
BSS: 2.23,2.24,2.36,2.34,2.35,2.36,2.39, 2.41, 2.42, 4.10, 6.7
• ### Day 14, Dec. 19

Lecture 8.30-10.15

Matrix game (Minimax theorem).

We'll use a section from G. Strang's (S) book Linear algebra and its applications (4th ed).

Exercises: (S) 1,2,3,4,5,6,8,10.