U.S.-Japan Cooperative Science: Algorithms for Linear Programs Over Symmetric Cones

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

9910084 Monteiro This award supports a three-year collaborative research project between Professor Renato Monteiro of the Georgia Institute of Technology and Professor Takashi Tsuchiya at the Institute of Statistical Mathematics in Tokyo, Japan. The researchers will be undertaking a study of algorithms for linear programs over symmetric cones. Since large-scale semidefinite programming (SDP) problems arise in many applications in continuous optimization, matrix analysis, engineering, statistics and discrete/combinatorial optimization, it is of paramount importance to develop fast and reliable algorithms to solve them. The goal of the proposed research is to provide new insight into the behavior of primal-dual interior-point algorithms and to develop novel computational tools that will enable practitioners to solve large-scale SDP problems. The researchers will investigate nonlinear-programming-type algorithms for solving large-scale specially structured SDP problems. They will also be researching new methodologies to enhance the computational performance of interior-point methods towards solving large-scale SDP problems. Finally they plan to develop and implement efficient interior-point methods for solving nonlinear SDP problems. The project brings together the efforts of two laboratories that have complementary expertise and research capabilities. This research project has excellent potential to have a strong impact on the growing literature about (SDP) problems and on the development of efficient methods to solve them. It will also lead to new or improved algorithms to find exact or approximate solutions to large-scale optimization problems arising in diverse applications in industry, finance science, and engineering. The project advances international human resources through the participation of a graduate student. Through the exchange of ideas and technology, this project will broaden our base of basic knowledge and promote international understanding and cooperation. Results of the research will be published in international scientific journals and also presented at scientific meetings in the U.S. and abroad.