Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Linear and Quadratic optimization problems arise frequently in operations research and their properties are well understood. However, since in real-life applications one must deal with thousands or millions of decision variables, efficient algorithms must be studied. The simplex method of Dantzig was considered *the* linear programming algorithm for many years. The fact that it works is based on a simple geometric approach with convexity as the key property. However, as the number of variables increases, this algorithm proves to be quite slow. Interior-point methods combine powerful ideas of linear algebra (eg, sparse matrix Cholesky factorization) and a modified version of the classical Newton method (for finding zeroes of a function) to produce a very powerful family of algorithms that is easy to understand and more efficient than the simplex method when the number of variables at hand is considerable. What's more, the same idea can be applied to solve convex quadratic problems. The talk will assume no previous knowledge of optimization.