\documentclass{crorr}
%%%%% journal  info -- DO NOT CHANGE %%%%%%%%%
\setcounter{page}{1}
\renewcommand\thisnumber{1}
\renewcommand\thisyear {2014}
\renewcommand\thismonth{xxx}
\renewcommand\thisvolume{6}

%\usepackage{amsmath,amssymb}

\newcommand{\N}{\mathbb N}
\newcommand{\cP}{\mathcal P}
\newcommand{\cs}{{\mathcal{S}}}
\newcommand{\ck}{{\mathcal{K}}}
\newcommand{\cn}{{\mathcal{N}}}
\newcommand{\cc}{{\mathcal{C}}}
\newcommand{\CP}{{\mathcal{CP}}}
\newcommand{\COP}{{\mathcal{COP}}}

\def\nd{\noindent}
\def\Diag{\mathrm{Diag}}
\def\diag{\mathrm{diag}}

\newcommand{\R}{\mathbb{R}}

\newcommand{\ncSOStools}{{\tt NCSOStools}}
%\newcommand{\ncSOStoolz}{{\tt NCSOStools}}}

\newcommand{\df}[1]{\emph{#1}}
\newcommand{\bO}{\mathbf{0}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bJ}{\mathbf{J}}
\newcommand{\bI}{\mathbf{I}}
\newcommand{\cS}{\mathbb S}

\DeclareMathOperator{\tr}{trace}
\DeclareMathOperator{\convcone}{conv\,cone}
\DeclareMathOperator{\vvec}{\mathrm{vec}}
\DeclareMathOperator{\New}{\mathbf{New}}

\def\ben{\begin{enumerate} }
\def\een{\end{enumerate} }

\def\beq{\begin{equation} }
\def\eeq{\end{equation} }

\newcommand{\dd}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}

\markboth{Janez Povh}{DATA CLUSTERING FOR CIRCLE DETECTION}
\title[From combinatorial optimization to real algebraic geometry and back]{From combinatorial optimization 
to real algebraic geometry and back\thanks{Supported by the Slovenian research agency via program P1-0383 and
project L74119 and by Creative Core FISNM-3330-13-500033 Simulations project funded by the European Union.}}

%\Subjclass[2010]{Primary 90C22, 90C27, 14P10; Secondary 13J30, 15B48}

\author[Janez Povh]{\bf Janez Povh\affil{1}\comma\corrauth}
\address{\affilnum{1}\ Faculty of Information Studies Novo Mesto\\
 Ulica talcev 3, 8000 Novo Mesto, Slovenia\\
 E-mail: $\langle$janez.povh@fis.unm.si$\rangle$}

\usepackage[displaymath,mathlines,pagewise]{lineno}

\begin{document}
\begin{linenumbers}

\begin{abstract}
In this paper, we explain the relations between combinatorial optimization and real algebraic geometry with a special focus to the quadratic assignment problem. We demonstrate how to write a quadratic optimization problem over discrete feasible set as a linear optimization problem over the cone of completely positive matrices. The latter formulation enables a hierarchy of approximations which rely on results from polynomial optimization, a sub-field of real algebraic geometry.
\end{abstract}

\keywords{combinatorial optimization,
copositive programming, semidefinite programming, polynomial optimization, sum of squares, real algebraic geometry}

\maketitle

\section{Introduction}\label{sec:intro}

In combinatorial optimization, the main task is to find an optimum of given the objective function over a
subset of a finite combinatorial set, which is usually the set of all subsets of the given universal set, 
the set of all permutations, combinations, etc. Solving
the most interesting problems usually requires complete enumeration,
i.e., checking all feasible solutions, which might be time-consuming.
A typical approach to overcome the complexity obstacles is to
reformulate the problem in such a way that the cost function becomes
linear and the feasible set becomes some discrete subset of $\R^2$.
The next step usually consists of embedding the feasible set into a
convex subset of $\R^2$ which enables the application of efficient
methods from convex optimization. We may always choose the convex
superset in such a way that it is  an
 intersection of a convex
cone and a linear subspace. If the cone is well-equipped (i.e., we can
find  a self-concordant barrier function for the cone), then the
resulting conic program can be solved to a precision $\varepsilon$ in
polynomially many iterations, where the number of iteration is also a polynomial function of $\log \varepsilon$ \cite{Renegar}. This approach usually gives only lower
or upper bounds for the optimum of the original problem but these bounds
may be used to reduce the initial feasible set significantly or to reduce the branching tree at Branch and Bound
method.

Relaxations, which result in linear programming problems, were
intensively studied in the past decades because  many efficient algorithms
exist for their solution. For several problems, e. g., quadratic $0-1$ problems,
there is no reasonable linear approximation of the feasible set and
if we want to get tight bounds, we have to use
methods from nonlinear programming. These methods are widely
considered much harder to implement and the size of instances that we
can solve by using them is much more limited.

In the last two decades, significant progress has been made in the optimization
over the cone of positive semidefinite matrices. The
results about this topic are gathered under the name
\df{semidefinite programming} (SDP).
Now we share a good understanding of the geometry in SDP
\cite{Klerk, Wolkowicz, Anjos} and have a variety of efficient SDP solvers 
based on the interior point concept
\cite{Klerk, Nartner, Renegar, Wolkowicz} or on other concepts such us
the bundle method  \cite{Helmberg, Fischer} and the Augmented Lagrangian
method \cite{Povh3, Malick}.

Semidefinite programming has attained an important role in
combinatorial optimization. We point out two reasons for that. 
The first is the efficiency of the methods for solving
semidefinite programs. The second reason is the strong evidence that
many semidefinite models are significantly stronger than purely
linear ones, justifying the additional computational costs for their solutions.

Optimization of the linear function over the cone of copositive or
completely positive matrices is called \df{copositive
programming}.\index{copositive programming} Several authors
have recently highlighted the importance of copositive programming in
combinatorial optimization
\cite{Klerk2, Povh, Burer, Eichfelder, Dickinson}. It has been shown
that feasible sets for some hard combinatorial problems (like
the stability number problem, the quadratic assignment problem, the graph
partitioning problem) may be represented as the intersection of a
linear space and the cone of copositive or completely positive
matrices. This does not make the problems tractable since the
separation problem for the copositive cone is NP hard \cite{Dickinson2}, but it opens many new possibilities to
construct approximation schemes for the problems.

When we try to find advanced approximation of copositive programming problems, we naturally meet real algebraic geometry.
This is a very rich field within algebra which mainly studies solution sets of a given finite set of polynomial equalities and inequalities, so-called semi-algebraic sets.
Basic questions studied within this area are if the given semialgebraic set is empty, bounded, connected, etc.
Polynomial optimization is a subfield of real algebraic geometry and it is focused on optimization problems where one wants to find an optimum of a real polynomial $f(\x)$ over the feasible set defined by polynomial inequalities:
\begin{equation}\label{eq:1}
                            f_K^{\inf}  =  \inf\{f(\x)\colon \x\in K\},~~\mbox{where}~~
 K=\{\x\in\R^n\colon g_i(\x)\ge 0~\mbox{for}~i=1,\ldots,k\}.
\end{equation}

Problem \eqref{eq:1} covers all well-known combinatorial problems; hence, it is in general hard to solve. In the last two decades, an approach based on sum-of-squares (SOS) and the dual moment idea became very promising. The SOS approach relies on the fact that if $f$ can be written as $s_0+\sum_i s_ig_i$ where $s_i$  are non-negative on $K$, then $f$ is non-negative on $K$. The largest $\varepsilon$ such that $f-\varepsilon=s_0+\sum_i s_ig_i$ is  a lower bound for the optimum of \eqref{eq:1}. If we consider $s_i$ that are SOS, we obtain SDP approximations for \eqref{eq:1}; if
we consider $s_i$, which are polynomials with a non-negative coefficient (this is sufficient if $K$ is a subset of a non-negative orthant), then we get LP approximations for \eqref{eq:1}.

Results that relate positivity of polynomial functions to
algebraic representations of these functions are known as \emph{Positivstellensatz} \cite{Marshall}. In real algebraic geometry, people also use the term \emph{Nichtnegativestellensatz} for results about algebraic certificates for non-negative polynomials. Some people use these two names only for theorems that are ``if and only if'', see e.g. Scheiderer \cite{Scheiderer}.
In this paper, we call a \emph{Positivstellensatz} any result which provides algebraic certificates for positivity (or non-negativity) for positive polynomials.

As the most famous Positivstellens\"{a}tze we consider the results of  P\'olya~\cite{Po´lya, Hardy}, Schm\"udgen  \cite{Schm¨udgen} and Putinar \cite{Putinar}.
P\'olya proved (see Theorem \ref{thm:polya} below) that if the given real homogeneous polynomial $f$ is positive on $\R_+^n\setminus\{\bO\}$, then multiplying it by $(\sum_i x_i)^r$ , where  $r$ is sufficiently large, gives a polynomial with non-negative coefficients, i.e., a certificate that  the original polynomial is non-negative on $\R_+^n$. There also exists a ``positive'' version of the P\'olya's theorem stating that all coefficients of $(\sum_i x_i)^rf$ are positive for $r$ sufficiently large \cite{Powers}.

Theorems of Schm\"udgen \cite{Schm¨udgen} and Putinar \cite{Putinar} show that (i) if the semialgebraic set $K$ is compact, then $f$ belongs to the preordering generated by $\{g_i\}$ (Schm\"udgen) and (ii) if the quadratic module generated by $\{g_i\}$ is Archimedean, then $f$ belongs to this module (Putinar). For definitions and details about these results we refer the reader to \cite{Laurent}. In both cases, we do not have ``if and only if'', i.e., we only have certificates for non-negativity. For complexity issues related with Schm\"udgen and Putinar Positivstellens\"{a}tze see~\cite{Schweighofer, Nie}, while a comprehensive overview of this type of results can be found in ~\cite{Scheiderer, Marshall}.

The P\'olya's Positivstellensatz therefore implies a non-negativity certificate based on polynomials with non-negative coefficients, while Schm\"udgen's and Putinar's theorems guaranty non-negativity certificates based on polynomials which are SOS.


\subsection{Notation}

We denote the vector
of all ones by $\be_n\in\R^n$ (or $\be$ if the dimension $n$ is obvious).
The square matrix of all ones is $\bJ_n$
(or $\bJ$), the identity matrix is $\bI$.
 When we consider
matrix $A\in\R^{m\times n}$ as a vector from $\R^{mn}$ obtained from $A$ column-wise, we write
this vector as $\vvec(A)$.

In this paper, we consider the following sets of matrices:
 \begin{itemize}
\item the vector space of real symmetric $n\times n$ matrices:
 $\cs_n= \{X\in \R^{n\times n}: X=X^T \}$,
 \item the cone of $n \times n$ symmetric nonnegative matrices:
$\cn_n = \{ X\in \cs_n\colon x_{ij}\geq 0, \forall i,j \}$,
 \item the cone of
$n\times n$ positive semidefinite matrices: $\cs^+_n = \{ X\in
\cs_n\colon y^TXy\geq 0, \forall y \in \R^n \}$.
 \item  the cone of
$n\times n$ copositive matrices: $\COP_n = \{ X \in \cs_n\colon
\x^TX\x\geq 0, \forall \x \in \R^n_+ \}$,
 \item the cone of $n\times n$
completely positive matrices:
$\CP_{n}= \mbox{conv}\{ \x\x^{T}: \x \in
\R^{n}_{+} \},$ where $\mbox{conv}(A)$ stands for the convex hull of $A$.
\end{itemize}

We also use $X\succeq 0$ for $X\in\cs_n^+$ and $X\ge 0$ for $X \in\cn$. Linear optimization problem over $\cn_n$ is a linear programming problem, while a linear optimization problem over $\cs_n^+$ is called a
semidefinite programming problem. Linear optimization problem over the cone of copositive or completely positive matrices is a copositive programming problem.

The sign $\otimes$ stands for the Kronecker product.  If $a\in\R^n$, then $\mbox{Diag}(a)$ is an $n\times n$
diagonal matrix with $a$ on the main diagonal and $\diag(X)$ is a vector containing the
main diagonal of a square matrix $X$.

For a matrix  $Z\in  \cs_{k^2}$, with $k\ge 1$, we often use the
following block  notation:
\begin{equation}\label{eq:A_block_pq}
Z = \left[
\begin{array}{ccc}
Z^{11} & \cdots &Z^{1k}\\
\vdots&\ddots & \vdots\\
Z^{k1}& \cdots & Z^{kk}
\end{array}
\right],
\end{equation}
\nd where $Z^{ij}\in\R^{k\times k}$.

When $P$ or $P_{subscript}$ is the name of the optimization problem, then $OPT_P$ and $OPT_{subscript}$, respectively, denote
their optimal values.

If $f\in\R[\x]$ is a polynomial with real coefficients, we say that $f$ is a sum of squares (SOS) if there exist polynomials $s_i\in\R[\x]$ such that $f(\x)=\sum_is_i^2(\x)$.


\subsection{Contribution}
In this paper, we
\begin{itemize}
\item clearly explain how combinatorial optimization naturally meets with real algebraic geometry via copositive programming;
\item list the results from real algebraic geometry that have straightforward implications for combinatorial optimization;
\item demonstrate contributions to approximate solving of the combinatorial optimization problem \ref{eq:qap1} by results from real algebraic geometry.
\end{itemize}


\section{Combinatorial optimization}
Following \cite{Schrijver}, one of the first combinatorial optimization problems studied is an assignment problem. It was studied as a continuous optimization problem under the name \emph{transportation problem} as early as in 1784 by G. Monge \cite{Schrijver}.
The original version, now known as a linear assignment problem \ref{eq:lap}, asks how to assign e.g. workers to tasks such that the total time (or cost) for all tasks is minimum.
Suppose we have $n$ workers and $n$ tasks and we construct a  matrix $C\in\R^{n\times n}$ such that $c_{ij}$ is the cost of doing task $j$ by worker $i$.
With this notation the \ref{eq:lap} can be written as
\begin{equation}\label{eq:lap}
\tag*{(LAP)}
OPT_{LAP}=\min\{\sum_{i,j}c_{i,\varphi(i)}\colon \varphi~\mbox{a parmutation}\}.
\end{equation}

We can describe each permutation $\varphi$ of order $n$ by $0-1$ matrix $X^{\varphi}$ of order $n$ (we call such matrix a \emph{permutation matrix}):
\begin{equation*}
X^{\varphi}_{ij}= 1 \iff \varphi(i)=j.
\end{equation*}
Every permutation matrix is a $0-1$ matrix which has in each row and column exactly one non-zero (equal to 1). Therefore, \ref{eq:lap} can be rewritten as
\begin{equation*}
OPT_{LAP}=\min\{\tr(C^TX)\colon X~\mbox{a parmutation matrix}\}.
\end{equation*}

Note that the set of all permutation matrices $\Pi$ can be described in different ways:

\begin{eqnarray*}
\Pi & = &\{X\colon X_{ij}\in\{0,1\}, X\be = X^T\be = \be\} \\
& = & \{X\colon X\ge 0,~X^TX=\bI\}.
\end{eqnarray*}

Indeed, if the row and column sums of a $0-1$ matrix are equal to 1, then in every row and column there must be exactly one nonzero (equal to 1). This explains the first representation.
For the second representation, note that if $X\ge 0$ has orthogonal columns and rows, this means that in every row and column there is at most one nonzero (positive) element. It must be equal to 1 since the (Euclidean) norm of each row and column must be 1.

Using the first representation of permutation matrices we can formulate \ref{eq:lap} as follows:

\begin{equation}\label{eq:lap1}
\tag*{(LAP')}
OPT_{LAP}=\min\{\langle C,X\rangle\colon X_{ij}\in\{0,1\}, X\be = X^T\be = \be \},
\end{equation}

\nd where $\langle\cdot,\cdot\rangle$ stands for the standard inner product, i.e.,
$\langle X,\, Y\rangle = \tr(X^TY)$ for $X,Y\in\R^{m\times n}$.

We can solve the \ref{eq:lap} very efficiently (theoretically and practically) by using several optimization methods. The most efficient ones are so-called primal-dual methods. They are based on the fact that replacing the $0-1$ constraint  in the \ref{eq:lap1} by $X\ge 0$ does not change the optimal solution of the \ref{eq:lap}, since the convex set spanned by all permutation matrices is exactly the convex hull of a feasible set from the \ref{eq:lap1} after the replacement.

The most famous primal-dual method to solve the \ref{eq:lap} is the Hungarian method, which was introduced in 1955 by Harold Kuhn \cite{Kuhn} and at that time it was the first method with known polynomial complexity to solve the \ref{eq:lap}. Kuhn named the method after two Hungarian mathematicians Egerv\'ary and K\"{o}nig, whose results he used to construct the method.
Currently, the Shortest augmenting path method is considered the most efficient method to solve the \ref{eq:lap}.
We can also solve the \ref{eq:lap} by using any method for solving linear programming since the \ref{eq:lap1} becomes a linear programming problem if we replace $X_{ij}\in\{0,1\}$  by $X_{ij}\ge0$. See also \cite{Povh4}.

The quadratic assignment problem \ref{eq:qap1} is a generalization of the linear assignment problem.
It was introduced to model location problems which take into account the costs of placing new facilities on certain places and the interaction between all facilities.
It became a standard problem in
location theory and is very famous because of its hardness. Koopmans
and Beckmann \cite{Koopmans} introduced it in 1957 in the following
form:

\begin{equation}\label{eq:qap1}
\tag*{(QAP)}
   OPT_{QAP}~=~\min \ \{ \sum_{i,j}a_{ij}b_{\pi(i)\pi(j)}+
\sum_{i}c_{i,\pi(i)}\colon
\pi~\mbox{a~permutation}\},
\end{equation}

\nd where $A,B,C$ are $n\times n$ matrices. We assume (this is a standard
assumption) that $A$ and $B$ are symmetric.
Using a similar approach as above (we use the second representation for permutation matrices), we can rewrite
\begin{equation}\label{eq:qap2}
\tag*{(QAP')}
   OPT_{QAP}~=~\min \ \{ \langle X,\,AXB+C\rangle\colon  X\ge 0,~X^TX=\bI\}.
\end{equation}

The \ref{eq:qap1} is known to be very hard from a theoretical and practical point
of view.
 Problems of size $n\ge 25$ are currently still considered as difficult.
Sahni and Gonzales \cite{Sahni} showed that even finding an
$\varepsilon$-approximate solution for the \ref{eq:qap1} is NP-hard. Solving the \ref{eq:qap1} in
practice is usually based on the Branch and Bound (B$\&$B) algorithm.
The performance of B$\&$B algorithms depends on the computational
quality and efficiency of  lower bounds (see \cite{Anstreicher} for a
summary of recent advances in the solution of the \ref{eq:qap1} by the B$\&$B). The
study of lower bounds for the \ref{eq:qap1} is therefore very important for the
development of B$\&$B algorithms.
We propose the following surveys about the \ref{eq:qap1}
\cite{Cela, Rendl, Loiola}.

The most recent and promising trends of research for the bounding
methods for the \ref{eq:qap1} are based on semidefinite programming.
 Zhao et al., Sotirov and Rendl \cite{Rendl2, Zhao} lifted the problem from
the vector space $\R^{n\times n}$ to the cone of positive semidefinite matrices of order $n^2+1$ and formulated
several semidefinite relaxations  which give increasingly tight lower bounds for the \ref{eq:qap1}. They
used interior point methods \cite{Zhao} and the bundle method
\cite{Rendl3} to solve these programs. The computational results show that
these lower bounds are among the strongest known but  also the most
expensive to compute (state-of-the-art computers could compute the strongest of these  bounds  only for $n\le 35$).

Recently De Klerk and Sotirov \cite{Klerk3} exploited the symmetries in some special instances of the \ref{eq:qap1} and solve these instances for a size up to 128.

A new direction in solving the \ref{eq:qap1} started when it was shown that the \ref{eq:qap1} can be formulated as a linear programming problem over the cone of copositive or completely positive matrices.
 More precisely, starting with the \ref{eq:qap2}, where few initially redundant constraints were added
\begin{equation}\label{eq:qap3}
\tag*{(QAP'')}
   OPT_{QAP}~=~\min \ \{ \langle X,\,AXB+C\rangle\colon  X\ge 0,~X^TX=XX^T=\bI,~\langle X,\bJ X\bJ\rangle=n^2\}
\end{equation}
Povh and Rendl showed that the Lagrangian dual of the \ref{eq:qap3} is a copositive programming problem with a zero duality gap.
The conic dual of this Lagrangian dual has the following formulation

\begin{equation}\label{eq:qap4}
\tag*{($QAP_{\CP}$)}
\begin{array}{llrcl}
 &\min & \multicolumn{3}{c}{\langle B\otimes A+\Diag(c),Y \rangle}  \\
&\mathrm{s.\ t.} &   \sum_iY^{ii} & = & \bI, \\
&&  \langle \bI,\,Y^{ij}\rangle & = &\delta_{ij},\ \forall i,j,\\
& \multicolumn{2}{r}{\langle \bJ_{n^2},\,Y\rangle} &  = &n^2,\\
&  \multicolumn{2}{r}{Y} &\in & \CP_{n^2},
\end{array}
\end{equation}
where $c=\vvec(C)$.

In this formulation, we introduced the cone of completely positive matrices $\CP$.
Its dual is the cone of copositive matrices. Both cones are defined in the Introduction.
Formulation \ref{eq:qap4} means that the \ref{eq:qap1} can be restated as a linear programming problem over the cone of completely positive matrices. We call such a problem a copositive program (we use the same name for a linear programming problem over $\COP$).

The copositive programming formulation \ref{eq:qap4} together with the copositive formulation of the \emph{stability number problem} \cite{Klerk2} inspired several generalizations.
Burer \cite{Burer} proved that every quadratic optimization problem over the non-negativity orthant with linear and binary constraints can be formulated as a copositive program.
Dickinson et al.  \cite{Dickinson} generalized this result to hold for every quadratic  optimization problem over the closed set subject to linear and binary constraints if this closed  set satisfies some technical assumption (like being bounded or being  convex).

Although the strong membership problem for the cones $\CP$ and $\COP$ is NP-hard \cite{Dickinson2}, the reformulation \ref{eq:qap4} is important since any reasonable an approximation for the cone $\CP$ yields approximation for $OPT_{QAP}$.

The definition of $\COP$ is strongly related to positivity of certain real polynomials, hence we can use the real algebraic tools to get approximations for $\CP$ and $\COP$.

\section{Real algebraic geometry}

Checking whether the given real symmetric matrix $A$ is copositive is directly linked to a question if the corresponding polynomial $f_A(\x)=\sum_{i,j}a_{ij}x_ix_j$ has a non-negative infimum the on non-negative orthant. The question can be restated as a constrained or an unconstrained optimization problem:
\begin{equation}\label{eq:2}
A\in\COP \iff \inf_{\x\in\R_+^n} \sum_{i,j}a_{ij}x_ix_j\ge 0\iff \inf_{\z\in\R^n} \sum_{i,j}a_{ij}z_i^2z_j^2\ge 0.
\end{equation}
Indeed, if $A$ is copositive, then $\sum_{i,j}a_{ij}x_ix_j$ is non-negative on the non-negative orthant, hence   $\inf_{\z\in\R^n} \sum_{i,j}a_{ij}z_i^2z_j^2\ge 0$.
To see the reverse direction, we use the trivial fact that every $\x\ge 0$ can be represented by  $x_i=z_i^2$ for some $\z\in\R^n$.

Any sufficient and tractable condition that guaranties a non-negative infimum of the constrained or unconstrained  problem in \eqref{eq:2} can lead to an efficient inner approximation of $\COP$. Similarly, necessary conditions yield outer approximations of $\COP$.

One of the very first results from real algebraic geometry yielding sufficient conditions for copositivity (now regarded as Positivstellensatz) is due to P\'olya.
\begin{theorem}(P\'olya, 1929, Hardy, Littlewood, P\'olya, 1988)\label{thm:polya}
Let $f\in\R[\x]$ be a homogeneous polynomial on $\R^n$ such that $f(\x)>0$ for all $\x\in\R_+^n\setminus\{\bO\}$. Then for some $r\in\N$, we have that all coefficients of $(\be^T\x)^rf(\x)$ are non-negative.
\end{theorem}

Powers and Reznick \cite{Powers} proved a stronger result. If $r$ is larger than a certain number which depends only on the degree of $f$ and its minimum  on the standard simplex, then all coefficients of $(\be^T\x)^rf(\x)$ are positive, hence the P\'{o}lya's theorem is actually ``if and only if''.

This theorem motivated Parrilo \cite{Parrilo, Parrilo2} to introduce the following hierarchy of inner approximations for $\COP$:
\begin{equation}\label{eq:3}
\cc^0\subset \cc^1\subset \cdots\subset \COP,
\end{equation}
where $\cc^r$ is defined as follows
\begin{equation*}\label{eq:4}
\cc^r=\{A\in\cS_n\colon (\sum_i x_i^2)^r(\sum_{i,j}a_{ij}x_i^2x_j^2)~\mbox{has non-negative coefficients}\}.
\end{equation*}

Another well-known Positivstellensatz is the following theorem from Reznick.
\begin{theorem}\cite{Reznick2}\label{thm:reznick}
Let $f\in\R[\x]$ be a homogeneous polynomial of even degree on $\R^n$ such that $f(\x)>0$ for all $\x\in\R^n\setminus\{\bO\}$. Then for some $r\in\N_+$, we have that $(\x^T \x)^rf(\x)$ is SOS.
\end{theorem}

Faybusovich \cite[Theorem 1]{Faybusovich} provided an explicit bound for the exponent $r$ in the theorem above.
This theorem probably motivated  Parrilo \cite{Parrilo} to also introduce the following hierarchy
\begin{equation}\label{eq:5}
\ck^0\subset \ck^1\subset \cdots\subset \COP,
\end{equation}
where $\ck^r$ is defined as follows
\begin{equation*}\label{eq:6}
\ck^r=\{A\in\cS_n\colon (\sum_i x_i^2)^r(\sum_{i,j}a_{ij}x_i^2x_j^2)~\mbox{is SOS}\}.
\end{equation*}

The dual cones $\ck^{r*}$ form a decreasing hierarchy approximating $\CP$ from the outside.

Hierarchies \eqref{eq:3} and \eqref{eq:5} are important because separation problems over the cones in these hierarchies can be done with linear and semidefinite programming, respectively.
Indeed, the cone $\cc^0$ is the set of symmetric matrices which are non-negative component-wise.
Similarly, the cone $\ck^0$ consists of symmetric matrices which are the sum of a non-negative and a positive semidefinite matrix, while $\ck^{0*}$ contains exactly the matrices which are positive semidefinite and non-negative \cite{Parrilo, Klerk2}.
For higher members in the hierarchies above, we again obtain descriptions which rely on positive semidefinitness and component-wise non-negativity.
Note that if we consider matrices of order $\le 4$, then $\ck^0=\COP$ \cite{Diananda}.

Several results about certificates for non-negativity of polynomials over feasible sets defined by polynomial equalities and inequalities (like $K$ from \eqref{eq:1}) have been published in last two decades.
We mention the famous Positivstellensatz from Putinar and Vasilescu.
\begin{theorem}\cite[Theorem 1]{Putinar}\label{Thm:PosPV}
Let $m\in\N,~m\ge 1$ and $f_0,\ldots,f_m\in\R[\x]$ be homogeneous polynomials of even degree on $\R^n$ such that $f_0(\x)>0$ for all non-zero $\x\in\{\x\colon f_1(\x)= 1,~f_i(\x)\ge 0~\forall i\ge 1  \}$.
Then for some $r\in\N$, there exist homogeneous SOS polynomials $g_1,\ldots,g_m\in\R[\x]$ such that
$(\x^T\x)^r f_0(\x) = \sum_{i=1}^m f_i(\x)g_i(\x).$
\end{theorem}

This result was recently extended by Dickinson and Povh \cite{Dickinson4}.
\begin{theorem}
Let $m\in\N,~m\ge 1$ and $f_0,\ldots,f_m\in\R[\x]$ be homogeneous polynomials on $\R^n$ such that $f_0(\x)>0$ for all non-zero $\x\in\{\x\colon \x\ge 0,~  f_1(\x)= 1,~f_i(\x)\ge 0~\forall i\ge 1\}$.  Then for some $r\in\N$, there exist homogeneous polynomials $g_1,\ldots,g_m\in\R[\x]$ such that all of their coefficients are non-negative and $(\be^T\x)^r f_0(\x) = \sum_{i=1}^m f_i(\x)g_i(\x)$.
\end{theorem}

Dickinson and Povh proved in \cite{Dickinson3} that this Positivstellensatz implies in a natural way linear and semidefinite programming bounds for \ref{eq:qap1} which are comparable to the strongest bounds from the literature.

\section{Sum of squares and semidefinite programming}\label{sec:approx}
We can check whether polynomial $f\in\R[\x]$ of degree  $2d$ is SOS by semidefinite programming. Indeed, $f$ is SOS if and only if there exists a $Q\succeq 0$ such that
$f(\x)=V_d^TQV_d,$
where  $V_d$ is the vector of all monomials of degree $\le d$. Checking if $f$ is SOS is therefore a semidefinite programming feasibility problem. We can use objective function $\tr\,(Q)$ as a heuristic for rank minimization of $Q$. If in $V_d$ we include all monomials up to degree $d$, then
$V_d$ is of length  ${n+d}\choose d$.
We can find examples where we indeed need all these monomials. If $n=4$ and $d=10$, we obtain ${n+d \choose d}=1001$, hence the resulting SDPs are already on the boundary of the set of instances, solvable by interior point methods.

Nevertheless, very often, especially if the polynomial is sparse (has only few monomials), it is possible to considerably decrease the number of monomials in $V_d$. We can use a result, first  formulated in \cite{Reznick}, that characterizes the monomials that
can appear in a sum of squares representation. Define the  Newton polytope $\New_p$
 of a given polynomial $p$ of degree $2d$ as the integer lattice points in the convex hull of the degrees $\alpha$, which appear in $p$. Then, it can be shown that the only monomials $x^\beta$
that can appear in a sum of squares representation are those such that $2\beta$ is  in the
$\New_p$ (or equivalently $\beta \in \frac{1}{2}\New_p$). The package SOStools, Yalmip and some other packages for SOS decompositions
are essentially based on the Newton polytope algorithm.

Finding a certificate that follows from Putinar Vasilescu Positivstellensatz (Theorem \ref{Thm:PosPV}) can be done again by SDP, but here we are looking for $m$ positive semidefinite matrices that will yield polynomials $g_i$. Since the bounds for these polynomials (and therefore the sizes of SDP matrices) are not determined in advance, we typically put a uniform bound (i.e., we demand that the degree of $f_ig_i$ must be equal to degree $2s$). This yields a hierarchy of lower bounds for the infimum of $f_0$ over the given semialgebraic set via
\begin{eqnarray*}
OPT_{f_0}&=&\inf\{f_0(\x)\colon f_1(\x)= 1,~f_i(\x)\ge 0~\forall i\ge 1  \}\\
&\ge &\varepsilon_s~=~  \sup\{\varepsilon\colon f_0-\varepsilon = \sum_{i=1}^m s_if_i,~\deg(s_if_i)=2s,~s_i~\mbox{are SOS}\}.
\end{eqnarray*}

Computing $\varepsilon_s$ is therefore an SDP in $m$ SDP variables. When $s$ increases, the bounds $\varepsilon_s$ are getting tighter and tighter.
In some cases (e.g., when the semialgebraic set is compact), these bounds converge to $OPT_{f_0}$ \cite{Lasserre}.

\section{Approximating combinatorial optimization problems}
%\label{sec:approx}

In this section, we show how to use results from the previous section to obtain tractable relaxations for \ref{eq:qap1}.
The starting point is a formulation \ref{eq:qap4}.
A simple relaxation is obtained by changing
$ Y \in \CP_{n^2}$ to the weaker condition $Y \in\ck^{0*}_{n^2}$.

We obtain the model:
\begin{equation}\label{eq:qap5}
\tag*{($QAP_{\mathcal{K}_n^{0*}}$)}
\begin{array}{llrcl}
 &\min & \multicolumn{3}{c}{\langle B\otimes A+\Diag(c),Y \rangle}  \\
&\mathrm{s.\ t.} &   \sum_iY^{ii} & = & \bI, \\
&&  \langle \bI,\,Y^{ij}\rangle & = &\delta_{ij},\ \forall i,j,\\
& \multicolumn{2}{r}{\langle \bJ_{n^2},\,Y\rangle} &  = &n^2,\\
& \multicolumn{2}{r}{Y} &\in & \mathcal{N}_{n^2}\cap\cs_{n^2}^+,\\
\end{array}
\end{equation}
\nd \nd We have to emphasize that this is already a computationally expensive model
since the constraint $Y \in  \mathcal{N}_{n^2}$ implies $O(n^4)$
linear inequalities, but yields a very strong lower bound for the optimal value of \ref{eq:qap1}.
In fact, \ref{eq:qap5} is equivalent to the strongest approximation models from the literature, see \cite[Theorem 8]{Povh2}.

Trading quality of the relaxation for more computational efficiency,
we can follow the approach from Zhao et al. \cite{Zhao}, and observe the
following zero pattern for matrices feasible for
$QAP_{\mathcal{K}_n^{0*}}$:
$$
Y^{ii}_{jk} = 0 ,~~ Y^{jk}_{ii} = 0 ~~~\forall j\not= k, \forall i.
$$
Collecting all these $O(n^3)$ equations symbolically in the map
$\mathcal{G}(Y)=0$, we can consider a weaker but also a simpler relaxation:
\begin{equation}\label{eq:qap6}
\tag*{($QAP_{ZKRW1}$)}
\begin{array}{llrclrcl}
               & \min & \multicolumn{6}{l}{\langle B\otimes A+\Diag(c),Y
               \rangle}
               \qquad \\
               &\mathrm{s.\ t.} &   \sum_iY^{ii}_{jj} & = & 1,
& \langle \bI,\, Y^{jj}\rangle & = &1,\ \forall j,\\
& & \langle \bJ_{n^2},\,Y\rangle & = & n^2, & \mathcal{G}(Y) & = & 0\\
&& Y &\in & \cs_{n^2}^+
\end{array}
\end{equation}

We use the
acronym ZKRW1 to emphasize that this model is inspired by Zhao et
al.\ \cite{Zhao}. In \cite{Povh2}, it was shown
that this model is in fact equivalent to the 'gangster-model' from
\cite{Zhao}, see \cite[Theorem 7]{Povh2}.

The relaxation \ref{eq:qap6} has 'only' $O(n^3)$ constraints, but solving it is
still a computational challenge. More details about this can be found in \cite{Povh2}.


\section{Conclusions}

In this paper, we demonstrated that combinatorial optimization naturally poses optimization problems that are very hard to solve and therefore need an input from other area of mathematics. Via so-called Positivstellens\"atze, real algebraic geometry contributes to a hierarchical approach, i.e., a hierarchy of easier problems whose optimal solutions converge under some condition to the optimal solution of the original hard problem. These easier problems are typically linear or semidefinite programming problems which can be solved to optimality (at least $\varepsilon$ optimality) efficiently in theory and in practice. However, the size of these simpler problems grows very fast so in practice we are able to use only the members from the beginning of the hierarchy.


\subsection*{Acknowledgments}

The author thanks Kristijan Cafuta for fruitful discussions and help in coding the Matlab package \ncSOStools.

\appendix

\linespread{1.13}
\bibliographystyle{alpha}
\begin{thebibliography}{99}
\bibitem{Anjos}
Anjos, M.F. and Lasserre, J.B. (2012). Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms,
Software and Applications. Volume 166 of International Series in Operational Research and Management Science.
Springer.
\bibitem{Anstreicher}
Anstreicher, K.M. (2003). Recent advances in the solution of quadratic assignment problems. Mathematical Programming,
97(1-2):27--42.
\bibitem{Burer}
Burer, S. (2009). On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical
Programming, 120(2):479--495.
\bibitem{Cela}
Cela, E. (1998). The quadratic assignment problem. Springer.
\bibitem{Dickinson}
Dickinson, P.J.C., Eichfelder, G. and Povh, J. (2013). Erratum to: On the set-semidefinite representation of
nonconvex quadratic programs over arbitrary feasible sets. Optim. Lett., 7(6):1387--1397.
\bibitem{Dickinson2}
Dickinson, P.J.C. and Gijben, L. (2014). On the computational complexity of membership problems for the completely
positive cone and its dual. Computational Optimization and Applications, 57(2):403--415.
\bibitem{Diananda}
Diananda, P.H. (1962). On non-negative forms in real variables some or all of which are non-negative. In
Mathematical Proceedings of the Cambridge Philosophical Society, Volume 58, 17--25. Cambridge Univ. Press.
\bibitem{Klerk}
Klerk, E. de (2002). Aspects of semidefinite programming, Volume 65 of Applied Optimization. Kluwer Academic Publishers,
Dordrecht,  Interior point algorithms and selected applications.
\bibitem{Klerk2}
Klerk, E. de and Pasechnik, D.V. (2002). Approximation of the stability number of a graph via copositive programming.
SIAM Journal on Optimization, 12(4):875--892.
\bibitem{Klerk3}
Klerk, E. de and Sotirov, R. (2010). Exploiting group symmetry in semidefinite programming relaxations of the
quadratic assignment problem. Mathematical Programming, 122(2):225--246.
\bibitem{Dickinson3}
Dickinson, P.J.C. and Povh, J. (2014). Approximation of the quadratic assignment problem by new polynomial approximation
hierarchy. Submitted.
\bibitem{Dickinson4}
Dickinson, P.J.C. and Povh, J. (2014). On an extension of p´olyas positivstellensatz. Journal of Global Optimization, 1--11.
\bibitem{Eichfelder}
Eichfelder, G. and Povh, J. (2013). On the set-semidefinite representation of nonconvex quadratic programs over
arbitrary feasible sets. Optim. Lett., 7(6):1373--1386.
\bibitem{Faybusovich}
Faybusovich, L. (2004). Global optimization of homogeneous polynomials on the simplex and on the sphere. In Frontiers in
global optimization, Volume 74 of Nonconvex Optim. Appl., 109--121. Kluwer Acad. Publ., Boston, MA.
\bibitem{Fischer}
Fischer, I., Gruber, G., Rendl, F. and Sotirov, R. (2006). Computational experience with a bundle approach for
semidefinite cutting plane relaxations of Max-Cut and equipartition. Math. Program., 105(2-3, Ser. B):451--469.
\bibitem{Nartner}
Nartner, B.G. and Matou, Ji.r L. (2012). sek. Approximation Algorithms and Semidefinite Programming. Springer.
\bibitem{Helmberg}
Helmberg, C. (2000). Semidefinite programming for combinatorial optimization. Konrad-Zuse-Zentrum f\"{ur} Informationstechnik
Berlin.
\bibitem{Hardy}
Hardy, G.H., Littlewood, J.E. and P´olya, G. (1988). Inequalities. Cambridge University Press, 2nd edition.
\bibitem{Koopmans}
Koopmans, T.C. and Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica,
25:53--76.
\bibitem{Kuhn}
Kuhn, W.H. (1955). The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83--97.
\bibitem{Lasserre}
Lasserre. (2000/01). Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796--817.
\bibitem{Laurent}
Laurent, M. (2009). Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of
algebraic geometry, Volume 149 of IMA Vol. Math. Appl., 157--270. Springer, New York.
\bibitem{Loiola}
Loiola, E.M., Abreu, N.M.M. de, Boaventura-Netto, P.O., Hahn, P. and Querido, T. (2007). A
survey for the quadratic assignment problem. European Journal of Operational Research, 176(2):657--690.
\bibitem{Marshall}
Marshall, M. and Netzer, T. (2012). Positivstellens¨atze for real function algebras. Math. Z., 270(3-4):889--901.
\bibitem{Malick}
Malick, J., Povh, J., Rendl, F. and Wiegele, A. (2009). Regularization methods for semidefinite programming.
SIAM J. Optim., 20(1):336--356.
\bibitem{Nie}
Nie, J. and Schweighofer, M. (2007). On the complexity of Putinar’s Positivstellensatz. J. Complexity, 23(1):135--150.
\bibitem{Parrilo}
Parrilo, P.A. (2000). Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization.
PhD thesis, California Institute of Technology.
\bibitem{Parrilo2}
Parrilo, P.A. (2003). Semidefinite programming relaxations for semialgebraic problems. Math. Program., 96(2, Ser. B):293--320.
\bibitem{Po´lya}
Po´lya, G. (1974). \"{U}ber positive Darstellung von Polynomen vierteljschr. In Naturforsch. Ges. Zu¨rich, 73: 141--145, 1928, In: R.P. Boas (Ed.), Collected Papers, Volume 2, pages 309--313. MIT Press, Cambridge.
\bibitem{Povh4}
Povh, J. (2008). Assignment problems in logistics. Logistics \& Sustainable Transport, 1(3).
\bibitem{Powers}
Powers, V. and Reznick, B. (2001). A new bound for P´olya’s theorem with applications to polynomials positive on
polyhedra. J. Pure Appl. Algebra, 164(1-2):221--229. Effective methods in algebraic geometry (Bath, 2000).
\bibitem{Povh}
Povh, J. and Rendl, F. (2007). A copositive programming approach to graph partitioning. SIAM J. Optim., 18(1):223--241
(electronic).
\bibitem{Povh2}
Povh, J. and Rendl, F. (2009). Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete
Optim., 6(3):231--241.
\bibitem{Povh3}
Povh, J., Rendl, F. and Wiegele, A. (2006). A boundary point method to solve semidefinite programs. Computing,
78:277--286.
\bibitem{Putinar}
Putinar, M. (1993). Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J., 42(3):969--984.
\bibitem{Putinar2}
Putinar, M. and Vasilescu, F. (1999). Positive polynomials on semi-algebraic sets. Comptes Rendus de l’Acad´emie
des Sciences - Series I - Mathematics, 328(7).
\bibitem{Renegar}
Renegar, J. (2001). A mathematical view of interior-point methods in convex optimization. MPS/SIAM Series on Optimization.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS),
Philadelphia, PA.
\bibitem{Rendl}
Rendl, F. (2002). The quadratic assignment problem. Facility location: applications and theory. Springer, Berlin,
439--457.
\bibitem{Reznick}
Reznick, B. (1978). Extremal PSD forms with few terms. Duke Math. J., 45(2):363--374.
\bibitem{Reznick2}
Reznick, B. (1995). Uniform denominators in Hilbert’s seventeenth problem. Math. Z., 220(1):75--97.
\bibitem{Rendl2}
Rendl, F. and Sotirov, R. (2007). Bounds for the quadratic assignment problem using the bundle method. Mathematical
Programming, 109(2-3):505--524.
\bibitem{Rendl3}
Rendl, F. and Sotirov, R. (2007). Bounds for the quadratic assignment problem using the bundle method. Math. Program.,
109(2-3, Ser. B):505--524.
\bibitem{Schm¨udgen}
Schm¨udgen, K. (1991). The K-moment problem for compact semi-algebraic sets. Math. Ann., 289(2):203--206.
\bibitem{Schweighofer}
Schweighofer, M. (2004). On the complexity of Schm¨udgen’s positivstellensatz. J. Complexity, 20(4):529--543.
\bibitem{Schrijver}
Schrijver, A. (2005). On the history of combinatorial optimization (till 1960). Handbooks in Operations Research and
Management Science: Discrete Optimization, 12:1.
\bibitem{Scheiderer}
Scheiderer, C. (2009). Positivity and sums of squares: a guide to recent results. In Emerging applications of algebraic
geometry, Volume 149 of IMA Vol. Math. Appl., 271--324. Springer, New York.
\bibitem{Sahni}
Sahni, S. and Gonzalez, T. (1976). P-complete approximation problems. Journal of the ACM (JACM), 23(3):555--565.
\bibitem{Wolkowicz}
Wolkowicz, H., Saigal, R. and Vandenberghe, L. (Eds.) (2000). Handbook of semidefinite programming. International
Series in Operations Research \& Management Science, 27. Kluwer Academic Publishers, Boston, MA.
Theory, algorithms, and applications.
\bibitem{Zhao}
Zhao, Q., Karisch, S.E., Rendl, F. and Wolkowicz, H. (1998). Semidefinite programming relaxations for the quadratic
assignment problem. Journal of Combinatorial Optimization, 2(1):71--109.
\end{thebibliography}
\end{linenumbers}
\end{document}