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.


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Order Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.