[BANANA] (no subject)

[Gene H Golub]

Linear Algebra and Optimization Seminar
Information
Wednesday
October 24, 2007
4:15 pm - 5:30 pm
Bldg. 160 Rm. 326
Formerly CS 531

Rank Constraint Formulation in Nonlinear Optimization Problems
Jon Dattorro (Stanford University)

  It is often said that "the interesting problems" are not convex. 
Subscribing to such a view is to miss an important point: Art of Convex 
Optimization is the study of problem transformation into convex form. We 
explain how to constrain rank by introducing a linear regularization; an 
iterative generalization of the well-known trace heuristic. To illustrate 
the method during this talk, we show how to formulate a polynomial 
constraint, an equality constraint on vector norm, or an ellipsoid 
boundary constraint. Then we show how to state hard problems within this 
framework: e.g., max cut, Procrustes, Boolean feasibility, projection on 
ellipsoid boundary from anywhere in R^n, closest rank-1 matrix with 
cardinality constraint, sensor network localization or wireless location, 
and the MIT logo perfect reconstruction problem from compressed sensing 
http://www.optimization-online.org/DB_HTML/2007/06/1707.html all in convex 
form. Although this method of convex iteration is proven to converge 
locally, there can be no proof of global convergence from an arbitrary 
initialization. Empirically, we find there to be several problem classes 
where the method seems to work all the time. The challenge remaining is to 
explain why.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Gene Golub,  Fletcher Jones Professor of Computer Science
Gates 2B
Computer Science Dept
Stanford University
Stanford, CA 94305
USA

Office Phone: 650 723 3124
Mobile: 650 796 5402
NEW: E-mail to cell (in US): 6507965402@@teleflip.com
Home Phone: 650 323 0105