Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Guest lecture

Jiming Peng

University of Illinois at Urbana-Champaign

Sparse solutions in standard quadratic optimization

Abstract:

Sparse solutions in optimization has been a major concern for optimization problems from various applications such as image processing and portfolio selection. It is well-known that several classes of linear optimization problems such as the linear assignment problem, transportation problem and the $L_1$ minimization problem with linear equality constraints, have sparse solutions.\\ It has also been observed in experiments for long that several classes of quadratic optimization problems (QP) such as Markowitz's mean-variance model for portfolio selection always have sparse optimal solutions. However, so far little is known from a theoretical perspective.\\ In this talk, we present a new theoretical framework to interpret why certain classes of QPs do have sparse solutions. For this, we first use the optimality conditions for the so-called standard quadratic optimization problem to establish an intrinsic relation between the sparsity of the optimal solution of the QP and some prpbability events. Then we show that with a very high probability, the underlying QP has a very sparse solution if the input data of the associated QP follows certain distributions such as uniform and normal distributions. If time allows, we shall also discuss some extensions and open questions.

Host: Jiawang Nie

September 3, 2010

2:00 PM

AP&M 6402

****************************