Polynomial optimization considers optimization problems defined by polynomials. In contrast to classical nonlinearoptimization, it aims at finding global optimizers. Tensors are natural higher-order generalizations of matrices and are closely related to polynomials and moments. They are powerful tools in studying tensors. Many tensor problems can be formulated as polynomial optimization problems.

We propose a complete semidefinite relaxation algorithmfor detecting the copositivity of a symmetric tensor. We show that the detection can be done by solving a finite number of semidefinite relaxations for all tensors.

For the saddle point problem of polynomials,we give an algorithm for computing saddle points. We show that: i) if there exists a saddle point, our algorithm can get one by solving a finite number of Lasserre type semidefinite relaxations; ii) if there is no saddle point, our algorithm can detect its nonexistence.

Hermitian tensors are generalizations of Hermitian matrices, but they have very different properties. Canonical basis Hermitian tensors, real Hermitian tensors, special matrix flattenings, positive semidefiniteness, and separability are studied. We further study how to detect separability of Hermitian tensors. We formulate this as a truncated moment problem and then provide a semidefinite relaxation algorithm to solve it.

The problem of learning diagonal Gaussian mixture models can be formulated as computing incomplete symmetric tensor decompositions. We use generating polynomials to compute incomplete symmetric tensor decompositions and approximations. Then the tensor approximation is used to learn diagonal Gaussian mixture models. When the first and third order moments are sufficiently accurate, we show that the obtained parameters for the Gaussian mixture models are also highly accurate.

Tensors or multidimensional arrays are higher order generalizations of ma-trices. They are natural structures for expressing data that have inherent higher order structures. Tensor decompositions and Tensor approximations play an important role in learning those hidden structures. They have many applications in machine learning, statistical learning, data science, signal processing, neuroscience, and more. Canonical Polyadic Decomposition (CPD) is a tensor decomposition that decomposes a tensor to minimal number of summation of rank 1 tensors. While for a given tensor, Low-Rank Tensor Approximation (LRTA) aims at finding a new one whose rank is small and that is close to the given one. We study the generating polynomials for computing tensor decompositions and low-rank approximations for given tensors and propose methods that can compute tensor decompositions for generic tensors under certain rank conditions. For low-rank tensor approximation, the proposed method guarantees that the constructed tensor is a good enough low-rank approximation if the tensor is to be approximated is close enough to a low-rank one. The proof built on perturbation analysis is presented.

When the rank is higher than the second dimension, we are not able to findthe common zeros of generating polynomials directly. In this case, we need to use the quadratic equations that we get from those generating polynomials. We show that under certain conditions, we are able to find the tensor decompositions using standard linear algebra operations (i.e., solving linear systems, singular value decompositions, QR decompositions). Numerical examples and some comparisons are presented to show the performance of our algorithm. Multi-view learning is frequently used in data science. The pairwise correla- tion maximization is a classical approach for exploring the consensus of multiple views. Since the pairwise correlation is inherent for two views, the extensions to more views can be diversified and the intrinsic interconnections among views are generally lost. To address this issue, we propose to maximize the high-order tensor correlation. This can be formulated as a low-rank approximation problem with the high-order correlation tensor of multi-view data. We propose to use the generat- ing polynomial method to efficiently solve the high-order correlation maximization problem of tensor canonical correlation analysis for multi-view learning. Numerical results on simulated data and two real multi-view data sets demonstrate that our proposed method not only consistently outperforms existing methods but also is efficient for large scale tensors.

Optimization is essential in data science literature. The data science optimization studies all optimization problems that have applications in data science. The polynomial function is broadly used in data science optimization. In data science optimization, we are mostly interested in stochastic optimization, equilibrium games and loss function optimization.

The stochastic optimization studies optimization problems that are constructed with random variables. A classic kind of stochastic optimization is to find the optimizer of a function that is given by the expectation of some random variables. For stochastic optimization with polynomials, we propose an efficient perturbation sample average approximation model. It can be solved globally by Moment-SOS relaxations, and gives a robust approximation of the original problem.

The distributionally robust optimization (DRO) is another kind of stochastic optimization. It assumes the uncertainty is described by an ambiguity set, and aims to optimize the objective function under the worst-case of the ambiguity. For DRO defined with polynomials and under moment ambiguity, we transform it into a linear conic optimization with moment and psd polynomial cones, and give a semidefinite algorithm to solve it globally.

The bilevel optimization is a kind of challenging optimization problems whose feasible set is constrained by the optimizer set of another optimization problem. For bilevel optimization defined with polynomials, we propose a semidefinite algorithm to solve it globally. Under some general assumptions, the algorithm can either get the global minimizer(s), or detect the nonexistence of them.

The generalized Nash equilibrium problem (GNEP) is formed by a group of mutually parametrized optimization problems. It aims to find a equilibrium such that each objective function cannot be solely further optimized. For GNEPs with rational polynomial functions, we propose a new approach for solving them with a hierarchy of rational optimization problems. Under some general assumptions, we show that the proposed hierarchy can compute a GNE, if it exists, or detect its nonexistence.

Loss functions are essential in data science optimization. We study loss functions for finite sets and propose a kind of efficient sum-of-square (SOS) polynomial loss functions for general finite sets. We show how to compute the SOS loss functions of the lowest degree. In addition, we give a special kind of SOS loss functions such that all their local minimizers are also global minimizers.

The Generalized Nash Equilibrium Problem (GNEP) is a kind of game to find strategies for a group of players such that each player’s objective function is optimized, given other players’ strategies. If all the objective and constraining functions involved are polynomials, we call the problem a Generalized Nash Equilibrium Problem of Polynomials (GNEPP). When the constraining functions of each player are independent of other player’s strategies, the GNEP is called a (standard) Nash Equilibrium Problem (NEP). The GNEP is said to be convex if each player’s optimization is a convex optimization problem, given other players’ strategies.

For nonconvex Nash equilibrium problems that are given by polynomial functions, we formulate efficient polynomial optimization problems for computing Nash equilibria. We show that under generic assumptions, the method can find one or even all Nash equilibria if they exist, or detect the nonexistence of Nash equilibria. For convex GNEPPs, we introduce rational and parametric expressions for Lagrange multipliers to formulate polynomial optimization for computing Generalized Nash Equilibria (GNEs). We prove that under some specific assumptions, the method can find a GNE if there exists one, or detect the nonexistence of GNEs. Numerical experiments are presented to show the efficiency of the methods. The Moment-SOS hierarchy of semidefinite relaxations is used to solve the polynomial optimization.

Moreover, we study the Gauss-Seidel method for solving the nonconvex GNEPPs. We give a certificate for a class of GNEPPs such that the Gauss-Seidel method is guaranteed to converge, and the numerical experiments show that the Gauss-Seidel method can solve many GNEPPs efficiently.

Gaussian mixture models are widely used in statistics and machine learning because of their simple formulation and superior fitting ability. High order moments of the Gaussian mixture model form incomplete symmetric tensors generated by hidden parameters in the model. This thesis studies how to recover unknown parameters in diagonal Gaussian mixture models using high order moment tensors. The problem can be formulated as computing incomplete symmetric tensor decompositions. We propose to use generating polynomials to compute incomplete symmetric tensor approximations and approximations. The obtained decomposition is utilized to recover parameters in the model.

In the first part of thesis, we propose a learning algorithm using the first and third order moment tensors and require that the number of components $r\leq\frac{d}{2}-1$ for mixture of $d$-dimensional Gaussians. In the second part of thesis, we generalize the previous algorithm using higher order moment tensors and therefore we can recover the unknown parameters of the model when the number of components $r>\frac{d}{2}-1$. We provide an upper bound of the number of components in the Gaussian mixture model that the generalized algorithm can compute. For both algorithms, we prove that our recovered parameters are accurate when the estimated moments are accurate. Numerical simulations and comparisons with EM algorithm are presented to show the performance of our algorithms.

This dissertation contains three essays on revealed preference and decisions. Chapter 1 examines whether there is any behavior that cannot be described by a game where individuals play backwards-induction strategies. Chapter 2 characterizes a stochastic choice rule when randomness is driven by the feasibility of alternatives. Chapter 3 performs a revealed preference analysis on stochastic choices made by individuals who act as if they have preferences over lotteries when the characteristics of alternatives vary.