An algorithmic analysis of multiquadratic and semidefinite programming problems

Motakuri V. Ramana

1994 · 61 citations · 0 references

Concepts

Abstract

are addressed. Two algorithms are developed for certain feasibility versions of the SDP, and the rst of these is shown to have polynomial time complexity when the dimension of the matrix map involved is xed. The second algorithm is a globally convergent Newton-like method applied to a least-squares penalty function. The problem of characterizing and identifying quadratic maps with convex images is analyzed from both structural and complexity theoretic points of view. Then a study is made of the geometry of a class of convex sets called spectrahedra, which are the feasible regions in semide nite programs. Finally, in Chapter 7, we develop some cutting plane techniques for MQP, based on eigenvalue inequalities. Acknowledgements I express my sincere gratitude to my thesis advisor Professor Alan Goldman for his support, ideas and encouragement. My special thanks to Professors Laszlo Lovasz and James Renegar for sparing their time generously and giving me very useful suggestions. I thank the warm and friendly Professors Dan Naiman and Ed Scheinerman for making my four year long stay at Johns Hopkins a very pleasant one. I am indebted to Prof. Jong-Shi Pang and Prof. Roger Horn for giving a patient ear to many of my enthusiastic ideas and o ering suggestions. I also thank Prof. Shih-Ping Han for being a wonderful teacher, and Prof. Leslie Hall for being a patient second reader of my thesis. My interest in Multiquadratic Programming was initiated during my internship at AT&T Bell Laboratories in the summer of 1990, and I am obliged to Dr. Narendra Karmarkar for arranging this internship. I thank Dr. Farid Alizadeh, Dr. Florian Jarre, Profs. Raphael Loewy, Michael Overton and Stephen Vavasis for patiently answering my questions and sending me some literature. My heartfelt appreciation is due my parents, Lakshmi Pathy and Satyavathi, my sister,