# The Multi-Objective Polynomial Optimization

Jiawang Nie  Jiawang Nie, Zi Yang, Department of Mathematics, University of
California San Diego, 9500 Gilman Drive, La Jolla, CA, USA, 92093.
<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Zi Yang

###### Abstract.

The multi-objective optimization is to optimize several objective functions
over a common feasible set. Since the objectives usually do not share a common
optimizer, people often consider (weakly) Pareto points. This paper studies
multi-objective optimization problems that are given by polynomial functions.
First, we study the convex geometry for (weakly) Pareto values and give a
convex representation for them. Linear scalarization problems (LSPs) and
Chebyshev scalarization problems (CSPs) are typical approaches for getting
(weakly) Pareto points. For LSPs, we show how to use tight relaxations to
solve them, how to detect existence or nonexistence of proper weights. For
CSPs, we show how to solve them by moment relaxations. Moreover, we show how
to check if a given point is a (weakly) Pareto point or not and how to detect
existence or nonexistence of (weakly) Pareto points. We also study how to
detect unboundedness of polynomial optimization, which is used to detect
nonexistence of proper weights or (weakly) Pareto points.

###### Key words and phrases:

Pareto point, Pareto value, polynomial, scalarization, moment relaxation

###### 2010 Mathematics Subject Classification:

90C29,90C30,90C22

##  1\. Introduction

The multi-objective optimization problem (MOP) is to optimize several
objectives simultaneously over a common feasible set. MOPs have broad
applications in economics [14], finance [5], medical science [50, 52], and
machine learning [53]. In this paper, we consider the MOP in the form

(1.4)
$\displaystyle\left\\{\begin{array}[]{rl}\min&f(x):=(f_{1}(x),\ldots,f_{m}(x))\\\
\mathit{s.t.}&c_{i}(x)=0\,(i\in\mathcal{E}),\\\ &c_{j}(x)\geq
0\,(j\in\mathcal{I}),\\\ \end{array}\right.$

where all functions $f_{i},c_{i},c_{j}$ are polynomials in
$x:=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$. The $\mathcal{E}$ and
$\mathcal{I}$ are disjoint finite label sets. Let $K$ denote the feasible set
of (1.4). Generally, there does not exist a point such that all $f_{i}$’s are
minimized simultaneously. People often look for a point such that some or all
of the objectives cannot be further optimized. This leads to the following
concepts (see [36, 38, 48]).

######  Definition 1.1.

A point $x^{*}\in K$ is said to be a Pareto point (PP) if there is no $x\in K$
such that $f_{i}(x)\leq f_{i}(x^{*})$ for all $i=1,\ldots,m$ and
$f_{j}(x)<f_{j}(x^{*})$ for at least one $j$. The point $x^{*}$ is said to be
a weakly Pareto point (WPP) if there is no $x\in K$ such that
$f_{i}(x)<f_{i}(x^{*})$ for all $i=1,\ldots,m$.

In the literature, Pareto points (resp., weakly Pareto points) are also
referenced as Pareto optimizers (resp., weakly Pareto optimizers), or Pareto
solutions (resp., weakly Pareto solutions). A vector $v:=(v_{1},\ldots,v_{m})$
is called a Pareto value (resp., weakly Pareto value) for (1.4) if there
exists a Pareto point (resp., weakly Pareto point) $x^{*}$ such that
$v=f(x^{*})$. Pareto front is the set of objective values at Pareto points.
Every Pareto point is a weakly Pareto point, while the converse is not
necessarily true. Detecting existence or nonexistence of (weakly) Pareto
points is a major task for MOPs. We refer to [2, 3, 23, 36, 38, 48] for
related work about existence of PPs and WPPs.

Scalarization is a classical method for finding PPs or WPPs. It transforms a
MOP into a single objective optimization problem. A frequently used
scalarization is a nonnegative linear combination of objectives.

######  Definition 1.2.

The linear scalarization problem (LSP) for the MOP (1.4), with a nonzero
weight $w:=(w_{1},\ldots,w_{m})\geq 0$, is

(1.6) $\displaystyle\begin{array}[]{rl}\min\limits_{x\in
K}&w_{1}f_{1}(x)+\cdots+w_{m}f_{m}(x).\end{array}$

Every minimizer of the LSP (1.6) is a weakly Pareto point for nonzero $w\geq
0$ and every minimizer is a Pareto point for $w>0$. Varying weights in (1.6)
may give different (weakly) Pareto points. A nonzero weight $w$ is said to be
proper if the LSP (1.6) is bounded below. Otherwise, the $w$ is called
improper. One wonders whether or not every Pareto point is a minimizer of
(1.6) for some weight $w$. However, this is sometimes not the case (see [13,
54]). For instance, Example 5.4 has infinitely many Pareto points, but only
two of them can be obtained by solving LSPs. Under some assumptions, LSPs may
give all Pareto points (see [11]).

Another frequently used scalarization is the Chebyshev scalarization. It
requires to use the minimum value of each objective.

######  Definition 1.3.

The Chebyshev scalarization problem (CSP) for the MOP (1.4), with a nonzero
weight $w=(w_{1},\ldots,w_{m})\geq 0$, is

(1.8) $\displaystyle\begin{array}[]{rl}\min\limits_{x\in K}&\max\limits_{1\leq
i\leq m}\,w_{i}\big{(}f_{i}(x)-f_{i}^{*}\big{)}\end{array}$

where the minimum value $f_{i}^{*}:=\min\limits_{x\in K}f_{i}(x)>-\infty$.

Every minimizer of the CSP (1.8) is a weakly Pareto point. Interestingly,
every weakly Pareto point is the minimizer of a CSP for some weight (see [24,
38]). However, the minimizer of a CSP may not be a Pareto point. There also
exist other scalarization methods, such as the $\epsilon$-constraint method
[1, 37], the lexicographic method [7, 22]. We refer to [6, 10, 36, 38, 51] for
different scalarizations.

There exists important work for MOPs given by polynomials. When all functions
are linear, a semidefinite programming method is given to obtain the set of
Pareto points in [4]. When the functions are convex polynomials, Moment-SOS
relaxation methods are given to compute (weakly) Pareto points in [18, 19, 20,
21, 33], as well as some useful conditions for existence of (weakly) Pareto
points. When the functions are nonconvex polynomials, nonemptiness and
boundedness of Pareto solution sets are shown in [34], under certain
regularity conditions. When the objectives are polynomials and $K$ is the
entire space $\mathbb{R}^{n}$, some novel conditions are shown for existence
of (weakly) Pareto points in [23]. The following questions are of great
interests for studying MOPs:

  * •

What is a convenient description for the set of (weakly) Pareto values? When
can we represent the Pareto front in terms of convex sets?

  * •

For an LSP, how can we solve it efficiently for a Pareto point? If an LSP is
unbounded below, how can we detect the unboundedness? When $K$ is unbounded,
how can we find a proper weight? How can we detect nonexistence of proper
weights?

  * •

For a CSP, how can we solve it efficiently for a weakly Pareto point? How do
we get the minimum value for each objective? If some $f_{i}^{*}$ is $-\infty$,
how can we get a weakly Pareto point?

  * •

For a given point, how can we detect if it is a (weakly) Pareto point? How can
we get a (weakly) Pareto point if LSPs/CSPs fail to give one? How do we detect
nonexistence of (weakly) Pareto points?

### Contributions

The above questions are the major topics of this paper. When MOPs are given by
polynomials, there are special properties for them. The following are our
major contributions.

We study the convex geometry for (weakly) Pareto values. The epigraph set,
i.e., the set $\mathcal{U}$ as in (3.1), is useful for (weakly) Pareto values.
We give a characterization for the Pareto front. When the objectives are
convex, we show that the set of weakly Pareto values can be expressed in terms
of the boundary of a convex set. When the MOP is given by SOS convex
polynomials, we show that $\mathcal{U}$ can be given by semidefinite
representations. This is shown in Section 3.

For solving LSPs and CSPs, or detecting nonexistence of (weakly) Pareto
points, we often need to detect whether or not an optimization problem is
unbounded. To this end, we discuss how to detect unboundedness of polynomial
optimization. This is done in Section 4.

We discuss how to solve LSPs in Section 5. Under a generic nonsingularity
assumption, we give a tight relaxation method for solving the LSP. When the
feasible set $K$ is unbounded, we show how to find proper weights. We also
show how to detect nonexistence of proper weights.

Section 6 studies how to solve CSPs. We first apply the tight relaxation
method to compute minimum values $f_{1}^{*},\ldots,f_{m}^{*}$ for the
individual objectives. After that, we formulate the CSP equivalently as a
polynomial optimization problem and then solve it by using Moment-SOS
relaxations.

Section 7 discusses how to detect if a given point is a (weakly) Pareto point
or not. This can be done by solving certain polynomial optimization. We also
show how to detect existence or nonexistence of (weakly) Pareto points. This
requires to solve some moment feasibility problems.

We make some conclusions and propose some open questions in Section 8. Section
2 reviews some basic results for optimization with polynomials and moments.

##  2\. Preliminary

### Notation

The symbol $\mathbb{N}$ (resp., $\mathbb{R}$, $\mathbb{C}$) denotes the set of
nonnegative integral (resp., real, complex) numbers. The $\mathbb{R}^{n}_{+}$
stands for the nonnegative orthant, i.e., the set of nonnegative vectors. For
each label $i$, the $e_{i}$ denotes the vector of all zeros excepts its $i$th
entry being $1$, while $e$ denotes the vector of all ones. For an integer
$k>0$, denote $[k]:=\\{1,2,\ldots,k\\}.$ For $t\in\mathbb{R}$, $\lceil
t\rceil$ denotes the smallest integer greater than or equal to $t$. Denote by
$\mathbb{R}[x]:=\mathbb{R}[x_{1},\ldots,x_{n}]$ the ring of polynomials in
$x:=(x_{1},\ldots,x_{n})$ with real coefficients. The $\mathbb{R}[x]_{d}$
stands for the set of polynomials in $\mathbb{R}[x]$ with degrees at most $d$.
For a polynomial $p$, $\deg(p)$ denotes its total degree, $\tilde{p}$ denotes
its homogenization, and $p^{hom}$ denotes the homogeneous part of the highest
degree. For $\alpha:=(\alpha_{1},\ldots,\alpha_{n})\in\mathbb{N}^{n}$, we
denote $x^{\alpha}\,:=\,x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ and
$|\alpha|:=\alpha_{1}+\cdots+\alpha_{n}$. The power set of degree $d$ is

$\mathbb{N}^{n}_{d}:=\\{\alpha\in\mathbb{N}^{n}\mid|\alpha|\leq d\\}.$

The vector of monomials in $x$ and up to degree $d$ is

$[x]_{d}:=\begin{bmatrix}1&x_{1}&\cdots&x_{n}&x_{1}^{2}&x_{1}x_{2}&\cdots&x_{n}^{d}\end{bmatrix}^{T}.$

The superscript T denotes the transpose of a matrix/vector. The $I_{N}$ stands
for the $N$-by-$N$ identity matrix. By writing $X\succeq 0$ (resp., $X\succ
0$), we mean that $X$ is a symmetric positive semidefinite (resp., positive
definite) matrix. For a set $T$, $\mbox{conv}\left(T\right)$ denotes its
convex hull, $\mathit{cl}\left(T\right)$ denotes its closure, and
$\mathit{int}\left(T\right)$ denotes its interior, under the Euclidean
topology. The cardinality of $T$ is $|T|$. For a vector $u$, the $\|u\|$
denotes its standard Euclidean norm. For a function $h$ in $x$, the $\nabla h$
denotes its gradient vector in $x$. All computational results are shown with
four decimal digits.

###  2.1. Positive polynomials

A subset $I\subseteq\mathbb{R}[x]$ is an ideal if
$I\cdot\mathbb{R}[x]\subseteq I$ and $I+I\subseteq I$. For a tuple
$p=(p_{1},\ldots,p_{k})$ of polynomials in $\mathbb{R}[x]$, $\mbox{Ideal}(p)$
denotes the smallest ideal containing all $p_{i}$, which is the set
$p_{1}\cdot\mathbb{R}[x]+\cdots+p_{k}\cdot\mathbb{R}[x].$ In computation, we
often need to work with the truncation of degree $2k$:

$\mathit{Ideal}[p]_{2k}\,:=\,p_{1}\cdot\mathbb{R}[x]_{2k-\deg(p_{1})}+\cdots+p_{k}\cdot\mathbb{R}[x]_{2k-\deg(p_{k})}.$

A polynomial $\sigma$ is said to be a sum of squares (SOS) if
$\sigma=s_{1}^{2}+\cdots+s_{k}^{2}$ for some polynomials $s_{1},\ldots,s_{k}$.
Checking if a polynomial is SOS can be done by solving a semidefinite program
(SDP) [25]. If a polynomial is SOS, then it is nonnegative everywhere. The set
of all SOS polynomials in $x$ is denoted by $\Sigma[x]$ and its $d$th
truncation is $\Sigma[x]_{d}:=\Sigma[x]\cap\mathbb{R}[x]_{d}.$ For a tuple
$q=(q_{1},\ldots,q_{t})$ of polynomials, its quadratic module is

$\mathit{Qmod}[q]\,:=\,\Sigma[x]+q_{1}\cdot\Sigma[x]+\cdots+q_{t}\cdot\Sigma[x].$

The truncation of degree $2k$ for $\mathit{Qmod}[q]$ is

$\mathit{Qmod}[q]_{2k}\,:=\,\Sigma[x]_{2k}+q_{1}\cdot\Sigma[x]_{2k-\deg(g_{1})}+\cdots+q_{t}\cdot\Sigma[x]_{2k-\deg(q_{t})}.$

A subset $A\subseteq\mathbb{R}[x]$ is said to be archimedean if there exists
$\sigma\in A$ such that $\sigma(x)\geq 0$ defines a compact set in
$\mathbb{R}^{n}$. If $\mathit{Ideal}[p]+\mathit{Qmod}[q]$ is archimedean, then
the set $T:=\\{x\in\mathbb{R}^{n}:p(x)=0,\,q(x)\geq 0\\}$ must be compact. The
reverse is not necessarily true. However, if $T$ is compact, the
archimedeanness can be met by adding a redundant ball condition. When
$\mathit{Ideal}[p]+\mathit{Qmod}[q]$ is archimedean, every polynomial that is
positive on $T$ must belong to $\mathit{Ideal}[p]+\mathit{Qmod}[q]$. This
conclusion is referenced as Putinar’s Positivstellensatz [49]. Furthermore, if
a polynomial is nonnegative on $T$, then it also belongs to
$\mathit{Ideal}[p]+\mathit{Qmod}[q]$, under some standard optimality
conditions on its minimizers (see [41]).

###  2.2. Localizing and moment matrices

Denote by $\mathbb{R}^{\mathbb{N}_{d}^{n}}$ the space of real sequences
labeled by $\alpha\in\mathbb{N}_{d}^{n}$. A vector
$y:=(y_{\alpha})_{\alpha\in\mathbb{N}_{d}^{n}}$ is called a truncated multi-
sequence (tms) of degree $d$. It gives a linear functional on
$\mathbb{R}[x]_{d}$ such as

(2.1)
$\langle{\sum}_{\alpha\in\mathbb{N}_{d}^{n}}f_{\alpha}x^{\alpha},y\rangle\,:=\,{\sum}_{\alpha\in\mathbb{N}_{d}^{n}}f_{\alpha}y_{\alpha},$

where each $f_{\alpha}$ is a coefficient. The tms $y$ is said to admit a Borel
measure $\mu$ if $y_{\alpha}=\int x^{\alpha}\mathtt{d}\mu$ for all
$\alpha\in\mathbb{N}_{d}^{n}$. If it exists, such $\mu$ is called a
representing measure for $y$ and $y$ is said to admit the measure $\mu$. The
support of $\mu$ is denoted as $\mbox{supp}(\mu)$. If the cardinality
$|\mbox{supp}(\mu)|$ is finite, the measure $\mu$ is called finitely atomic.
It is called $r$-atomic if $|\mbox{supp}(\mu)|=r$.

In optimization, the support of $\mu$ is often constrained in a set $K$. For a
degree $d$, denote the moment cone

(2.2)
$\mathscr{R}_{d}(K)\,:=\,\Big{\\{}y\in\mathbb{R}^{\mathbb{N}^{n}_{d}}:\,\exists\,\mu,\,\,y=\int[x]_{d}\mathtt{d}\mu,\,\mbox{supp}(\mu)\subseteq
K\Big{\\}}.$

The dual cone of $\mathscr{R}_{d}(K)$ is the nonnegative polynomial cone

(2.3) $\mathscr{P}_{d}(K)\,:=\,\Big{\\{}p\in\mathbb{R}[x]_{d}:\,p(x)\geq
0\,\forall\,x\in K\Big{\\}}.$

The dual cone of $\mathscr{P}_{d}(K)$ is the closure of $\mathscr{R}_{d}(K)$.
When $K$ is compact, the moment cone $\mathscr{R}_{d}(K)$ is closed. We refer
to [28, 31] for more details about moment cones.

Consider a polynomial $q\in\mathbb{R}[x]_{2k}$ with $\deg(q)\leq 2k$. The
$k$th localizing matrix of $q$, generated by a tms
$z\in\mathbb{R}^{\mathbb{N}^{n}_{2k}}$, is the symmetric matrix
$L_{q}^{(k)}[z]$ such that

(2.4) $vec(a_{1})^{T}\big{(}L_{q}^{(k)}[z]\big{)}vec(a_{2})\,=\,\langle
qa_{1}a_{2},z\rangle$

for all $a_{1},a_{2}\in\mathbb{R}[x]_{k-\lceil\deg(q)/2\rceil}$. (The
$vec(a_{i})$ denotes the coefficient vector of $a_{i}$.) When $q=1$,
$L_{q}^{(k)}[z]$ is called a moment matrix and we denote

$M_{k}[z]\,:=\,L_{1}^{(k)}[z].$

The columns and rows of $L_{q}^{(k)}[z]$, as well as $M_{k}[z]$, are labeled
by $\alpha\in\mathbb{N}^{n}$ with $2|\alpha|\leq 2k-\deg(q)$.

Each $y\in\mathscr{R}_{d}(K)$ can be extended to a tms
$z\in\mathscr{R}_{2t}(K)$ such that $y=z|_{d}$, where $d\leq 2t$ and $z|_{d}$
denotes the truncation of $z$ with degree $d$:

(2.5) $z|_{d}\,:=\,(z_{\alpha})_{\alpha\in\mathbb{N}^{n}_{d}}.$

When $K$ is the feasible set of (1.4), a necessary condition for
$z\in\mathscr{R}_{2t}(K)$ is

$L_{c_{i}}^{(t)}[z]=0\,(i\in\mathcal{E}),\quad L_{c_{j}}^{(t)}[z]\succeq
0\,(j\in\mathcal{I}),$

while they may not be sufficient (see [28, 31]). However, if $z$ further
satisfies

(2.6)
$\operatorname{rank}\,M_{t-d_{c}}[z]\,=\,\operatorname{rank}\,M_{t}[z],\qquad$

then $z$ admits a $r$-atomic measure supported in $K$, with
$r=\operatorname{rank}\,M_{t}[z]$. The above integer $d_{c}$ is the degree

(2.7)
$d_{c}\,:=\,\max\\{\lceil\deg(c_{i})/2\rceil:i\in\mathcal{E}\cup\mathcal{I}\\}.$

This condition (2.6) is called flat extension (see [8, 9, 16, 30]). To get
optimizers in computation, the flat truncation is more frequently used (see
[40]).

Moment and localizing matrices are important tools for solving polynomial
optimization [12, 16, 25, 43]. They are also useful in tensor decompositions
[44, 47]. We refer to [28, 29, 31, 32] for the books and surveys about
polynomial and moment optimization.

##  3\. Convex geometry of Pareto values

Recall that a vector $v:=(v_{1},\ldots,v_{m})$ is a Pareto value (PV) if there
exists a Pareto point $x^{*}$ such that $v=f(x^{*})$. Similarly, $v$ is called
a weakly Pareto value (WPV) if $v=f(p)$ for a weakly Pareto point $p$. PVs and
WPVs are closely related to the epigraph set

(3.1) $\mathcal{U}\,:=\,\\{u=(u_{1},\ldots,u_{m})\mid u_{i}\geq
f_{i}(x),\,\mbox{for some}\,x\in K\\}.$

The image of the set $K$ under the objective vector $f=(f_{1},\ldots,f_{m})$
is

$f(K)\,:=\,\\{(f_{1}(x),\ldots,f_{m}(x)):\,x\in K\\}.$

Then, $\mathcal{U}\,=\,f(K)+\mathbb{R}_{+}^{m}$ and its convex hull
$\mbox{conv}\left(\mathcal{U}\right)=\mbox{conv}\left(f(K)\right)+\mathbb{R}_{+}^{m}$.
If $K$ is convex and each objective $f_{i}$ is convex, the set $\mathcal{U}$
is also convex. The converse is not necessarily true. When $\mathcal{U}$ is
convex, every Pareto point is a minimizer of some LSP (see [11]). The PVs and
WPVs can be characterized through the set $\mathcal{U}$.

###  3.1. Supporting hyperplanes

For a nonzero vector $w\in\mathbb{R}^{m}$ and $b\in\mathbb{R}$, the set
$H=\\{u\in\mathbb{R}^{m}:w^{T}u=b\\}$ is a supporting hyperplane for
$\mathcal{U}$ if $b=\inf_{u\in\mathcal{U}}\,w^{T}u.$ The $w$ is the normal of
$H$. In particular, if there exists $v\in\mathcal{U}$ such that $w^{T}u\geq
w^{T}v$ for all $u\in\mathcal{U}$, then $H$ is called a supporting hyperplane
through $v$. Since $\mathcal{U}$ contains $f(x)+\mathbb{R}_{+}^{n}$, the
normal $w$ must be nonnegative, for $H$ to be a supporting hyperplane.

To characterize Pareto values, we define a kind of minimal points. Let $\pi$
be a permutation of $(1,\ldots,m)$. For a set $T\subseteq\mathbb{R}^{m}$,
construct the following chain of nesting subsets

$T=T_{0}\supseteq T_{1}\supseteq\cdots\supseteq T_{m}$

such that: for each $k=1,\ldots,m$, $T_{k}$ is the subset of vectors in
$T_{k-1}$ whose $\pi(k)$th entry is the smallest. If $T_{m}\neq\emptyset$,
then each $v\in T_{m}$ is called a $\pi$-minimal point of $T$. For $u,v\in
T_{m}$, all the entries of $u,v$ must be the same, so $u=v$ and hence $T_{m}$
consists of a single point, if it is nonempty. In particular, if $T$ is
compact, then $T_{m}\neq\emptyset$ and it consists of a single point.

PVs and WPVs are characterized in the following. Some of these results may
already exist in the literature. For convenience of readers, we summarize them
together and give direct proofs.

######  Proposition 3.1.

Let $\mathcal{U}$ be as in $(\ref{set:U})$. For each $v\in f(K)$, we have:

  * (i)

The vector $v$ is a WPV if and only if $v$ lies on the boundary of
$\mathcal{U}$. Moreover, if $v$ is an extreme point of
$\mbox{conv}\left(\mathcal{U}\right)$, then $v$ is a PV.

  * (ii)

Assume $\mathcal{U}$ is convex. If $v$ is a WPV, then there exists a
supporting hyperplane for $\mathcal{U}$ through $v$ whose normal is
nonnegative, i.e., there exists $0\neq w\geq 0$ such that $w^{T}u\geq w^{T}v$
for all $u\in\mathcal{U}$.

  * (iii)

Suppose $H=\\{u:w^{T}u=w^{T}v\\}$ is a supporting hyperplane for $\mathcal{U}$
through $v$, with a normal vector $0\neq w\geq 0$. If $w>0$, then $v$ is a PV.
When $w$ has a zero entry, if $u\in f(K)$ is a $\pi$-minimal point of
$H\cap\mathcal{U}$ for a permutation $\pi$ of $(1,\ldots,m)$, then $u$ is a
PV. If $u\in f(K)$ is an extreme point of $H\cap\mathcal{U}$, then $u$ is also
a PV.

###### Proof.

(i) If $v$ lies on the boundary of $\mathcal{U}$, then there is no $p\in K$
such that $f(p)<v$, so $v$ is a WPV. If $v$ is an interior point of
$\mathcal{U}$, then exist $p\in K$ and $q\geq 0$ such that $f(p)+q<v$, which
denies that $v$ is a WPV. This shows that $v$ is a WPV if and only if $v$ lie
on the boundary of $\mathcal{U}$.

Next, suppose $v$ is an extreme point of
$\mbox{conv}\left(\mathcal{U}\right)$. Suppose otherwise that $v$ is not a PV,
then there exists $p\in K$ such that $f(p)\leq v,f(p)\neq v.$ This means that
$v=f(p)+q$, for some $0\neq q\in\mathbb{R}_{+}^{m}$. Hence
$v=\frac{1}{2}f(p)+\frac{1}{2}(f(p)+2q),$ which implies $v$ is not an extreme
point of $\mbox{conv}\left(\mathcal{U}\right)$, a contradiction. So $v$ is a
PV.

(ii) If $v$ is a WPV, then $v$ lies on the boundary of $\mathcal{U}$. Since
$\mathcal{U}$ is convex, there is a supporting hyperplane for $\mathcal{U}$
through $v$, i.e., there exists $w\neq 0$ such that $w^{T}u\geq w^{T}v$ for
all $u\in\mathcal{U}$. The set $\mathcal{U}$ contains $v+\mathbb{R}_{+}^{m}$,
so $w\geq 0$.

(iii) For the case $w>0$, the conclusion is obvious. When $w$ has zero
entries, let $I=\\{i\in[m]:w_{i}>0\\}$. To prove $u:=(u_{1},\ldots,u_{m})$ is
a PV, suppose $p\in K$ is such that $f(p)\leq u.$ Since $u\in
H\cap\mathcal{U}$, $w^{T}f(p)\leq w^{T}u=w^{T}v.$ Also note that
$w^{T}f(p)\geq w^{T}u$, since $H$ is a supporting hyperplane. So we must have
$w^{T}f(p)=w^{T}v$ and $f_{i}(p)=u_{i}$ for all $i\in I$. Write that
$u=f(p)+q$, for some $q\in\mathbb{R}_{+}^{m}$. Note that $q_{i}=0$ for all
$i\in I$. Since $u$ is a $\pi$-minimal point of $H\cap\mathcal{U}$ and
$f(p)\leq u$, the vector $f(p)$ is also a $\pi$-minimal point of
$H\cap\mathcal{U}$. Hence $u=f(p)$, by the $\pi$-minimality. This means that
$u$ is a PV.

When $u$ is an extreme point of $H\cap\mathcal{U}$, we can prove that $u$ is a
PV in the same way as for the item (i). $\Box$

We have the following remarks for Proposition 3.1.

  * •

Not every WPV lies on the boundary of $\mbox{conv}\left(\mathcal{U}\right)$.
For instance, consider

$\left\\{\begin{array}[]{rl}\min&(x_{1},\,x_{2})\\\ \mathit{s.t.}&x_{1}\geq
0,x_{2}\geq 0,\,x_{1}^{2}+x_{2}^{2}=1.\end{array}\right.$

For each $t\in(0,1)$, the point $(t,\sqrt{1-t^{2}})$ is a WPP (also a PP), but
it does not lies on the boundary of $\mbox{conv}\left(\mathcal{U}\right)$.

  * •

If $\mathcal{U}$ is not convex, there may not exist a supporting hyperplane
through a WPV. For instance, in the above MOP, for every $t\in(0,1)$, there is
no supporting hyperplane for $\mbox{conv}\left(\mathcal{U}\right)$ through
$(t,\sqrt{1-t^{2}})$.

  * •

For the item (iii) of Proposition 3.1, if $w$ has a zero entry, then $v$ may
not be a Pareto value. For instance, consider the unconstrained MOP

$\min\quad(x_{1},\,x_{2}^{2}).$

For $w=(0,1)$ and $v=(0,0)$, the equation $w^{T}u=0$ gives a supporting
hyperplane through $(0,0)$, but $(0,0)$ is not a Pareto value.

  * •

If $v$ is a PV, it may not be an extreme point of $\mathcal{U}$ or
$H\cap\mathcal{U}$. For instance, consider the MOP

$\left\\{\begin{array}[]{rl}\min&(x_{1},\,x_{2})\\\ \mathit{s.t.}&x_{1}\geq
0,x_{2}\geq 0,\,x_{1}+x_{2}=1.\end{array}\right.$

The set $\mathcal{U}=\\{x_{1}\geq 0,\,x_{2}\geq 0,\,x_{1}+x_{2}\geq 1\\}$.
Clearly, for every $t\in(0,1)$, the vector $(t,1-t)$ is a PV, but it is not an
extreme point of $\mathcal{U}$. The hyperplane $H=\\{x_{1}+x_{2}=1\\}$
supports $\mathcal{U}$ at $(t,1-t)$. However, $(t,1-t)$ is not an extreme
point of the intersection $H\cap\mathcal{U}$, for every $t\in(0,1)$.

###  3.2. A convex representation

When the feasible set $K$ is bounded, there always exist supporting
hyperplanes for $\mathcal{U}$. When $K$ is unbounded, they may or may not
exist. For given $v=(v_{1},\ldots,v_{m})\in f(K)$, how do we determine if
there is a supporting hyperplane through it? For this purpose, we consider the
linear optimization in $w_{0}\in\mathbb{R}$ and
$w=(w_{1},\ldots,w_{m})\in\mathbb{R}^{m}$:

(3.2) $\left\\{\begin{array}[]{rl}\omega^{*}:=\max&w_{0}\\\
\mathit{s.t.}&1-e^{T}w=0,\,w_{i}\geq w_{0}\,(i\in[m]),\\\
&\sum_{i=1}^{m}w_{i}(f_{i}(x)-v_{i})\geq 0\quad\mbox{on}\quad
K.\end{array}\right.$

Clearly, there is a supporting hyperplane through $v$ if and only if the
optimal value $\omega^{*}\geq 0$. Let $d$ be the maximum degree of objectives
$f_{i}$. The third constraint in (3.2) is equivalent to the membership

$\begin{array}[]{c}\sum_{i=1}^{m}w_{i}(f_{i}(x)-v_{i})\in\mathscr{P}_{d}(K),\end{array}$

where $\mathscr{P}_{d}(K)$ is the nonnegative polynomial cone as in (2.3). The
dual cone of $\mathscr{P}_{d}(K)$ is the closure
$\mbox{cl}\big{(}\mathscr{R}_{d}(K)\big{)}$, where $\mathscr{R}_{d}(K)$ is the
moment cone as in (2.2). The dual optimization of (3.2) can be shown to be

(3.3) $\left\\{\begin{array}[]{rl}\min&t\\\ \mathit{s.t.}&t-\langle
f_{i}-v_{i},y\rangle\geq 0\,(i\in[m]),\\\ &1=mt-\sum_{i=1}^{m}\langle
f_{i}-v_{i},y\rangle,\,\,y\in\mbox{cl}\big{(}\mathscr{R}_{d}(K)\big{)}.\end{array}\right.$

In the above, the vector $y$ is a tms labeled as

$y\,=\,(y_{\alpha})_{\alpha\in\mathbb{N}^{n}_{d}}.$

If (3.3) has a feasible point with $t<0$, then there are no nonnegative
supporting hyperplanes through $v$. Since each $v_{i}$ is a scalar, one can
see that

$\langle f_{i}-v_{i},y\rangle=\langle f_{i},y\rangle-v_{i}\langle
1,y_{0}\rangle=\langle f_{i},y\rangle-v_{i}y_{0}.$

When $t<0$ is feasible for (3.3), there also exists a feasible
$y\in\mathscr{R}_{d}(K)$ with $y_{0}>0$. One can scale such $(t,y)$ so that
$y_{0}=1$. Hence, the existence of $t<0$ in (3.3) is equivalent to

$\left\\{\begin{array}[]{l}\tau=mt^{\prime}-\sum_{i}(\langle f_{i},y\rangle-
v_{i}),\\\ t^{\prime}\geq\langle f_{i},y\rangle-v_{i}\,(i\in[m]),\\\
\tau>0>t^{\prime},\,y_{0}=1,\,y\in\mathscr{R}_{d}(K).\end{array}\right.$

The above is then equivalent to that

(3.4)
$\mathcal{V}\,:=\,\left\\{v\left|\begin{array}[]{l}v=(v_{1},\ldots,v_{m})\\\
v_{i}>\langle f_{i},y\rangle\,(i\in[m]),\\\
y_{0}=1,\,y\in\mathscr{R}_{d}(K)\end{array}\right.\right\\}\neq\emptyset.$

######  Theorem 3.2.

Assume $K$ has nonempty interior. Then, the interior of the convex hull
$\mbox{conv}\left(\mathcal{U}\right)$ is the set $\mathcal{V}$ as in (3.4).
Moreover, when $\mathcal{U}$ is convex, a vector $v\in f(K)$ is a weakly
Pareto value if and only if $v$ belongs to the boundary of the closure
$\mbox{cl}\big{(}\mathcal{V}\big{)}$.

###### Proof.

Since $K$ has nonempty interior, the cone $\mathscr{R}_{d}(K)$ has nonempty
interior. Hence, the strong duality holds between (3.2) and (3.3), since (3.3)
has strictly feasible points. This is because one can select $y$ from the
interior of $\mathscr{R}_{d}(K)$, choose $t$ sufficiently large to satisfy all
the inequalities, and then scale such $(t,y)$ for the equality to hold.

A point $v$ lies in the interior of $\mbox{conv}\left(\mathcal{U}\right)$ if
and only if there is no supporting hyperplane for $\mathcal{U}$ through it.
The normal of every supporting hyperplane for $\mathcal{U}$ is nonnegative.
Thus, $v$ lies in the interior of $\mbox{conv}\left(\mathcal{U}\right)$ if and
only if the optimal value $\omega^{*}$ of (3.2) is negative or it is
infeasible. By the strong duality between (3.2) and (3.3), this is equivalent
to that $v$ belongs to $\mathcal{V}$.

When $\mathcal{U}$ is convex, i.e., $\mbox{conv}(\mathcal{U})=\mathcal{U}$, a
vector $v\in f(K)$ is a WPV if and only if $v$ lies on the boundary of
$\mathcal{U}$, by Proposition 3.1. This is equivalent to that $v$ lies on the
boundary of $\mbox{cl}\big{(}\mathcal{V}\big{)}$, since the interior of
$\mathcal{U}$ is $\mathcal{V}$. $\Box$

A computational efficient description for the moment cone $\mathscr{R}_{d}(K)$
is usually not available. However, when the polynomials are SOS-convex, there
exists a semidefinite representation for the set $\mathcal{V}$ in (3.4).
Recall that a polynomial $p\in\mathbb{R}[x]$ is SOS-convex (see [15]) if
$\nabla^{2}p=Q(x)^{T}Q(x)$ for some matrix polynomial $Q(x)$.

######  Theorem 3.3.

Assume $\mathcal{E}=\emptyset$ and $K$ has nonempty interior. If all $f_{i}$
and $-c_{j}$ ($j\in\mathcal{I}$) are SOS-convex polynomials, then the interior
of $\mathcal{U}$ is equal to

(3.5)
$\mathcal{V}_{1}\,:=\,\left\\{(v_{1},\ldots,v_{m})\left|\begin{array}[]{l}\langle
c_{j},y\rangle\geq 0\,(j\in\mathcal{I}),\,v_{i}>\langle
f_{i},y\rangle\,(i\in[m]),\\\ y_{0}=1,\,M_{d_{0}}[y]\succeq
0,\,y\in\mathbb{R}^{\mathbb{N}^{n}_{2d_{0}}}\end{array}\right.\right\\},$

where $d_{0}:=\max\\{\lceil
d/2\rceil,\lceil\deg(c_{j})/2\rceil(j\in\mathcal{I}\\}$. Moreover, for $v\in
f(K)$, the $v$ is a weakly Pareto value if and only if it lies on the boundary
of $\mbox{cl}\big{(}\mathcal{V}_{1}\big{)}$.

###### Proof.

Clearly, if $v$ belongs to $\mathcal{V}$ as in (3.4) for some
$y\in\mathscr{R}_{d}(K)$, then it must belong to $\mathcal{V}_{1}$.
Conversely, if $(v,y)$ satisfies (3.5), then let
$\hat{x}:=(y_{e_{1}},\ldots,y_{e_{n}})$ and $\hat{y}:=[\hat{x}]_{d}$. Under
the SOS convexity assumption, the Jensen’s inequality (see [27]) implies that

$\langle f_{i},y\rangle\geq f_{i}(\hat{x})=\langle f_{i},\hat{y}\rangle,\quad
0\geq\langle-c_{j},y\rangle\geq-c_{j}(\hat{x})=\langle-c_{j},\hat{y}\rangle.$

So we have $\hat{x}\in K$ and $\hat{y}\in\mathscr{R}_{d}(K)$, hence $v$
belongs to $\mathcal{V}_{1}$. The conclusion then follows from Theorem 3.2.
$\Box$

######  Example 3.4.

Consider the SOS-convex polynomials

$\begin{array}[]{c}f_{1}=(x_{1}-x_{2})^{4}+(x_{2}-x_{3})^{4},\,\,f_{2}=\sum_{i=1}^{3}x_{i}^{4}+x_{1}^{2}x_{2}^{2}+x_{1}^{2}x_{3}^{2}+x_{2}^{2}x_{3}^{2},\end{array}$

and the ball constraint $1\geq\|x\|^{2}$. One can verify that

$\begin{array}[]{l}\nabla^{2}f_{1}=12\begin{bmatrix}x_{1}-x_{2}&0\\\
x_{2}-x_{1}&x_{2}-x_{3}\\\
0&x_{3}-x_{2}\end{bmatrix}\begin{bmatrix}x_{1}-x_{2}&0\\\
x_{2}-x_{1}&x_{2}-x_{3}\\\ 0&x_{3}-x_{2}\end{bmatrix}^{T},\\\
\nabla^{2}f_{2}=4\begin{bmatrix}x_{1}&x_{1}&0\\\ x_{2}&0&x_{2}\\\
0&x_{3}&x_{3}\end{bmatrix}\begin{bmatrix}x_{1}&x_{1}&0\\\ x_{2}&0&x_{2}\\\
0&x_{3}&x_{3}\end{bmatrix}^{T}+\sum_{i=1}^{3}A_{i}A_{i}^{T},\end{array}$

where each $A_{i}$ is the diagonal matrix with the diagonal vector
$\sqrt{2}x_{i}(e+(\sqrt{2}-1)e_{i})$. Note that $y_{000}=1$. The inequalities
in the set $\mathcal{V}_{1}$ as in (3.5) are

$\begin{array}[]{l}1-y_{200}-y_{020}-y_{020}\geq 0,\\\
v_{1}>\sum_{i=0}^{4}{4\choose
i}(-1)^{i}(y_{(4-i)e_{1}+ie_{2}}+y_{(4-i)e_{2}+ie_{3}}),\\\
v_{2}>\sum_{i=1}^{3}y_{4e_{i}}+y_{220}+y_{022}+y_{202}.\end{array}$

The moment matrix inequality $M_{2}[y]\succeq 0$ reads as

$\left[\begin{array}[]{cccccccccc}y_{000}&y_{100}&y_{010}&y_{001}&y_{200}&y_{110}&y_{101}&y_{020}&y_{011}&y_{002}\\\
y_{100}&y_{200}&y_{110}&y_{101}&y_{300}&y_{210}&y_{201}&y_{120}&y_{111}&y_{102}\\\
y_{010}&y_{110}&y_{020}&y_{011}&y_{210}&y_{120}&y_{111}&y_{030}&y_{021}&y_{012}\\\
y_{001}&y_{101}&y_{011}&y_{002}&y_{201}&y_{111}&y_{102}&y_{021}&y_{012}&y_{003}\\\
y_{200}&y_{300}&y_{210}&y_{201}&y_{400}&y_{310}&y_{301}&y_{220}&y_{211}&y_{202}\\\
y_{110}&y_{210}&y_{120}&y_{111}&y_{310}&y_{220}&y_{211}&y_{130}&y_{121}&y_{112}\\\
y_{101}&y_{201}&y_{111}&y_{102}&y_{301}&y_{211}&y_{202}&y_{121}&y_{112}&y_{103}\\\
y_{020}&y_{120}&y_{030}&y_{021}&y_{220}&y_{130}&y_{121}&y_{040}&y_{031}&y_{022}\\\
y_{011}&y_{111}&y_{021}&y_{012}&y_{211}&y_{121}&y_{112}&y_{031}&y_{022}&y_{013}\\\
y_{002}&y_{102}&y_{012}&y_{003}&y_{202}&y_{112}&y_{103}&y_{022}&y_{013}&y_{004}\\\
\end{array}\right]\succeq 0.$

##  4\. Unboundedness in Polynomial Optimization

We discuss how to detect whether or not a polynomial optimization problem is
unbounded. This question frequently appears in multi-objective optimization.
For a polynomial $g(x)$ of degree $d$, consider the optimization

(4.1) $\min\quad g(x)\quad\mathit{s.t.}\quad x\in K.$

The feasible set $K$ is the same as for (1.4). When $K$ is unbounded, (4.1)
may be unbounded below, i.e., there exists a sequence $\\{u_{k}\\}\subseteq K$
such that $g(u_{k})\to-\infty$. We discuss how to detect unboundedness of
(4.1). The homogenization of the set $K$ is ($\tilde{x}:=(x_{0},x)$ is the
homogenizing variable)

(4.2)
$\widetilde{K}\,:=\,\left\\{\tilde{x}\left|\begin{array}[]{l}\tilde{c}_{i}(\tilde{x})=0\,(i\in\mathcal{E}),\,\tilde{x}^{T}\tilde{x}=1,\\\
\tilde{c}_{j}(\tilde{x})\geq 0\,(j\in\mathcal{I}),\,x_{0}\geq
0\end{array}\right.\right\\}.$

The intersection of $\tilde{K}$ and $x_{0}=0$ is

(4.3)
$K^{\circ}\,:=\,\left\\{x\in\mathbb{R}^{n}\left|\begin{array}[]{l}c_{i}^{\mathit{hom}}(x)=0\,(i\in\mathcal{E}),\,x^{T}x=1,\\\
c_{j}^{\mathit{hom}}(x)\geq 0\,(j\in\mathcal{I})\\\
\end{array}\right.\right\\},$

where each $c_{i}^{\mathit{hom}}(x)=\tilde{c}_{i}(0,x)$. The set $K$ is said
to be closed at $\infty$ (see [39]) if

$\widetilde{K}\,=\,\mathit{cl}\left(\big{\\{}\tilde{x}\in\widetilde{K}:\,x_{0}>0\big{\\}}\right).$

###  4.1. A certificate for unboundedness

The optimization (4.1) is bounded below if and only if $g$ has a lower bound
$\gamma$ on $K$, i.e., $g-\gamma\in\mathscr{P}_{d}(K)$. So we consider the
optimization

(4.4) $\max\quad\gamma\quad\mathit{s.t.}\quad g-\gamma\in\mathscr{P}_{d}(K).$

To check infeasibility of (4.4), we use the homogenization trick in [39]. When
$K$ is closed at $\infty$, a polynomial $p\geq 0$ on $K$ if and only if its
homogenization $\tilde{p}\geq 0$ on $\widetilde{K}$ (see [39]). So,
$g-\gamma\in\mathscr{P}_{d}(K)$ is equivalent to $\widetilde{g}-\gamma
x_{0}^{d}\in\mathscr{P}_{d}(\widetilde{K})$, and hence (4.4) is the same as

(4.5) $\max\quad\gamma\quad\mathit{s.t.}\quad\widetilde{g}-\gamma
x_{0}^{d}\in\mathscr{P}_{d}\big{(}\widetilde{K}\big{)}.$

The dual optimization of (4.5) is

(4.6) $\min\quad\langle\widetilde{g},y\rangle\quad\mathit{s.t.}\quad\langle
x_{0}^{d},y\rangle=1,\,y\in\mathscr{R}_{d}\big{(}\widetilde{K}\big{)}.$

If (4.6) is unbounded below, then (4.5) must be infeasible, which implies that
(4.4) is infeasible and (4.1) is unbounded below, when $K$ is closed at
$\infty$.

When $K\neq\emptyset$, the linear conic optimization (4.6) has a feasible
point. It is unbounded below if there is a decreasing ray $\Delta y$:

(4.7) $\langle\widetilde{g},\Delta y\rangle=-1,\quad\langle x_{0}^{d},\Delta
y\rangle=0,\quad\Delta y\in\mathscr{R}_{d}\big{(}\widetilde{K}\big{)}.$

If $\nu$ is a representing measure for $\Delta y$ and is supported in
$\widetilde{K}$, then

$0=\langle x_{0}^{d},\Delta y\rangle=\int x_{0}^{d}\mathtt{d}\nu$

implies that $\mbox{supp}(\nu)\subseteq\widetilde{K}\cap\\{x_{0}=0\\}.$ Thus,
(4.7) is equivalent to

(4.8) $\langle g^{\mathit{hom}},z\rangle=-1,\quad
z\in\mathscr{R}_{d}(K^{\circ}),$

where $K^{\circ}$ is the set as in (4.3). Let $d_{1}$ be the degree

(4.9) $d_{1}\,:=\,\lceil d/2\rceil.$

To check if (4.8) is feasible or not, we select a generic
$R\in\mathit{int}\left(\Sigma[x]_{2d_{1}}\right)$ and consider the linear
moment optimization

(4.10) $\left\\{\begin{array}[]{rl}\min&\langle R,z\rangle\\\
\mathit{s.t.}&\langle
g^{\mathit{hom}},z\rangle=-1,\,z\in\mathscr{R}_{2d_{1}}(K^{\circ}).\end{array}\right.$

The following shows how to detect unboundedness of (4.1).

######  Theorem 4.1.

Let $\widetilde{K}$, $K^{\circ}$ be the sets as in (4.2)-(4.3).

  * (i)

Suppose (4.8) is feasible. If
$R\in\mathit{int}\left(\Sigma[x]_{2d_{1}}\right)$ is generic, then (4.10) has
a unique optimizer $z^{*}$ and $z^{*}=\lambda[u]_{2d_{1}}$, with $u\in
K^{\circ}$ and $\lambda>0$.

  * (ii)

Suppose $z:=\lambda[u]_{d}$, with $u\in K^{\circ}$ and $\lambda>0$, is a
feasible point for (4.8). If
$(0,u)\in\mathit{cl}\left(\widetilde{K}\cap\\{x_{0}>0\\}\right)$, then (4.1)
is unbounded below.

###### Proof.

(i) Since $R$ is generic in the interior
$\mathit{int}\left(\Sigma[x]_{2d_{1}}\right)$, there exists $\epsilon>0$ such
that $R-\epsilon\|[x]_{d_{0}}\|^{2}\in\Sigma[x]_{2d_{1}}$. Hence, for all
$z\in\mathscr{R}_{2d_{0}}(K^{\circ})$, it holds that

$\langle
R,z\rangle\,\geq\,\epsilon\langle\|[x]_{d_{1}}\|^{2},z\rangle\,\geq\,\epsilon\cdot\mbox{trace}(M_{d_{1}}[z]).$

Since (4.8) is feasible, the optimization (4.10) is also feasible, say,
$z^{(0)}$ is a feasible point. Then, (4.10) is equivalent to

(4.11) $\left\\{\begin{array}[]{rl}\min&\langle R,z\rangle\\\
\mathit{s.t.}&\mbox{trace}(M_{d_{1}}[z])\leq\frac{1}{\epsilon}\langle
R,z^{(0)}\rangle,\\\ &\langle
f^{\mathit{hom}},z\rangle=-1,\,z\in\mathscr{R}_{2d_{1}}(K^{\circ}).\end{array}\right.$

The feasible set of (4.11) is compact, so it has an optimizer, say, $z^{*}$.
When $R$ is generic, the optimizer $z^{*}$ must be unique and it is an extreme
point of the feasible set of (4.10). Since (4.10) has only a single equality
constraint, the optimizer $z^{*}$ must lie in an extreme ray of the cone
$\mathscr{R}_{2d_{1}}(K^{\circ})$. This means that $z^{*}=\lambda[u]_{2d_{1}}$
for a point $u\in K^{\circ}$ and scalar $\lambda>0$ (note $z^{*}$ is nonzero).

(ii) Since $(0,u)\in\mathit{cl}\left(\widetilde{K}\cap\\{x_{0}>0\\}\right)$,
there is a sequence

$\\{(t_{k},u_{k})\\}_{k=1}^{\infty}\subseteq\widetilde{K}\cap\\{x_{0}>0\\}$

such that $\lim\limits_{k\to\infty}(t_{k},u_{k})=(0,u)$. Note that each
$t_{k}>0$ and

$-1=\langle g^{hom},\lambda[u]_{d}\rangle=\lambda
g^{hom}(u)=\lim_{k\to\infty}\lambda\tilde{g}(t_{k},u_{k}).$

Thus, for $k$ big enough, $\lambda\tilde{g}(t_{k},u_{k})\leq-\frac{1}{2}$ and

$\lambda\tilde{g}(t_{k},u_{k})=\lambda\cdot(t_{k})^{d}g(u_{k}/t_{k})\leq-1/2.$

This implies that $g(u_{k}/t_{k})\leq\frac{-1}{2\lambda\cdot(t_{k})^{d}}$ for
all $k$ big enough, so $g(u_{k}/t_{k})\to-\infty$ as $k\to\infty$. Since each
$u_{k}/t_{k}\in K$, $g$ is unbounded below on $K$. $\Box$

We remark that Theorem 4.1(ii) does not assume that $K$ is closed at $\infty$.

######  Example 4.2.

Consider the following optimization problem

$\left\\{\begin{array}[]{rl}\min&g(x):=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{1}x_{2}x_{3}\\\
\mathit{s.t.}&x_{1}^{2}x_{2}^{2}(x_{1}^{2}+x_{2}^{2})+x_{3}^{6}-3x_{1}^{2}x_{2}^{2}x_{3}^{2}-1=0.\end{array}\right.$

Note that $g^{\mathit{hom}}=x_{1}x_{2}x_{3}$ and a feasible point of (4.8) is
$3\sqrt{3}[(1,1,-1)/\sqrt{3}]_{6}$. The point $(0,\frac{1}{\sqrt{3}}(1,1,-1))$
lies on the closure $\mathit{cl}\left(\tilde{K}\cap\\{x_{0}>0\\}\right)$, so
this optimization problem is unbounded below.

When (4.6) is unbounded below, it is not necessary that (4.6) has a decreasing
ray, i.e., the system (4.8) may be infeasible. That is, (4.8) is sufficient
for unboundedness of (4.1), but it may not be necessary. For instance,
consider the optimization

$\left\\{\begin{array}[]{rl}\min&g(x):=x_{1}x_{2}x_{3}+x_{1}^{2}x_{2}^{2}(x_{1}^{2}+x_{2}^{2})+x_{3}^{6}-3x_{1}^{2}x_{2}^{2}x_{3}^{2}\\\
\mathit{s.t.}&x_{1}^{2}+x_{2}^{2}-2x_{3}^{2}=0,\,x_{1}x_{2}\geq
0.\end{array}\right.$

It is unbounded below, because $g(t,t,-t)=-t^{3}\to-\infty$ as $t\to+\infty$,
while $(t,t,-t)$ is feasible for all $t\geq 0$. However, the certificate (4.8)
is infeasible. This is because
$g^{\mathit{hom}}=x_{1}^{2}x_{2}^{2}(x_{1}^{2}+x_{2}^{2})+x_{3}^{6}-3x_{1}^{2}x_{2}^{2}x_{3}^{2}$
is the Motzkin polynomial and $\langle g^{\mathit{hom}},z\rangle\geq 0$ for
all $z\in\mathscr{R}_{d}(K^{\circ})$. When (4.8) fails to be feasible, the
question of detecting unboundedness of (4.1) is mostly open.

###  4.2. Solving linear moment systems

Semidefinite relaxations can be applied to solve (4.8) and (4.10). For more
generality, we consider the moment system

(4.12) $a_{i}\geq\langle g_{i},z\rangle\,\,(i=1,\ldots,m),\quad
z\in\mathscr{R}_{d}(K^{\circ}),$

for given polynomials $g_{1},\ldots,g_{m}\in\mathbb{R}[x]_{d}$ and given
scalars $a_{1},\ldots,a_{m}\in\mathbb{R}$. It is worthy to note that in (4.8)
and (4.10), the equality is equivalently to the inequality like the above, due
to the conic membership condition.

Select a generic $R\in\mathit{int}\left(\Sigma[x]_{2d_{1}}\right)$ and
consider the moment optimization

(4.13) $\left\\{\begin{array}[]{rl}\min&\langle R,z\rangle\\\
\mathit{s.t.}&a_{i}-\langle g_{i},z\rangle\geq
0\,(i\in[m]),\,z\in\mathscr{R}_{2d_{1}}(K^{\circ}).\end{array}\right.$

Let $d_{2}:=\max\\{d_{1},d_{c}\\}$, where $d_{c}$ is as in (2.7). For
$k=d_{2},d_{2}+1,\cdots$, we solve the hierarchy of semidefinite relaxations

(4.14) $\left\\{\begin{array}[]{rl}\min&\langle R,z\rangle\\\
\mathit{s.t.}&a_{i}-\langle g_{i},z\rangle\geq 0\,\,(i=1,\ldots,m),\\\
&L^{(k)}_{c_{i}^{hom}}[z]=0\,(i\in\mathcal{E}),\,L^{(k)}_{c_{j}^{hom}}[z]\succeq
0\,(j\in\mathcal{I}),\\\ &L^{(k)}_{x^{T}x-1}[z]=0,\,M_{k}[z]\succeq
0,\,z\in\mathbb{R}^{\mathbb{N}^{n}_{2k}}.\end{array}\right.$

Suppose $z^{(k)}$ is a minimizer of (4.14) for the relaxation order $k$. If
there exists an integer $t\in[d_{c},k]$ such that the rank condition (2.6)
holds, then the truncation $z^{(k)}|_{2t}$ has a $r$-atomic representing
measure supported in $K^{\circ}$, i.e.,

$z^{(k)}\big{|}_{2t}=\lambda_{1}[u_{1}]_{2t}+\cdots+\lambda_{r}[u_{r}]_{2t}$

for scalars $\lambda_{1},\ldots,\lambda_{r}>0$, distinct points
$u_{1},\ldots,u_{r}\in K^{\circ}$ and $r=\operatorname{rank}\,M_{t}[z^{(k)}]$.
Then, the truncation $z^{(k)}|_{d}$ is a feasible point for (4.12).

######  Algorithm 4.3.

Let $k:=d_{2}$. Do the following loop:

  * Step 1

Solve the semidefinite relaxation (4.14) for a minimizer $z^{(k)}$.

  * Step 2

Check if there exists $t\in[d_{c},k]$ such that (2.6) holds. If it does, then
the truncation $z^{(k)}|_{d}$ is a feasible point for (4.8).

  * Step 3

If (2.6) fails for all $t\in[d_{c},k]$, let $k:=k+1$ and go to Step 1.

Algorithm 4.3 can be implemented in the software GloptiPoly 3 [17]. The
following is the convergence property for the hierarchy of relaxations (4.14).

######  Theorem 4.4.

Assume the system (4.12) is feasible and
$R\in\mathit{int}\left(\Sigma[x]_{2d_{1}}\right)$ is generic. Then, we have:

  * (i)

The optimization (4.13) has a unique minimizer $z^{*}$ and

(4.15) $z^{*}=\lambda_{1}[u_{1}]_{2d_{1}}+\cdots+\lambda_{r}[u_{r}]_{2d_{1}}$

for scalars $\lambda_{1},\ldots,\lambda_{r}>0$, distinct points
$u_{1},\ldots,u_{r}\in K^{\circ}$ and $r\leq m$.

  * (ii)

For each fixed $t\geq d_{1}$, the sequence
$\\{z^{(k)}|_{2t}\\}_{k=d_{2}}^{\infty}$ is bounded and every accumulation
point $z^{**}$ of $\\{z^{(k)}|_{2t}\\}_{k=d_{2}}^{\infty}$ satisfies
$z^{*}=z^{**}|_{2d_{1}}$.

###### Proof.

(i) As in the proof for item (i) of Theorem 4.1, the trace of $M_{d_{1}}[z]$
can be bounded by a constant. Similarly, it implies that (4.13) has a
minimizer $z^{*}$. The minimizer $z^{*}$ is unique, since the objective
$\langle R,z\rangle$ is linear in $z$ and has generic coefficients. The
membership $z^{*}\in\mathscr{R}_{2d_{1}}(K^{\circ})$ implies that $z^{*}$ has
a decomposition like (4.15). We only need to show that $r\leq m$. Consider the
following linear program in $(\tau_{1},\ldots,\tau_{r})$:

(4.16)
$\left\\{\begin{array}[]{cl}\min&\tau_{1}R(u_{1})+\cdots+\tau_{r}R(u_{r})\\\
\mathit{s.t.}&-1\geq\sum_{j=1}^{r}\tau_{j}g_{i}(u_{j}),\,i=1,\ldots,m,\\\
&\tau_{1}\geq 0,\ldots,\tau_{r}\geq 0.\end{array}\right.$

Note that (4.14) and (4.16) have the same optimal value. Since it is a linear
program, (4.16) has a minimizer $\tau^{*}=(\tau_{1}^{*},\ldots,\tau_{r}^{*})$
of at most $m$ nonzero entries. This implies that the number $r$ in (4.15) can
be chosen to be at most $m$.

(ii) Since $R$ lies in the interior of $\Sigma[x]_{2d_{1}}$, there is
$\epsilon>0$ such that $R-\epsilon\in\Sigma[x]_{2d_{1}}$. Then the constraint
$M_{k}[z]\succeq 0$ implies that

$\langle R,z\rangle-\epsilon(z)_{0}=\langle R-\epsilon,z\rangle\geq 0.$

So we get that $(z)_{0}\leq\frac{\langle R,z\rangle}{\epsilon}$. The optimal
value of (4.14) is always less than or equal to that of (4.10). Therefore, the
sequence $\\{\big{(}z^{(k)}\big{)}_{0}\\}_{k=d_{2}}^{\infty}$ is bounded.
Moreover, the constraint $L^{(k)}_{x^{T}x-1}[z]=0$ implies that

$(z)_{2\alpha}=(z)_{2e_{1}+2\alpha}+\cdots+(z)_{2e_{n}+2\alpha}\geq\max\big{(}(z)_{2e_{1}+2\alpha},\ldots,(z)_{2e_{n}+2\alpha}\big{)}$

for all monomial powers $\alpha$. The diagonal entries of the psd moment
matrix $M_{k}[z]$ are precisely the entries $(z)_{2\beta}$, for powers
$\beta$. This implies that the sequence
$\\{\big{(}z^{(k)}\big{)}_{2\beta}\\}_{k=d_{2}}^{\infty}$ is bounded for all
powers $\beta$. Therefore, for each fixed $t\geq d_{1}$, the sequence of each
diagonal entry of $M_{t}[z^{(k)}]$ is bounded, and so is the truncated
sequence $\\{z^{(k)}|_{2t}\\}_{k=d_{2}}^{\infty}$. Let $\mathcal{H}_{k}$ be
the set of feasible points $z$ in (4.14) for the relaxation order $k$, except
the first $m$ inequalities. Denote the truncation:

$G_{k}\,:=\,\\{z|_{2t}:\,z\in\mathcal{H}_{k}\\}.$

Then, $G_{k+1}\subseteq G_{k}$ for all $k$. Since there is a sphere constraint
$x^{T}x=1$, the quadratic module for the set $K^{\circ}$ is archimedean, so
(see Prop. 3.3 of [42])

$\mathscr{R}_{2t}(K^{\circ})=\cap_{k=d_{2}}^{\infty}G_{k}.$

If $z^{**}$ is an accumulation point of
$\\{z^{(k)}|_{2t}\\}_{k=d_{2}}^{\infty}$, then $z^{**}\in G_{k}$ for all $k$
and hence $z^{**}\in\mathscr{R}_{2t}(K^{\circ})$. Note that the truncation
$z^{**}|_{2d_{1}}$ is also a minimizer of (4.13). Since the minimizer is
unique, we must have $z^{*}=z^{**}|_{2d_{1}}$. $\Box$

The optimization (4.13) is a linear conic optimization problem with the moment
cone. It can also be viewed as a generalized problem of moments. We refer to
[26, 42] for how to solve such optimization problems.

##  5\. The linear scalarization

This section discusses how to solve linear scalarization problems, how to
choose proper weights, and how to detect nonexistence of proper weights. For a
weight $w:=(w_{1},\ldots,w_{m})$, denote the weighted sum

$f_{w}(x):=w_{1}f_{1}(x)+\cdots+w_{m}f_{m}(x).$

We consider the LSP

(5.1) $\min\quad f_{w}(x)\quad\mathit{s.t.}\quad x\in K.$

Recall that $w\neq 0$ is a proper weight if (5.1) is bounded below.
Equivalently, $w$ is a proper weight if and only if $w$ is the normal of a
supporting hyperplane for the set $\mathcal{U}$ as in (3.1).

###  5.1. Tight relaxations for LSPs

The Moment-SOS hierarchy of semidefinite relaxations [25] can be applied to
solve (5.1). When the feasible set $K$ is unbounded, the Moment-SOS hierarchy
may not converge. Here, we apply the tight relaxation method in [45] to solve
(5.1).

The Karush-Kuhn-Tucker (KKT) conditions for (5.1) are

$\nabla f_{w}(u)=\sum_{i\in\mathcal{E}\cup\mathcal{I}}\lambda_{i}\nabla
c_{i}(u),\quad\lambda_{j}\geq 0,\,\lambda_{j}c_{j}(u)=0\,(j\in\mathcal{I}),$

where the $\lambda_{j}$’s are Lagrange multipliers. For convenience, we write
such that

$\begin{array}[]{c}\mathcal{E}\cup\mathcal{I}\,=\,\\{1,\ldots,s\\},\quad
c\,:=\,(c_{1}(x),\ldots,c_{s}(x)),\\\
c_{eq}\,:=\,(c_{i})_{i\in\mathcal{E}},\quad
c_{in}\,:=\,(c_{j})_{j\in\mathcal{I}}.\end{array}$

The KKT conditions imply that

(5.2) $\underbrace{\begin{bmatrix}\nabla c_{1}(x)&\nabla
c_{2}(x)&\cdots&\nabla c_{s}(x)\\\ c_{1}(x)&0&\cdots&0\\\
0&c_{2}(x)&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&c_{s}(x)\\\
\end{bmatrix}}_{C(x)}\underbrace{\begin{bmatrix}\lambda_{1}\\\ \vdots\\\
\lambda_{s}\end{bmatrix}}_{\lambda}=\begin{bmatrix}\nabla f_{w}(x)\\\ 0\\\
\vdots\\\ 0\end{bmatrix}.$

The polynomial tuple $c$ is said to be nonsingular if the matrix $C(x)$ as
above has full column rank for all complex $x\in\mathbb{C}^{n}$ (see [45]).
When $c$ is nonsingular, there exists a matrix polynomial $L(x)$ such that
$L(x)C(x)=I_{s}$. Then

$\lambda=L(x)\begin{bmatrix}\nabla f_{w}(x)\\\ 0\end{bmatrix}.$

For each $i=1,\ldots,s$, let $\lambda_{i}(x):=\big{(}L(x)_{:,1:n}\nabla
f_{w}(x)\big{)}_{i}$ be the $i$th entry polynomial. Denote the polynomial sets

(5.3) $\displaystyle\Phi$
$\displaystyle:=\big{\\{}c_{i}\big{\\}}_{i\in\mathcal{E}}\cup\big{\\{}\lambda_{j}(x)c_{j}\big{\\}}_{j\in\mathcal{I}}\cup\big{\\{}\nabla
f_{w}-\sum_{i\in\mathcal{E}\cup\mathcal{I}}\lambda_{i}(x)c_{i}\big{\\}},$
(5.4) $\displaystyle\Psi$
$\displaystyle:=\\{c_{j},\,\lambda_{j}(x)\\}_{j\in\mathcal{I}}.$

(If $p$ is a vector of polynomials, then $\\{p\\}$ denotes the set of entries
of $p$.) If its minimum value is achieved at a KKT point, then (5.1) is
equivalent to

(5.5) $\left\\{\begin{array}[]{rl}\min&f_{w}(x)\\\
\mathit{s.t.}&p(x)=0\,(p\in\Phi),\,q(x)\geq 0\,(q\in\Psi).\\\
\end{array}\right.$

Let $k_{0}:=\max\\{\lceil\deg(p)/2\rceil:p\in\Phi\cup\Psi\\}$. For an integer
$k\geq k_{0}$, the $k$th order moment relaxation is

(5.6) $\left\\{\begin{array}[]{rl}\min&\langle f_{w},y\rangle\\\
\mathit{s.t.}&L_{p}^{(k)}[y]=0\,(p\in\Phi),\,L_{q}^{(k)}[y]\succeq
0\,(q\in\Psi),\\\ &y_{0}=1,\,M_{k}[y]\succeq
0,\,y\in\mathbb{R}^{\mathbb{N}^{n}_{2k}}.\end{array}\right.$

For $k=k_{0},k_{0}+1,\ldots$, the relaxation (5.6) is a semidefinite program.
The following is the algorithm for solving (5.5).

######  Algorithm 5.1.

Formulate the sets $\Phi,\Psi$ as in (5.3)-(5.4). Let $k:=k_{0}$.

  * Step 1

Solve the relaxation (5.6) for a minimizer $y^{*}$ and let $t:=k_{0}$.

  * Step 2

If $y^{*}$ satisfies the rank condition

(5.7)
$\operatorname{rank}{M_{t}[y^{*}]}\,=\,\operatorname{rank}{M_{t-k_{0}}[y^{*}]},$

then extract $r:=\operatorname{rank}{M_{t}[y^{*}]}$ minimizers for (5.5).

  * Step 3

If (5.7) fails to hold and $t<k$, let $t:=t+1$ and then go to Step 2;
otherwise, let $k:=k+1$ and go to Step 1.

The rank condition (5.7) is called flat truncation. It is a sufficient (and
almost necessary) condition for checking convergence of the Moment-SOS
hierarchy [40]. The Algorithm 5.1 can be implemented in GloptiPoly 3 [17]. The
following is the convergence property for the hierarchy of relaxations (5.6),
which follows from [46, Theorem 4.4].

######  Theorem 5.2.

Assume $c$ is nonsingular and the LSP (5.1) has a minimizer for the weight
$w$. Then, for all $k$ large enough, the optimal value of the relaxation (5.6)
is equal to that of (5.1). Moreover, under either one of the following
conditions

  * (i)

the set $\mathit{Ideal}[\Phi]+\mathit{Qmod}[\Psi]$ is archimedean, or

  * (ii)

the real zero set of polynomials in $\Phi$ is finite,

if each minimizer of (5.1) is an isolated critical point, then all minimizers
of the relaxation (5.6) must satisfy (5.7), when $k$ is big enough. Therefore,
Algorithm 5.1 must terminate within finitely many loops.

######  Example 5.3.

Consider the objectives

$\begin{array}[]{l}f_{1}=\sum_{i=1}^{5}x_{i}^{4}+x_{1}^{2}x_{2}+x_{1}x_{2}^{2}-3x_{1}x_{2}x_{3}+x_{3}x_{4}x_{5}+x_{3}^{3},\\\
f_{2}=\sum_{i=1}^{5}x_{i}^{2}-x_{1}x_{2}^{2}-x_{2}x_{3}^{2}+x_{3}x_{4}^{2}+x_{4}x_{5}^{2}\end{array}$

and the constraint $x_{1}^{2}+\cdots+x_{5}^{2}\geq 1$. The feasible set is
unbounded. A list of some weights and the corresponding Pareto points111
Throughout the paper, all computational results are displayed with four
decimal digits. are given in Table 1.

Table 1. Some Pareto points for Example 5.3. weight $w$ | Pareto point
---|---
$(0.5,0.5)$ | $(-0.3371,0.4659,-0.7504,-0.2807,-0.1655)$
$(0.25,0.75)$ | $(-0.0986,0.3316,-0.6802,-0.5493,-0.3405)$
$(0.75,0.25)$ | $(-0.7711,0.9015,-1.1818,-0.5752,-0.5114)$

It is worthy to note that

$\mathit{Ideal}[c_{eq}]\subseteq\mathit{Ideal}[\Phi],\quad\mathit{Qmod}[c_{in}]\subseteq\mathit{Qmod}[\Psi].$

Hence, if $\mathit{Ideal}[c_{in}]+\mathit{Qmod}[c_{in}]$ is archimedean, then
the condition (i) in Theorem 5.2 holds. Therefore, if the archimdeanness is
met for the constraints in (1.4), then the condition (i) must hold.

It is possible that $f_{w}(x)$ is unbounded below on $K$ for some weight $w$.
For instance, $f_{w}(x)$ is unbounded below for $w=(0,1)$ in Example 5.3. We
refer to Section 4 for how to detect unboundedness. Moreover, we remark that
not every Pareto point is the minimizer of a LSP, as shown in the following.

######  Example 5.4.

Consider the MOP with

$f_{1}\,=\,-x_{1}^{3}-x_{2}^{3}+(x_{3}-x_{4})^{2},\quad
f_{2}\,=\,x_{1}^{2}-x_{2}^{2}+(x_{3}+x_{4})^{2}$

and the constraints $0\leq x_{1},x_{2}\leq 1$. The LSP is

$\min\quad w_{1}f_{1}(x)+w_{2}f_{2}(x)\quad\mathit{s.t.}\quad 0\leq
x_{1},x_{2}\leq 1.$

For $w_{1}\geq w_{2}$, the minimizer is $(1,1,0,0)$. For $w_{1}<w_{2}$, the
minimizer is $(0,1,0,0)$. So the LSP can only give two Pareto points, by
exploring all possibilities of weights. However, each $(x_{1},1,0,0)$, with
$0\leq x_{1}\leq 1$, is a Pareto point.

###  5.2. Existence and choices of proper weights

When $K$ is compact, the LSP (5.1) is bounded below for all weights. When $K$
is unbounded, (5.1) may be unbounded below for some $w$ and has no minimizers.
To find a (weakly) Pareto point, we look for a nonzero weight $w\geq 0$ such
that (5.1) is bounded below, i.e., $w$ is a proper weight. The set of all
proper weights is denoted as

(5.8) $\mathcal{W}\,:=\,\big{\\{}w\in\mathbb{R}_{+}^{m}:\,w\neq
0,\,f_{w}(x)\,\mbox{is bounded below on}\,K\big{\\}}.$

Clearly, the proper weight set $\mathcal{W}$ is a convex cone.

Note that a nonzero weight $w\in\mathcal{W}$ if and only if there exists a
scalar $\gamma\in\mathbb{R}$ such that $f_{w}(x)-\gamma\in\mathscr{P}_{d}(K)$.
So,

(5.9) $\mathcal{W}\,=\,\big{\\{}w\in\mathbb{R}_{+}^{m}:\,w\neq
0,\,f_{w}(x)\in\mathscr{P}_{d}(K)+\mathbb{R}\big{\\}}.$

The cone $\mathscr{P}_{d}(K)$ can be approximated by the sum of the ideal
$\mathit{Ideal}[c_{eq}]$ and the quadratic module $\mathit{Qmod}[c_{in}]$.
Thus, we have the following.

######  Proposition 5.5.

It holds that

(5.10) $\big{\\{}w\in\mathbb{R}_{+}^{m}:\,w\neq
0,\,f_{w}(x)\in\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]+\mathbb{R}\big{\\}}\,\subseteq\,\mathcal{W}.$

When $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ is archimedean ($K$ is
bounded for this case), the containment in (5.10) is an equality. This is
because if $f_{w}(x)$ is bounded below on $K$, then
$f_{w}(x)-\gamma\in\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ for $\gamma$
small enough. When $K$ is unbounded, the sum
$\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ cannot be archimedean, and the
containment in (5.10) is typically not an equality. For instance, for
$K=\mathbb{R}^{3}$, $f_{1}=x_{1}^{2}x_{2}^{2}(x_{1}^{2}+x_{2}^{2})$,
$f_{2}=x_{3}^{6}-3x_{1}^{2}x_{2}^{2}x_{3}^{2}$, we have $(1,1)\in\mathcal{W}$
but $f_{(1,1)}\not\in\Sigma[x]+\mathbb{R}$. For this case,
$\mathit{Ideal}[c_{eq}]=\\{0\\}$, $\mathit{Qmod}[c_{in}]=\Sigma[x]$, and
$f_{(1,1)}$ is the Motzkin polynomial that is nonnegative but not SOS.

Among all proper weights $w\geq 0$ normalized as $e^{T}w=1$, the smallest
possibility of the minimum value of (5.1) is equal to the smallest one of
$f_{1}^{*},\ldots,f_{m}^{*}$, where $f_{i}^{*}$ is the minimum value of
$f_{i}(x)$ on $K$. Some of $f_{i}^{*}$ may be $-\infty$. For the choice
$w=e_{i}$, the minimum value of (5.1) is $f_{i}^{*}$. Beyond them, people are
also interested in $w$ such that the minimum value of (5.1) is maximum. We
discuss how to find such $w$ in the following.

Assume $d$ is the maximum degree of $f_{1},\ldots,f_{m}$. For the minimum
value of $f_{w}(x)$ on $K$ to be maximum, we consider the optimization

(5.11) $\left\\{\begin{array}[]{rl}\max&\gamma\\\
\mathit{s.t.}&1-e^{T}w=0,\,w_{1}\geq 0,\ldots,w_{m}\geq 0,\\\
&\sum_{i=1}^{m}w_{i}f_{i}-\gamma\,\in\,\mathscr{P}_{d}(K).\end{array}\right.$

The dual cone of $\mathscr{P}_{d}(K)$ is
$\mathit{cl}\left(\mathscr{R}_{d}(K)\right)$. (When $K$ is compact, the moment
cone $\mathscr{R}_{d}(K)$ is closed.) The dual optimization of (5.11) is

(5.12) $\left\\{\begin{array}[]{rl}\min&\mu\\\ \mathit{s.t.}&\mu-\langle
f_{i},y\rangle\geq 0\,(i=1,\ldots,m),\\\
&y_{0}=1,\,y\in\mathit{cl}\left(\mathscr{R}_{d}(K)\right).\end{array}\right.$

The $k$th order SOS relaxation for (5.11) is

(5.13) $\left\\{\begin{array}[]{rl}\max&\gamma\\\ \mathit{s.t.}&w_{1}+\cdots
w_{m}=1,\,w_{1}\geq 0,\ldots,w_{m}\geq 0,\\\
&\sum_{i=1}^{m}w_{i}f_{i}-\gamma\,\in\,\mathit{Ideal}[c_{eq}]_{2k}+\mathit{Qmod}[c_{in}]_{2k}.\end{array}\right.$

The dual optimization of (5.13) is the $k$th order moment relaxation for
(5.12):

(5.14) $\left\\{\begin{array}[]{rl}\min&\mu\\\ \mathit{s.t.}&\mu-\langle
f_{i},y\rangle\geq 0\,(i=1,\ldots,m),\\\
&L_{c_{i}}^{(k)}[y]=0\,(i\in\mathcal{E}),\,L_{c_{j}}^{(k)}[y]\succeq
0\,(j\in\mathcal{I}),\\\ &y_{0}=1,\,M_{k}[y]\succeq
0,\,y\in\mathbb{R}^{\mathbb{N}^{n}_{2k}}.\end{array}\right.$

As $k$ increases, the above gives a hierarchy of Moment-SOS relaxations for
solving (5.11). When the sum $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ is
archimedean, the convergence of the hierarchy was shown in [26, 42].

######  Example 5.6.

Consider the objectives

$\begin{array}[]{l}f_{1}={\left({x_{1}}^{2}+x_{2}+x_{3}\right)}^{2}+{\left({x_{2}}^{2}+x_{3}+x_{4}\right)}^{2}-3\,x_{1}x_{2}x_{3}x_{4},\\\
f_{2}=\sum_{i=1}^{4}x_{i}^{4}-\left(x_{1}-x_{2}\right)\left(x_{2}-x_{3}\right)\left(x_{3}-x_{4}\right)\left(x_{4}-x_{1}\right),\\\
f_{3}=3\sum_{i=1}^{4}x_{i}^{3}+x_{1}^{2}\left({x_{2}}^{2}-{x_{3}}^{2}\right)+x_{2}^{2}\left({x_{3}}^{2}-{x_{4}}^{2}\right)+x_{3}^{2}\left({x_{4}}^{2}-{x_{1}}^{2}\right)\end{array}$

and the constraints $x_{1}x_{2}\geq 1,x_{2}x_{3}\geq 1,x_{3}x_{4}\geq
1,x_{1}\geq 0$. Each $f_{i}$ is unbounded below on the feasible set $K$. The
optimization (5.11) can be solved by the Moment-SOS hierarchy of
(5.13)-(5.14). The computed optimal weight $w^{*}$ and Pareto point $x^{*}$
are respectively

$w^{*}=(0.5769,0.2229,0.2003),\,x^{*}=(1.0105,0.9897,1.0105,0.9897).$

The maximum of the minimum value of $f_{w}(x)$ on $K$ is $\gamma^{*}=11.9435$.

When $K$ is unbounded, the LSP (5.1) may be unbounded below for some $w$. For
this case, we look for the most average weight $w$ such that $f_{w}(x)$ is
bounded below on $K$. Recall that
$\widetilde{f_{w}}(\tilde{x}):=x_{0}^{d}f_{w}(\frac{x}{x_{0}})$ is the
homogenization. When $K$ is closed at $\infty$, $f_{w}(x)-\gamma\geq 0$ on $K$
if and only if $\widetilde{f_{w}}(\tilde{x})-\gamma x_{0}^{d}\geq 0$ on
$\widetilde{K}$, where $\widetilde{K}$ is the homogenization of $K$ as in
(4.2). So, we consider the optimization

(5.15) $\left\\{\begin{array}[]{rl}\max&\mu\\\
\mathit{s.t.}&e^{T}w=1,\,w_{i}\geq\mu\,(i=1,\ldots,m),\\\
&\widetilde{f_{w}}-\gamma x_{0}^{d}\geq
0\quad\mbox{on}\quad\widetilde{K}.\end{array}\right.$

Let $\widetilde{c}_{eq}$ denote the set of equality constraining polynomials
and $\widetilde{c}_{in}$ be the set of inequality constraining polynomials in
$\widetilde{K}$. The optimization (5.15) can be solved by the hierarchy of
relaxations

(5.16) $\left\\{\begin{array}[]{rl}\max&\mu\\\
\mathit{s.t.}&e^{T}w=1,\,w_{i}\geq\mu\,(i=1,\ldots,m),\\\
&\widetilde{f_{w}}-\gamma
x_{0}^{d}\in\mathit{Ideal}[\widetilde{c}_{eq}]_{2k}+\mathit{Qmod}[\widetilde{c}_{in}]_{2k}.\end{array}\right.$

We refer to [26, 42] for how to solve (5.15) by the Moment-SOS hierarchy.

######  Example 5.7.

Consider the objectives

$\begin{array}[]{l}f_{1}=-\sum_{i=1}^{4}x_{i}^{3}+2x_{2}^{4}-x_{1}x_{2}x_{3}x_{4},\,\,f_{2}=(\sum_{i=1}^{4}x_{i})^{3}-x_{1}^{4}-x_{2}^{4}-x_{4}^{4},\\\
f_{3}=x_{1}^{4}-x_{2}^{4}+x_{3}^{4}+x_{4}^{4}-x_{1}x_{2}x_{3}-x_{1}x_{2}\end{array}$

and the constraint $x\geq 0$. All objectives $f_{1},f_{2},f_{3}$ are unbounded
below on $K$. By solving (5.16), we get the most average weight
$w^{*}=(0.3529,0.2964,0.3507)$. The minimum value of the corresponding
$f_{w^{*}}$ is $-0.0067$. Solving the LSP (5.1), we get two Pareto points:
$(0,0,0,0.7812)$ and $(0.7812,0,0,0)$.

###  5.3. Nonexistence of proper weights

When the feasible set $K$ is unbounded, there may not exist a weight $w\geq 0$
such that $f_{w}(x)$ is bounded below on $K$. We discuss how to detect
nonexistence of proper weights.

Recall that $d$ is the maximum degree of $f_{i}$ and
$\widetilde{f_{w}}(\tilde{x}):=x_{0}^{d}f_{w}(\frac{x}{x_{0}})$. When $K$ is
closed at $\infty$, the optimization (5.11) is equivalent to

(5.17) $\left\\{\begin{array}[]{rl}\max&\gamma\\\ \mathit{s.t.}&w_{1}+\cdots
w_{m}=1,\,(w_{1},\ldots,w_{m})\geq 0,\\\ &\widetilde{f_{w}}-\gamma
x_{0}^{d}\in\mathscr{P}_{d}(\widetilde{K}).\end{array}\right.$

The dual optimization of (5.17) is

(5.18) $\left\\{\begin{array}[]{rl}\min&\mu\\\ \mathit{s.t.}&\mu-\langle
x_{0}^{d}f_{i}(x/x_{0}),\tilde{y}\rangle\geq 0\,(i=1,\ldots,m),\\\ &\langle
x_{0}^{d},\tilde{y}\rangle=1,\,\tilde{y}\in\mathscr{R}_{d}(\widetilde{K}).\end{array}\right.$

When (5.18) is unbounded below, the problem (5.17) must be infeasible, and
hence there is no proper weight. This is the case if (5.18) has a decreasing
ray $\Delta\tilde{y}$:

(5.19) $\left\\{\begin{array}[]{l}-1\geq\langle
x_{0}^{d}f_{i}(x/x_{0}),\Delta\tilde{y}\rangle\,\,(i=1,\ldots,m),\\\ \langle
x_{0}^{d},\Delta\tilde{y}\rangle=0,\,\,\Delta\tilde{y}\in\mathscr{R}_{d}(\widetilde{K}).\end{array}\right.$

Let $f_{i}^{(d)}$ denote the homogeneous part of degree $d$ for $f_{i}$, i.e.,

$f_{i}^{(d)}=x_{0}^{d}f_{i}(x/x_{0})\big{|}_{x_{0}=0}.$

The equality $\langle x_{0}^{d},\Delta\tilde{y}\rangle=0$ implies that every
representing measure for $\Delta\tilde{y}$ must be supported in the hyperplane
$x_{0}=0$. Therefore, (5.19) can be reduced to

(5.20) $-1\geq\langle f_{i}^{(d)},\Delta
y\rangle\,\,(i=1,\ldots,m),\quad\Delta y\in\mathscr{R}_{d}(K^{\circ}),$

where $K^{\circ}$ is the set as in (4.3). We remark that if $\deg(f_{i})<d$,
then $f_{i}^{(d)}=0$ and hence $\langle f_{i}^{(d)},\Delta y\rangle=0$, which
implies that (5.19) is infeasible. Therefore, the decreasing ray
$\Delta\tilde{y}$ as in (5.19) exist only if all $f_{i}$ have the same degree.
The following is the nonexistence theorem of proper weights. Like before, the
closeness of $K$ at infinity can be weakened.

######  Theorem 5.8.

Assume (5.20) has a feasible point $\Delta
y=\lambda_{1}[z_{1}]_{d}+\cdots+\lambda_{r}[z_{r}]_{d}$, with
$\lambda_{1},\ldots,\lambda_{r}>0$ and $z_{1},\ldots,z_{r}\in K^{\circ}$. If
each $(0,z_{i})$ lies on
$\mathit{cl}\left(\widetilde{K}\cap\\{x_{0}>0\\}\right)$, then the LSP (5.1)
is unbounded below for all nonzero $w\geq 0$ and hence
$\mathcal{W}=\emptyset$.

###### Proof.

For each $w\geq 0$ with $e^{T}w=1$, it holds that

$\begin{array}[]{c}-1\geq\langle\sum_{i=1}^{m}w_{i}f_{i}^{(d)},\Delta
y\rangle=\langle\widetilde{f_{w}},\Delta y\rangle,\quad\Delta
y\in\mathscr{R}_{d}(K^{\circ}).\end{array}$

Since $\Delta y=\lambda_{1}[z_{1}]_{d}+\cdots+\lambda_{r}[z_{r}]_{d}$, there
exists at least one $i$ such that

$-1/r\,\geq\,\langle\widetilde{f_{w}},\lambda_{i}[z_{i}]_{d}\rangle.$

By Theorem 4.1(ii), $f_{w}(x)$ is unbounded below on $K$, since $(0,z_{i})$
lies in the closure of $\widetilde{K}\cap\\{x_{0}>0\\}$ and $\lambda_{i}>0$. A
nonzero weight $w\geq 0$ is proper if and only if $w/(e^{T}w)$ is proper.
Hence, no proper weights exist and $\mathcal{W}=\emptyset$. $\Box$

The moment system (5.20) is in the form (4.12). Algorithm 4.3 can be applied
to get a feasible point for (5.20). This can be done by solving a hierarchy of
moment relaxations like (4.14). The convergence is shown in Theorem 4.4.

######  Example 5.9.

Consider the objectives

$\begin{array}[]{l}f_{1}=-\sum_{i=1}^{5}x_{i}^{3}-x_{2}^{4}+x_{4}^{4}-x_{1}x_{2}x_{3}-x_{3}x_{4}x_{5},\\\
f_{2}=(\sum_{i=1}^{5}x_{i})^{3}-\sum_{i=1}^{4}x_{i}^{4}+x_{1}x_{2}x_{3}x_{4}+x_{2}x_{3}x_{4}x_{5},\\\
f_{3}=x_{1}^{4}-x_{2}^{4}+x_{3}^{4}+x_{4}^{4}-x_{1}x_{2}x_{3}-x_{3}x_{4}x_{5},\\\
f_{4}=-(x_{1}x_{2})^{2}+(x_{2}x_{3})^{2}+(x_{3}x_{4})^{2}+(x_{4}x_{5})^{2}\end{array}$

and the constraints $x_{1}^{2}\geq 1,\ldots,x_{5}^{2}\geq 1$. By Algorithm
4.3, we get that $\Delta y=\lambda[u]_{4}$ is feasible for (5.20) with

$u=(-0.7014,-0.7049,0.0533,-0.0428,0.0803),\quad\lambda=4.1146.$

The point $(0,u)$ lies on the closure of $\widetilde{K}\cap\\{x_{0}>0\\}$.
Therefore, the LSP (5.1) is unbounded below for all nonzero weights $w\geq 0$
by Theorem 5.8.

We remark that when no proper weights exist, the system (5.20) is still
possibly infeasible. For instance, this is the case for

$K=\mathbb{R}^{1},\quad f_{1}=x_{1}^{3}+x_{1},\quad f_{2}=-x_{1}^{3}.$

There is no nonzero $(w_{1},w_{2})\geq 0$ such that $f_{w}(x)$ is bounded
below on $\mathbb{R}^{1}$. However, there is no $\Delta y$ such that

$-1\geq\langle x_{1}^{3},\Delta y\rangle,\quad-1\geq\langle-x_{1}^{3},\Delta
y\rangle,\quad\Delta y\in\mathscr{R}_{3}(\\{x_{1}^{2}=1\\}).$

Moreover, when no proper weights exist, Pareto points may still exist. For
instance, this is the case for

$\min\quad(x_{1},x_{2})\quad\mathit{s.t.}\quad x_{1}+x_{2}^{3}\geq 0.$

For every $t$, $(t^{3},-t)$ is a Pareto point, but there is no nonzero
$w=(w_{1},w_{2})\geq 0$ such that $w_{1}x_{1}+w_{2}x_{2}$ is bounded below on
$x_{1}+x_{2}^{3}\geq 0$.

##  6\. The Chebyshev scalarization

The Chebyshev scalarization problem is

(6.1) $\begin{array}[]{rl}\min\limits_{x\in K}&\max\limits_{1\leq i\leq
m}w_{i}(f_{i}(x)-f_{i}^{*})\end{array}$

for a nonzero weight $w:=(w_{1},\ldots,w_{m})\geq 0$. In the above, each
$f_{i}^{*}$ is the minimum value of $f_{i}$ on $K$. In this section, we assume
all $f_{i}^{*}>-\infty$. If one of them is $-\infty$, we refer to Subsection
7.2 for how to get PPs and WPPs.

Each minimizer of (6.1) is a weakly Pareto point. Conversely, every weakly
Pareto point is a minimizer of the CSP (6.1) for some weight, provided each
$f_{i}^{*}>-\infty$. This is because if $x^{*}$ is a weakly Pareto point, then
there exist weights $w_{i}\geq 0$ such that all
$w_{i}(f_{i}(x^{*})-f_{i}^{*})$ are equal, since $f_{i}(x^{*})-f_{i}^{*}\geq
0$ for each $i$. Then $x^{*}$ is the minimizer for that CSP. Observe that
$f_{i}^{*}$ equals the minimum value of the LSP (5.1) for the weight
$w=e_{i}$. Algorithm 5.1 can be applied to compute $f_{i}^{*}$.

After all $f_{i}^{*}$ are obtained, one can solve the CSP (6.1) for a weakly
Pareto point. With the new variable $x_{n+1}$, the CSP (6.1) is equivalent to

(6.2) $\left\\{\begin{array}[]{rl}\min&x_{n+1}\\\
\mathit{s.t.}&x_{n+1}-w_{i}(f_{i}(x)-f_{i}^{*})\geq 0\,(i=1,\ldots,m),\\\
&c_{i}(x)=0\,(i\in\mathcal{E}),\,c_{j}(x)\geq
0\,(j\in\mathcal{I}).\end{array}\right.$

To get convergent Moment-SOS relaxations, we typically need archimedeanness
for constraining polynomials. The feasible set of (6.2) is unbounded. To fix
this issue, one can select a feasible point $\xi\in K$ and let

$B_{0}\,:=\,\max\limits_{1\leq i\leq
m}\big{(}w_{i}(f_{i}(\xi)-f_{i}^{*})\big{)}.$

Then (6.2) is equivalent to

(6.3) $\left\\{\begin{array}[]{rl}\min&x_{n+1}\\\
\mathit{s.t.}&x_{n+1}-w_{i}(f_{i}(x)-f_{i}^{*})\geq 0\,(i=1,\ldots,m),\\\
&B_{0}-x_{n+1}\geq 0,\,x_{n+1}\geq 0,\\\
&c_{i}(x)=0\,(i\in\mathcal{E}),\,c_{j}(x)\geq
0\,(j\in\mathcal{I}).\end{array}\right.$

For convenience, denote the set

(6.4)
$\mathcal{G}:=\big{\\{}c_{j}\big{\\}}_{j\in\mathcal{I}}\cup\\{x_{n+1},\,B_{0}-x_{n+1}\\}\cup\big{\\{}x_{n+1}-w_{i}(f_{i}-f_{i}^{*})\big{\\}}_{i=1}^{m}.$

The $k$th order moment relaxation for (6.3) is

(6.5) $\left\\{\begin{array}[]{rl}\min&\langle x_{n+1},y\rangle\\\
\mathit{s.t.}&L_{c_{i}}^{(k)}[y]=0\,(i\in\mathcal{E}),\,L_{p}^{(k)}[y]\succeq
0\,(p\in\mathcal{G}),\\\ &y_{0}=1,\,M_{k}[y]\succeq
0,\,y\in\mathbb{R}^{\mathbb{N}^{n+1}_{2k}}.\end{array}\right.$

Let $d_{0}$ be the degree

(6.6) $d_{0}\,:=\,\max\big{\\{}\lceil
d/2\rceil,\lceil\deg(c_{i})/2\rceil\,(i\in\mathcal{E}\cup\mathcal{I})\big{\\}}.$

Suppose $y^{*}$ is a minimizer of (6.5). If there exists $t\in[d_{0},k]$ such
that

(6.7)
$\operatorname{rank}\,M_{t}[y^{*}]\,=\,\operatorname{rank}\,M_{t-d_{0}}[y^{*}],$

then we can get $\operatorname{rank}\,M_{t}[y^{*}]$ minimizers for (6.1) (see
[16, 40]). The following is about the convergence of the hierarchy of (6.5).

######  Theorem 6.1.

Assume $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ is archimedean. Suppose
$y^{(k)}$ is a minimizer of the moment relaxation (6.5) for the order $k$. If
the CSP (6.1) has finitely many minimizers, then for $t$ big enough, every
accumulation point of $\\{y^{(k)}|_{2t}\\}_{k=d_{0}}^{\infty}$ must satisfy
(6.7).

###### Proof.

Since $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ is archimedean, there
exists a scalar $N$ such that
$N-x^{T}x\,\in\,\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}].$ Note that

$B_{0}^{2}-x_{n+1}^{2}=(B_{0}-x_{n+1})^{2}+2x_{n+1}\cdot\frac{(B_{0}-x_{n+1})^{2}}{B_{0}}+2(B_{0}-x_{n+1})\frac{x_{n+1}^{2}}{B_{0}}.$

Therefore, we get that

$N-x^{T}x+B_{0}^{2}-x_{n+1}^{2}\,\in\,\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[\mathcal{G}].$

This means that $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[\mathcal{G}]$ is
archimedean. When the CSP (6.1) has finitely many minimizers, the conclusion
is implied by Theorem 3.3 of [40]. $\Box$

When $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[c_{in}]$ is not archimedean (this
is the case if $K$ is unbounded), the homogenization method in Subsection 5.2
can be similarly applied. Moreover, the method in [35] can also be applied to
solve (6.1).

######  Example 6.2.

Consider the objectives

$\begin{array}[]{l}f_{1}=\sum_{i=1}^{4}x_{i}^{2}-(x_{1}x_{2}+x_{3}x_{4})(x_{1}x_{3}+x_{2}x_{4}),\\\
f_{2}=\sum_{i=1}^{4}x_{i}^{4}+x_{1}x_{2}x_{3}+x_{2}x_{3}x_{4}+x_{1}x_{2}x_{3}x_{4},\\\
f_{3}=\sum_{i=1}^{4}x_{i}^{6}+(x_{1}^{2}-x_{2}^{2}+1)(x_{2}^{2}-x_{3}^{2}+1)(x_{3}^{2}-x_{4}^{2}+1)\end{array}$

and the constraint $x_{1}x_{2}\leq 1,x_{2}x_{3}\leq 1,x_{3}x_{4}\leq
1,x_{1}x_{4}\leq 1$. The minimum values $f_{1}^{*},f_{2}^{*},f_{3}^{*}$ are
$0.0000,-0.0710,0.6029$ respectively. A list of some weights and corresponding
weakly Pareto points are in Table 2. Indeed, they are all Pareto points,
confirmed by solving the optimization (7.1).

Table 2. Some Pareto points for Example 6.2. weight $w$ | Pareto point
---|---
$(1,1,1)$ | $(0.000,0.000,0.000,0.4503)$
$(1,2,2)$ | $(-0.0024,-0.0979,-0.0635,-0.5248)$
$(1,2,3)$ | $(-0.0029,-0.1228,-0.0700,-0.5648)$

##  7\. Existence and nonexistence of PPs and WPPs

This section discusses how to check if a given point is a (weakly) Pareto
point and how to detect existence or nonexistence of (weakly) Pareto points.

###  7.1. Detection of PPs and WPPs

For a given point $x^{*}\in K$, how can we detect if it is a Pareto point or
not? To this end, consider the optimization

(7.1) $\left\\{\begin{array}[]{rl}\min&f_{e}(x):=f_{1}(x)+\cdots+f_{m}(x)\\\
&f_{i}(x^{*})-f_{i}(x)\geq 0\,\,(i=1,\ldots,m),\\\ &x\in K.\end{array}\right.$

This is a kind of lexicographic method (see [36]). Let $z^{*}$ be a minimizer
of (7.1), if it exists. Then, $x^{*}$ is a Pareto point if and only if the
minimum value of (7.1) is equal to $f_{e}(x^{*})$. Moreover, if $x^{*}$ is not
a Pareto point, the minimizer $z^{*}$ must be a Pareto point, since all the
weights are positive. A Pareto point may be obtained by solving (7.1) for
given $x^{*}\in K$, provided (7.1) has a minimizer.

Let $F$ be the feasible set of (7.1) and

(7.2)
$\mathcal{F}\,:=\,\big{\\{}c_{j}\big{\\}}_{j\in\mathcal{I}}\cup\big{\\{}f_{i}(x^{*})-f_{i}(x))\big{\\}}_{i=1}^{m}.$

For a degree $k\geq d/2$, the $k$th order moment relaxation for (7.1) is

(7.3) $\left\\{\begin{array}[]{rl}\min&\langle f_{e},y\rangle\\\
\mathit{s.t.}&L_{c_{i}}^{(k)}[y]=0\,(i\in\mathcal{E}),\,L_{q}^{(k)}[y]\succeq
0\,(q\in\mathcal{F}),\\\ &y_{0}=1,\,M_{k}[y]\succeq
0,\,y\in\mathbb{R}^{\mathbb{N}^{n}_{2k}}.\end{array}\right.$

Recall that $d_{0}$ is the degree as in (6.6). Suppose $y^{*}$ is a minimizer
of (7.3). If there exists $t\in[d_{0},k]$ such that

(7.4)
$\operatorname{rank}\,M_{t}[y^{*}]\,=\,\operatorname{rank}\,M_{t-d_{0}}[y^{*}],$

then we can get $r:=\operatorname{rank}\,M_{t}[y^{*}]$ minimizers for (7.1).
Recall that $c_{eq}$ is the tuple of equality constraining polynomials. The
following result follows from Theorem 3.3 of [40].

######  Theorem 7.1.

Assume $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[\mathcal{F}]$ is archimedean.
Suppose $y^{(k)}$ is a minimizer of the relaxation (7.3) for the order $k$. If
(7.1) has only finitely many minimizers, then for $t$ big enough, every
accumulation point of $\\{y^{(k)}|_{2t}\\}_{k=1}^{\infty}$ must satisfy (7.4).

When $\mathit{Ideal}[c_{eq}]+\mathit{Qmod}[\mathcal{F}]$ is not archimedean,
the hierarchy of relaxations (7.3) may not converge. For such a case, we refer
to the homogenization method in Subsection 5.2 or the method in [35].

######  Example 7.2.

(i) Consider the objectives

$\begin{array}[]{l}f_{1}=x_{1}^{2}(x_{1}-2)^{2}+(x_{1}-x_{2})^{2}+(x_{2}-x_{3})^{2}+(x_{3}-x_{4})^{2},\\\
f_{2}=-x_{1}^{2}-x_{2}^{2}-x_{3}^{2}-x_{4}^{2}+x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{4}\end{array}$

and the constraint $x\geq 0$. We first solve the CSP (6.1) with
$w_{1}=w_{2}=1$ and get the weakly Pareto point $x^{*}=(0,0,0,0)$. It is not a
Pareto point. By solving (7.1), we get the Pareto point
$(2.000,2.001,2.001,2.001)$.
(ii) Consider the objectives

$f_{1}=x_{1}^{3}-x_{1}^{2}x_{2}-x_{2},\quad
f_{2}=x_{2}^{3}-x_{1}x_{2}^{2}-x_{1}$

and the constraint $x_{1}x_{2}\leq 1$. The LSP (5.1) is unbounded below for
all weights $w_{i}$, which is confirmed by a feasible point for (5.20). But we
are still able to find a Pareto point by solving (7.1) for some given $x^{*}$.
For instance, for $x^{*}=(-1,-0.5)$, solving (7.1) gives the Pareto point
$(1.0000,1.0000)$.

We can similarly detect if a given point $x^{*}\in K$ is a weakly Pareto point
or not. Consider the optimization

(7.5) $\left\\{\begin{array}[]{rl}\min&\max\limits_{1\leq i\leq
m}\big{(}f_{i}(x)-f_{i}(x^{*})\big{)}\\\
\mathit{s.t.}&f_{i}(x^{*})-f_{i}(x)\geq 0\,(i=1,\ldots,m),\\\
&c_{i}(x)=0\,(i\in\mathcal{E}),\,c_{j}(x)\geq
0\,(j\in\mathcal{I}).\end{array}\right.$

Let $z^{*}$ be a minimizer of (7.5), if it exists. Then, $x^{*}$ is a weakly
Pareto point if and only if the optimal value of (7.5) is equal to $0$.
Moreover, if $x^{*}$ is not a weakly Pareto point, then one can show that
$z^{*}$ is a weakly Pareto point. By introducing the new variable $x_{n+1}$,
the optimization (7.5) is equivalent to

(7.6) $\left\\{\begin{array}[]{rl}\min&x_{n+1}\\\
\mathit{s.t.}&x_{n+1}-f_{i}(x)+f_{i}(x^{*})\geq 0\,(i=1,\ldots,m),\\\
&f_{i}(x^{*})-f_{i}(x)\geq 0\,(i=1,\ldots,m),\\\
&c_{i}(x)=0\,(i\in\mathcal{E}),\,c_{j}(x)\geq
0\,(j\in\mathcal{I}).\end{array}\right.$

The optimal value of (7.6) is always less than or equal to $0$. A similar
hierarchy of moment relaxations like (6.5) can be applied to solve (7.6), and
a similar convergence result like Theorem 6.1 holds. When the feasible set of
(7.5) is unbounded, the Moment-SOS hierarchy may not converge. For such a
case, we refer to the homogenization method in Subsection 5.2 or the method in
[35].

###  7.2. Existence of PPs and WPPs

When $K$ is unbounded, we discuss how to detect existence of PPs and WPPs.
Consider the min-max optimization

(7.7) $\min\limits_{x\in K}\,\max\limits_{1\leq i\leq m}f_{i}(x).$

The following is the existence result. See Subsection 3.1 for $\pi$-minimal
points.

######  Theorem 7.3.

The min-max optimization (7.7) has the following properties:

  * (i)

If (7.7) is unbounded below, then there is no weakly Pareto point, and hence
there is no Pareto point. If (7.7) is bounded below, then every minimizer of
(7.7) (if it exists) is a weakly Pareto point.

  * (ii)

Let $S$ be the set of minimizers of (7.7). For each $x^{*}\in S$, if
$f(x^{*})$ is a $\pi$-minimal point of the image $f(S)$ for a permutation
$\pi$ of $(1,\ldots,m)$, then $x^{*}$ is a Pareto point. In particular, if $S$
is compact, then there exists a Pareto point.

###### Proof.

(i) If (7.7) is unbounded below, then for every $x\in K$, there exists $z\in
K$ such that

$\max_{1\leq i\leq m}f_{i}(z)\,<\,\min_{1\leq i\leq m}f_{i}(x).$

This implies $f(z)<f(x)$, hence there is no weakly Pareto point.

Suppose (7.7) is bounded below and it has a minimizer, say, $x^{*}$. Then
$x^{*}$ must be a weakly Pareto pint. If otherwise there is $z\in K$ such that
$f(z)<f(x^{*})$, then

$\max_{i}f_{i}(z)\,<\,\max_{i}f_{i}(x^{*}),$

which contradicts that $x^{*}$ is a minimizer.

(ii) Suppose $f(x^{*})$ is a $\pi$-minimal point of $f(S)$. Let $z\in K$ be a
point such that $f(z)\leq f(x^{*})$. Since $x^{*}$ is a minimizer of (7.7),
one can see that

$\max_{1\leq i\leq m}f_{i}(x^{*})\,\leq\,\max_{1\leq i\leq
m}f_{i}(z)\,\leq\,\max_{1\leq i\leq m}f_{i}(x^{*}).$

This implies that $z$ is also a minimizer of (7.7), so $z\in S$. Since
$f(x^{*})$ is $\pi$-minimal among $f(S)$, $f(x^{*})\leq f(z)$, so
$f(x^{*})=f(z)$ and hence $x^{*}$ is a Pareto point. When $S$ is compact, the
set $S$ must have a $\pi$-minimal point, for every permutation $\pi$ of
$(1,\ldots,m)$, and hence (1.4) has a Pareto point, by Proposition 3.1. $\Box$

Each optimizer $x^{*}$ of (7.7) is a weakly Pareto point. One can solve (7.1)
to check if $x^{*}$ is a Pareto point or not. If it is not, each minimizer of
(7.1) is a Pareto point. We remark that (7.7) can be reformulated as
polynomial optimization. By introducing the new variable $x_{n+1}$, the
optimization (7.7) is equivalent to

(7.8) $\left\\{\begin{array}[]{rl}\min&x_{n+1}\\\ \mathit{s.t.}&x_{n+1}\geq
f_{i}(x)\,(i\in[m]),\,x\in K.\end{array}\right.$

The Moment-SOS hierarchy can be applied to solve it. When the set $K$ is
unbounded, the feasible set of (7.8) is also unbounded. The Moment-SOS
hierarchy may not converge. For such a case, we refer to the homogenization
method in Subsection 5.2 or the method in [35].

Once a minimizer $x^{*}$ for (7.8) is obtained, we can solve (7.1) to detect
if it is a Pareto point or not. If it is not, we may get a Pareto point by
solving (7.1).

######  Example 7.4.

Consider the MOP with objectives

$\begin{array}[]{ll}f_{1}=x_{1}^{3}+x_{2}^{3}-x_{3}^{3}+x_{3}^{2}x_{4}^{2},&f_{2}=x_{2}^{3}+x_{3}^{3}-x_{4}^{3}+x_{4}^{2}x_{1}^{2},\\\
f_{3}=x_{3}^{3}+x_{4}^{3}-x_{1}^{3}+x_{1}^{2}x_{2}^{2},&f_{4}=x_{4}^{3}+x_{1}^{3}-x_{2}^{3}+x_{2}^{2}x_{3}^{2},\end{array}$

and with the exterior constraint $x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+x_{4}^{3}\geq
1$. All $f_{1},f_{2},f_{3},f_{4}$ are unbounded below on $K$. The CSP (6.1)
does not exist since each $f_{i}^{*}=-\infty$. However, solving (7.8) gives
the Pareto point $(0.6300,0.6300,0.6300,0.6300).$

###  7.3. Nonexistence of WPPs

We discuss how to detect nonexistence of weakly Pareto points, when $K$ is
unbounded. Recall that $d_{i}:=\deg(f_{i})$. Observe that (7.7) is unbounded
below if and only if the following optimization is unbounded below:

(7.9) $\left\\{\begin{array}[]{rl}\min&x_{n+1}\\\
\mathit{s.t.}&-(-x_{n+1})^{d_{i}}-f_{i}(x)\geq 0\,(i\in[m]),\,x\in
K.\end{array}\right.$

Let $K_{1}$ be the feasible set of (7.9) and let its homogenization be
($\tilde{x}:=(x_{0},x)$):

(7.10)
$\widetilde{K}_{1}\,:=\left\\{(x_{0},x,x_{n+1})\left|\begin{array}[]{l}-(-x_{n+1})^{d_{i}}-\widetilde{f_{i}}(\tilde{x})\geq
0\,(i\in[m]),\\\
\widetilde{c_{i}}(\tilde{x})=0\,(i\in\mathcal{E}),\,\,\widetilde{c_{j}}(\tilde{x})\geq
0\,(j\in\mathcal{I}),\\\ \|\tilde{x}\|^{2}+\|x_{n+1}\|^{2}=1,\,x_{0}\geq
0\end{array}\right.\right\\}.$

When $K_{1}$ is closed at $\infty$, $x_{n+1}\geq\gamma$ on $K_{1}$ if and only
if $x_{n+1}-\gamma x_{0}\geq 0$ on $\widetilde{K}_{1}$, i.e., $x_{n+1}-\gamma
x_{0}\in\mathscr{P}_{1}(\widetilde{K}_{1})$. So, we consider the linear conic
optimization

(7.11) $\max\quad\gamma\quad\mathit{s.t.}\quad x_{n+1}-\gamma
x_{0}\in\mathscr{P}_{1}(\widetilde{K}_{1}).$

The optimization (7.7) is unbounded below if and only if (7.11) is infeasible,
when $K_{1}$ is closed at $\infty$. The dual optimization of (7.11) is

(7.12) $\min\quad\langle
x_{n+1},\check{y}\rangle\quad\mathit{s.t.}\quad\langle
x_{0},\check{y}\rangle=1,\,\check{y}\in\mathscr{R}_{1}(\widetilde{K}_{1}).$

Note that (7.12) is feasible if $K$ is nonempty. So, it is unbounded below if
there is a decreasing ray $\Delta\check{y}$:

(7.13) $\begin{array}[]{c}\langle
x_{n+1},\Delta\check{y}\rangle=-1,\quad\langle
x_{0},\Delta\check{y}\rangle=0,\quad\Delta\check{y}\in\mathscr{R}_{1}(\widetilde{K}_{1}).\end{array}$

Since $x_{0}\geq 0$ on $\widetilde{K}_{1}$, the equality $\langle
x_{0},\Delta\check{y}\rangle=0$ implies that every representing measure for
$\Delta\check{y}$ is supported in $x_{0}=0$. Therefore, (7.13) is equivalent
to

(7.14) $\begin{array}[]{c}\langle
x_{n+1},\Delta\tilde{y}\rangle=-1,\quad\Delta\tilde{y}\in\mathscr{R}_{1}(K_{1}^{\circ}),\end{array}$

where $K_{1}^{\circ}$ is the linear section $x_{0}=0$ of $\widetilde{K}_{1}$:

(7.15)
$K_{1}^{\circ}\,:=\,\left\\{(x,x_{n+1})\left|\begin{array}[]{l}-(-x_{n+1})^{d_{i}}-f_{i}^{hom}(x)\geq
0\,(i\in[m]),\\\ c_{i}^{hom}(x)=0\,(i\in\mathcal{E}),\,c_{j}^{hom}(x)\geq
0\,(j\in\mathcal{I}),\\\ \|x\|^{2}+x_{n+1}^{2}=1\end{array}\right.\right\\}.$

The following is the theorem for nonexistence of WPPs.

######  Theorem 7.5.

Suppose $\Delta\tilde{y}=\lambda v$, with $\lambda>0$ and $v\in
K_{1}^{\circ}$, is a feasible point for (7.14). If the point
$(0,v)\in\mathit{cl}\left(\widetilde{K}_{1}\cap\\{x_{0}>0\\}\right)$, then
(7.9) and (7.7) must be unbounded below, and hence there are no weakly Pareto
points.

###### Proof.

The unboundedness of (7.9) is implied by the item (ii) of Theorem 4.1, for the
case that $g^{\mathit{hom}}:=x_{n+1}$ and $K^{\circ}$ is replaced by
$K_{1}^{\circ}$. Note that (7.7) is unbounded below if and only if (7.9) is
unbounded below. So, (7.7) is also unbounded below. By Theorem 7.3, there are
no weakly Pareto points. $\Box$

The tms $\Delta\tilde{y}=\lambda v$ satisfying (7.14) can be obtained by
Algorithm 4.3 with a minor variation. The only difference is to choose a
generic $R\in\mathit{int}\left(\Sigma[x,x_{n+1}]_{2d_{1}}\right)$ and then
solve the hierarchy of moment relaxations:

(7.16) $\left\\{\begin{array}[]{cl}\min&\langle R,z\rangle\\\
\mathit{s.t.}&\langle
x_{n+1},z\rangle=-1,\,L^{(k)}_{\|(x,x_{n+1})\|^{2}-1}[z]=0,\\\
&L^{(k)}_{c_{i}^{hom}}[z]=0\,(i\in\mathcal{E}),\,L^{(k)}_{c_{j}^{hom}}[z]\succeq
0\,(j\in\mathcal{I}),\\\ &L^{(k)}_{h_{i}}[z]\succeq
0\,(i\in[m]),\,M_{k}[z]\succeq
0,\,z\in\mathbb{R}^{\mathbb{N}^{n+1}_{2k}}.\end{array}\right.$

In the above, each $h_{i}:=-(-x_{0})^{d_{i}}-f_{i}^{hom}(x)$. The convergence
property for the hierarchy of (7.16) is similar to that for Theorem 4.4.

######  Example 7.6.

Consider the MOP with objectives

$\begin{array}[]{rcl}f_{1}&=&(x_{1}x_{2}+x_{3}x_{4})(x_{1}x_{4}+x_{2}x_{3})+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2},\\\
f_{2}&=&x_{1}^{3}x_{2}^{2}+x_{2}^{3}x_{3}^{2}+x_{3}^{3}x_{4}^{2}+x_{4}^{3}x_{1}^{2},\\\
f_{3}&=&x_{1}^{4}-x_{2}^{4}+x_{3}^{4}-x_{4}^{4}+x_{1}x_{2}x_{4}+x_{1}x_{3}x_{4},\\\
f_{4}&=&(x_{1}-x_{2})(x_{3}-x_{4})^{2}+(x_{1}-x_{3})(x_{2}-x_{4})^{2}+\\\
&&\quad(x_{1}-x_{4})(x_{2}-x_{3})^{2}+x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{4}\end{array}$

and with the constraints $x_{1}x_{2}x_{3}\geq 1$, $x_{2}x_{3}x_{4}\geq 1$.
Solving the moment relaxation (7.16) gives the feasible point
$\Delta\tilde{y}=3.3597[v]_{5}$ with

$v=(v_{1},v_{2},v_{3},v_{4},v_{5})=(-0.2761,0.8737,0.0000,-0.2680,-0.2976).$

The set $K_{1}$ is not closed at infinity but $(0,v)$ belongs to
$\mathit{cl}\left(\widetilde{K}_{1}\cap\\{x_{0}>0\\}\right)$. This is because
$\lim_{\ell\to\infty}s_{\ell}/\|s_{\ell}\|=(0,v)$, where

$s_{\ell}\,:=\,(-\sqrt[3]{v_{2}v_{4}/\ell},v_{1},v_{2},-1/\ell,v_{4},v_{5}).$

One can check that
$s_{\ell}/\|s_{\ell}\|\in\widetilde{K}_{1}\cap\\{x_{0}>0\\}$ when $\ell$ is
big enough. By Theorem 7.5, there is no weakly Pareto point.

###  7.4. Nonexistence of PPs

When there are no weakly Pareto points, there must exist no Pareto points. So
Theorem 7.5 is also applicable to detect nonexistence of Pareto points.
However, a Pareto point may not exist while weakly Pareto points exist. This
section discusses how to detect nonexistence of Pareto points for this case.

We consider the optimization (7.1) with $x^{*}\in K$. A Pareto point exists if
and only if (7.1) is bounded below and has a minimizer for some $x^{*}\in K$.
The “if” implication is clear. When $x^{*}$ itself is a Pareto point, then
$x^{*}$ must be a minimizer for (7.1). This explains the “only if”
implication. Let $K(x^{*})$ be the feasible set of (7.1) determined by $x^{*}$
and let $\widetilde{K}(x^{*})$ be the homogenization of $K(x^{*})$ similarly
as in (4.2). Suppose $K(x^{*})$ is closed at $\infty$. Then (7.1) is bounded
below if and only if $\widetilde{f_{e}}(\tilde{x})-\gamma
x_{0}^{d}\in\mathscr{P}_{d}(\widetilde{K}(x^{*}))$ for some $\gamma$. We
consider the linear conic optimization

(7.17)
$\max\quad\gamma\quad\mathit{s.t.}\quad\widetilde{f_{e}}(\tilde{x})-\gamma
x_{0}^{d}\in\mathscr{P}_{d}(\widetilde{K}(x^{*})).$

Pareto points do not exist if (7.1) is unbounded below for all $x^{*}\in K$.
This is equivalent to that (7.17) is infeasible for all $x^{*}\in K$. The dual
optimization of (7.17) is

(7.18)
$\min\quad\langle\widetilde{f_{e}},\tilde{y}\rangle\quad\mathit{s.t.}\quad\langle
x_{0}^{d},\tilde{y}\rangle=1,\,\tilde{y}\in\mathscr{R}_{d}(\widetilde{K}(x^{*})).$

By weak duality, (7.17) is infeasible if (7.18) is unbounded below. The
problem (7.18) is feasible for all $x^{*}\in K$. Therefore, (7.18) is
unbounded below if there is a decreasing ray $\Delta\tilde{y}$:

(7.19) $\langle\widetilde{f_{e}},\Delta\tilde{y}\rangle=-1,\quad\langle
x_{0}^{d},\Delta\tilde{y}\rangle=0,\quad\Delta\tilde{y}\in\mathscr{R}_{d}(\widetilde{K}(x^{*})).$

Since $x_{0}\geq 0$ on $\widetilde{K}(x^{*})$, $\langle
x_{0}^{d},\Delta\check{y}\rangle=0$ if and only if every representing measure
for $\Delta\check{y}$ is supported in the hyperplane $x_{0}=0$. Hence, (7.19)
is equivalent to

(7.20) $\begin{array}[]{c}\langle
f_{e}^{hom},\Delta\tilde{y}\rangle=-1,\quad\Delta\tilde{y}\in\mathscr{R}_{d}(\widetilde{K}_{0}^{*}).\end{array}$

where $f_{e}^{hom}(x):=\widetilde{f_{e}}(0,x)$ and $K_{0}^{*}$ is the
intersection $K(x^{*})\cap\\{x_{0}=0\\}$:

(7.21)
$K_{0}^{*}\,:=\,\left\\{x\left|\begin{array}[]{l}c_{j}^{hom}(x)=0\,(j\in\mathcal{E}),\,c_{j}^{hom}(x)\geq
0\,(j\in\mathcal{I}),\\\ -f_{i}^{hom}(x)\geq
0\,(i\in[m]),\,x^{T}x=1.\end{array}\right.\right\\}.$

It is important to observe that $K^{*}_{0}$ and (7.20) do not depend on
$x^{*}$. If such $\Delta\check{y}$ exists, then (7.1) is unbounded below for
all $x^{*}\in K$, and hence there are no Pareto points. This implies the
following theorem.

######  Theorem 7.7.

Suppose $K(x^{*})$ is closed at infinity for all $x^{*}\in K$. If there is
$\Delta\tilde{y}$ such that (7.20) holds, then (7.1) is unbounded below for
all $x^{*}\in K$ and hence Pareto points do not exist.

Theorem 7.7 only shows nonexistence of Pareto points, but it does not imply
nonexistence of weakly Pareto points. For instance, consider the MOP

$\min\quad(x_{1},x_{2})\quad\mathit{s.t.}\quad x_{1}\geq 0.$

The tms $\Delta\tilde{y}:=[(0,-1)]_{1}$ satisfies (7.20), so there are no
Pareto points. But each $(0,x_{2})$ is a weakly Pareto point. The existence of
$\Delta\tilde{y}$ satisfying (7.20) can be checked by applying Algorithm 4.3
similarly, with the polynomial $g_{1}:=f_{e}^{\mathit{hom}}$ and the set
$K_{0}^{*}$. The properties are summarized in Theorems 4.1 and 4.4.

######  Example 7.8.

Consider the objectives

$\begin{array}[]{rcl}f_{1}&=&x_{1}^{4}+x_{3}^{4}+(x_{1}x_{2})^{2}+(x_{2}x_{3})^{2}+(x_{3}x_{4})^{2}+x_{1}x_{2}x_{3}x_{4},\\\
f_{2}&=&x_{1}^{4}+x_{2}^{4}+x_{3}^{4}+x_{4}^{4}-2x_{2}^{4}-x_{1}^{3}x_{2}-x_{3}^{3}x_{4},\end{array}$

and the constraint $x_{1}x_{2}x_{3}x_{4}\geq 0$. Since $f_{1}(0,t,0,0)=0$ is
the minimum value, the point $(0,t,0,0)$ is a weakly Pareto point for all
$t\in\mathbb{R}$. Since all the polynomials are homogeneous, $K(x^{*})$ is
closed at infinity for all $x^{*}\in K$. By Algorithm 4.3, we get
$\Delta\tilde{y}=1.0023[u]_{4}$ satisfying (7.20), for
$u=(0.0000,-0.9994,0.0000,0.0339)$. Hence, there is no Pareto point.

##  8\. Conclusions and discussions

This paper studies multi-objective optimization given by polynomials. We
characterize the convex geometry for (weakly) Pareto values and give convex
representations for them. For LSPs, we show how to use tight relaxations to
solve them, how to find proper weights, and how to detect nonexistence of
proper weights. For CSPs, we show how to solve them by moment relaxations.
Furthermore, we show how to check if a given point is a (weakly) Pareto point
and how to detect existence or nonexistence of (weakly) Pareto points. To
detect nonexistence of proper weights and (weakly) Pareto points, we also show
how to detect unboundedness of polynomial optimization.

There are some open questions for studying these topics. To detect
nonexistence of (weakly) Pareto points, or to detect nonexistence of proper
weights, we need to check unboundedness of polynomial optimization. This is
discussed in Section 4. A feasible point for the system (4.8) is only a
sufficient condition for unboundedness of the optimization (4.1), but it may
not be necessary.

######  Question 8.1.

When (4.8) is infeasible, what is a computationally convenient certificate for
unboundedness of (4.1)?

Another important question is to detect nonexistence of proper weights. This
is discussed in Subsection 5.3. We have seen that (5.20) is sufficient for the
proper weight set $\mathcal{W}=\emptyset$, but it may not be necessary.

######  Question 8.2.

When (5.20) does not have a feasible point, how can we detect nonexistence of
proper weights?

In Subsections 7.3 and 7.4, we discussed how to detect nonexistence of
(weakly) Pareto points. Under certain conditions, we have shown that (7.14)
implies nonexistence of weakly Pareto points and (7.20) implies nonexistence
of Pareto points. However, they may not be necessary for nonexistence.

######  Question 8.3.

Beyond (7.14) and (7.20), what are computationally convenient certificates for
nonexistence of (weakly) Pareto points?

The above questions are mostly open, to the best of the authors’ knowledge.
They are interesting future work.

## References

  * [1] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi, Online team formation in social networks, in WWW’12, pages 839–848, 2012.
  * [2] T. Bao and B. Mordukhovich, Variational principles for set-valued mappings with applications to multiobjective optimization, Control Cybernet 36(3):531–562, 2007.
  * [3] T. Bao and B. Mordukhovich,  Relative Pareto minimizers for multiobjective problems: existence and optimality conditions. Math. Program., 122(2):301–347, 2010.
  * [4] V. Blanco, J. Puerto and S. Ali, A semidefinite programming approach for solving multiobjective linear programming, J. Global Optim. 58(3):465–480, 2014.
  * [5] B. Chen, Y. Lin, W. Zeng, H. Xu, and D. Zhang, The mean-variance cardinality constrained portfolio optimization problem using a local search-based multi-objective evolutionary algorithm. Applied Intelligence, 47(2):505–525, 2017.
  * [6] J. Cho, Y. Wang, R. Chen, K. Chan and A. Swami, A survey on modeling and optimizing multi-objective systems, IEEE Commun. Surv. Tutor., 19(3):1867–1901, 2017.
  * [7] E. Clayton, W. Weber, and B. Taylor III, A goal programming approach to the optimization of multi response simulation models, IIE Transactions 14(4):282–287, 1982.
  * [8] R. E. Curto and L. A. Fialkow, _Solution of the truncated complex moment problem for flat data_ , Mem. Amer. Math. Soc. vol. 119, AMS, Providence, RI, 1996.
  * [9] R. Curto and L. Fialkow, Truncated K-moment problems in several variables, J. Operator Theory 54(2005), pp. 189-226.
  * [10] Y. Donoso and R. Fabregat, Multi-objective optimization in computer networks using metaheuristics, CRC Press, 2016.
  * [11] M. Emmerich and A. Deutz, A tutorial on multiobjective optimization: fundamentals and evolutionary methods, Nat. Comput. 17(3):585–609, 2018.
  * [12] J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Math. Program. 170(2), 507–539, 2018.
  * [13] P.J. Fleming, Computer aided design of regulators using multiobjective optimization, in Control Applications of Nonlinear Programming and Optimization, pp. 47–52, Elsevier, 1986.
  * [14] M. Geiger and M. Sevaux, The biobjective inventory routing problem–problem solution and decision support, in INOC, pp. 365–378, Springer, 2011.
  * [15] J.W. Helton and J. Nie, Semidefinite representation of convex sets, Math. Program., Series A, Vol. 122, No.1, pp. 21-64, 2010.
  * [16] D. Henrion and J. B. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive polynomials in control, pp. 293–310, Lecture Notes in Control and Inform. Sci., 312, Springer, Berlin, 2005.
  * [17] D. Henrion, J. B. Lasserre and J. Loefberg, GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24(4-5), pp. 761–779, 2009.
  * [18] L. Jiao, J. Lee, Y. Ogata and T. Tanaka, Multi-objective optimization problems with SOS-convex polynomials over an LMI constraint, Taiwanese J. Math., 24(4):1021–1043, 2020.
  * [19] L. Jiao, J. Lee and Y. Zhou, A hybrid approach for finding efficient solutions in vector optimization with SOS-convex polynomials, Operations Research Letters 48(2), pp. 188–194, 2020.
  * [20] L. Jiao and J. Lee, Finding efficient solutions in robust multiple objective optimization with SOS-convex polynomial data, Annals of Operations Research, 296, pp. 803–820, 2021.
  * [21] L. Jiao, J. Lee and N. Sisarat, Multi-objective convex polynomial optimization and semidefinite programming relaxations, J. Global Optim. 80(1), pp. 117–138, 2021.
  * [22] D. Jones and M. Tamiz, Practical goal programming, volume 141. Springer, 2010.
  * [23] D.S. Kim, T. Pham, and N.V. Tuyen, On the existence of Pareto solutions for polynomial vector optimization problems, Math. Program. 177, pp. 321–341, 2019.
  * [24] J. Koski and R. Silvennoinen, Norm methods and partial weighting in multicriterion optimization of structures, Internat. J. Numer. Methods Engrg. 24(6):1101–1121, 1987.
  * [25] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on optimization, 11(3):796–817, 2001.
  * [26] J. B. Lasserre, A semidefinite programming approach to the generalized problem of moments, Math. Program. 112(1):65–92, 2008.
  * [27] J. B. Lasserre, Convexity in semi-algebraic geometry and polynomial optimization, SIAM J. Optim. 19 (2009), pp. 1995–2014.
  * [28] J. B. Lasserre, An introduction to polynomial and semi-algebraic optimization, Cambridge University Press, 2015.
  * [29] J. B. Lasserre, The Moment-SOS Hierarchy, Proceedings of the International Congress of Mathematicians (ICM 2018), Vol 3, B. Sirakov, P. Ney de Souza and M. Viana (Eds.), World Scientific, pp. 3761–3784, 2019.
  * [30] M. Laurent, Revisiting two theorems of curto and fialkow on moment matrices, _Proceedings of the AMS_ , vol. 133, no. 10, pp. 2965–2976, 2005.
  * [31] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging applications of algebraic geometry, pp. 157–270, Springer, 2009.
  * [32] M. Laurent, Optimization over polynomials: Selected topics, Proceedings of the International Congress of Mathematicians, S.Y. Jang, Y.R. Kim, D-W. Lee, & I. Yie (eds.), pp. 843–869, 2014.
  * [33] J. Lee and L. Jiao, Solving fractional multicriteria optimization problems with sum of squares convex polynomial data, Journal of Optimization Theory and Applications 176, pp. 428–455, 2018.
  * [34] D. Liu, R. Hu and Y. Fang, Solvability of a regular polynomial vector optimization problem without convexity, Preprint, 2021, arXiv:2101.03739[math.OC].
  * [35] N. H. A. Mai, J. B. Lasserre and V. Magron, Positivity certificates and polynomial optimization on non-compact semialgebraic sets, Math. Program., to appear, 2021.
  * [36] R. Marler and J. Arora, Survey of multi-objective optimization methods for engineering, Struct. Multidiscip. Optim., 26(6):369–395, 2004.
  * [37] N. Matsatsinis and P. Delias, Agentallocator: An agent-based multi-criteria decision support system for task allocation, in HoloMAS, pp. 225–235, Springer, 2003.
  * [38] K. Miettinen, Nonlinear multiobjective optimization, volume 12, Springer Science & Business Media, 2012.
  * [39] J. Nie, Discriminants and nonnegative polynomials, J. Symbolic Comput., 47(2):167–191, 2012.
  * [40] J. Nie, Certifying convergence of Lasserre’s hierarchy via flat truncation. Math. Program. 142(1-2):485–510, 2013.
  * [41] J. Nie, Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. program. 146(1-2):97–121, 2014.
  * [42] J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program. 153(1):247–274, 2015.
  * [43] J. Nie, The hierarchy of local minimums in polynomial optimization, Math. Program. 151(2), 555–583, 2015.
  * [44] J. Nie, Generating polynomials and symmetric tensor decompositions, Found. Comput. Math. 17 (2), 423–465, 2017.
  * [45] J. Nie, Tight relaxations for polynomial optimization and lagrange multiplier expressions, Math. Program. 178(1-2):1–37, 2019.
  * [46] J. Nie, Z. Yang, and G. Zhou, The saddle point problem of polynomials, Found. Comput. Math., to appear, 2021.
  * [47] J. Nie and K. Ye, Hankel tensor decompositions and ranks, SIAM Journal on Matrix Analysis and Applications 40(2), 486–516, 2019.
  * [48] J. Jahn, Vector Optimization: Theory, Applications, and Extensions, Springer-Verlag, Berlin, 2004.
  * [49] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42(3):969–984, 1993.
  * [50] S. Rosenthal and M. Borschbach, Design perspectives of an evolutionary process for multi-objective molecular optimization, in International Conference on Evolutionary Multi-Criterion Optimization, pp. 529–544, Springer, 2017.
  * [51] P. Ruíz-Canales and A. Rufián-Lizana, A characterization of weakly efficient points, Math. Program. 68(1-3):205–212, 1995.
  * [52] E. Horst, P. Marqués-Gallego, T. Mulder-Krieger, Jacobus van Veldhoven, Johannes Kruisselbrink, Alexander Aleman, Michael TM Emmerich, Johannes Brussee, Andreas Bender, and Adriaan P IJzerman. Multi-objective evolutionary design of adenosine receptor ligands, J. Chem. Inf. Model. 52(7):1713–1721, 2012.
  * [53] P. Wang, M. Emmerich, R. Li, K. Tang, T. Bäck, and X. Yao, Convex hull-based multiobjective genetic programming for maximizing receiver operating characteristic performance, IEEE Transactions on Evolutionary Computation 19(2):188–200, 2014.
  * [54] S. Zionts, Multiple criteria mathematical programming: an updated overview and several approaches, in Mathematical models for decision support pp. 135–167, Springer, 1988.