Geometric aspects of interior-point algorithms of optimization

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

Proposal: DMS 0102628 Principal Investigator: Leonid FayBusovich, Department of Mathematics, University of Notre Dame Abstract. PI analyzes geometric and algebraic structures arising in connection with optimization problems. The major goal is to further expand the domain of applications of interior-point algorithms. A method based on the theory of random matrices is proposed to calculate characteristic functions of cones generated by Chebyshev systems and thus self-concordant barriers for these cones. This drastically expands the domain of applicability of interior-point algorithms. In particular, possible applications to spline approximations are outlined. A general approach to the construction of self-concordant barriers for a broad class of infinite-dimensional domains is proposed. The technique of JB-algebras is suggested to carry over the recent impressive applications of the theory of Euclidean Jordan algebras to symmetric programming to the infinite-dimensional situation. Possible control applications are outlined. The theory of interior-point algorithms provides a general framework for the analysis of a broad class of extremely efficient optimization algorithms. These algorithms are used to solve problems aiming at finding the best possible solutions under various constraints (e.g. time constraints , available resources e.t.c ). The realization of the project will enable us to drastically expand a class of problems that can be solved with the help of powerful modern computers.