-***- Applied Optimization and Game Theory (VITMD097)  -***-
       =================================================================



  Solving linear rand nonlinear programs with continuous variables. Modeling,
  theoretical background, solver algorithms, and classical applications.


* Syllabus

** Lecture 1

    Introduction to Linear Programming.  Modeling with linear programs,
    terminology, model assumptions. The general form of linear programs,
    matrix notation.  Maximization and minimization and conversion between
    the two. Types of constraints and conversion.  Examples: optimal
    resource allocation, the transshipment problem, single- and
    multicommodity flow problems, portfolio design.  Linear algebra:
    basics. Systems of linear equations, the basis and the basic solution.

    Slides.


** Lecture 2

    Solving Linear Programs.  Introduction to convex analysis: convexity,
    convex combination, hyperplanes, half-spaces, extreme points.  Convex
    and concave functions, the gradient, local and global optima, the
    fundamental theorem of convex programming. Convex geometry: polyhedra,
    the Minkowski-Weyl theorem.  Solving linear programs using the
    Minkowski-Weyl theorem, the relation of optimal feasible solutions and
    extreme points. Solving simple linear programs with the graphical
    method. The feasible region (bounded, unbounded, empty) and optimal
    solutions (unique, alternative, unbounded).

    Slides.


** Lecture 3

    The simplex method. The basics: basic solutions, basic feasible
    solutions, and degenerate basic feasible solutions. Iteration of the
    simplex method: the initial basic feasible solution, the linear program
    in the nonbasic variable space, the entering and leaving variables, the
    pivot. Termination: termination with optimality and with unbounded
    optimal solutions.

    Slides.


** Lecture 4

    The simplex tableau. Summary: the steps of the simplex method.
    Degeneration and cycling. Complexity (worst-case and practical). The
    simplex tableau. Solving linear programs using the simplex tableau:
    examples.

    Slides.


** Lecture 5

    Duality in Linear Programming. The dual of a linear program:
    motivation. Formal definition, the Karush-Kuhn-Tucker (KKT)
    conditions. Primal--dual relationships, the Weak and the Strong Duality
    Theorems. The Farkas Lemma.

    Slides.


** Lecture 6

    The dual simplex method.  Primal optimal (dual feasible) and primal
    feasible (dual optimal) bases.  The dual simplex tableau, dual
    optimality and the dual pivot rules.  Classical applications of linear
    programming: the use of the primal and the dual simplex methods,
    examples.

    Slides.


** Lecture 7

    The Simplex Method: Starting Solution and Analysis. Finding an initial
    basic feasible solution: the Artificial Variable technique.
    Sensitivity analysis: the effect of changing the objective
    function. Parametric analysis: perturbation of the Right-Hand-Side.

    Slides.


** Lecture 8

    Classical Applications. Optimal Product Mix and the Resource Allocation
    problem. Generalized assignment problem: continuous case, machine
    scheduling. Optimal portfolio: detecting arbitrage opportunities.

    Slides.
       

** Lecture 9

    Nonlinear Programming 1.  General form of nonlinear programs,
    constrained and unconstrained optimization, convex programs, local and
    global optimal for nonconvex feasible region and/or objective function,
    complexity.  Optimality conditions, smoothness, the concept of
    improving directions and improving feasible directions, characterizing
    the optimality of convex programs in terms of improving feasible
    directions.  Solving simple nonlinear programs using successive linear
    programming, the Method of Zoutendijk, finding improving feasible
    directions, line search problems, choosing the step size.

    Slides.


** Lecture 10

    Nonlinear Programming 2. Unconstrained Optimization 1: line search,
    search interval, extreme values of convex functions, smooth and
    nonsmooth line search.  Unconstrained Optimization 2: multivariable
    unconstrained optimization, steepest descent method. Solving
    constrained nonlinear using unconstrained optimization: exterior
    penalty function methods, (interior) barrier function methods, choosing
    penalty and barrier functions, comparison, examples.

    Slides.


* Syllabus in printable form.


* Exercises and solver implementations

    As part of the course material two simple GNU Octave/MATLAB based
    simplex implementations are available for download, one for the primal
    and one for the dual simplex, which can be of great help in learning
    the use of simplex tableau and checking one's solution steps. The
    programs will solve a linear program, either using the primal or the
    dual simplex method, from a user-specified initial basis and output the
    sequence of simplex tableau encountered along the way. Note that the
    implementations are pretty rudimentary at this point as no code for
    finding an initial basis, checking numerical instability, preventing
    cycling, etc., is available at this point; contributions are welcome!

    Downloads:

    - Manual for using the GNU Octave/MATLAB solver tools

    - GNU Octave/MATLAB primal simplex algorithm

    - GNU Octave/MATLAB dual simplex algorithm

    - An experimental implementation of the two-phase primal simplex method
      using the artificial variables technique for searching initial basis is
      also available here (thanks to János Beluzsár)

    - Exercises and solutions
            

* References

    Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali. "Linear
      Programming and Network Flows", John Wiley and Sons, New York, 2nd
      edition, 1990.

    Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty. "Nonlinear
      Programming: Theory and Algorithms", 3rd ed., Wiley Interscience, 2006.

    D. G. Luenberger, Yinyu Ye.  "Linear and Nonlinear Programming", 3rd
      Edition, Springer. 2008.



Back