Polynomial optimization: matrix factorization ranks, portfolio selection, and queueing theory

Inspired by Leonhard Euler’s belief that every event in the world can be understood in terms of maximizing or minimizing a specific quantity, this thesis delves into the realm of mathematical optimization. The thesis is divided into four parts, with optimization acting as the unifying thread.

Part 1 introduces a particular class of optimization problems called generalized moment problems (GMPs) and explores the moment method, a powerful tool used to solve GMPs. We introduce the new concept of ideal sparsity, a technique that aids in solving GMPs by improving the bounds of their associated hierarchy of semidefinite programs.

Part 2 focuses on matrix factorization ranks, in particular, the nonnegative rank, the completely positive rank, and the separable rank. These ranks are extensively studied using the moment method, and ideal sparsity is applied (whenever possible) to enhance the bounds on these ranks and speed-up their computation.

Part 3 centers around portfolio optimization and the mean-variance-skewness kurtosis (MVSK) problem. Multi-objective optimization techniques are employed to uncover Pareto optimal solutions to the MVSK problem. We show that most linear scalarizations of the MVSK problem result in specific convex polynomial optimization problems which can be solved efficiently.

Part 4 explores hypergraph-based polynomials emerging from queueing theory in the setting of parallel-server systems with job redundancy policies. By exploiting the symmetry inherent in the polynomials and some classical results on matrix algebras, the convexity of these polynomials is demonstrated, thereby allowing us to prove that the polynomials attain their optima at the barycenter of the simplex.