Interactions of Algebra, Statistics and Optimization

This thesis studies the interplay between algebra and statistics in constrained optimization. It contains four papers: Publications I - III study constrained optimization from the perspective of maximum likelihood estimation in statistics, and Publication IV looks at the optimization problems with polynomial constraints. In maximum likelihood estimation, one observes a data sample and computes the probability density that maximizes the likelihood of observing the given set of data points. As an additional property, we allow assigning different weights to each observation in the sample, for example, to reflect their relative importance. In Publication I, we study the complexity of computing the optimal solution over the family of log-concave densities. We show that there exists a full-dimensional set of weights, such that the corresponding optimal solution is transcendental whenever the data sample consists of rational points. In Publication II, we look at the family of Gaussian distributions and impose that the random variables satisfy certain dependence relations induced by graphs with undirected, directed and bidirected edges. We develop a package GraphicalModelsMLE for the computer algebra system Macaulay2 and discuss interesting applications to enable further research in this field. In Publication III, we take the first step to combine two rich research areas: log-concave density estimation and graphical models. We show that the maximum likelihood log-concave density estimator exists and is unique when the underlying undirected graph is chordal, the number of data points is strictly larger than the size of the largest clique of the graph, and all feasible densities can be written as a product of non-negative log-concave functions, each corresponding to a clique of the graph. Moreover, this estimator is consistent when the undirected graph is a disjoint union of cliques under mild assumptions on the true density. Optimization with polynomial constraints is another rich area of research that is interesting theoretically and useful in various applications. We focus on the case where the objective function has some desirable algebraic properties and the feasible set is the zero set of a system of polynomial equations. Specifically, in Publication IV, we study gradient-solvable objective functions parametrized by data. Roughly speaking, gradient solvability means there exists an explicit formula in radicals that connects the data points and the critical points. We show that there is a finite number of critical points whenever the data is sufficiently general.