Low-rank Semidefinite Programming: Theory and Applications

by Alex Lemon, Anthony Man-Cho So, Yinyu Ye

Finding low-rank solutions of semidefinite programs is important in many applications. For example, semidefinite programs that arise as relaxations of polynomial optimization problems are exact relaxations when the semidefinite program has a rank-1 solution. Unfortunately, computing a minimum-rank solution of a semidefinite program is an NP-hard problem. This monograph reviews the theory of low-rank semidefinite programming, presenting theorems that guarantee the existence of a low-rank solution, heuristics for computing low-rank solutions, and algorithms for finding low-rank approximate solutions. It then presents applications of the theory to trust-region problems and signal processing.

178 pages, Paperback

Published August 4, 2016

About the author

Alex Lemon's poetry collections include Hallelujah Blackout (2008 Milkweed Editions) and Mosquito (Tin House Books 2006). A memoir is also forthcoming from Scribner. His poems have appeared or are forthcoming in numerous magazines including AGNI, BOMB, Denver Quarterly Gulf Coast, Kenyon Review, New England Review, Pleiades and Tin House. Among his awards are a 2005 Literature Fellowship in Poetry from the National Endowment for the Arts and a 2006 Minnesota Arts Board Grant. He is the co-editor of LUNA: A Journal of Poetry and Translation and is a frequent contributor to The Bloomsbury Review. He teaches in the English Department at TCU in Fort Worth, TX.