\documentstyle[11pt]{article}
\newtheorem{defi}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{rem}{Remark}[section] 
\newtheorem{conj}{Conjecture}[section]
\newtheorem{alg}{Algorithm}[section]
\newtheorem{ex}{Exercise}[section]
\newcounter{count}
\newcommand{\p}{{\cal P}}
\newcommand{\q}{{\cal Q}}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\kmat}{{\rm mat\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\conv}{{\rm conv\,}}
\newcommand{\rint}{{\rm rint\,}}
\renewcommand{\theequation}{\thesection.\thecount}
\newcommand{\beq}{\addtocounter{count}{1} \begin{equation}}
\newcommand{\beqr}{\addtocounter{count}{1} \begin{eqnarray}}
\newcommand{\addc}{\addtocounter{count}{1} }
\newcommand{\bs}{\setcounter{count}{0} \section}
\newcommand{\bpr}{{\bf Proof.} \hspace{1 em}}
\newcommand{\epr}{\\ \hspace*{4.5in}  $\Box$}
\begin{document}
\bibliographystyle{plain}
\title{PRIMAL-DUAL INTERIOR POINT METHOD FOR ORTHOGONAL CONSTRAINED 
MATRIX PROBLEMS -- {\bf There is a duality gap !!!}}
\author{Stefan E. Karisch
\thanks{Technische Universitat Graz, Institut fur
Mathematik,
Kopernikusgassa 24, A-8010 Graz, Austria}
\and Franz Rendl
\thanks{Technische Universitat Graz, Institut fur Mathematik,
Kopernikusgassa 24, A-8010 Graz, Austria}
\and Henry Wolkowicz
\thanks{University of Waterloo, Department of
Combinatorics and Optimization, Faculty of Mathematics,
Waterloo, Ontario, N2L 3G1 Canada}
}
 %\today %\date{May 1993}
\date{}
\begin{titlepage}
\maketitle
\thispagestyle{empty}
\begin{center}
\today
\end{center}
%\begin{abstract}
%\end{abstract}

        \vspace{2ex}
        \noindent{\em Key words:
Combinatorial optimization, quadratic assignment problem,
trust regions,  optimality conditions, algorithms}
       \vspace{2ex}

        \noindent{\em AMS 1991 Subject Classification:
Primary 90B80, 90C20, 90C35, 90C27; Secondary 65H20, 65K05}
\tableofcontents
\end{titlepage}
\pagebreak
\bs{There is a duality gap for the pure quadratic problem}
We look at the simple (solvable) problem
\beq
\label{eq:pq}
(P)
\begin{array}{ccc}
\mu^*:=
&\min & \tr AXBX^t \\
 &  \mbox{~subject to~} &XX^t = I 
    \end{array}
\end{equation}
The Lagrangian of $(P)$ is
$$
L(X,S) = \tr AXBX^t + \tr SXX^t - \tr S.
$$
A hidden constraint is the norm constraint $||\mbox{vec}(X)||=\sqrt{n}$, 
and an equivalent problem to $(P)$ is then
\beq
\label{eq:pqe}
\mu^* = \min\limits_{||\mbox{vec}(X)||=\sqrt{n}} \max\limits_{S=S^t} L(X,S)
\end{equation}
The first-order neccessary optimality condition for 
$(P)$ is
$$
AXB = -SX \Longrightarrow AXBX^t = - S \mbox{~~and~~} \tr S = -\mu^*.
$$
The Lagrangian dual of $(P)$ is 
\beq
\label{eq:ld}
\mu^D := \max\limits_{S=S^t} \min\limits_{||\mbox{vec}(X)||=\sqrt{n}} L(X,S)
\end{equation}
and clearly weak duality, i.e.\ $\mu^{*}\geq\mu^{D}$ holds. (\ref{eq:ld})
is equivalent to
$$
\mu^D =  \max\limits_{S=S^t} \min\limits_{||\mbox{vec}(X)||=\sqrt{n}} 
\mbox{~~vec}(X)^t (B \otimes A + I \otimes S)\mbox{~vec}(X) - \tr S
$$
and
\beq
\label{eq:d1}
\begin{array}{ccc}
 \mu^D = &\max\limits_{S=S^t} & nz -\tr S \\ 
&  \mbox{~subject to~}  &  (B \otimes A + I \otimes S) \succeq zI 
\end{array}
\end{equation}
which is again equivalent to
\beq
\label{eq:d2}
(D)
\begin{array}{ccc}
\mu^D = &\max\limits_{\hat{S}=\hat{S}^t} & -\tr \hat{S} \\ 
&  \mbox{~subject to~}  &  (B \otimes A + I \otimes \hat{S}) \succeq 0. 
\end{array}
\end{equation}
by using $\hat{S}:= S - zI$.

\bs {A simple Example}

Consider the following $2\times 2$ example
$$
A:= \left( 
\begin{array}{cc}
1 & 0 \\
0 & 2 
\end{array} 
\right) ~~~~~~~~
B:= \left( 
\begin{array}{cc}
3 & 0 \\
0 & 4 
\end{array} 
\right).
$$
Then $\mu^* = 10$ and therefore $-\tr\hat{S}$ should be equal to 10. Clearly
$$
B \otimes A = \left( 
\begin{array}{cccc}
3 & 0 & 0 & 0 \\
0 & 6 & 0 & 0 \\
0 & 0 & 4 & 0 \\
0 & 0 & 0 & 8 \\
\end{array} 
\right).
$$
Let 
$$
\hat{S}:= \left( 
\begin{array}{cc}
s_{11} & s_{12} \\
s_{12} & s_{22} 
\end{array} 
\right)
$$
then in order to satisfy (\ref{eq:d2}), $s_{11}\geq -3$ and $s_{22}\geq -6$.
In order to maximize $(D)$, equality must hold, and therefore $-\tr \hat{S} = 
9$ in the optimum. This shows the duality gap for a simple example.

\bs {What are the reasons?}

In the dual program $(D)$ the psd-constraints are stronger than 
the second-order optimality conditions of the primal problem $(P)$. 
The second-order necessary conditions would "only" require "psd" on 
the null space of the gradient of the orthogonality constraints, and so we
get a duality gap. This should also be explained by the theory, i.e.\ no 
constraint qualification might hold for $(P)$.

Since orthogonality seems to make problems why not look at the following
form of QAP next
\beq
\label{eq:qap}
(QAP)
\begin{array}{ccc}
q^*:=
&\min & \tr AXBX^t + 2CX^t \\
 &  \mbox{~subject to~} & Xu = X^tu = u \\
 &                      & X_{ij}^{2} - X_{ij} = 0, ~~~~\forall i,j.

    \end{array}
\end{equation}

These are just some first and probably unorganized thoughts. What do you 
think?



\end{document}