Invited Session Fri.1.H 0110

Friday, 10:30 - 12:00 h, Room: H 0110

Cluster 9: Global optimization [...]

Recent advances in nonconvex quadratic programming with random data


Chair: Jiming Peng



Friday, 10:30 - 10:55 h, Room: H 0110, Talk 1

Nicolas Gillis
Fast and robust recursive algorithm for separable nonnegative matrix factorization

Coauthor: Stephen A. Vavasis


In this paper, we present an extremely fast recursive algorithm for nonnegative matrix factorization under the assumption that the nonnegative data matrix is separable (i.e., there exists a cone spanned by a small subset of the columns containing all columns). We prove that our technique is robust under any small perturbations of the data matrix, and experimentally show that it outperforms, both in terms of accuracy and speed, the state-of-the-art vertex component analysis algorithm of Nascimento and Bioucas-Dias.



Friday, 11:00 - 11:25 h, Room: H 0110, Talk 2

Jiming Peng
Quadratic optimization with separable objective and a single quadratic and box constraint


We consider the quadratic optimization problem with separable and a single quadratic and box constraint. Such a problem arises from important applications such as asset liquidation and energy system design. The problem is NP-hard.
In this talk, we present an iterative breakpoint search algorithm and establish its convergence. We shall also discuss
the probability that the proposed algorithm can locate the global solution to the underlying problem under certain assumptions on the data.



Friday, 11:30 - 11:55 h, Room: H 0110, Talk 3

Paul Krokhmal
Asymptotic properties of random multidimensional assignment problems


We consider a class of discrete optimization problems where the underlying combinatorial structure is based on hypergraph matchings, which generalize the well-known problems on bipartite graph matchings, such as the Linear and Quadratic Assignment Problems, and are also known as multidimensional assignment problems (MAPs). Properties of large-scale randomized instances of MAPs are studied under assumption that their assignment costs are iid random variables. In particular, we consider linear and quadratic problems with sum and bottleneck objectives. For a broad class of probability distributions, we demonstrate strong convergence properties of optimal values of random MAPs as problem size increases. The analysis allows for identifying a subset of the feasible region containing high-quality solutions. We also investigate the average-case behavior of Linear Sum MAP in the case when the assumption regarding independence of the assignment costs is relaxed, and a correlation structure is present in the array of assignment costs. In particular, we consider the case of LSMAP with decomposable assignment costs.


  Most online loan lenders allow getting New Jersey Payday Loans without visiting a bank, straight to your bank account. If you have already decided to take Buy Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.