-***- 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
Summary
Video
** 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
Summary
Video
** 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
Summary
Video
** 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
Summary
Video
** 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
Summary
Video
** 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
Summary
Video
** 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
Summary
Video
** 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
Summary
** 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