\documentclass[11pt]{article}
\usepackage{epsfig}
 
\setlength{\textheight}{8.3in}
\setlength{\headsep}{10pt}
\setlength{\parskip}{.6ex}
\setlength{\itemsep}{-.7ex}
 
%\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{0pt}
\newcommand{\ssp}{\renewcommand{\baselinestretch}{1}\large\normalsize}
\newcommand{\dsp}{\renewcommand{\baselinestretch}{1.3}\large\normalsize}
\bibliographystyle{plain}
\begin{document}
\dsp
\begin{center}
{\Large {\bf Workshop on}\\
Semidefinite Programming and Interior-Point Approaches for Combinatorial
Optimization Problems}
\end{center}

\epsfig{file=laurpol.ps,width=3in}

\noindent {\bf Organizers:}   
 Joseph Cheriyan,
 Bill Cunningham,
 Levent Tun{\c c}el,
 Tony Vannelli,
  Henry Wolkowicz (University of Waterloo), and
 Panos Pardalos (University of Florida).

\noindent {\bf Date Held:}  May 15-17, 1996

\noindent {\bf Location:} 
The Fields Institute, University of Toronto campus,
Toronto, Ontario, Canada

\noindent {\bf Supported Jointly by:}
Fields Institute and Centre de  researche math\'{e}matiques
(Universit\'{e} de Montr\'{e}al)

 Semidefinite Programming (SDP) is a generalization of
Linear Programming (LP) in that the nonnegativity constraints on the
variables is replaced by a positive semidefinite constraint on matrix
variables. Many of the elegant theoretical properties and powerful
solution techniques follow through from LP to SDP. 
In particular, the primal-dual interior-point methods, which are
currently so successful for LP, can be used to
efficiently solve SDP problems. 

In addition to the interesting theoretical and algorithmic questions,
SDP has found many important applications in Combinatorial Optimization,
Control Theory, Statistics,
and other areas of Mathematical Programming.
SDP is currently a very hot area of research. This can be seen by the
number of talks on SDP at various recent optimization conferences and
the number of recent publications, e.g.  
\cite{BoGhFeBa:94,VanBoy:94,Al:94,RendWolkZhao:94}.

The workshop on SDP at the Fields Institute attracted roughly 100
researchers. 
Participants from Australia, Austria, Brazil,
Belgium, Canada, Israel,
France, Hungary, Italy,
The Netherlands, Puerto Rico, and USA gave the workshop an important
international component.
There were 39 talks during the three days of the workshop.
(A list of participants, speakers, titles, abstracts, 
and this article, can be found
with URL: http://orion.uwaterloo.ca/\~{ }hwolkowi/fields.d/readme.html)
Following is a short, far from comprehensive,
outline of several of the talks.


The workshop started with two talks on 
{\bf Matrix Completion Problems}, i.e. under what circumstances a partial
matrix has a completion of a desired type.  These problems have
been studied extensively beginning in the early 80's, and exemplifies one
of the early instances of SDP, e.g. \cite{joh:90}.\\
 {\bf Monique Laurent} (Ecole Normale Superieure)
spoke on: ``A Connection Between Positive Semidefinite and
            Euclidean Distance Matrix Completion Problems''.
Although there is a
       strong relationship between positive semidefinite matrices and
Euclidean distance
       matrices, it was not clear how to link the two completion
problems.
 Monique showed how the
       results for the Euclidean distance matrix completion problem can
be derived from the
       corresponding results for the positive semidefinite completion
problem, using a
       functional transform introduced by Schoenberg. \\
{\bf Charlie Johnson} (College of William and Mary) spoke on 
``Recent Progress on Matrix Completion problems''.
After discussing the state of the art on positive definite
completion problems, he continued with
various other completion problems including
those for totally positive matrices, P-matrices, inverse M-matrices,
       completely positive and doubly nonnegative matrices. \\

There were many talks on applications to {\bf Combinatorial Optimization.}
One of the main reasons for the current interest in SDP is the success
in finding good approximations for the max-cut problem, e.g. 
\cite{GoWi:93,Helmberg:94}. However, SDP has applications to many other
combinatorial problems, e.g. \cite{VanBoy:94,Al:94}.\\
{\bf Stefan Karisch   } (University of Graz) spoke on:
``Semidefinite Programming and Graph Equipartition''. Stefan
showed how SDP can be used
to approximate the problem of partitioning a graph
into equally sized components. Improvements were shown on previous
eigenvalue approaches.\\
{\bf Christoph Helmberg   } (University of Graz ) spoke
on ``Quadratic Knapsack Relaxations Using Cutting Planes
                      and Semidefinite Programming''. Though the
quadratic knapsack  problem  is extremely difficult to solve by linear
programming alone, it was shown that SDP  is very useful for quadratic
knapsack problems. \\
{\bf Hsueh-I Lu   } (Brown University) spoke on: ``Approximation
Algorithms for Semidefinite Programs
               arising from Max Cut and Coloring''.\\
{\bf Tamas Terlaky   } (Delft University of Technology) spoke on:
``Potential Reduction Algorithms for Structured
                  Combinatorial Optimization Problems''.
Tamas presented a modified potential function, for binary feasibility
problems, that is computationally more attractive than the existing
ones.  A special class of binary feasibility
problems were reformulated as nonconvex
quadratic optimization problems. The reformulation is very compact.
Computational results on several instances of the graph coloring and
       frequency assignment problem were presented. 
These results compared three different potential functions.\\
{\bf Qing Zhao   } (University of Waterloo)
 spoke on: ``Semidefinite Programming Relaxations for the
Quadratic Assignment Problem''. Qing used the special structure of QAP to
construct a {\em gangster} operator which enabled him to
 work in the minimal face of the feasible set.
By exploiting this special structure and also using
a conjugate gradient method,
he was able to get strong bounds for the Nugent test set.


Many talks concentrated on {\bf Primal-Dual Interior-Point Methods} for
SDP. One of the reasons for the success of SDP is that interior-point
approaches from LP can be extended to SDP; though the extension is not
completely straightforward, e.g. \cite{int:Nesterov5}. 
Interesting complications can arise such as
duality gaps, \cite{RaTuWo:95}, 
lack of strict complementary slackness, \cite{AlHaOv:95}, and confusing
choices in the complementarity equations, \cite{AlHaOv:96}.  \\
{\bf Kees Roos   } (Delft University of Technology) spoke on:
``Initialization in Semidefinite Programming via a
                            Self-Dual Embedding''. In this way the
initialization problem for semidefinite problems
       can be solved nicely. The method also provides a solution for the
initialization of
       quadratic programs and it is applicable as well to more general
convex problems with
       conic formulation.\\
{\bf  Zhi-Quan Luo   } (McMaster University)
spoke on ``Superlinear Convergence of a Symmetric Primal-Dual Path
Following
              Algorithm for Semidefinite Programming ''.  \\
{\bf Michael J. Todd   } (Cornell University) spoke
on: ``The Nesterov-Todd direction in semidefinite programming ''.
Mike showed how to compute the direction efficiently and how to view it
a s a Newton direction.\\
{\bf Romesh Saigal   } (University of Michigan) spoke on:
``An Infeasible Start Predictor Corrector Method for Semidefinite Linear
              Programming''.\\
{\bf  Shuzhong Zhang   } (Erasmus University Rotterdam)
spoke on: ``Symmetric Primal-Dual Path Following Algorithms for SDP''.\\
{\bf  Yin Zhang    }  (University of Maryland)
spoke on: ``Infeasible Primal-Dual Interior-Point
Methods for Semidefinite Programming''. Yin  presented formulations,
     or symmetrization schemes, for the complementarity condition to
     obtain square optimality systems so that Newton-type
     methods can be applied.
He also discussed a complexity theorem 
    for an infeasible, long-step, path-following algorithm and several
computational issues with preliminary numerical results.\\

Several talks discussed the {\bf Geometry, Duality, and Complexity} of solving
SDP:\\
{\bf Franz Rendl } (University of Graz) spoke on:
``Large Scale SDP using Eigenvalues''.
The advantage of this approach lies in the fact, that extreme
eigenvalues of symmetric matrices can be computed without having
the matrix explicitly available.\\
{\bf Gabor Pataki  }  (University of Waterloo) spoke on:
``Cone-LP's and Semidefinite Programs: Geometry and a Simplex-type Method ''.\\
{\bf  Motakuri Ramana  } (University of Florida) spoke
on: ``Strong Duality for Semidefinite Programming''.
Unlike LP, a duality gap can occur in SDP. Two approaches for closing
the gap are compared and shown to have a common basis, though one is of
polynomial size while the other is not.\\
{\bf   Jos F. Sturm  } (Erasmus University Rotterdam)  spoke on:
``Duality and Self-Duality for Semidefinite and Conic Convex Programming''.\\
{\bf  Lorant Porkolab  } (Rutgers University)
spoke on:
``Bounds on Feasible Solutions of Semidefinite Programs''.\\
{\bf   Leonid Faybusovich }  (Notre Dame University) spoke on:
``Infinite-dimensional Semidefinite Programming: Self-Concordant Barriers
and Path-Following Algorithms for Semidefinite Programming''.\\
{\bf Alexander Shapiro  }  (Georgia Institute of Technology)
spoke on: ``Second Order Optimality Conditions and
Stability Analysis of Semidefinite Programs''.\\
{\bf Katya Scheinberg   }  (Columbia University) spoke on:
``Interior Point Trajectories in Semidefinite Programming''.\\
{\bf  Manuel A. Nunez } (MIT) spoke on:
``Condition Measures and Properties of the Central Trajectory of a
              Semidefinite Program''.
Manuel used Renegar's condition number to provide bounds on solution
size and rates of change of solution. This shows that Renegar's
condition number can greatly simplify sensitivity analysis for
SDP.\\

Other {\bf applications of SDP} were introduced and discussed. The
wide ranging applicability, as well as fascinating and
intriguing theoretical qualities,  shows that SDP
promises to be an active discipline of mathematical programming
for many years to come.\\
{\bf  Lieven Vandenberghe }  (Stanford University) spoke
on:
``Determinant Maximization with Linear Matrix Inequality Constraints''.
This problem has many interesting applications including finding the
ellipsoid of minimal volume that contains a given polytope or given
points.  \\
{\bf  Arjan Berkelaar    } (Erasmus University Rotterdam) spoke on:
``Convergence Issues and Path-following Algorithms for Semidefinite
              Programming ''.
Arjan discussed convergence issues related to recent primal-dual
interior-pint algorithms for the monotone semidefinite linear
complementarity problem.\\
{\bf  Renato Monteiro } (Georgia Institute of Technology)
``On Two Interior-Point Mappings for Nonlinear
       Semidefinite Complementarity Problems''.
Renato presented properties of two fundamental mappings associated with
the family of interior-point methods for solving monotone nonlinear
complementarity problems over the cone of symmetric positive
semidefinite matrices.
The first of these maps lead to a family of new continuous trajectories
which include the central trajectory as a special case.
The trajectories completely ``fill up'' the
set of interior feasible points of the problem in the same way as the
weighted central paths do the interior of the feasible region of
a linear program.\\
{\bf  Boris Mirkin } (DIMACS, Rutgers University)
``A Mine of Semidefinite Programming Problems''.\\
In addition, {\bf Related Problems} presented included:\\
{\bf Ding-zhu Du}  (University of Minnesota)
spoke on ``On Floorplan Design and Optimization''.\\
{\bf Jun Gu}  (Hong Kong Univ. of Science and Technology)
spoke on ``Parallel Algorithms for Satisfiability (SAT)
Problem''.\\
{\bf Linas Mockus} (AT\&T Bell Laboratories)  spoke on 
``Bayesian Approach to Combinatorial Optimization''.\\
{\bf Mauricio Resende} (AT\&T Bell Laboratories) spoke on ``Using linear
programming to
help solve quadratic assignment problems''. The linear programming
problems
used to obtain lower bounds for quadratic assignment problems are very
large and highly degenerate. For such problems simplex type algorithms
or
interior point methods based on direct factorizations, can only handle
small
instances. Large instance can be successfully solved
with an interior point algorithm that uses a preconditioned conjugate
gradient
approach to approximately compute interior point directions.\\
{\bf   M. R. Emamy-K } (University of Puerto Rico)
``How efficient can we maximize threshold
                        pseudo-Boolean functions ?''
The class of threshold pseudo-boolean functions was introduced  by
P.L. Hammer et. al. about 10 years ago. Existence of a polynomial
algorithm
to maximize these functions has been an open problem since then.\\
{\bf   Pham Dinh Tao } (LMI-INSA   Rouen)
``D.c. (difference of convex functions) Optimization: Theory, Algorithms
and Applications''.
 A general discussion of d.c. optimization was presented.
Its importance lies in the fact that d.c.  programming marks the 
passage from convex optimization to nonconvex optimization. \\
{\bf   Laura Palagi } (Universit`a di Roma "La Sapienza")
``Trust region Problems: Theoretic Results and New Algorithmic
              Developments ''.
The trust region subproblem is important in nonlinear programming as
well as other applications in combinatorial optimization. The special
structure of the problem allows one to solve an  equivalent
unconstrained minimization of a piecewise quartic merit function.\\
{\bf Le Thi Hoai An  } (LMI-INSA   Rouen)
``An efficient adapted DCA and Branch-and-Bound algorithm for globally
              solving large-scale 0-1 quadratic programming problems''.\\


A proceedings of the workshop will be published by the American Mathematical
Society in the FIELDS Series.

\bibliography{.master,.publs,.psd}
\end{document}

 




