## 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**

**Abstract:**

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

**Abstract:**

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

**Abstract:**

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.