← volver

Ciclo seminarios Instituto Sistemas Complejos de Ingeniería (ISCI) / Robert Freund, MIT

13:30 – 14:30, sala Asamblea (401), Beauchef 851, cuarto piso, Torre Oriente, Santiago.

Expone: Robert Freund, Theresa Seley Professor in Management Science and a Professor of Operations Research at the MIT Sloan School of Management.

Título del seminario: “An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities”

Abstract
The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of linear inequalities P: Ax <= u when the set of solutions S := { x Ax <= u } has positive volume.  However, when P is infeasible, the ellipsoid algorithm has no built-in mechanism for proving that P is infeasible.  This is in contrast to the other two fundamental algorithms for tackling P, namely the simplex method and interior point methods, each of which can be easily implemented in a way that either produces a solution of P or proves that P is infeasible by producing a solution to the alternative system ALT: A*w = 0$, u*w < 0, w >= 0.  Motivated thusly, we develop an Oblivious Ellipsoid Algorithm (OEA) that produces a solution of P when P is feasible and produces a solution of ALT when P is infeasible, and whose operations complexity in the regime m >> n is on the same order as a standard ellipsoid method (O(m^4)) when P is infeasible (but has worse complexity when P is feasible). However, if one is only interested in a proof/certificate of infeasibility and not necessarily a solution of ALT, then we show that a simplified version of OEA achieves  O(m^3n) complexity, which is superior to the O(m^4) complexity bound of a standard ellipsoid algorithm applied to solve ALT.

Organiza: Instituto Milenio sistemas Complejos de Ingeniería (ISCI)

INSCRIPCIONES