\def\cprime{$'$} \def\cprime{$'$}
\begin{thebibliography}{10}

\bibitem{Alizadehnotes:00}
F.~ALIZADEH.
\newblock Lecture notes on semidefinite programming.
\newblock Technical report, Rutgers University, Piscataway, NJ, 2000.
\newblock URL: http://karush.rutgers.edu/\~{ }alizadeh/.

\bibitem{AlHaOv:94}
F.~ALIZADEH, J-P.A. HAEBERLY, and M.L. OVERTON.
\newblock A new primal-dual interior-point method for semidefinite programming.
\newblock In J.G. Lewis, editor, {\em Proceedings of the Fifth SIAM Conference
  on Applied Linear Algebra}, pages 113--117. SIAM, 1994.

\bibitem{AnWo:00}
M.F. ANJOS and H.~WOLKOWICZ.
\newblock A strengthened {SDP} relaxation via a second lifting for the
  {M}ax-{C}ut problem.
\newblock {\em Special Issue of Discrete Applied Mathematics devoted to
  Foundations of Heuristics in Combinatorial Optimization}, to appear.

\bibitem{AnsBri:00}
K.M. ANSTREICHER and N.W. BRIXIUS.
\newblock Solving quadratic assignment problems using convex quadratic
  programming relaxations.
\newblock Technical report, University of Iowa, Iowa City, IA, 2000.

\bibitem{AnChWoYu:98}
K.M. ANSTREICHER, X.~CHEN, H.~WOLKOWICZ, and Y.~YUAN.
\newblock Strong duality for a trust-region type relaxation of the quadratic
  assignment problem.
\newblock {\em Linear Algebra Appl.}, 301(1-3):121--136, 1999.

\bibitem{AnWo:98}
K.M. ANSTREICHER and H.~WOLKOWICZ.
\newblock On {L}agrangian relaxation of quadratic matrix constraints.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 22(1):41--55, 2000.

\bibitem{Bell:60}
R.~BELLMAN.
\newblock {\em Introduction to Matrix Analysis}.
\newblock McGraw Hill, New York, 1957.

\bibitem{FanBell:63}
R.~BELLMAN and K.~FAN.
\newblock On systems of linear inequalities in {H}ermitian matrix variables.
\newblock In {\em Proceedings of Symposia in Pure Mathematics, Vol 7, AMS},
  1963.

\bibitem{bentalnemirov:98}
A.~BEN-TAL and A.S. NEMIROVSKI.
\newblock {Convex Optimization in Engineering: Modeling, Analysis, Algorithms}.
\newblock Technical Report on notes from course given by A. Nemirovski, Delft
  University of Technology, Delft, The Netherlands, 1998.

\bibitem{Bohnen:48}
F.~BOHNENBLUST.
\newblock Joint positiveness of matrices.
\newblock Manuscript, 1948.

\bibitem{bw2}
J.M. BORWEIN and H.~WOLKOWICZ.
\newblock Characterization of optimality for the abstract convex program with
  finite-dimensional range.
\newblock {\em J. Austral. Math. Soc. Ser. A}, 30(4):390--411, 1980/81.

\bibitem{BoGhFeBa:93}
S.~BOYD, V.~BALAKRISHNAN, E.~FERON, and L.~{El~{G}HAOUI}.
\newblock Control system analysis and synthesis via linear matrix inequalities.
\newblock {\em {Proc. ACC}}, pages 2147--2154, 1993.

\bibitem{BoB:91}
S.~BOYD and C.~H. BARRATT.
\newblock {\em Linear Controller Design. Limits of Performance}.
\newblock Prentice-Hall, 1991.

\bibitem{CuDoWo:75}
J.~CULLUM, W.E. DONATH, and P.~WOLFE.
\newblock The minimization of certain nondifferentiable sums of eigenvalues of
  symmetric matrices.
\newblock {\em Mathematical Programming Study}, 3:35--55, 1975.

\bibitem{DennSch:83}
Jr. DENNIS, J.~E. and ROBERT~B. SCHNABEL.
\newblock {\em Numerical methods for unconstrained optimization and nonlinear
  equations}, volume~16 of {\em Classics in Applied Mathematics}.
\newblock Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
  PA, 1996.
\newblock Corrected reprint of the 1983 original.

\bibitem{MR98g:52001}
M.M. DEZA and M.~LAURENT.
\newblock {\em Geometry of cuts and metrics}.
\newblock Springer-Verlag, Berlin, 1997.

\bibitem{DHM:84}
L.C.W. DIXON, S.E. HERSOM, and Z.A. MAANY.
\newblock Initial experience obtained solving the low thrust satellite
  trajectory optimisation problem.
\newblock Technical Report T.R. 152, The Hatfield Polytechnic Numerical
  Optimization Centre, 1984.

\bibitem{DymGoh:81}
H.~DYM and I.~GOHBERG.
\newblock Extensions of band matrices with band inverses.
\newblock {\em Linear Algebra Appl.}, 36:1--24, 1981.

\bibitem{MR91d:90089}
A.V. FIACCO and G.P. McCORMICK.
\newblock {\em Nonlinear programming}.
\newblock Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
  PA, second (first 1968) edition, 1990.
\newblock Sequential unconstrained minimization techniques.

\bibitem{MR96h:90117}
A.~FISCHER.
\newblock A {N}ewton-type method for positive-semidefinite linear
  complementarity problems.
\newblock {\em J. Optim. Theory Appl.}, 86(3):585--608, 1995.

\bibitem{FuKo:95}
T.~FUJIE and M.~KOJIMA.
\newblock Semidefinite programming relaxation for nonconvex quadratic programs.
\newblock {\em J. Global Optim.}, 10(4):367--380, 1997.

\bibitem{Gay:81}
D.M. GAY.
\newblock Computing optimal locally constrained steps.
\newblock {\em SIAM J. Sci. Statist. Comput.}, 2:186--197, 1981.

\bibitem{GenHachNestvandooren:00}
Y.~GENIN, Y.~HACHEZ, Y.E. NESTEROV, and P.~VAN DOOREN.
\newblock Optimization problems over positive pseudo-polynomial matrices.
\newblock Technical report, CORE, Universite Catholique de Louvain, Belgium,
  2000.

\bibitem{Goem:97}
M.X. GOEMANS.
\newblock Semidefinite programming in combinatorial optimization.
\newblock {\em Math. Programming}, 79:143--162, 1997.

\bibitem{Goemans98}
M.X. GOEMANS.
\newblock Semidefinite programming and combinatorial optimization.
\newblock {\em Documenta Mathematica}, Extra Volume ICM 1998:657--666, 1998.
\newblock Invited talk at the International Congress of Mathematicians, Berlin,
  1998.

\bibitem{Goemans}
M.X. GOEMANS and D.P. WILLIAMSON.
\newblock Improved approximation algorithms for maximum cut and satisfiability
  problems using semidefinite programming.
\newblock {\em J. Assoc. Comput. Mach.}, 42(6):1115--1145, 1995.

\bibitem{GrJoSaWo:84}
B.~GRONE, C.R. JOHNSON, E.~MARQUES~de SA, and H.~WOLKOWICZ.
\newblock Positive definite completions of partial {H}ermitian matrices.
\newblock {\em Linear Algebra Appl.}, 58:109--124, 1984.

\bibitem{MR2000j:90078}
Ming Gu.
\newblock Primal-dual interior-point methods for semidefinite programming in
  finite precision.
\newblock {\em SIAM J. Optim.}, 10(2):462--502 (electronic), 2000.

\bibitem{GulerTuncel:98}
O.~G{\" U}LER and L.~TUN{\c{C}}EL.
\newblock Characterization of the barrier parameter of homogeneous convex
  cones.
\newblock {\em Math. Programming}, 81:55--76, 1998.

\bibitem{Hauser:99}
R.~HAUSER.
\newblock Self-scaled barrier functions: Decomposition and classification.
\newblock Technical Report DAMTP 1999/NA13, Department of Applied Mathematics
  and Theoretical Physics, University of Cambridge, Cambridge, England, 1998.

\bibitem{HeReVaWo:93}
C.~HELMBERG, F.~RENDL, R.~J. VANDERBEI, and H.~WOLKOWICZ.
\newblock An interior-point method for semidefinite programming.
\newblock {\em SIAM J. Optim.}, 6(2):342--361, 1996.

\bibitem{Hol:75}
R.B. HOLMES.
\newblock {\em Geometric Functional Analysis and its Applications}.
\newblock Springer-Verlag, Berlin, 1975.

\bibitem{HoJo:85}
R.A. HORN and C.R. JOHNSON.
\newblock {\em Matrix analysis}.
\newblock Cambridge University Press, Cambridge, 1990.
\newblock Corrected reprint of the 1985 original.

\bibitem{HoJo:91}
R.A. HORN and C.R. JOHNSON.
\newblock {\em Topics in matrix analysis}.
\newblock Cambridge University Press, Cambridge, 1994.
\newblock Corrected reprint of the 1991 original.

\bibitem{Ja:86}
J.~JAHN.
\newblock {\em Mathematical Vector Optimization in Partially Ordered Linear
  Spaces}.
\newblock Peter Lang, Frankfurt am Main, 1986.

\bibitem{Jame:70}
G.~JAMESON.
\newblock {\em Ordered linear spaces}.
\newblock Springer-Verlag, New York, 1970.

\bibitem{MR1430560}
B.~JANSEN, C.~ROOS, and T.~TERLAKY.
\newblock A family of polynomial affine scaling algorithms for positive
  semidefinite linear complementarity problems.
\newblock {\em SIAM J. Optim.}, 7(1):126--140, 1997.

\bibitem{joh:90}
C.R. JOHNSON.
\newblock Matrix completion problems: a survey.
\newblock {\em Proceedings of Symposium in Applied Mathematics}, 40:171--198,
  1990.

\bibitem{KoShShi:95}
M.~KOJIMA, M.~SHIDA, and S.~SHINDOH.
\newblock Reduction of monotone linear complementarity problems over cones to
  linear programs over cones.
\newblock Technical report, Dept. of Information Sciences, Tokyo Institute of
  Technology, Tokyo, Japan, 1995.

\bibitem{KoShHa:94}
M.~KOJIMA, S.~SHINDOH, and S.~HARA.
\newblock Interior-point methods for the monotone semidefinite linear
  complementarity problem in symmetric matrices.
\newblock {\em SIAM J. Optim.}, 7(1):86--125, 1997.

\bibitem{infieldsLaur:97}
M.~LAURENT.
\newblock A tour d'horizon on positive semidefinite and {E}uclidean distance
  matrix completion problems.
\newblock In {\em Topics in Semidefinite and Interior-Point Methods}, volume~18
  of {\em The Fields Institute for Research in Mathematical Sciences,
  Communications Series}, pages 51--76, Providence, Rhode Island, 1998.
  American Mathematical Society.

\bibitem{LaPo:94}
M.~LAURENT and S.~POLJAK.
\newblock On a positive semidefinite relaxation of the cut polytope.
\newblock {\em Linear Algebra Appl.}, 223/224:439--461, 1995.

\bibitem{Lewco663:94}
A.S. LEWIS.
\newblock {\em Take-home final exam, {C}ourse {CO}663 in {C}onvex {A}nalysis}.
\newblock University of Waterloo, Ontario, Canada, 1994.

\bibitem{Le:94}
A.S. LEWIS.
\newblock Derivatives of spectral functions.
\newblock {\em Math. Oper. Res.}, 21(3):576--588, 1996.

\bibitem{Lo:79}
L.~LOV{\'{A}}SZ.
\newblock On the {S}hannon capacity of a graph.
\newblock {\em IEEE Transactions on Information Theory}, 25:1--7, 1979.

\bibitem{Lu:69}
D.G. LUENBERGER.
\newblock {\em Optimization by Vector Space Methods}.
\newblock John Wiley, 1969.

\bibitem{Maa:85}
Z.A. MAANY.
\newblock A new algorithm for highly curved constrained optimization.
\newblock Technical Report T.R. 161, The Hatfield Polytechnic Numerical
  Optimization Centre, 1985.

\bibitem{MarOlk:79}
A.W. MARSHALL and I.~OLKIN.
\newblock {\em Inequalities: Theory of Majorization and its Applications}.
\newblock Academic Press, 1979.

\bibitem{Mont:95}
R.D.C. MONTEIRO.
\newblock Primal-dual path-following algorithms for semidefinite programming.
\newblock {\em SIAM J. Optim.}, 7(3):663--678, 1997.

\bibitem{MoTu:96}
R.D.C. MONTEIRO and T.~TSUCHIYA.
\newblock Polynomiality of primal-dual algorithms for semidefinite linear
  complementarity problems based on the {Kojima-Shindoh-Hara} family of
  directions.
\newblock {\em Math. Programming}, 84:39--53, 1999.

\bibitem{MontZhang:96}
R.D.C. MONTEIRO and Y.~ZHANG.
\newblock A unified analysis for a class of long-step primal-dual
  path-following interior-point algorithms for semidefinite programming.
\newblock {\em Math. Programming}, 81(3, Ser. A):281--299, 1998.

\bibitem{MoSo:83}
J.J. MOR\'{E} and D.C. SORENSEN.
\newblock Computing a trust region step.
\newblock {\em SIAM J. Sci. Statist. Comput.}, 4:553--572, 1983.

\bibitem{nesterov97}
Y.E. NESTEROV.
\newblock Structure of non-negative polynomial and optimization problems.
\newblock Technical report, Louvan-la-Neuve, Belgium, 1997.
\newblock Preprint DP 9749.

\bibitem{NeN:88}
Y.E. NESTEROV and A.S. NEMIROVSKI.
\newblock A general approach to polynomial-time algorithms design for convex
  programming.
\newblock Technical report, Centr. Econ. \& Math. Inst., USSR Acad. Sci.,
  Moscow, USSR, 1988.

\bibitem{MR89k:90130}
Y.E. NESTEROV and A.S. NEMIROVSKI.
\newblock Polynomial barrier methods in convex programming.
\newblock {\em \`Ekonom. i Mat. Metody}, 24(6):1084--1091, 1988.

\bibitem{int:Nesterov4}
Y.E. NESTEROV and A.S. NEMIROVSKI.
\newblock Self--concordant functions and polynomial--time methods in convex
  programming.
\newblock {Book--Preprint}, Central Economic and Mathematical Institute, USSR
  Academy of Science, Moscow, USSR, 1989.
\newblock Published in Nesterov and Nemirovsky \cite{int:Nesterov5}.

\bibitem{NeN:90b}
Y.E. NESTEROV and A.S. NEMIROVSKI.
\newblock {\em Optimization over positive semidefinite matrices: {M}athematical
  background and user's manual}.
\newblock USSR Acad. Sci. Centr. Econ. \& Math. Inst., 32 Krasikova St.,
  Moscow~117418 USSR, 1990.

\bibitem{NeN:90}
Y.E. NESTEROV and A.S. NEMIROVSKI.
\newblock Self-concordant functions and polynomial time methods in convex
  programming.
\newblock Technical report, Centr. Econ. \& Math. Inst., USSR Acad. Sci.,
  Moscow, USSR, April 1990.

\bibitem{NeN:91}
Y.E. NESTEROV and A.S. NEMIROVSKI.
\newblock Conic formulation of a convex programming problem and duality.
\newblock Technical report, Centr. Econ. \& Math. Inst., USSR Academy of
  Sciences, Moscow USSR, 1991.

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

\bibitem{NesterovTodd:97}
Y.E. NESTEROV and M.J. TODD.
\newblock Self-scaled barriers and interior-point methods for convex
  programming.
\newblock {\em Math. Oper. Res.}, 22(1):1--42, 1997.

\bibitem{MR55:13315}
L.W. NEUSTADT.
\newblock {\em Optimization}.
\newblock Princeton University Press, Princeton, N. J., 1976.
\newblock A Theory of Necessary Conditions, With a chapter by H. T. Banks.

\bibitem{OrRhe:70}
J.M. ORTEGA and W.C. RHEINBOLDT.
\newblock {\em Iterative Solution of Nonlinear Equations in Several Variables}.
\newblock Academic Press, New York, NY, 1970.

\bibitem{Ov:88}
M.L. OVERTON.
\newblock On minimizing the maximum eigenvalue of a symmetric matrix.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 9:256--268, 1988.

\bibitem{Ov:92}
M.L. OVERTON.
\newblock Large-scale optimization of eigenvalues.
\newblock {\em SIAM J. Optim.}, 2:88--120, 1992.

\bibitem{GPat:95}
G.~PATAKI.
\newblock On the rank of extreme matrices in semidefinite programs and the
  multiplicity of optimal eigenvalues.
\newblock {\em Math. Oper. Res.}, 23(2):339--358, 1998.

\bibitem{PatTun:97}
G.~PATAKI and L.~TUN{\c{C}}EL.
\newblock On the generic properties of convex optimization problems in conic
  form.
\newblock {\em Math. Programming}, to appear.

\bibitem{MR37:3315}
A.L. PERESSINI.
\newblock {\em Ordered Topological Vector Spaces}.
\newblock Harper \& Row Publishers, New York, 1967.

\bibitem{PoReWo:94}
S.~POLJAK, F.~RENDL, and H.~WOLKOWICZ.
\newblock A recipe for semidefinite relaxation for $(0,1)$-quadratic
  programming.
\newblock {\em J. Global Optim.}, 7(1):51--73, 1995.

\bibitem{Rendl:97}
F.~RENDL.
\newblock Semidefinite programming and combinatorial optimization.
\newblock {\em Appl. Numer. Math.}, 29:255--281, 1999.

\bibitem{ReWo:94}
F.~RENDL and H.~WOLKOWICZ.
\newblock A semidefinite framework for trust region subproblems with
  applications to large scale minimization.
\newblock {\em Math. Programming}, 77(2, Ser. B):273--299, 1997.

\bibitem{Renegar:92}
J.~RENEGAR.
\newblock On the computational complexity and geometry of the first-order
  theory of the reals. {I}{I}{I}. {Q}uantifier elimination.
\newblock {\em J. Symbolic Comput.}, 13(3):329--352, 1992.

\bibitem{MR95d:65116}
J.~RENEGAR.
\newblock Is it possible to know a problem instance is ill-posed? {S}ome
  foundations for a general theory of condition numbers.
\newblock {\em J. Complexity}, 10(1):1--56, 1994.

\bibitem{MR96c:90048}
J.~RENEGAR.
\newblock Incorporating condition measures into the complexity theory of linear
  programming.
\newblock {\em SIAM J. Optim.}, 5(3):506--524, 1995.

\bibitem{MR96i:90029}
J.~RENEGAR.
\newblock Linear programming, complexity theory and elementary functional
  analysis.
\newblock {\em Math. Programming}, 70(3, Ser. A):279--351, 1995.

\bibitem{MR97g:90134}
J.~RENEGAR.
\newblock Condition numbers, the barrier method, and the conjugate-gradient
  method.
\newblock {\em SIAM J. Optim.}, 6(4):879--912, 1996.

\bibitem{MR83g:90075}
S.~SCHAIBLE and W.T. ZIEMBA, editors.
\newblock {\em Generalized Concavity in Optimization and Economics}, New York,
  1981. Academic Press Inc. [Harcourt Brace Jovanovich Publishers].

\bibitem{Sho:87}
N.Z. SHOR.
\newblock Quadratic optimization problems.
\newblock {\em Izv. Akad. Nauk SSSR Tekhn. Kibernet.}, 222(1):128--139, 222,
  1987.

\bibitem{sw5}
R.~STERN and H.~WOLKOWICZ.
\newblock Trust region problems and nonsymmetric eigenvalue perturbations.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 15(3):755--778, 1994.

\bibitem{StWo:93}
R.~STERN and H.~WOLKOWICZ.
\newblock Indefinite trust region subproblems and nonsymmetric eigenvalue
  perturbations.
\newblock {\em SIAM J. Optim.}, 5(2):286--313, 1995.

\bibitem{Todd:00}
M.J. TODD.
\newblock Semidefinite programming.
\newblock Technical report, School of OR and IE, Cornell University, Ithaca,
  NY, 2000.

\bibitem{TunXu:99}
L.~TUN{\c{C}}EL and S.~XU.
\newblock On homogeneous convex cones, {C}aratheodory number, and duality
  mapping semidefinite liftings.
\newblock Technical Report CORR 99-21, Department of Combinatorics and
  Optimization, Waterloo, Ont, 1999.

\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.

\bibitem{VanBoy:94}
L.~VANDENBERGHE and S.~BOYD.
\newblock Semidefinite programming.
\newblock {\em SIAM Rev.}, 38(1):49--95, 1996.

\bibitem{w11}
H.~WOLKOWICZ.
\newblock Some applications of optimization in matrix theory.
\newblock {\em Linear Algebra Appl.}, 40:101--118, 1981.

\bibitem{SaVaWo:97}
H.~WOLKOWICZ, R.~SAIGAL, and L.~VANDENBERGHE, editors.
\newblock {\em HANDBOOK OF SEMIDEFINITE PROGRAMMING: Theory, Algorithms, and
  Applications}.
\newblock Kluwer Academic Publishers, Boston, MA, 2000.
\newblock xxvi+654 pages.

\bibitem{MR91e:90078}
Y.~Yuan.
\newblock On a subproblem of trust region algorithms for constrained
  optimization.
\newblock {\em Math. Programming}, 47(1 (Ser. A)):53--63, 1990.

\bibitem{Yuan:91}
Y.~YUAN.
\newblock A dual algorithm for minimizing a quadratic function with two
  quadratic constraints.
\newblock {\em Journal of Computational Mathematics}, 9:348--359, 1991.

\bibitem{KaReWoZh:94}
Q.~ZHAO, S.E. KARISCH, F.~RENDL, and H.~WOLKOWICZ.
\newblock Semidefinite programming relaxations for the quadratic assignment
  problem.
\newblock {\em J. Comb. Optim.}, 2(1):71--109, 1998.
\newblock Semidefinite programming and interior-point approaches for
  combinatorial optimization problems (Toronto, ON, 1996).

\end{thebibliography}