\documentstyle[11pt,fullpage]{article}
 
\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 Proposal for a Workshop on}\\
Semidefinite Programming and Interior-Point Approaches for Combinatorial
Optimization Problems}
\end{center}

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

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

\noindent {\bf Dates:}  May 15-16, 1996

\noindent {\bf Format:}  20 speakers.  35 minute talks.

\noindent {\bf Aim:}  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. 

Moreover, the recent
interest in SDP is due to the applications in Engineering and
Combinatorial Optimization. This is evident from the numerous
publications and conferences devoted to SDP, e.g.: the recent 15th
International Symposium on Mathematical Programming, Ann Arbor, 1994,
had four special sessions devoted to SDP one of which was a plenary session,
\cite{VanBoy:94b}; the recent book \cite{BoGhFeBa:94} describes the
engineering applications of SDP; the book \cite{int:Nesterov5} describes
efficient algorithms. More information about workshops and publications
can be found over WWW using the special home page for SDP
with URL http://new-rutcor.rutgers.edu/\~{ }alizadeh and also the URL
ftp://orion.uwaterloo.ca/pub/henry/software/readme.html.

In the last decade thousands
of papers have been written on interior point methods. Many of these
interior point techniques have been applied successfully to SDP.
In fact, the number of iterations typically depends on $n,$ the order of
the matrix variable, rather than on $n^2$, the number of unknown
elements. The interior-point approach is presently the only successful
method for general SDP problems.

This workshop will focus on bringing together several of the diverse
communities wherein SDP has found applications. The main topics are:
\begin{itemize}
\item
Applications of SDP in Engineering and Combinatorial Optimization;
\item
Solution techniques for SDP based on interior-point methods.
\end{itemize}


\noindent {\bf Related Experience::}
Panos Pardalos and Henry Wolkowicz organized a very successful workshop
on the Quadratic Assignment Problem, at DIMACS, April, 1993, see the
proceedings \cite{PardWolk:94}.


The workshop date is scheduled in order to
attract some very well known researchers from Europe who
will be attending the SIAM
Conference on Optimization in Victoria.

A proceedings of refereed invited papers is planned.

\noindent {\bf Topics:}
\begin{itemize}
\item
Semidefinite Programming Theory: duality theory; convergence theory;
numerical stability.
\item
Semidefinite Programming  Algorithms: interior point methods; simplex
type algorithms.
\item
Global Optimization and Combinatorial Applications:
quadratic assignment problem; 
clique problem;
graph partitioning; 
boolean programming.
\item
Nonlinear Programming: trust region subproblems;
quadratic programs with quadratic constraints; SQP algorithms.
\item
Engineering Applications: VLSI design; solutions of Lyapunov equations;
general linear matrix inequalities in systems and control theory.
\item
Matrix Completion Problems: positive definite completions; specified
inertial completions.
\end{itemize}


\noindent {\bf Participants:}
Waterloo faculty members with interests in some or all of these
areas include M. Best, 
A.S. Lewis, M. Loebl (C\&O),
  P. Calamai and K. Ponnambalam (SD),
and G. Pataki (post-doctoral fellow from Carnegie-Mellon at C\&O).
Graduate Students at Waterloo: S. Kruk, G. Scott, B. Yu, Q. Zhao
Other possible Canadian participants include:
J.M. Bourjolly (Concordia)
S. Boyd (Ottawa)
R.J. Caron (Windsor),
R. Dembo (Algorithmics, Toronto)
J.-L. Goffin (McGill),
Z.-Q. Luo (McMaster),
R. Stern (Concordia),
S. Zlobec (McGill).

\noindent {\bf Potential Invitees:} Invited speakers will be drawn from the following list.
Some of the invitees may have independent funding. In addition, an open
invitation to the workshop will be issued over the various relevant
newsgroups on the internet.


\noindent
W. Adams (Clemson)
F. Alizadeh (Rutgers),
E. Balas (Carnegie Mellon)
W. Barrett  (Brigham Young)
A. Ben-Israel (Rutgers)
S. Boyd (Stanford),
S. Ceria (Columbia)
G. Cornuejols (Carnegie Mellon)
R.M. Freund (MIT),
M. Goemans (MIT),
C Johnson (William and Mary)
D. Karger (MIT)
N. Karmarkar (AT \&T Bell Labs),
M. Kojima (Tokyo),
M. Laurent (LIENS, Paris),
R. Loewy (Technion, Haifa)
L. Lovasz  (Yale),
N. Megiddo (IBM, Almaden),
A. Nemirovskii (Technion, Haifa),
M. Overton (Courant),
J. Pang (Johns Hopkins),
M. Ramana (U. Florida),
F. Rendl (Graz),
M.G.C. Resende (AT\&T Bell Labs),
H.D. Sherali (Virginia Polytechnic),
M. Sudan (IBM, Yorktown Heights),
E. Tardos (Cornell)
T. Terlaky (Holland),
M. J. Todd (Cornell), 
R. Vanderbei (Princeton),
L. Vandenberghe (Louven),
D. Williamson (IBM, Yorktown Heights),
Y. Ye (Iowa),

\noindent {\bf Budget:}
All Canadian participants are NSERC funded. So, we are
seeking funds for foreign speakers, a few student participants,
and a modest reception.

\noindent
Foreign speakers (14-16)   \$ 12,000 to \$ 14,000\\
Student participants (4-6) \$ 2,000 to \$ 3,000\\
Reception and refreshments \$ 1,000


\noindent {\bf Total funding sought} from all sources : {\bf \$ 18,000}\\
(including Fields Institute and Collaborative Research Fund).

\begin{center}
 Joseph Cheriyan, 
  Bill Cunningham,
Panos Pardalos,\\
Levent Tun{\c c}el, Tony Vannelli, Henry Wolkowicz
\end{center}

%\bibliography{.master,.publs,.psd}
\begin{thebibliography}{1}

\bibitem{BoGhFeBa:94}
S.~BOYD, L.~{El~{G}HAOUI}, E.~FERON, and V.~BALAKRISHNAN.
\newblock {\em Linear Matrix Inequalities in System and Control Theory},
  volume~15 of {\em Studies in Applied Mathematics}.
\newblock {SIAM}, Philadelphia, PA, June 1994.

\bibitem{int:Nesterov5}
Y.~E. NESTEROV and A.~S. NEMIROVSKY.
\newblock {\em Interior Point Polynomial Algorithms in Convex Programming\ :\
  Theory and Algorithms}.
\newblock SIAM Publications. SIAM, Philadelphia, USA, 1994.

\bibitem{PardWolk:94}
P.~PARDALOS and H.~WOLKOWICZ (Editors).
\newblock {\em Quadratic assignment and related problems}, volume~16 of {\em
  DIMACS Series in Discrete Mathematics and Theoretical Computer Science}.
\newblock American Mathematical Society, 1994.

\bibitem{VanBoy:94b}
L.~VANDENBERGHE and S.~BOYD.
\newblock Positive definite programming.
\newblock In {\em Mathematical Programming: State of the Art, 1994}, pages
  276--308. The University of Michigan, 1994.

\end{thebibliography}
\end{document}

 




