Home

Convex Optimization

DATE: 28th June - 2nd July 2010
LOCATION: Brunel University

The main aims of this course are to develop knowledge of different theoretical aspects of convex optimization and to develop practical skills in applying optimization technology in the real world. For doctoral students who are working on the theoretical issues in optimization, it provides a solid foundation upon which advanced theoretical problems can be addressed in their further research. For students whose research focus is developing complex optimization models for real life problems, the course offers plenty of hands-on modelling experience with an industry strength solver. The course will enable all students to gain deeper and broader insights into the exciting world of optimization. It promises to be a challenging, stimulating and enjoyable week for all.

Main contributors: Dr Paresh Date (Brunel University), Dr Cormac Lucas (Brunel University), Prof John Beasley (Brunel University), Dr Nenad Mladenovic (Brunel University), Prof Jacek Gondzio (University of Edinburgh), Prof Shabbir Ahmed (Georgia Institute of Technology).

PRE-REQUISITES

  1. Undergraduate level knowledge of linear algebra (e.g. the relevant chapter in Winston’s textbook on OR) and calculus (e.g. basic notions of continuity and differentiability).
  2. The students are expected to have familiarized themselves with the material marked with an asterisk in the teaching schedule and with other directed reading.

AIMS

  1. To develop knowledge of different aspects of convex optimization and its applications.
  2. To develop an ability to model real life problems as mathematical programming problems and an ability to adapt industry standard solvers to process them.
  3. To develop an ability to analyze optimization algorithms for their merits and shortcomings.
  4. To develop an ability to work independently as well as in a peer group with limited supervision.

LEARNING OUTCOMES

The course provides opportunities for students to develop and demonstrate knowledge and understanding, qualities, skills and other attributes in the following areas:

A: Knowledge and Understanding
On successful completion of this course, the students will have

  1. knowledge of theoretical underpinning of convexity in optimisation and of general nonlinear programming methods. This knowledge will act as a foundation to understand an advanced graduate textbook or a research paper without significant help.
  2. understanding of linear programming methods and related theoretical issues.
  3. knowledge of semi-definite programming.
  4. ability to use an industry standard optimization software system for processing optimization models.

B: Cognitive Skills
On successful completion of this course, the students will be able to

  1. formulate realistic industrial problems as mathematical programming problems.
  2. analyze critically the choice of algorithms for solving different classes of a particular optimization model regarding their computational effectiveness.
  3. construct elementary proofs related to the properties of optimization methods.

C: Other Skills and Attributes (Practical/Professional/Transferable)
On successful completion of this course, the students will be able to

  1. plan and execute a solution to an optimization problem as a group and will be able to present the results to peers and tutors.

PRINCIPAL TOPICS OF STUDY:

  • Foundations of Convexity: affine and convex sets, convex functions, composition of convex functions.
  • General Convex Optimization: examples of convex optimization problems, duality, unconstrained minimization, steepest descent method, first and second order optimality conditions in unconstrained minimization, Newton's method and convergence analysis, norm approximation problems.
  • Linear Programming: simplex method, duality for LP, interior point methods for LP.
  • Convex Quadratic Programming: simplex method for quadratic programming, application in finance, KKT conditions for convex QP.
  • Semi-definite Programming: formulation, extension of interior point methods to SDP, quadratically constrained convex quadratic programs.
  • A case study of convex optimization in industry.
  • Numerical Linear Algebra: algorithm complexity, Cholesky factorization, sparsity.
  • Use of Industry Strength Solver Systems for LP/QP to process industrial problems.

    • REFERENCES

    [1] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. As of June 2009, this text is freely available to download at http://www.stanford.edu/~boyd/cvxbook/ . The chapters relevant to this course are 2-5 and 9-11.

    [2] D.G. Luenberger, Linear and Nonlinear Programming, Kluwer, 2003. The chapters relevant to this course are 2-10.

    [3] R. Fourer, .M. Gay, B.W. Kernighan, Ampl: A Modeling Language for Mathematical Programming, Brooks Cole, 2002.

    [4] Hillier and Lieberman, Introduction to Operations Research, McGraw Hill, 2002. The chapter relevant to this course is 13.