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