Ämnesdisposition

  • Allmänt

    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


    Schedule

  • 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.