This webpage contains titles/abstracts/articles/links of papers/books (and student theses) which are available as ps/pdf files in this directory. (The link to the AMS Mathematical Reviews is available for (some) of the papers. Also available is a Jan/12 search at ISI Web of Knowledge for citations ) A complete list of my publications (including: unpublished techreports; student theses) is available as a gzipped bib file and as an html file and as a gzipped ps file.

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014

2014

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014

2013

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014

2012

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2011

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2010

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2009

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2008

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2007

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2006

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2005

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2004

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2003

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2002

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2001

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2000

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1999

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1998

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1997

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1996

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1995

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1994

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1993

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1992

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1991

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1990

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1989

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1988

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1987

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1986

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1985

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1984

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1983

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1982

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1981

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1980

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1979

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

1978

1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 19911992 19931994 19951996 19971998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

Efficient use of semidefinite programming for selection of rotamers in protein conformations , Jan. 2013. ,

• FORMAT: local pdf file
• authors: Forbes Burkowski, Yuen-Lam Cheung, Henry Wolkowicz.
• abstract: Determination of a protein's structure can facilitate an understanding of how the structure changes when that protein combines with other proteins or smaller molecules. In this paper we study a semidefinite programming (SDP) relaxation of the (NP-hard) side chain positioning problem (SCP) presented in Chazelle et al. \cite{MR2098320}. We show that the Slater constraint qualification (SCQ) fails for the SDP relaxation. We then show the advantages of using facial reduction to regularize the problem. In fact, after applying facial reduction, we have a \emph{smaller} problem that is \emph{more stable} both in theory and in practice.
• date of entry: Jan 1, 2013; submitted Jan 1, 2013
journal = "INFORMS Journal on Computing", pages="748-766", number="4", volume="26", year="2014" #number="submitted Dec. 2012", #address="publish online jun20/14 #volume="accepted Dec. 2013",

A general Hua-type matrix equality and its applications , Jan. 2013. ,

• FORMAT: local pdf file
• authors: Minghua Lin, Henry Wolkowicz.
• abstract: We present a very general Hua-type matrix equality. Among several applications of the proposed equality, we give a matrix version of the Acz\'{e}l inequality.
• date of entry: Jan 1, 2013; submitted Jan 7, 2013

Applications of {H}iroshima's theorem in matrix norm inequalities , Jan. 2013. ,

• FORMAT: local pdf file
• authors: Minghua Lin, Henry Wolkowicz.
• abstract: } In this article, several matrix norm inequalities are proved by making use of the Hiroshima 2003 result on majorization relations.
• status Nov./13; to appear in Acta Sci. Math. (Szeged)

Large-Scale Manifold Learning by Semidefinite Facial Reduction, April 2012.

• FORMAT: local pdf file
• authors: Babak Alipanahi, Nathan Krislock, Ali Ghodsi, Henry Wolkowicz
• abstract: The problem of nonlinear dimensionality reduction is often formulated as a semidefinite programming (SDP) problem. However, only SDP problems of limited size can be solved directly using current SDP solvers. To overcome this difficulty, we propose a novel SDP formulation for dimensionality reduction based on semidefinite facial reduction that significantly reduces the number of variables and constraints of the SDP problem, allowing us to solve very large manifold learning problems. Moreover, our reduction is exact, so we obtain high quality solutions without the need for post-processing by local gradient descent search methods, as is often required by other SDP-based methods for manifold learning.
• date of entry: Apr/12, 16 pages.

The Generalized Trust Region Subproblem, Nov. 2012. ,

• FORMAT: local pdf file; see Ting Kei Pong's web page for the MATLAB GTRS codes
• authors: Ting Kei Pong, Henry Wolkowicz.
• abstract: The \emph{interval bounded generalized trust region subproblem} (GTRS) consists in minimizing a general quadratic objective, $q_0(x) \rightarrow \min$, subject to an upper and lower bounded general quadratic constraint, $\ell \leq q_1(x) \leq u$. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this \emph{implicitly} convex problem under a constraint qualification and show that it can be assumed without loss of generality. We next classify the GTRS into easy case and hard case instances, and demonstrate that the upper and lower bounded general problem can be reduced to an equivalent equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. We then discuss how the Rendl-Wolkowicz algorithm proposed in \cite{FortinWolk:03,ReWo:94} can be extended to solve the resulting equality constrained problem, highlighting the connection between the GTRS and the problem of finding minimum generalized eigenvalues of a parameterized matrix pencil. Finally, we present numerical results to illustrate this algorithm at the end of the paper.
• date of entry: Nov/12 submitted Nov. 17, 2012. Accepted 2013. ( Springer online first link, DOI 10.1007/s10589-013-9635-7, Print ISSN 0926-6003, Online ISSN 1573-2894); ( optimization online link)

Determining protein structures from NOESY distance constraints by semidefinite programming, March 2012. ,

• FORMAT: local pdf file and preprint on HAL
• authors: Babak Alipanahi, Nathan Krislock, Ali Ghodsi, Henry Wolkowicz, Logan Donaldson, and Ming Li,
• abstract: All practical contemporary protein NMR structure determination methods use molecular dynamics coupled with a simulated annealing schedule. The objective of these methods is to minimize the error of deviating from the NOE distance constraints. However, this objective function is highly nonconvex and, consequently, difficult to optimize. Euclidean distance geometry methods based on semidefinite programming (SDP) provide a natural formulation for this problem. However, complexity of SDP solvers and ambiguous distance constraints are major challenges to this approach. The contribution of this paper is to provide a new SDP formulation of this problem that overcomes these two issues for the first time. We model the protein as a set of intersecting two- and three-dimensional cliques, then we adapt and extend a technique called semidefinite facial reduction to reduce the SDP problem size to approximately one quarter of the size of the original problem. The reduced SDP problem can not only be solved approximately 100 times faster, but is also resistant to numerical problems from having erroneous and inexact distance bounds.
• date of entry: Mar/12 RECOMB 2012 special issue of the Journal of Computational, Biology (JCB), VOLUME = {20}, YEAR = {2013}, NUMBER = {4}, PAGES = {296--310}

An Eigenvalue Majorization Inequality for Positive Semidefinite Block Matrices: In Memory of Ky Fan , CORR 2011-04

• FORMAT: pdf file
• authors: Ming Hua Lin, Henry Wolkowicz
• abstract: Let $H=\begin{bmatrix}M& K\cr K^*&N\end{bmatrix}$ be a Hermitian matrix. It is known that the eigenvalues of $M\oplus N$ are majorized by the eigenvalues of $H$. If, in addition, $H$ is positive semidefinite and the block $K$ is Hermitian, then the following reverse majorization inequality holds for the eigenvalues: \begin{eqnarray*} \lambda\left(\begin{bmatrix}M&K\cr K&N\end{bmatrix}\right) \prec \lambda((M+N)\oplus 0) . \end{eqnarray*} Interesting corollaries are included.
• date of entry: July 25/11
• to appear LAMA in special issue for Ky Fan.

Numerical Computations and the $\omega$-Condition Number, , CORR 2011-03

• FORMAT: pdf file
• authors: Vinh Doan, Henry Wolkowicz
• abstract: We study the computation and properties of a new measure for the condition number of a positive definite matrix. This measure, the ratio of the arithmetic and geometric means of the eigenvalues, depends uniformly on all the eigenvalues of the matrix. Moreover, it can be evaluated easily and accurately. And, we see that: (i) it correlates better with the number of iterations in iterative methods compared to the standard condition number which depends only on the largest and smallest eigenvalues; (ii) it provides a criteria for obtaining optimal efficient preconditioners; and (iii) it presents a more average relative error measure compared to the worst case behaviour of the standard condition number.
• date of entry: July 4/11, 19 pages.
• software for calculating omega (MATLAB file)

Preprocessing and Reduction for Degenerate Semidefinite Programs, CORR 2011-02

• FORMAT: pdf file
• authors: Yuen-Lam (Vris) Cheung, Simon Schurr, Henry Wolkowicz
• abstract: This paper presents a backward stable preprocessing technique for (nearly) ill-posed semidefinite programming, SDP, problems, i.e.,~programs for which Slater's constraint qualification, existence of strictly feasible points, (nearly) fails. Current popular algorithms for semidefinite programming rely on \emph{primal-dual interior-point, p-d i-p} methods. These algorithms require Slater's constraint qualification for both the primal and dual problems. This assumption guarantees the existence of Lagrange multipliers, well-posedness of the problem, and stability of algorithms. However, there are many instances of SDPs where Slater's constraint qualification fails or {\em nearly} fails. Our backward stable preprocessing technique is based on finding a {\em rank-revealing} rotation of the problem followed by facial reduction. This results in a smaller, well-posed, \emph{nearby} problem that can be solved by standard SDP solvers.
• date of entry: Feb 18/11, revised june/12, appeared in "Computational and Analytical Mathematics", In Honor of Jonathan Borwein's 60th Birthday, Springer, VOL 50, Springer Proceedings in Mathematics & Statistics, 2013, ISBN 978-1-4614-7620-7
• software/instances tar file

A Robust Algorithm for Semidefinite Programming CORR 2010-09

• FORMAT: pdf pdf file
• authors: Xuan Vinh Doan, Serge Kruk, Henry Wolkowicz
• available software, RSD0.1 version for both medium and large/sparse problems; see the README.html file
• abstract: Current successful methods for solving semidefinite programs, SDP, are based on primal-dual interior-point approaches. These usually involve a symmetrization step to allow for application of Newton's method followed by block elimination to reduce the size of the Newton equation. Both these steps create ill-conditioning in the Newton equation and singularity of the Jacobian of the optimality conditions at the optimum. In order to avoid the ill-conditioning, we derive and test a backwards stable primal-dual interior-point method for SDP. Relative to current public domain software, we realize both a distinct improvement in the accuracy of the optimum and a reduction in the number of iterations. This is true for random problems as well as for problems of special structure. Our algorithm is based on a Gauss-Newton approach applied to a single bilinear form of the optimality conditions. The well-conditioned Jacobian allows for a preconditioned (matrix-free) iterative method for finding the search direction at each iteration.
• date of entry: Nov. 9/10
as of May 1/13: Optimization Methods and Software, vol 27, number 4-5, pages 667-693.

Euclidean Distance Matrices and Applications CORR 2010-06

• FORMAT: pdf file
• authors: Nathan Krislock, Henry Wolkowicz
• abstract: This is a survey of EDM with emphasis on SNL.
• date of entry: July 9/10
• in Handbook of Semidefinite, Cone and Polynomial Jan/2012 Optimization

On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming, CORR 2010-02

• FORMAT: pdf file
• authors: Yichuan Ding, Dongdong Ge, Henry Wolkowicz
• abstract: In this paper, we analyze two popular semidefinite programming \SDPb relaxations for quadratically constrained quadratic programs \QCQPb with matrix variables. These are based on \emph{vector-lifting} and on \emph{matrix lifting} and are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose an inexpensive \SDP relaxation and still obtain a strong bound. Our results also shed important insights on how to simplify large-scale \SDP constraints by exploiting the particular sparsity pattern.
• date of entry: Apr 27/10
• MOR, vol 36, 2011, pp 88-104.

Noisy Sensor Network Localization using Semidefinite Representations and Facial Reduction , CORR 2010-01

• FORMAT: pdf file
• authors: Nathan Krislock, Franz Rendl, Henry Wolkowicz
• abstract: In this paper we extend a recent algorithm for solving the sensor network localization problem (\SNL) to include instances with noisy data. In particular, we continue to exploit the implicit degeneracy in the semidefinite programming (\SDP) relaxation of \SNL. An essential step involves finding good initial estimates for a noisy Euclidean distance matrix, \EDM, completion problem. After finding the \EDM completion from the noisy data, we rotate the problem using the original positions of the anchors. This is a preliminary working paper, and is a work in progress. Tests are currently on-going.
• date of entry: Mar 19/10

Euclidean Distance Matrices, Semidefinite Programming, and Sensor Network Localization, CORR 2009-05 (a survey)

• FORMAT: pdf file
• authors: Abdo Y. Alfakih, Miguel F. Anjos, Veronica Piccialli, Henry Wolkowicz
• abstract: The fundamental problem of distance geometry, \FPDG, involves the characterization and study of sets of points based only on given values of (some of) the distances between pairs of points. This problem has a wide range of applications in various areas of mathematics, physics, chemistry, and engineering. Euclidean Distance Matrices, \EDM, play an important role in \FPDG. They use the squared distances and provide elegant and powerful convex relaxations for \FPDG. These \EDM problems are closely related to graph realization, \GRL; and graph rigidity, \GRD, plays an important role. Moreover, by relaxing the embedding dimension restriction, \EDM problems can be approximated efficiently using semidefinite programming, \SDP. Throughout this survey we emphasize the interplay between: \FPDG, \EDM, \GRL, \GRD, and \SDP. In addition, we illustrate our concepts on one instance of \FPDG, the Sensor Network Localization Problem, \SNL.
• date of entry: Nov 2/09
• to appear in: Portugaliae Mathematica

Generating Eigenvalue Bounds Using Optimization CORR 2009-02 , May, 2009.

• FORMAT: pdf file;
• Number of Pages: 26
• Title: Generating Eigenvalue Bounds Using Optimization
• author
• Henry Wolkowicz
• abstract:
• This paper illustrates how optimization can be used to derive known and new theoretical results about perturbations of matrices and sensitivity of eigenvalues. More specifically, the Karush-Kuhn-Tucker conditions, the shadow prices, and the parametric solution of a fractional program are used to derive explicit formulae for bounds for functions of matrix eigenvalues.
• STATUS: Nonlinear Analysis and Variational Problems; Dedicated to the memory of Dr. George Isac, vol 35, part 2, pages 465-490.
• DATE OF ENTRY: June 2009

Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions, CORR 2009-04 , May , 2009/revised Jan/10.

• FORMAT: pdf file;
• Number of Pages: 30
• Title: Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions
• author
• Nathan Krislock and Henry Wolkowicz
• abstract:
• The sensor network localization, \SNL, problem in embedding dimension $r$, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, \SDPc completion problem, by using the linear mapping between Euclidean distance matrices, \EDMc and semidefinite matrices. The resulting \SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution.

This relaxation is highly degenerate in the sense that the feasble set is restricted to a low dimensional face of the \SDP cone, implying that the Slater constraint qualification fails. The degeneracy in the \SDP arises from cliques in the graph of the \SNL problem. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the \SNL problem, with exact data, that explicitly solves the corresponding rank restricted \SDP problem. No \SDP solvers are used. We are able to efficiently solve this NP-HARD problem with high probability, by finding a representation of the minimal face of the \SDP cone that contains the \SDP matrix representation of the \EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the \SDP cone that correspond to cliques of the \SNL problem.

• SOFTWARE versions (also available at Nathan's website): (Newer versions are in progress and will be posted as they become available.) See the EDM link
• STATUS: Submitted May/09; Accepted May/10 SIOPT appeared siopt July/10; and at arXiv.org cite as arXiv:1002.0013v1
• DATE OF ENTRY: May 2009/revised Jan/10

Sensor network localization, Euclidean distance matrix completions, and graph realization, , Oct. 2008.

• FORMAT: pdf file;
• Number of Pages: 6
• Title: Sensor network localization, Euclidean distance matrix completions, and graph realization
• author
• Yichuan Ding, Nathan Krislock, Jiawei Qian, Henry Wolkowicz
• extended abstract:
• For MELT 08.
• STATUS: extended abstract
• DATE OF ENTRY: Oct 2008

Strong Duality and Minimal Representations for Cone Optimization , as of 2012:

• FORMAT: pdf file (feb24/11);
• Number of Pages: 33
• author
• Levent Tuncel and Henry Wolkowicz
• abstract:
• The elegant results for strong duality and strict complementarity for linear programming, \LP, can fail for cone programming over nonpolyhedral cones. One can have: unattained optimal values; nonzero duality gaps; and no primal-dual optimal pair that satisfies strict complementarity. This failure is tied to the nonclosure of sums of nonpolyhedral closed cones.

We take a fresh look at known and new results for duality, optimality, constraint qualifications, and strict complementarity, for linear cone optimization problems in finite dimensions. These results include: weakest and universal constraint qualifications, \CQs; duality and characterizations of optimality that hold without any \CQ; geometry of {\em nice and devious} cones; the geometric relationships between zero duality gaps, strict complementarity, and the facial structure of cones; and, the connection between theory and empirical evidence for lack of a \CQ and failure of strict complementarity.

One theme is the notion of {\em minimal representation} of the cone and the constraints in order to regularize the problem and avoid both the theoretical and numerical difficulties that arise due to (near) loss of a \CQ. We include a discussion on obtaining these representations efficiently. A parallel theme is the loss of strict complementarity and the corresponding theoretical and numerical difficulties that arise; a discussion on avoiding these difficulties is included. We include results and examples on the surprising theoretical connection between duality and complementarity and nonclosure of sums of closed cones.

Our emphasis is on results that deal with Semidefinite Programming, \SDP.

• STATUS: number="2", volume = "53", URL = "COAP DOI: 10.1007/s10589-012-9480-0", journal = "coap", pages = "619-648", year="2012".
• DATE OF ENTRY: Aug 2008

On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming , May 2007.

• FORMAT: pdf file; alternate/official pdf file
• Number of Pages: 33
• author
• Yichuan Ding (Masters thesis)
• abstract:
• Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the S-Procedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form $\tr(X^TQX + 2C^T X) + \beta$, and $\tr(X^TQX + XPX^T + 2C^T X)+ \beta$ respectively, where $X$ is an $n$ by $r$ real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.
• STATUS: submitted
• DATE OF ENTRY: May 2007

Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization , Oct. 28, 2008.

• oct 27/08 (longer) version with appendix FORMAT: pdf file
• Number of Pages: 33
• Title: Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization (From the issue entitled "Special Issue: Optimization and Engineering Applications / Guest Edited by K. Kostina and J. Martins")
• authors
• Yichuan Ding, Nathan Krislock, Jiawei Qian, Henry Wolkowicz
• abstract:
• We study Semidefinite Programming, \SDPc relaxations for Sensor Network Localization, \SNLc with anchors and with noisy distance information. The main point of the paper is to view \SNL as a (nearest) Euclidean Distance Matrix, \EDM, completion problem and to show the advantages for using this latter, well studied model. We first show that the current popular \SDP relaxation is equivalent to known relaxations in the literature for \EDM completions. The existence of anchors in the problem is {\em not} special. The set of anchors simply corresponds to a given fixed clique for the graph of the \EDM problem. We next propose a method of projection when a large clique or a dense subgraph is identified in the underlying graph. This projection reduces the size, and improves the stability, of the relaxation. In addition, viewing the problem as an \EDM completion problem yields better low rank approximations for the low dimensional realizations. And, the projection/reduction procedure can be repeated for other given cliques of sensors or for sets of sensors, where many distances are known. Thus, further size reduction can be obtained. Optimality/duality conditions and a primal-dual interior-exterior path following algorithm are derived for the \SDP relaxations We discuss the relative stability and strength of two formulations and the corresponding algorithms that are used. In particular, we show that the quadratic formulation arising from the \SDP relaxation is better conditioned than the linearized form, that is used in the literature and that arises from applying a Schur complement.
• STATUS: Optimization and Engineering Volume 11, Number 1, 45-66, DOI: 10.1007/s11081-008-9072-0, and direct link
• DATE OF ENTRY: Dec. 2006 /revised Oct/08;

Numerical Stability in LP and SDP (pdf file local copy) , Oct. 2006.

• FORMAT: pdf file - preliminary version and UofW library link
• Number of Pages: 155
• Title: Numerical Stability in LP and SDP (PhD thesis of Hua Wei)
• authors
• Hua Wei (supervisor Henry Wolkowicz)

• abstract:
• We study numerical stability for interior-point methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the ill-conditioning that arises is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only $10^{-8}$ when the machine precision on a 32-bit computer is approximately $10^{-16}$. We then propose a simple alternative approach for the normal equation based interior-point method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve well-conditioned, huge, sparse problems, by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking. Finally, we present an algorithm to construct SDP problem instances with prescribed complementarity gaps. We then introduce two {\em measures of complementary gaps}. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is {\em no} correlation between the complementarity gaps and the geometrical measure used in \cite{ord5106}, or with Renegar's condition number.
• STATUS: accepted
• DATE OF ENTRY: Oct. 2006

Large Scale Portfolio Optimization with Piecewise Linear Transaction Costs , Sept, 2006.

• FORMAT: pdf file
• Number of Pages: 40
• Title: Large Scale Portfolio Optimization with Piecewise Linear Transaction Costs
• authors
• Marina Potaptchik, Levent Tuncel, Henry Wolkowicz

• abstract:
• We consider the fundamental problem of computing an optimal portfolio based on a quadratic mean-variance model of the objective function and a given polyhedral representation of the constraints. The main departure from the classical quadratic programming formulation is the inclusion in the objective function of piecewise linear, separable functions representing the transaction costs. We handle the nonsmoothness in the objective function by using spline approximations. The problem is then solved using a primal-dual interior-point method with a crossover to an active set method. Our numerical tests show that we can solve large scale problems efficiently and accurately.
• STATUS: submitted
• DATE OF ENTRY: Sept, 2006

A Low Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem , Sept, 2006.

• FORMAT: pdf file and a directory of MATLAB files
• Number of Pages: 22
• Title: A Low Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem
• authors
• Yichuan Ding, Henry Wolkowicz

• abstract:
• The quadratic assignment problem (\QAP) is arguably one of the hardest of the NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch and bound methods, which rely on obtaining \emph{strong and inexpensive} bounds. In this paper we introduce a new semidefinite programming (\SDP) relaxation for generating bounds for the \QAP in the trace formulation $\min_{X \in \Pi} \tr AXBX^T + CX^T$. We apply majorization to obtain a relaxation of the orthogonal similarity set of the matrix $B$. This exploits the matrix structure of \QAP and results in a relaxation with $O(n^2)$ variables, a much smaller dimension than other current \SDP relaxations. We compare the resulting bounds with several other computationally inexpensive bounds, such as the convex quadratic programming relaxation (\QPB). We find that our method provides stronger bounds on average and is adaptable for branch and bound methods.
• STATUS: appeared in MOR, Nov. 2009 (pdf file here)
• DATE OF ENTRY: Sept, 2006

Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors , May, 2006.

• FORMAT: pdf file
• Number of Pages: 47
• Title: Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors
• authors
• Nathan Krislock, Veronica Piccialli, Henry Wolkowicz

• abstract:
• We derive a robust primal-dual interior-point algorithm for a semidefinite programming, \SDP, relaxation for sensor localization with anchors and with noisy distance information. The relaxation is based on finding a {\em Euclidean Distance Matrix, \EDM,} that is nearest in the Frobenius norm for the known noisy distances and that satisfies given upper and lower bounds on the unknown distances. We show that the \SDP relaxation for this nearest \EDM problem is usually underdetermined and is an ill-posed problem. Our interior-point algorithm exploits the structure and maintains exact feasibility at each iteration. High accuracy solutions can be obtained despite the ill-conditioning of the optimality conditions. \noindent Included are discussions on the strength and stability of the \SDP relaxations, as well as results on invariant cones related to the operators that map between the cones of semidefinite and Euclidean distance matrices.
• STATUS: submitted
• DATE OF ENTRY: May, 2006

Multi-Stage Investment Decision under Contingent Demand for Networking Planning , Mar. 2006.

• FORMAT: pdf file
• Number of Pages: 20
• Title: Multi-Stage Investment Decision under Contingent Demand for Networking Planning
• authors
• Miguel F. Anjos, Michael Desroches, Anwar Haque, Oleg Grodzevich, Hua Wei, Henry Wolkowicz

• abstract:
• Telecommunication companies, such as Internet and cellular service providers, are seeing rapid and uncertain growth of traffic routed through their networks. It has become a challenge for these companies to make optimal decisions for equipment purchase that simultaneously satisfy the uncertain future demand while minimizing investment cost. This paper presents a decision-making framework for installing the required equipment into the networks while in the uncertain environment. The framework is based on new multi-stage stochastic programming mathematical models that capture the complexity of the individual Central Office (CO) decision-making process. The models are solved using the on-line NEOS server. Two examples are presented to illustrate the procedure. The optimization model also addresses the equipment pricing problem, i.e., what premium is worth paying for shorter installation times.
• STATUS: to appear in Proceedings of the 2006 IEEE GLOBECOM Conference in San Francisco
• DATE OF ENTRY: Mar. 2006

Generating and Measuring Instances of Hard Semidefinite Programs , January, 2006.

• FORMAT: pdf file
• Number of Pages: 20
• Title: Generating and Measuring Instances of Hard Semidefinite Programs
• authors
• Hua Wei and Henry Wolkowicz

• abstract:
• Linear Programming, \LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, \SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification, e.g Slater's condition (strict feasibility) holds. And, there exist \SDP problems which have a zero duality gap but no strict complementary primal-dual optimal solution. We refer to these problems as {\em hard instances} of \SDP. In this paper, we introduce a procedure for generating hard instances of \SDP. We then introduce two {\em measures of hardness} and illustrate empirically that these measures correlate well with the size of the gap in strict complementarity as well as with the asymptotic local convergence rate, and also with the number of iterations required to obtain optimal solutions to a specified accuracy. In addition, our numerical tests show that no correlation exists between the complementarity gaps and recently introduced geometrical measures or with Renegar's condition number. We include tests on the \SDPLIB problem set.
• STATUS: to appear in Mathematical Programming, 2009, volume 125, number 1, Page31 - 45 DOI10.1007/s10107-008-0256-3 Online since December 19, 2008
• DATE OF ENTRY: Jan. 2006
• software

Regularization Using a Parameterized Trust Region Subproblem , January, 2005.

• FORMAT: pdf file - preliminary version
• Number of Pages: 77
• Title: Regularization Using a Parameterized Trust Region Subproblem (Master's thesis of Oleg Grodzevich)
• authors
• Oleg Grodzevich (supervisor Henry Wolkowicz)

• abstract:
• We present a new method for regularization of ill-conditioned problems that extends the traditional trust-region approach. Ill-conditioned problems arise, for example, in image restoration or mathematical processing of medical data, and involve matrices that are very ill-conditioned. The method makes use of the L-curve and L-curve maximum curvature criterion as a strategy recently proposed to find a good regularization parameter. We describe the method and show its application to an image restoration problem. We also provide a MATLAB code for the algorithm. Finally, a comparison to the CGLS approach is given and analyzed, and future research directions are proposed.
• STATUS: accepted
• DATE OF ENTRY: Dec. 2005

Some Necessary and Some Sufficient Trace Inequalities for Euclidean Distance Matrices , CORR 2005-21, Dec, 2005.

• FORMAT: pdf file
• Number of Pages: 7
• Title: Some Necessary and Some Sufficient Trace Inequalities for Euclidean Distance Matrices
• authors
• Abdo Alfakih and Henry Wolkowicz

• abstract:
• In this paper, we use known bounds on the smallest eigenvalue of a symmetric matrix and Schoenberg's Theorem to provide both necessary as well as sufficient trace inequalities that guarantee a matrix $D$ is a Euclidean distance matrix, \EDM\hspace{-.04in}. We also provide necessary and sufficient trace inequalities that guarantee a matrix $D$ is an \EDM generated by a regular figure.
• STATUS: LAMA, 2007, pages = "499--506", volume = "55", number = "5".
• DATE OF ENTRY: Dec. 2005

Regularization Using a Parameterized Trust Region Subproblem , CORR 2005-11, May, 2005.

• FORMAT: pdf file
• Number of Pages: 37
• Title: Regularization Using a Parameterized Trust Region Subproblem
• authors
• Oleg Grodzevich and Henry Wolkowicz

• abstract:
• We present a new method for regularization of ill-conditioned problems, such as those that arise in image restoration or mathematical processing of medical data. The method extends the traditional {\em trust-region subproblem}, \TRS, approach that makes use of the {\em L-curve} maximum curvature criterion, a strategy recently proposed to find a good regularization parameter. We use derivative information, and properties of an algorithm for solving the TRS, to efficiently move along points on the L-curve and reach the point of maximum curvature. We do not find a complete characterization of the L-curve. A MATLAB code for the algorithm is tested and a comparison to the conjugate gradient least squares, CGLS, approach is given and analyzed.
• STATUS: Mathematical Programming, pages = "193-220", volume = "116", year="2009".
• DATE OF ENTRY: May. 2005

A Stable Iterative Method for Linear Programming (ps file) and pdf file, Oct., 2004/revised Mar, 2007.

• Number of Pages: 41
• Title: A Stable Iterative Method for Linear Programming changed to: A stable primal-dual approach for linear programming under nondegeneracy assumptions
• authors
• Maria Gonzalez-Lima, Hua Wei, Henry Wolkowicz

• Abstract:
• This paper studies a new primal-dual interior/exterior-point method for linear programming. We begin with the usual perturbed primal-dual optimality equations $F_\mu(x,y,z)=0$. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. We use a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in one single bilinear equation that maintains the well-posedness property. We then apply a preconditioned conjugate gradient method (PCG), within an inexact Newton framework, directly on the linearized equations. This is done without forming the usual {\em normal equations, NEQ,} or {\em augmented} system. Sparsity is maintained. The work of an iteration consists almost entirely in the (approximate) solution of this well-posed linearized system, using PCG. Therefore, improvements depend on efficient preconditioning. Exact primal and dual feasibility are guaranteed throughout the iterations when starting feasible.

Since the linearization is well posed, standard preconditioners can be applied. And we can use affine scaling and not maintain positivity once we are close enough to the optimum, i.e. we apply a {\em crossover} technique. This allows for {\em warm starts} with perturbed data. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). Therefore, we get smaller systems as the iterations progress. These techniques reduce the number and complexity of the iterations.

We present numerical examples where roundoff error causes problems for NEQ and present numerical tests with direct solvers as well as iterative solvers with both {\em diagonal} and {\em Cholesky type} preconditioners. Our tests show that our method takes direct advantage of sparsity and stability of the data. We include warm start tests for perturbed problems.

• DATE OF ENTRY: Oct, 2004; revision mar/07  appeared in COAP in Apr./09 (pdf file here) also online version at: online first, DOI: 10.1007/s10589-007-9157-2

Essay on: The Kronecker Product Mar., 2004.

• pdf file, Number of Pages: 35
• Title: Essay on: The Kronecker Product
• authors
• Kathrin Schaeke

• Abstract:
• In this paper, we review basic properties of the Kronecker product, and give an overview of its history and applications. We then move on to introducing the symmetric Kronecker product, and we derive several of its properties. Furthermore, we show its application in finding search directions in semidefinite programming.
• DATE OF ENTRY: Apr, 2004

Approximate and Exact Completion Problems for Euclidean Distance Matrices using Semidefinite Programming Apr., 2004.

(and pdf file)
• Number of Pages: 40
• Title: Approximate and Exact Completion Problems for Euclidean Distance Matrices using Semidefinite Programming
• authors
• Suliman Al-Homidan, Henry Wolkowicz

• Abstract:
• A partial pre-distance matrix $A$ is a matrix with zero diagonal and with certain elements {\em fixed} to given nonnegative values; the other elements are considered {\em free}. The \edm\ completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, \EDM\@. The nearest (or approximate) \edm\ problem is to find a Euclidean distance matrix, \EDM\@, that is nearest in the Frobenius norm to the matrix $A$, when the free variables are discounted.
In this paper we introduce two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of \EDM into a semidefinite programming problem, \SDP\@. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the \EDM and \SDP cones invariant.
We briefly discuss numerical tests.
• Mathematical Review
• STATUS: Linear Algebra and its Applications, 2005, vol 406 109-141
• DATE OF ENTRY: Apr, 2004

Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming, July., 2003.

• Number of Pages: 32
• Title: Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming
• authors
• Levent Tuncel, Henry Wolkowicz

• Abstract:
• Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is the AHO direction. However, in contrast to the LP case, existence and uniqueness of the AHO search direction is not guaranteed under the standard nondegeneracy assumptions. Two different sufficient conditions are known that guarantee the existence and uniqueness independent of the specific linear constraints. The first is given by Shida-Shindoh-Kojima and is based on the semidefiniteness of the symmetrization of the product $SX$ at the current iterate. The second is a centrality condition given by Monteiro-Zanj{\'a}como. In this paper, we revisit and strengthen both of the above mentioned sufficient conditions. We include characterizations for existence and uniqueness in the matrix equations arising from the linearization of the optimality conditions. As well, we present new results on the relationship between the Kronecker product and the {\em symmetric Kronecker product} that arise from these matrix equations. We conclude with a proof that the existence and uniqueness of the AHO direction is a generic property for every SDP problem and extend the results to the general Monteiro-Zhang family of search directions.
• ???Mathematical Review
• STATUS: LAA, vol 400, 2005, pages 31-60.
• DATE OF ENTRY: July 23, 2003

MSc thesis of Mike Froh, Dec. 2003.

• FORMAT: pdf file
• Number of Pages: 76
• Title: Trust Region Subproblems and Linear Least-Squares Regularization
• authors: Mike Froh

• Abstract: Solving an ill-conditioned linear least-squares problem, minimizing the norm of the residual vector, in practice often yields a solution which may differ significantly from the true" solution, particularly when the right-hand side is subject to noise. By finding the solution of minimum norm, subject to some tolerance on the norm of the residual, we find a smoother" solution, which, in practice, may be closer to the true solution. In this work, we make use of the fact that this process of regularization is a special case of the Trust-Region Subproblem (TRS), and apply the work of Rendl and Wolkowicz to derive a new method for computing a regularized solution by computing an eigenpair. The technique exploits sparsity, and scales well to large problems.
• STATUS: accepted
• DATE OF ENTRY: Dec , 2003

Novel Approaches to Hard Discrete Optimization April., 2003.

• Number of Pages: 181
• Title: Novel Approaches to Hard Discrete Optimization
• Editors
• Panos Pardalos, Henry Wolkowicz

• preface:
• This volume contains refereed papers presented at the workshop on "Novel Approaches to hard Discrete Optimization" held at the Univ. of Waterloo during April 2001.
• Mathematical Review
• STATUS: Kluwer Academic Publishers - 2003
• DATE OF ENTRY: May 3, 2003
• A Survey of the Trust Region Subproblem Within a Semidefinite Programming Framework, August, 2002.

• related TRS software
• Mar/03 version pdf file number of Pages: 42; with Mar/03 version ps file number of Pages: 42; and August/02 version number of Pages: 76
• Title: A Survey of the Trust Region Subproblem Within a Semidefinite Programming Framework
• authors: Charles Fortin, Henry Wolkowicz
• abstract
The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for their strong convergence properties. However, a drawback has been the inability to exploit sparsity as well as the difficulty in dealing with the so-called hard case. These concerns have been addressed by recent advances in the theory and algorithmic development.

This paper provides an in depth study of TRS and its properties as well as a survey of recent advances. We emphasize large scale problems and robustness. This is done using semidefinite programming (SDP) and the modern primal-dual approaches as a unifying framework. The SDP framework solves TRS efficiently; and it shows that TRS is always a well-posed problem, i.e. the optimal value and an optimum can be calculated to a given tolerance. This is contrary to statements in the literature which label TRS ill-posed or degenerate, if the so-called hard case holds. We provide both theoretical and empirical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights and techniques for handling the hard case.

• CORR Report 2002-22
• STATUS: published in OMS 2003
• DATE OF ENTRY: Aug. 28, 2002

A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming, July, 2002.

• Number of Pages: 24
• Title: A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming
• authors: Franz Rendl, Renata Sotirov, Henry Wolkowicz
• abstract
Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the SDP relaxations of NP-hard problems, a simple primal-dual feasible starting point is available. In theory, the Newton type search directions maintain feasibility. However, in practice it is assumed that roundoff-error must be taken into account and the residuals are used to recover feasibility.

We introduce preprocessing for SDP to obtain a modified HKM direction. This direction attains {\em exact primal and dual feasibility} throughout the iterations while: setting the residuals to 0; reducing the arithmetic expense; maintaining the same iteration counts for well-conditioned problems; and reducing the iteration count for ill-conditioned problems. We apply the technique to the Max-Cut, Lov\'asz Theta, and Quadratic Assignment problems. We include an illustration on an ill-conditioned two dimensional problem, a discussion on convergence, and a similar simplification for the Monteiro-Zhang family of search directions.

This paper can serve as an introduction to both the HKM search direction and preprocessing (presolve) for SDP.

• CORR Report 2002-16
• STATUS: submitted
• DATE OF ENTRY: Aug. 12, 2002

Semidefinite Programming, July, 2002.

• Number of Pages: 16
• Title: Semidefinite Programming
• authors: Henry Wolkowicz
• abstract
Semidefinite Programming, denoted SDP, has been studied (under various names) as far back as the 1940s. The interest has grown tremendously since the early 1990s and it is currently considered to be the hottest area in Optimization. The research activity was motivated by the discovery of new applications in several areas, combined with the development of efficient new algorithms. This article serves as an introduction to the basics of SDP.
• CORR Report 2002-4
• STATUS: invited article Encyclopedia of Statistical Sciences
• DATE OF ENTRY: July. 16, 2002

Euclidean Distance Matrices and the Molecular Conformation Problem, July, 2002.

• Number of Pages: 6
• Title: Euclidean Distance Matrices and the Molecular Conformation Problem
• authors: Abdo Alfakih and Henry Wolkowicz

• CORR Report 2002-17
• STATUS: submitted to SIAM/SIAG-OPT Newsletter
• DATE OF ENTRY: July. 15, 2002

A Simple Iterative Method for Linear Programming, CORR 2001-66, Dec. 15, 2001.

• FORMATs: (with hyperlinks) gzipped pdf file and gzipped ps file
• Web Page with Available Software and Latest Numerical Test Results: The numerical tests were done using MATLAB 6. The matlab files are available in this directory.
• Number of Pages: 30
• Title: A Simple Iterative Method for Linear Programming
• authors: Maria Gonzalez-Lima and Henry Wolkowicz

• Abstract: This paper presents a new primal-dual interior/exterior-point method for linear programming. We begin with the usual perturbed primal-dual optimality equations $F_\mu(x,y,z)=0$. Under nondegeneracy assumptions, this nonlinear system is well-conditioned, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. We apply preprocessing to obtain one single bilinear equation which is also well-conditioned. We then apply a preconditioned conjugate gradient method (PCG), within an inexact Newton framework, directly on the linearized equations. This is done without forming the {\em normal equations} system. The work of an iteration consists almost entirely in the (approximate) solution of this well-conditioned linearized system, using PCG. Therefore, improvements depend on efficient preconditioning. In the sparse case, the linearized system consists of a large sparse part and a small dense part. Primal and dual feasibility are 100\% guaranteed throughout the iterations. Since the linearization is well conditioned, we can use affine scaling and not maintain positivity once we are close enough to the optimum. In addition, we identify some of the primal and dual variables which are converging to 0 and delete them. Therefore, we get smaller systems as the iterations progress. These techniques reduce the number and complexity of the iterations. We present numerical tests with both {\em diagonal} and {\em partial Cholesky} preconditioners.
• STATUS: inprogress
• DATE OF ENTRY: Dec. 14, 2001

Solving Semidefinite Programs using Preconditioned Conjugate Graditents CORR 2001-49, April. 2003.

is a revision of the paper

Simple Efficient Solutions for Semidefinite Programming, CORR 2001-49, Sept. 6, 2001.

• FORMATs: (with hyperlinks) gzipped pdf file and gzipped ps file (see appendix for latest numerical tests)
• Web Page with Available Software and Latest Numerical Test Results: The numerical tests were done using MATLAB 6. The matlab files are available in this directory.
• Number of Pages: 20
• Title: Simple Efficient Solutions for Semidefinite Programming
• authors: Henry Wolkowicz

• Abstract: This paper provides a simple approach for solving a semidefinite program, SDP\@. As is common with many other approaches, we apply a primal-dual method that uses the perturbed optimality equations for SDP, $F_\mu(X,y,Z)=0$, where $X,Z$ are $n \times n$ symmetric matrices and $y \in \Re^m$. However, we look at this as an overdetermined system of nonlinear (bilinear) equations on vectors $X,y,Z$ which has a zero residual at optimality. We do not use any symmetrization on this system. That the vectors $X,Z$ are symmetric matrices is ignored. What is different in this paper is a preprocessing step that results in one single, well-conditioned, overdetermined bilinear equation. We do not form a Schur complement form for the linearized system. In addition, asymptotic q-quadratic convergence is obtained with a {\em crossover} approach that switches to affine scaling without maintaining the positive (semi)definiteness of $X$ and $Z$. This results in a marked reduction in the number and the complexity of the iterations.

We use the long accepted method for nonlinear least squares problems, the Gauss-Newton method. For large sparse data, we use an {\em inexact Gauss-Newton} approach with a preconditioned conjugate gradient method applied directly on the linearized equations in matrix space. This does not require any operator formations into a Schur complement system or matrix representations of linear operators. The cost of an iteration consists almost entirely in the solution of a (generally well-conditioned) least squares problem of size $n^2 \times \pmatrix{n+1\cr 2}$. This system consists of one large (sparse) block with $\pmatrix{n\cr 2}$ columns (one CG iteration cost is one sparse matrix multiplication) and one small (dense) block with $n$ columns (one CG iteration cost is one matrix row scaling). Exact primal and dual feasibility are guaranteed throughout the iterations.

To illustrate the approach, we apply it to the well known SDP relaxation of the Max-Cut problem. This includes the derivation of the {\em optimal diagonal preconditioner}. The numerical tests show that the algorithm exploits sparsity and obtains q-quadratic convergence.

• STATUS: volume 19, number 1, OMS, 2004 - accepted Dec./03
• DATE OF ENTRY: Sept. 6, 2001

Geometry of Semidefinite Max-Cut Relaxations via Ranks June, 2001.

• FORMAT: gzipped pdf file
• Number of Pages: 42
• Title: Geometry of Semidefinite Max-Cut Relaxations via Ranks
• authors
• Miguel F. Anjos and Henry Wolkowicz

• abstract:
• Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice. Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let ${\cal F}_n$ denote the feasible set of SDP2 for the complete graph with $n$ nodes, let $F_n$ denote the appropriately defined projection of ${\cal F}_n$ into $\Sn$, the space of real symmetric $n \times n$ matrices, and let $C_n$ denote the cut polytope in $\Sn$. Further let $Y \in {\cal F}_n$ be the matrix variable of the SDP2 relaxation and $X \in F_n$ be its projection. Then for the complete graph on 3 nodes, $F_3 = C_3$ holds. We prove that the rank of the matrix variable $Y \in {\cal F}_3$ of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix $X$ lies. This shows explicitly the connection between the rank of the variable $Y$ of the second lifting and the possible locations of the projected matrix $X$ within $C_3$. The results we prove for $n=3$ cast further light on how SDP2 captures all the structure of $C_3$, and furthermore they are stepping stones for studying the general case $n \geq 4$. For this case, we show that the characterization of the vertices of the cut polytope via $\rank Y = 1$ extends to all $n \geq 4$. More interestingly, we show that the characterization of the one-dimensional faces via $\rank Y = 2$ also holds for $n \geq 4$. Furthermore, we prove that if $\rank Y = 2$ for $n \geq 3$, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where $X$ lies. lin {\cal F}_n$be the matrix variable of the SDP2 relaxation and$X \in F_n$be its projection. Then for the complete graph on 3 nodes,$F_3 = C_3$holds. We prove that the rank of the matrix variable$Y \in {\cal F}_3$of SDP2Further let$Y \in {\cal F}_n$be the matrix variable of the SDP2 relaxation and$X \in F_n$be its projection. Then for the complete graph on 3 nodes,$F_3 = C_3$holds. We prove that the rank of the matrix variable$Y \in {\cal F}_3$of SDP2. STATUS: submitted • appeared in: HANDBOOK OF APPLIED OPTIMIZATION, (Oxford Univ. Press, 2002) • DATE OF ENTRY: June 14, 2001 Two Theorems On Euclidean Distance Matrices and Gale Transform Jan, 2001. • FORMAT: gzipped pdf file • Number of Pages: 8 • Title: Two Theorems On Euclidean Distance Matrices and Gale Transform • authors • A. Alfakih and H. Wolkowicz, • abstract: • We present a characterization of those Euclidean distance matrices$D$which can be expressed as$D= \lambda (E - C)$for some nonnegative scalar$\lambda$and some correlati on matrix$C$, where$E$is the matrix of all ones. This shows that the cones $\cone \left(E-\EE_n \right) \, {\neq} \, \overline{\cone \left(E-\EE_n \right)} =\DD_n,$ where$\EE_n$is the elliptope (set of correlation matrices) and$\DD_n$is the (closed convex) cone of Euclidean distance matrices. The characterization is given using the Gale transform of the points generating$D$. We also show that given points$p^1$,$p^2$, \ldots,$p^n \in \Re^r$, for any scalars$\lambda_1$,$\lambda_2$, \ldots,$\lambda_n$such that $\sum_{j=1}^n \lambda_j \; p^j = 0, \;\;\;\;\;\;\; \sum_{j=1}^n \lambda_j = 0,$ we have $\sum_{j=1}^n \lambda_j \; \| p^i - p^j \|^2 = \alpha \mbox{ for all } i=1,\ld ots,n,$ for some scalar$\alpha$independent of$i$. • STATUS: To appear in LAA • DATE OF ENTRY: Jan 30, 2001 Semidefinite Programming for Discrete Optimization and Matrix Completion Problems, June, 2000. • FORMAT: gzipped pdf file • Number of Pages: 88 • Title: Semidefinite Programming for Discrete Optimization and Matrix Completion Problems, • authors • M. Anjos and H. Wolkowicz, • abstract: • Semidefinite Programming (SDP) is currently one of the most active areas of research in optimization. SDP has attracted researchers from a wide variety of areas because of its theoretical and numerical elegance as well as its wide applicability. In this paper we present a survey of two major areas of application for SDP, namely discrete optimization and matrix completion problems. In the first part of this paper we present a recipe for finding SDP relaxations based on adding redundant constraints and using Lagrangian relaxation. We illustrate this with several examples. We first show that many relaxations for the Max-Cut problem (MC) are equivalent to both the Lagrangian and the well-known SDP relaxation. We then apply the recipe to obtain new strengthened SDP relaxations for MC as well as known SDP relaxations for several other hard discrete optimization problems. In the second part of this paper we discuss two completion problems, the positive semidefinite and the Euclidean distance matrix completion problem. We present some theoretical results on the existence of such completions and then proceed to the application of SDP to find approximate completions. We conclude this paper with a new application of SDP to find approximate matrix completions for large and sparse instances of Euclidean distance matrices. • STATUS: among the top 25 requested papers in Discrete Applied Mathematics for the period April 2002 - April 2004. • DATE OF ENTRY: June 29, 2000 New Convex Relaxations for the Maximum Cut and VLSI Layout Problems , (PhD thesis of Miguel Anjos), May. 1, 2001. • FORMAT: gzipped pdf file • Number of Pages: 205 • Title: New Convex Relaxations for the Maximum Cut and VLSI Layout Problems • authors: Miguel Anjos • Abstract: It is well known that many of the optimization problems which arise in applications are hard'', which usually means that they are NP-hard. Hence much research has been devoted to finding good'' relaxations for these hard problems. Usually a good'' relaxation is one which can be solved (either exactly or within a prescribed numerical tolerance) in polynomial-time. Nesterov and Nemirovskii \cite{int:Nesterov5} showed that by this criterion, many convex optimization problems are good relaxations. This thesis introduces two new approaches for constructing convex relaxations for hard optimization problems. • STATUS: accepted • DATE OF ENTRY: May 1, 2001 High Accuracy Algorithms for the Solutions of Semidefinite Linear Programs, (PhD thesis of Serge Kruk), Feb. 25, 2001. • FORMAT: gzipped pdf file and link to library • Number of Pages: 134 • Title: High Accuracy Algorithms for the Solutions of Semidefinite Linear Programs • authors: Serge Kruk • Abstract: We present a new family of search directions and of corresponding algorithms to solve conic linear programs. The implementation is specialized to semidefinite programs but the algorithms described handle both nonnegative orthant and Lorentz cone problems and Cartesian products of these sets. The primary objective is not to develop yet another interior-point algorithm with polynomial time complexity. The aim is practical and addresses an often neglected aspect of the current research in the area, accuracy. Secondary goals, tempered by the first, are numerical efficiency and an efficient handling of sparsity. The main search direction, called Gauss-Newton, is obtained as a least-squares solution to the optimality condition of the log-barrier problem. This motivation ensures that the direction is well-defined everywhere and that the underlying Jacobian is well-conditioned under standard assumptions. Moreover, it is invariant under affine transformation of the space and under orthogonal transformation of the constraining cone. The Gauss-Newton direction, both in the special cases of linear programming and on the central path of semidefinite programs, coincides with the search directions used in practical implementations. Finally, it may be viewed as a generalization of most search directions in use today since the Monteiro-Zhang family can be derived as scaled projections of the Gauss-Newton direction. • STATUS: accepted • DATE OF ENTRY: Feb 25, 2001 Semidefinite Programming for Discrete Optimization and Matrix Completion Problems, June, 2000. • FORMAT: gzipped ps file • Number of Pages: 88 • Title: Semidefinite Programming for Discrete Optimization and Matrix Completion Problems, • authors • M. Anjos and H. Wolkowicz, • abstract: • Semidefinite Programming (SDP) is currently one of the most active areas of research in optimization. SDP has attracted researchers from a wide variety of areas because of its theoretical and numerical elegance as well as its wide applicability. In this paper we present a survey of two major areas of application for SDP, namely discrete optimization and matrix completion problems. In the first part of this paper we present a recipe for finding SDP relaxations based on adding redundant constraints and using Lagrangian relaxation. We illustrate this with several examples. We first show that many relaxations for the Max-Cut problem (MC) are equivalent to both the Lagrangian and the well-known SDP relaxation. We then apply the recipe to obtain new strengthened SDP relaxations for MC as well as known SDP relaxations for several other hard discrete optimization problems. In the second part of this paper we discuss two completion problems, the positive semidefinite and the Euclidean distance matrix completion problem. We present some theoretical results on the existence of such completions and then proceed to the application of SDP to find approximate completions. We conclude this paper with a new application of SDP to find approximate matrix completions for large and sparse instances of Euclidean distance matrices. • STATUS: submitted • DATE OF ENTRY: June 29, 2000 Convergence of an infeasible short-step path-following algorithm based on the Gauss-Newton direction , April, 2000. • FORMAT: gzipped ps file ( and pdf file) • Number of Pages: 15 • Title: Convergence of an infeasible short-step path-following algorithm based on the Gauss-Newton direction • authors • Serge Kruk and Henry Wolkowicz • abstract: • This short note proves the polynomial time convergence of a short step, approximate path following, interior-point primal-dual algorithm for semidefinite programs based on the Gauss-Newton direction obtained from minimizing the norm of the perturbed optimality conditions. This is the first proof of convergence for the Gauss-Newton direction. The proof relies solely on classical results of nonlinear optimization and does not explicitly require feasibility or positive definiteness of the iterates. • STATUS: pages = "517-534", volume = "10 ", year "2003" • Journal of Applied Mathematics (contents) • DATE OF ENTRY: Apr. 28, 2000, revised Apr. 9, 2003 A Survey of the Trust Region Subproblem within a Semidefinite Framework , April, 2000. • FORMAT: gzipped ps file; or a pdf file related TRS software • Number of Pages: 115 • Title: A Survey of the Trust Region Subproblem within a Semidefinite Framework (Master's thesis of Charles Fortin) • authors • Charles Fortin (supervisor Henry Wolkowicz) • abstract: • Trust region subproblems arise within a class of unconstrained methods called trust region methods. The subproblems consist of minimizing a quadrati c function subject to a norm constraint. This thesis is a survey of different methods developed to find an approximate solution to the subproblem. We study the well-known method of Mor\'{e} and Sorensen \cite{MoSo} and two recent methods for large sparse subproblems: the so-called Lanczos method of Gould et al. \cite{Gould} and the Rendl and Wolkowicz algorithm \cite{RW}. The common ground to explore these methods will be semidefinite programming. This approach has been used by Rendl and Wolkowicz \cite{RW} to explain their method and the Mor\'{e} and Sorensen algorithm; we extend this work to the Lanczos method. The last chapter of this thesis is dedicated to some improvements done to the Rendl and Wolkowicz algorithm and to comparisons between the Lanczos method and the Rendl and Wolkowicz algorithm. In particular, we show some weakness of the Lanczos method and show that the Rendl and Wolkowicz algorithm is more robust. • STATUS: accepted • DATE OF ENTRY: Apr. 19, 2000 The Trust Region Subproblem and Semidefinite Programming , 2004. • FORMAT: gzipped ps file; or a pdf file related TRS software • Number of Pages: 26 • Title: The Trust Region Subproblem and Semidefinite Programming • authors: Charles Fortin and Henry Wolkowicz • abstract: • The trust region (TR) subproblem (the minimization of a qua dratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g., function minimization, seque ntial quadratic programming, regularization, ridge regression, and discrete optimiza tion. In particular, it determines the step in TR algorithms for function minimization. Trust region algorithms are popul ar for their strong convergence properties. However, a drawback has been the inability to exploit sparsity as well as the difficulty in dealing with the so-called hard case. These concerns have been addressed by recent advances in the theory and algorithmic development. In particular, this has allowed Lanczos techniques to replace Cholesky factorizations. This article provides an in depth study of TRS and its properties as well as a survey of recent advances. We emphasize large scale problems and robustness. This is done using semidefinite progr amming (SDP) and the modern primal?dual approaches as a unifying framework. The SDP fra mework arises naturally and solves TRS efficiently. In addition, it shows that TRS is always a well-posed problem, i .e., the optimal value and an optimum can be calculated to a given tolerance. We provide both theoretical and empir ical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights and techniques for handling the hard case, as well as numerical results on large test problems • STATUS: appeared • DATE OF ENTRY: 2014 A Tight Semidefinite Relaxation of the Cut Polytope, March, 2000. • FORMAT: gzipped ps file and pdf file, • Number of Pages: 24 • Title: A Tight Semidefinite Relaxation of the Cut Polytope, • authors • M. Anjos and H. Wolkowicz, • abstract: • We present a tight semidefinite programming (SDP) relaxation for the max-cut problem (MC) which improves on several previous SDP relaxations in the literature. This new SDP relaxation is a tightening of the SDP relaxation recently introduced by the authors, and it inherits all the helpful properties of the latter. We show that it is a strict improvement over the SDP relaxation obtained by adding all the triangle inequalities to the well-known SDP relaxation. • STATUS: Merged with another paper and appeared as: M.F. Anjos and H. Wolkowicz. "Strengthened Semidefinite Relaxations via a Second Lifting for the Max-Cut Problem", Discrete Applied Mathematics, Vol. 119 (1-2), 2002, 79-106. • DATE OF ENTRY: Mar. 7, 2000 Semidefinite Programming Approaches to the Quadratic Assignment Problem, gzipped ps file, ( pdf file) December, 1999. • FORMAT: gzipped ps file • Number of Pages: 41 • Title: Semidefinite Programming Approaches to the Quadratic Assignment Problem, • authors • H. Wolkowicz, • abstract: • The Quadratic Assignment Problem, QAP, is arguably the hardest of the NP-hard problems. One of the main reasons is that it is very difficult to get good quality bounds for branch and bound algorithms. We show that many of the bounds that have appeared in the literature can be ranked and put into a unified Semidefinite Programming, SDP, framework. This is done using redundant quadratic constraints and Lagrangian relaxation. Thus, the final SDP relaxation ends up being the strongest. • STATUS: submitted • DATE OF ENTRY: Dec 9, 1999 Lack of Strong duality for Quadratic Problems with Orthogonal Constraints, gzipped ps file, pdf file) December, 1999. • FORMAT: gzipped ps file SDP • Number of Pages: 14 • Title: Lack of Strong Duality for Quadratic Problems with Orthogonal Constraints, • authors • H. Wolkowicz, • abstract: • The general quadratically constrained quadratic program (QQP) is an important modelling tool for many diverse problems. The QQP is in general NP hard, and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming (SDP) relaxations and can be solved efficiently. For several special cases of QQP, e.g. general convex quadratic programs and the trust region subproblems (one quadratic constraint), the Lagrangian relaxation provides the exact optimal value. This means that there is a zero duality gap and the problem is tractable. Surprisingly, there is another class of nonconvex problems with zero duality gaps. It has recently been shown, \cite{AnWo:98,AnChWoYu:98}, that the special homogeneous QQP with objective function that arises in the trace formulation of the quadratic assignment problem, and with quadratic constraints that correspond to the matrix orthogonality condition$XX\tran=I$(or the negative semidefinite condition$XX^T -I\preceq 0$) have zero duality gaps if one adds the seemingly redundant constraints$X\tran X=I$($X\tran X-I \preceq 0,$respectively). This special structured QQP is a special case of the {\em Procrustes Problem} where the objective has an inhomogeneous objective function. In this paper we show that the strong duality result does not hold for this more general problem. In fact, strong duality will fail for the simple pure linear objective case. We also show how to close the duality gap for this pure linear case. • STATUS: to appear in EJOR • DATE OF ENTRY: Dec 3, 1999, revised on Dec 5, 2001 Matrix Completion Problems, November, 1999. • FORMAT: in Handbook of SDP, Kluwer Academic, 2000 • Number of Pages: 11 • Title: Matrix Completion Problems, • authors • A. Alfakih, H. Wolkowicz, • abstract: • STATUS: Kluwer Academic Publishers - to appear in 2000 • DATE OF ENTRY: Nov 3, 1999 • Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, November, 1999. • FORMAT: in Handbook of SDP, Kluwer Academic, 2000 • Number of Pages: 57 • Title: Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, • authors • Y. Nesterov, H. Wolkowicz, Y. Ye. • abstract: • STATUS: Kluwer Academic Publishers - to appear in 2000 • DATE OF ENTRY: Nov 3, 1999 • Sequential, Quadratic Constrained, Quadratic Programming for General Nonlinear Programming, November, 1999. November, 1999. • FORMAT: in Handbook of SDP, Kluwer Academic, 2000 • Number of Pages: 11 • Title: Sequential, Quadratic Constrained, Quadratic Programming for General Nonlinear Programming, November, 1999. • authors • S. Kruk, H. Wolkowicz • abstract: • STATUS: Kluwer Academic Publishers - to appear in 2000 • DATE OF ENTRY: Nov 3, 1999 • HANDBOOK OF SEMIDEFINITE PROGRAMMING: Theory, Algorithms, and Applications Feb., 2000. • FORMAT: TOC gzipped postscript. • Number of Pages: 670 • Title: HANDBOOK OF SEMIDEFINITE PROGRAMMING: Theory, Algorithms, and Applications, Kluwer Academic, 2000. • Editors • H. Wolkowicz, R. Saigal, L. Vandenberghe, • preface: • Semidefinite programming (or SDP) has been one of the most exciting and active research areas in optimization during the 1990s. It has attracted researchers with very diverse backgrounds, including experts in convex programming, linear algebra, numerical optimization, combinatorial optimization, control theory, and statistics. This tremendous research activity was spurred by the discovery of important applications in combinatorial optimization and control theory, the development of efficient interior-point algorithms for solving SDP problems, and the depth and elegance of the underlying optimization theory. This book includes nineteen chapters on the theory, algorithms, and applications of semidefinite programming. Written by the leading experts on the subject, it offers an advanced and broad overview of the current state of the field. The coverage is somewhat less comprehensive, and the overall level more advanced, than we had planned at the start of the project. In order to finish the book in a timely fashion, we have had to abandon hopes for separate chapters on some important topics (such as a discussion of SDP algorithms in the framework of general convex programming using the theory of self-concordant barriers, or an overview of numerical implementation aspects of interior-point methods for SDP). We apologize for any important gaps in the contents, and hope that the historical notes at the end of the book provide a useful guide to the literature on the topics that are not adequately covered in this handbook. We would like to thank all the authors for their outstanding contributions, their editorial help, and for their patience during the many revisions of the handbook. In addition, we thank Mike Todd for his valuable editorial advice on many occasions. We would also like to thank The Natural Sciences Engineering Research Council Canada and The Fields Institute for their financial support, and Erna Unrau for her help in combining some of the bibliographies into one. • Table of contents • Mathematical Review • STATUS: Kluwer Academic Publishers - 2000 • DATE OF ENTRY: Nov 3, 1999 • Semidefinite and Lagrangian Relaxations for Hard Combinatorial Problems (for Proceedings of 19th IFIP TC7 CONFERENCE) July, 1999. • FORMAT: gzipped postscript. • Number of Pages: 36 • Title: Semidefinite and Lagrangian Relaxations for Hard Combinatorial Problems • Authors: • H. Wolkowicz • available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ proccambridge.ps.gz • ABSTRACT: Semidefinite Programming is currently a very exciting and active area of research. Semidefinite relaxations generally provide very tight bounds for many classes of numerically hard problems. In addition, these relaxations can be solved efficiently by interior-point methods. In this paper we study these semidefinite relaxations using the equivalent Lagrangian relaxations. In particular, the theme of the paper is to show that the Lagrangian relaxation is, in some respects, best. In all instances we consider, we show that whenever we have a tractable bound (relaxation), then the same bound can be obtained from a Lagrangian relaxation. • Mathematical Review • STATUS: Kluwer Academic Publishers, 2000. • DATE OF ENTRY: Dec 7, 1999 • Semidefinite Programming (for Appl. Math. Handbook) 1999. • FORMAT: gzipped postscript. • Number of Pages: 11 • Title: Semidefinite Programming (for Appl. Math. Handbook) • Authors: • H. Wolkowicz • available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ applhandbk.ps.gz • ABSTRACT: A short survey of Semidefinite Programming. • STATUS: To appear in The Handbook of Applied Mathematics, Kluwer Publ. • DATE OF ENTRY: Sept 26, 1999 • A Strengthened Relaxation via a Second Lifting for the Max-Cut Problem, 1999. • FORMAT: gzipped postscript. • Number of Pages: 11 • Title: A Strengthened Relaxation via a Second Lifting for the Max-Cut Problem • pdf file • Authors: • M. ANJOS and H. Wolkowicz • available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ strengthMC.ps.gz • ABSTRACT: We present a strengthened semidefinite programming, SDP, relaxation for the Max-Cut problem, MC, and for the general quadratic boolean maximization problem. The well-known SDP relaxation can be obtained via Lagrangian relaxation and results in an SDP with variable$X \in {\cal S}^n$, the space of$n \times n$symmetric matrices, and$n$constraints,$\diag(X)=e,$where$e$is the vector of ones. The strengthened bound is based on applying a {\em lifting procedure} to this well-known semidefinite relaxation after adding the nonlinear constraints$X^2-nX=0$and$X\circ X=E.$The lifting procedure is again done via Lagrangian relaxation and results in an SDP with variable$Y \in {\cal S}^{t(n-1)+1}$, where$t(r)=r(r+1)/2,$and$2t(n-1)+1$constraints. It is shown that the new bound obtained this way strictly improves the previous SDP bound, both empirically and theoretically. • STATUS: (submitted to Discr. Appl. Math. but combined with "A Tight Semidefinite Relaxation of the Cut Polytope") • DATE OF ENTRY: June 28, 1999 • Presolving for Semidefinite Programs Without Constraint Qualifications, 1998 • FORMAT: gzipped postscript. • Number of Pages: 20 • Title: Presolving for Semidefinite Programs Without Constraint Qualifications • Authors: • G. GRUBER and S. KRUK and F. RENDL and H. Wolkowicz • available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ presolving.ps.gz • ABSTRACT: Presolving for linear programming is an essential ingredient in many commercial packages. This step eliminates redundant constraints and identically zero variables, and it identifies possible infeasibility and unboundedness. In semidefinite programming, identically zero variables corresponds to lack of a constraint qualification which can result in both theoretical and numerical difficulties. A nonzero duality gap can exist which nullifies the elegant and powerful duality theory. Small perturbations can result in infeasibility and/or large perturbations in solutions. Such problems fall into the class of ill-posed problems. It is interesting to note that classes of problems where constraint qualifications fail arise from semidefinite programming relaxations of hard combinatorial problems. We look at several such classes and present two approaches to find regularized solutions. Some preliminary numerical results are included. • STATUS: submitted • DATE OF ENTRY: July 28, 1998 • Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem, 1998 • FORMAT: gzipped postscript. • Number of Pages: 21 • Title: Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem • and a pdf file • Authors: • Kurt Anstreicher, Xin Chen, Henry Wolkowicz, and Ya-Xiang Yuan • available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ sdptrsqap.ps.gz • ABSTRACT: Lagrangian duality underlies many efficient algorithms for convex minimization problems. A key ingredient is strong duality. Lagrangian relaxation also provides lower bounds for nonconvex problems, where the quality of the lower bound depends on the duality gap. Quadratically constrained quadratic programs (QQPs) provide important examples of nonconvex programs. For the simple case of one quadratic constraint (the trust region subproblem) strong duality holds. In addition, necessary and sufficient (strengthened) second order optimality conditions exist. However, these duality results already fail for the two trust region subproblem. Surprisingly, there are classes of more complex, nonconvex QQPs where strong duality holds. One example is the special case of orthogonality constraints, which arise naturally in relaxations for the quadratic assignment problem (QAP). In this paper we show that strong duality also holds for a relaxation of QAP where the orthogonality constraint is replaced by a semidefinite inequality constraint. Using this strong duality result, and semidefinite duality, we develop new trust region type necessary and sufficient optimality conditions for these problems. Our proof of strong duality introduces and uses a generalization of the Hoffman-Wielandt inequality. • STATUS: LAA, Volume 301, Nov. 1999 pgs 121-136 • Mathematical Review • DATE OF ENTRY: July 15, 1998 • Duality for Semidefinite Programming, 1998 • FORMAT: gzipped postscript. • Number of Pages: 3 • Title: Duality for Semidefinite Programming • Authors: • Henry Wolkowicz • University of Waterloo Department of Combinatorics and Optimization Waterloo, Ontario N2L 3G1, Canada available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ dualityencycl.ps.gz • To appear in the Encyclopedia of Optimization • STATUS: to appear. • DATE OF ENTRY: June 1, 1998 • On Lagrangian Relaxation of Quadratic Matrix Constraints, 1999 • FORMAT: gzipped postscript. • Number of Pages: 17 • Title: On Lagrangian Relaxation of Quadratic Matrix Constraints • (addendum: An Alternate Strengthened Relaxation of MC) • Authors: • Kurt Anstreicher • Department of Management Sciences, The University of Iowa and Henry Wolkowicz University of Waterloo Department of Combinatorics and Optimization Waterloo, Ontario N2L 3G1, Canada Research Report CORR 98-24 available by anonymous ftp at orion.math.uwaterloo.ca, in directory pub/henry/reports and also with URL: http://orion.math.uwaterloo.ca:80/~hwolkowi/henry/reports/ qqplagrng.ps.gz • Abstract. Quadratically constrained quadratic programs (QQP) play an important modeling role for many diverse problems. These problems are in general NP hard, and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations. For several special cases of QQP, e.g. convex programs and trust region subproblems, the Lagrangian relaxation provides the exact optimal value, i.e. there is a zero duality gap. However this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective. In this paper we consider a certain QQP where the quadratic constraints correspond to the matrix orthogonality condition$X\tran X=I$. For this problem we show that the Lagrangian dual based on relaxing the constraints$X\tran X=I$, {\em and} the seemingly redundant constraints$X\tran X=I$, has a zero duality gap. This result has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix. We also show that the technique of relaxing quadratic matrix constraints can be used to obtain a strengthened semidefinite relaxation for the max-cut problem. • STATUS: research report CORR 24/98. SIMAX, volume = "22", number = "1", year="2000", pages = "41-55". • Mathematical Review • DATE OF ENTRY: June 1, 1998 • On the embeddability of Weighted Graphs in Euclidean Spaces • FORMAT: gzipped postscript. • Number of Pages: 12 • Title: On the embeddability of Weighted Graphs in Euclidean Spaces • Authors: • Abdo Alfakih and Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. Given an incomplete edge-weighted graph,$G=(V,E,\omega)$,$G$is said to be embeddable in$\Re^r$, or$r$-embeddable, if the vertices of$G$can be mapped to points in$\Re^r$such that every two adjacent vertices$v_i$,$v_j$of$G$are mapped to points$x^i$,$x^j \in \Re^r$whose Euclidean distance is equal to the weight of the edge$(v_i,v_j)$. Barvinok \cite{bar95} proved that if$G$is$r$-embeddable for some$r$, then it is$r^*$-embeddable where$r^*= \lfloor(\sqrt{8|E|+1}-1)/2 \rfloor$. In this paper we provide a constructive proof of this result by presenting an algorithm to construct such an$r^*$-embedding. • STATUS: research report CORR 12/98, submitted. • DATE OF ENTRY: May 27, 1998 • The Gauss-Newton Direction in Semidefinite Programming 1998 • FORMAT: gzipped postscript. • Number of Pages: 26 • Title: The Gauss-Newton Direction in Semidefinite Programming • (or the original longer version, gzipped ps) • Authors: • Serge Kruk, Masakazu Muramatsu, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz • Abstract • Primal-dual interior-point methods have proven to be very successful for both linear programming (LP) and, more recently, for semidefinite programming (SDP) problems. Many of the techniques that have been so successful for LP have been extended to SDP. In fact, interior point methods are currently the only successful techniques for SDP. We present a new paradigm for deriving these methods: 1) using the optimality conditions from the dual log-barrier problem, we obtain primal feasibility, dual feasibility, and perturbed complementary slackness equations; 2) the perturbed complementary slackness condition is quite nonlinear, so we modify this condition to obtain a bilinear condition, i.e. a condition that is less nonlinear; 3) we now find a search direction by applying the Gauss-Newton method to the least squares problem for these optimality conditions; equivalently we find the least squares solution of the linearized perturbed optimality conditions. In the case of LP, the Gauss-Newton direction for the least squares problem is equivalent to the Newton direction applied to solving the modified (square) nonlinear system of optimality conditions. Though this paradigm does not directly provide a new search direction for linear programming, it does provide a new approach for convergence proofs as well as motivation for step lengths larger than one. However, there is one major difference between LP and SDP that raises several interesting questions. That difference is the form of the perturbed complementarity condition used in the optimality conditions. In LP this condition is modified to be$ZX - \mu I = 0.$The primal matrix$X$and the dual slack matrix$Z$are diagonal in LP but may only be symmetric in SDP; this results in$ZX$not being symmetric in general, i.e. the optimality conditions in the SDP case end up as an overdetermined system of nonlinear equations. There have been various approaches which modify the complementarity condition so that the linearization of the optimality conditions are square'', i.e. map between the same spaces. These approaches can have several drawbacks, e.g. numerical instability near the optimum and lack of positive definiteness after symmetrization. Our least squares approach requires no symmetrization and does not suffer from these drawbacks. We concentrate on solving the overdetermined, system in the best way possible. In particular, we use Gauss-Newton type methods. This leads to numerically stable as well as excellent search directions which lead to the central path. Though the numerical efficient calculation of the Gauss-Newton direction is still an open question, we present a preliminary top down'' elimination approach that is competitive timewise and empirical evidence suggests that it is often more robust than other directions currently in use. • NOTE = "A long (original) version of this paper is available here, gzipped ps • STATUS: Optimization Methods and Software (OMS), Volume 15, Number 1 (April, 2001), S. Kruk, M. Muramatsu, F. Rendl, R.J. Vanderbei and H. Wolkowicz, The Gauss-Newton direction in semidefinite programming 1-27 • DATE OF ENTRY: May 15, 1998 • Pseudo-Linear Programming • FORMAT: gzipped postscript, pdf. • Number of Pages: 14 • Title: Pseudo-Linear Programming • Authors: • Serge Kruk and Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. This short note revisits an algorithm previously sketched by Mathis and Mathis, Siam Review 1995, and used to solve a nonlinear hospital fee optimization problem. An analysis of the problem structure reveals how the Simplex algorithm, viewed under the correct light, can be the driving force behind a successful algorithm for a nonlinear problem. • STATUS: SIAM Review, Volume 41, Number 4 pp. 795-805 1999. For electronic version use URL: http://epubs.siam.org/sam-bin/dbq/article/33525 • Mathematical Review • DATE OF ENTRY: Feb. 1998 • Problem 19-1 in IMAGE from ILAS, Issue Number 19, 1997. • FORMAT: gzipped postscript. • Number of Pages: 15 • Title: Solution to Problem 19-1 in IMAGE from ILAS, Issue Number 19, 1997. • Authors: • Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. This solution discusses the question of when$X,Z$positive semidefinite implies that the symmetrization$ZX+XZ$is positive semidefinite. These questions arise in the algorithms for semidefinite programming. • STATUS: appeared in IMAGE issue 20, April 1998. • DATE OF ENTRY: Dec. 1997 • THE QUASI-CAUCHY RELATION AND DIAGONAL UPDATING, • FORMAT: gzipped postscript. • Number of Pages: 15 • Title: THE QUASI-CAUCHY RELATION AND DIAGONAL UPDATING (pdf) • Authors: • M. Zhu and K.L. Nazareth, Washington State University, and Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. The quasi-Cauchy (QC) relation is the weak-secant or weak-quasi Newton relation of Dennis and Wolkowicz with the added restriction that full matrices are replaced by diagonal matrices. The latter are especially appropriate for scaling a Cauchy (steepest-descent) algorithm, hence our choice of terminology. • In this article, we explore the QC relation and develop variational techniques for updating diagonal matrices that satisfy it. Numerical results are also given to illustrate the use of such updates within a Cauchy algorithm. • STATUS: SIAM J. Optim. 9 (1999), no. 4, 1192--1204 • Mathematical Review • DATE OF ENTRY: Dec. 1997 • Solving Euclidean distance matrix completion problems via semidefinite programming • FORMAT: gzipped postscript. • Number of Pages: 18 • Title: Solving Euclidean distance matrix completion problems via semidefinite programming (ps file) • (pdf file) • software: a matlab program is available (revised in new folder Nov/14). • Authors: • Abdo Alfakih and Amir Khandani and Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. Given a partial symmetric matrix$A$with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of$A$that make$A$a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in \cite{JoKrWo:95} and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming problem (SDP). Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed. • STATUS: = appeared in Computational Optimization and Applications, volume 12, pages 13-30, year 1998. • Math Review • DATE OF ENTRY: July 1997 and revised on May 5 1998. • SQ2P, Sequential Quadratic Constrained Quadratic Programming, • FORMAT: gzipped postscript and pdf. • Number of Pages: 20 • Title: SQ2P, Sequential Quadratic Constrained Quadratic Programming, • Authors: • Serge Kruk and Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. Arguably the most successful family of techniques used to solve general nonlinear programs is known as Sequential Quadratic Programming. This iterative approach rests on a quadratic model of the Lagrangean subjected to linear approximations of the constraints. For all its success, the practical implementations must somehow overcome the weaker model of the feasible region. • A model demonstrably closer to the original problem uses second-order Taylor expansions of both objective function and constraints. Such a model preserves all curvature information and can therefore provide better Lagrange multipliers estimates. While considered before, this approach has generally been discarded as intractable. But the expanding field of semidefinite programming offers tools, both theoretical and practical, to overcome for a large class of problems this presumed intractability. The theory and practice of semidefinite programming, in recent years, produced notable breakthroughs in combinatorial optimization. The approach described here tries to apply the same framework to continuous optimization problems. • STATUS: appeared in Advances in Nonlinear Programming, Kluwer Academic, 1998, pages 177-204. • Math. Review • DATE OF ENTRY: Jan 1997, revised Oct/97. • SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE SET PARTITIONING PROBLEM • FORMAT: gzipped postscript. • Number of Pages: 17 • Title: SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE SET PARTITIONING PROBLEM • (pdf file) • Authors: • Henry Wolkowicz and Qing Zhao Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. We present a relaxation for the set partitioning problem that combines the standard linear programming relaxation with a semidefinite programming relaxation. We include numerical results that illustrate the strength and efficiency of this relaxation. • STATUS: in progress, but never completely finished • DATE OF ENTRY: Oct 1996 • SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE GRAPH PARTITIONING PROBLEM • FORMAT: gzipped postscript. • Number of Pages: 17 • Title: SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE GRAPH PARTITIONING PROBLEM selected for inclusion in the special volume Discrete Applied Mathematics, Editors' Choice Edition 1999 • a matlab program will be available. • Authors: • Henry Wolkowicz and Qing Zhao Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. A semidefinite programming, SDP, relaxation for the graph partitioning problem, GP, is derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of GP. The special structure of the relaxation is exploited in order to project the SDP onto the {\em minimal face}, of the cone of positive semidefinite matrices, which contains the feasible set. This guarantees that the Slater constraint qualification holds; which allows for a primal-dual interior-point solution technique. A {\em gangster operator} is the key to providing an efficient representation of the constraints. An incomplete preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. Numerical results illustrate the efficacy of the SDP relaxations. • STATUS: Discrete Appl. Math. 96/97 (1999), 461--479. • Mathematical Review • DATE OF ENTRY: Oct 1996 • SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE QUADRATIC ASSIGNMENT PROBLEM • FORMAT: gzipped postscript. • Number of Pages: 41 • Title: SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE QUADRATIC ASSIGNMENT PROBLEM • and a pdf file. • a matlab program will be available. • Authors: • Qing Zhao Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada, Stefan E.\ Karisch\thanks{University of Copenhagen, Department of Computer Science, Universitetsparken 1, DK-2100 Copenhagen, Denmark}, Franz Rendl\thanks{Graz University of Technology, Department of Mathematics, Steyrergasse 30, A-8010 Graz, Austria}, Henry Wolkowicz, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Typos: in "Corollary 3.1" "the Minimal face can be expressed as \hat{V}S_{(n-1)^2+1}{\hat{V}}^{\top}" Here S_{(n-1)^2+1} should be the positive semidefinite cone in the space of symmetric matrices of dimension {(n-1)^2+1}. The S should be a P. So, this is a typo, i.e. it should read \hat{V}P_{(n-1)^2+1}{\hat{V}}^{\top} • Abstract. Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e.\ the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods. In particular, the special structure gives rise to several interesting linear operators, e.g.: block diagonal; arrow; and the gangster operators. A study of these operators leads to efficient exploitation of sparsity. • A preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is found by exploiting the special structure of the relaxation and the above mentioned linear operators. Feasible solutions for QAP are recovered from the Lagrangian relaxation information; thus illustrating the importance of going through the Lagrangian relaxation when obtaining the SDP relaxation. Numerical results are presented which indicate that the described methods yield at least competitive lower bounds. • STATUS: J. of Comb. Opt. 2 (1998), no. 1, 71--109. ( pdf file) • Mathematical Review • DATE OF ENTRY: June 1996 • AN INTERIOR-POINT METHOD FOR APPROXIMATE POSITIVE SEMIDEFINITE COMPLETIONS • FORMAT: gzipped postscript. • Number of Pages: 17 • Title: AN INTERIOR-POINT METHOD FOR APPROXIMATE POSITIVE SEMIDEFINITE COMPLETIONS • software: a matlab program is available. • Authors: • Charles R. Johnson and Brenda Kroschel College of William \& Mary, Department of Mathematics, Williamsburg, Virginia 23187-8795. E-mail: crjohnso@cs.wm.edu and kroschel@cs.wm.edu. and • Henry Wolkowicz Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. Given a nonnegative, symmetric, matrix of weights,$H$, we study the problem of finding an Hermitian, positive semidefinite matrix which is closest to a given Hermitian matrix,$A,$with respect to the weighting$H.$This extends the notion of exact matrix completion problems. We present optimality conditions, duality theory, and a primal-dual interior-point algorithm. Included are numerical tests that illustrate the efficiency and robustness of the algorithm. • STATUS: Computational Optimization and Applications, 1998, vol 9. • Mathematical Review • DATE OF ENTRY: May 1995 • ERRATA, June 2001: In Corollary 2.2 add the assumption "if Pbar so defined is psd" (thanks to Nick Higham for pointing this out). • STRONG DUALITY FOR SEMIDEFINITE PROGRAMMING • FORMAT: pdf. • Number of Pages: 32 • Title: STRONG DUALITY FOR SEMIDEFINITE PROGRAMMING • Authors: • Motakuri Ramana Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611 • Levent Tun\c{c}el and Henry Wolkowicz Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. • Abstract. It is well known that the duality theory for linear programming (LP) is powerful and elegant and lies behind algorithms such as simplex and interior-point methods. However, duality for nonlinear programs requires constraint qualifications to avoid duality gaps. Semidefinite linear programming (SDP) is a generalization of LP where the nonnegativity constraints are replaced by a semidefiniteness constraint on the matrix variables. There are many applications, e.g. in systems and control theory and in combinatorial optimization. However, the Lagrangian dual for SDP can have a duality gap. We discuss the relationships among various duals and give a unified treatment for strong duality in semidefinite programming. These duals guarantee strong duality, i.e. a zero duality gap and dual attainment. This paper is motivated by the recent paper by Ramana where one of these duals is introduced. • STATUS: SIOPT, 1997, vol 7. • Mathematical Review • DATE OF ENTRY: May 1995 • Combining Semidefinite and Polyhedral Relaxations for Integer Programs • FORMAT: gzipped postscript. • Number of Pages: 8 • Title: Combining Semidefinite and Polyhedral Relaxations for Integer Programs • software: a matlab toolkit is available with documentation. • Authors: • Christoph Helmberg Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung • Svata Poljak, University Passau, Faculty of Mathematics and Informatic, Innstrasse 33, 94030 Passau, Germany • Franz Rendl Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung • Henry Wolkowicz Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. This author thanks the Department of Civil Engineering and Operations Research, Princeton University, for their support during his stay while on research leave. Thanks also to the National Science and Engineering Research Council Canada for their support. • Abstract. We present a general framework for designing semidefinite relaxations for constrained 0-1 quadratic programming and show how valid inequalities of the cut--polytope can be used to strengthen these relaxations. As examples we improve the$\vartheta$--function and give a semidefinite relaxation for the quadratic knapsack problem. The practical value of this approach is supported by numerical experiments which make use of the recent development of efficient interior point codes for semidefinite programming. • STATUS: Proceedings of the 4th International IPCO Conference, 1995. • Mathematical Review • DATE OF ENTRY: May 1995 • A Semidefinite Framework for Trust Region Subproblems with Applications to Large Scale Minimization • FORMAT: gzipped postscript. • Number of Pages: 41 • Title: A Semidefinite Framework for Trust Region Subproblems with Applications to Large Scale Minimization • software is available in matlab --- and pdf version. • authors: • Franz Rendl, Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung (rendl@fmatbds01.tu-graz.ac.at).} • Henry Wolkowicz, University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario N2L 3G1, Canada (E-mail: hwolkowi@orion.math.uwaterloo.ca and URL: http://orion.math.uwaterloo.ca/\~{ }hwolkowi). Research support by the National Science and Engineering Research Council Canada. • Abstract: A primal-dual pair of semidefinite programs provides a general framework for the theory and algorithms for the trust region subproblem (TRS). This problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of TRS is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for TRS. In particular, a dual simplex type method is studied that solves TRS as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is$1+\alpha(n)$times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where$0<\alpha(n)<1$is a fraction which decreases as the dimension increases. • STATUS: Math Progr 1997, vol 77. • Mathematical Review • DATE OF ENTRY: Dec. 1994, revised entry jan 24, 1995 • A RECIPE FOR BEST SEMIDEFINITE RELAXATION FOR (0,1)-QUADRATIC PROGRAMMING • FORMAT: gzipped postscript. • Number of Pages: 27 • Title: A RECIPE FOR BEST SEMIDEFINITE RELAXATION FOR (0,1)-QUADRATIC PROGRAMMING • Authors: • Svata Poljak, University Passau, Faculty of Mathematics and Informatic, Innstrasse 33, 94030 Passau, Germany • Franz Rendl, Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung • Henry Wolkowicz, University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario N2L 3G1, Canada. • Abstract. We review various relaxations of (0,1)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partition Problem and the Max-Clique Problem. Finally we show our relaxation to be best possible among all quadratic majorants with zero trace. • STATUS: J. Global Optimization, 1995, vol 7, pp 51-73. • Mathematical Review • DATE OF ENTRY: Oct. 1994 • NOTE: TYPO: relation (2.3) is not correct if there is no$u$such that$u^te=0$and$Q+\Diag(u)$negative semidefinite (eg. in the case that$\diag(Q)^t e > 0$). • An Interior-Point Method for Semidefinite Programming • FORMAT: gzipped postscript. • Number of Pages: 23 • Title: An Interior-Point Method for Semidefinite Programming , (ps file) • software: a matlab toolkit is available with documentation. • Authors: • Christoph Helmberg Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung • Franz Rendl Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung • Robert J. Vanderbei, Program in Statistics \& Operations Research Princeton University, Princeton, NJ 08544. Research support by AFOSR through grant AFOSR-91-0359. • Henry Wolkowicz Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. This author thanks the Department of Civil Engineering and Operations Research, Princeton University, for their support during his stay while on research leave. Thanks also to the National Science and Engineering Research Council Canada for their support. • Abstract. We propose a new interior point based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We present a theoretical convergence analysis, and show that the approach is very efficient for graph bisection problems, such as max-cut. The approach can also be applied to max-min eigenvalue problems. • STATUS: SIOPT, 1996, vol 6. • Mathematical Review • DATE OF ENTRY: October 1994 • The Quadratic Assignment Problem: A Survey and Recent Developments • FORMAT: gzipped postscript. • Number of Pages: 42 • Title: The Quadratic Assignment Problem: A Survey and Recent Developments • and (a pdf file) • Authors: • Panos M. Pardalos, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL\ 32611\ USA and Technical University of Crete, Greece • Franz Rendl, Technische Universitat Graz, Institut fur Mathematik, Kopernikusgassa 24, A-8010 Graz, Austria • Henry Wolkowicz, University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada • Abstract. Quadratic Assignment Problems model many applications in diverse areas such as operations research, parallel and distributed computing, and combinatorial data analysis. In this paper we survey some of the most important techniques, applications, and methods regarding the quadratic assignment problem. We focus our attention on recent developments. • STATUS: Appeared in AMS Proceedings of the DIMACS workshop on QAP, 1994 • Mathematical Review • DATE OF ENTRY: Mar. 1994 • A Computational Study of Graph Partitioning • FORMAT: gzipped postscript and a pdf file • Title: A Computational Study of Graph Partitioning • software: a matlab toolkit is available with documentation. • Authors: • Julie Falkner, Massey University, Department of Mathematics, Private Bag 11222, Palmerston North, New Zealand • Franz Rendl, Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria • Henry Wolkowicz, University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, N2L 3G1, Canada • Abstract. Let$G = (N,E)$be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the vertex set into$k$disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points. • STATUS: Appeared in Math. Progr. Vol 66, 1994. • Mathematical Review • DATE OF ENTRY: Nov. 1993 • TRUST REGION PROBLEMS AND NONSYMMETRIC EIGENVALUE PERTURBATIONS • FORMAT: pdf. • Title: TRUST REGION PROBLEMS AND NONSYMMETRIC EIGENVALUE PERTURBATIONS • (and gzipped ps) • Authors:{Ronald J. Stern \\ Department of Mathematics and Statistics\\ Concordia University\\ Montreal, Quebec H4B 1R6, Canada\\ Henry Wolkowicz \\ University of Waterloo\\ Department of Combinatorics and Optimization \\ Waterloo, Ontario N2L 3G1, Canada} • ABSTRACT A characterization is given for the spectrum of a symmetric matrix to remain real after a nonsymmetric sign restricted border perturbation, including the case where the perturbation is skew-symmetric. The characterization is in terms of the stationary points of a quadratic function on the unit sphere. This yields interlacing relationships between the eigenvalues of the original matrix and those of the perturbed matrix. As a result of the linkage between the perturbation and stationarity problems, new theo\-retical insights are gained for each. Applications of the main results include a characterization of those matrices which are exponentially nonnegative with respect to the$n$-dimensional ice-cream cone, which in turn leads to a decomposition theorem for such matrices. In addition, results are obtained for nonsymmetric • STATUS: appeared in SIAM J. Matrix Analysis and Applications", year = "1994", volume ="15", number = "3", • Mathematical Review • DATE OF ENTRY: Oct. 1993 • COMMENTS: There are missing figures in the postscript file which will appear in the published version. • INDEFINITE TRUST REGION SUBPROBLEMS AND NONSYMMETRIC EIGENVALUE PERTURBATIONS • FORMAT: pdf • Title: INDEFINITE TRUST REGION SUBPROBLEMS AND NONSYMMETRIC EIGENVALUE PERTURBATIONS • Authors:{Ronald J. Stern \\ Department of Mathematics and Statistics\\ Concordia University\\ Montreal, Quebec H4B 1R6, Canada\\ ~\\and \\~\\ Henry Wolkowicz \\ University of Waterloo\\ Department of Combinatorics and Optimization \\ Waterloo, Ontario N2L 3G1, Canada} • ABSTRACT This paper extends the theory of trust region subproblems in two ways: (i) it allows indefinite inner products in the quadratic constraint and (ii) it uses a two sided (upper and lower bound) quadratic constraint. Characterizations of optimality are presented, which have no gap between necessity and sufficiency. Conditions for the existence of solutions are given in terms of the definiteness of a matrix pencil. A simple dual program is introduced which involves the maximization of a strictly concave function on an interval. This dual program simplifies the theory and algorithms for trust region subproblems. It also illustrates that the trust region subproblems are implicit convex programming problems, and thus explains why they are so tractable. The duality theory also provides connections to eigenvalue perturbation theory. Trust region subproblems with zero linear term in the objective function correspond to eigenvalue problems, and adding a linear term in the objective function is seen to correspond to a perturbed eigenvalue problem. Some eigenvalue interlacing results are presented. • STATUS: SIOPT, 1995, vol 5. • Mathematical Review • DATE OF ENTRY: Oct. 1993 • Trust regions and relaxations for the quadratic assignment problem. • FORMAT: gzipped postscript. • TITLE: Trust regions and relaxations for the quadratic assignment problem. • and a pdf file. • Authors:{Stefan E. Karisch and Franz Rendl\\ Technische Universit\"{a}t Graz\\ Institut f\"{u}r Mathematik\\ Kopernikusgasse 24, A-8010 Graz, Austria \\ ~\\and \\~\\ Henry Wolkowicz \\ University of Waterloo \\ Department of Combinatorics and Optimization \\ Waterloo, Ontario, Canada} • ABSTRACT The quadratic assignment problem (QAP) consists in minimizing a quadratic function over the set of permutation matrices. The problem belongs to the class of$NP$-hard combinatorial optimization problems. Although it has been studied extensively over the past 35 years, problems of size$n \geq 15$still prove to be intractable. Since good lower bounds are necessary to solve larger problem instances, results of these continuous optimization approaches for QAP. Since these approaches include trust region techniques and optimization over partial orders, new results for these areas are obtained, as well. • STATUS: Appeared in DIMACS Series in Discrete Math. and Theoretical Comp. Sc. (Proceedings - workshop on QAP) • Mathematical Review • DATE OF ENTRY: Nov. 1993 • A Projection Technique for Partitioning the Nodes of a Graph • FORMAT gzipped postscript: gp.ps.gz • FORMAT pdf: pdf file • A Projection Technique for Partitioning \\ the Nodes of a Graph} • Authors:{Franz Rendl \\ Technische Universit\"{a}t Graz\\ Institut f\"{u}r Mathematik\\ Kopernikusgasse 24, A-8010 Graz, Austria \\ and \\ Henry Wolkowicz \\ University of Waterloo\\ Department of Combinatorics and Optimization \\ Waterloo, Ontario, N2L 3G1, Canada} • Abstract. Let$G = (N,E)$be an undirected graph. We present several new techniques for partitioning the node set$N$into$k$disjoint subsets of specified sizes. These techniques involve eigenvalue bounds and tools from continuous optimization. Comparisons with examples taken from the literature show these techniques to be very successful. • STATUS: Annals of Operations Research, 1995, vol 58. • Mathematical Review • DATE OF ENTRY: Feb. 1993 • CONVEX RELAXATIONS OF 0-1 QUADRATIC PROGRAMMING • files:01quad.ps.gz • FORMAT: gzipped postscript. • CONVEX RELAXATIONS OF 0-1 QUADRATIC PROGRAMMING} • Authors:{Svatopluk Poljak\thanks{on leave from the Department of Applied Mathematics, Charles University, Malostransk\'e nam.~25, 118~00 Praha 1, Czech Republic }\\ Institute of Mathematics\\ Academia Sinica\\ Nankang, Taipei, Taiwan 11529\\ ~\\and \\~\\ Henry Wolkowicz\thanks{This author would like to thank the Department of Civil Engineering and Operations Research, Princeton University, for their support during his research leave.} \\ • Abstract. We consider three parametric relaxations of the 0-1 quadratic programming problem. These relaxations are to: quadratic maximization over simple box constraints, quadratic maximization over the sphere, and the maximum eigenvalue of a bordered matrix. When minimized over the parameter, each of the relaxations provides an upper bound on the original discrete problem. Moreover, these bounds are efficiently computable. Our main result is that, surprisingly, all three bounds are equal. • STATUS: MOR, 1995, vol 20. • Mathematical Review • DATE OF ENTRY: Oct. 1993 • MEASURES FOR SYMMETRIC RANK-ONE UPDATES • files: sr1.ps.gz • FORMAT: gzipped postscript. • MEASURES FOR SYMMETRIC RANK-ONE UPDATES} Henry Wolkowicz \\ University of Waterloo\\ Department of Combinatorics and Optimization \\ Waterloo, Ontario N2L 3G1, Canada} • Authors:{ Henry Wolkowicz \\ University of Waterloo\\ Department of Combinatorics and Optimization \\ Waterloo, Ontario, N2L 3G1, Canada} • ABSTRACT Measures of deviation of a symmetric positive definite matrix from the identity are derived. They give rise to symmetric rank-one, SR1, type updates. The measures are motivated by considering the volume of the symmetric difference of the two ellipsoids, which arise from the current and updated quadratic models in quasi-Newton methods. The measure defined by the problem - maximize the determinant subject to a bound of 1 on the largest eigenvalue - yields the SR1 update. The measure$\sigma(A) = \frac{\lambda_1(A)}{\det (A)^{\frac{1}{n}}}$yields the optimally conditioned, sized, symmetric rank-one updates, \cite{IpTod:88,OsbSun:89}. The volume considerations also suggest a correction' for the initial stepsize for these sized updates. It is then shown that the$\sigma$-optimal updates, as well as the Oren-Luenberger self-scaling updates \cite{OreLuen:74}, are all optimal updates for the$\kappa$measure, the$\ell_2$condition number. Moreover, all four sized updates result in the same largest (and smallest) 'scaled' eigenvalue and corresponding eigenvector. In fact, the inverse-sized BFGS is the mean of the$\sigma$-optimal updates, while the inverse of the sized DFP is the mean of the inverses of the$\sigma$-optimal updates. The difference between these four updates is determined by the middle$n-2$scaled eigenvalues. The$\kappa$measure also provides a natural Broyden class replacement for the SR1 when it is not positive definite. • STATUS: Appeared in MOR vol 19 no 4, 1994. • Mathematical Review • DATE OF ENTRY: Oct. 1993 • AN ALL INCLUSIVE EFFICIENT REGION OF UPDATES FOR LEAST CHANGE SECANT METHODS • files: eff.ps.gz • FORMAT: gzipped postscript. • TITLE: AN ALL INCLUSIVE EFFICIENT REGION OF UPDATES FOR LEAST CHANGE SECANT METHODS • Authors:{ Henry Wolkowicz\thanks{ Research supported by Natural Sciences Engineering Research Council Canada grant.} \and Qing Zhao\thanks{ Research supported by Natural Sciences Engineering Research Council Canada grant and an Operating Grant from NSERC Micronet.} } • ABSTRACT Least change secant methods, for function minimization, depend on finding a good'' symmetric positive definite update to approximate the Hessian. This update contains new curvature information while simultaneously preserving, as much as possible, the built up information from the previous update. Updates are generally derived using measures of least change based on some function of the eigenvalues of the (scaled) Hessian. A new approach for finding good least change updates is the multicriteria problem of Byrd. This uses the deviation from unity, of the$n$eigenvalues of the scaled update, as measures of least change. The efficient (multicriteria optimal) class for this problem is the Broyden class on the `good'' side of the symmetric rank one (SR1) update. It is called the {\em Broyden Efficient Class}. This paper uses the framework of multicriteria optimization, and the eigenvalues of the scaled (sized) and inverse scaled updates, to study the question of what is a good update. In particular, it is shown that the basic multicriteria notions of efficiency and proper efficiency yield a region of updates that contains the well known updates studied to date. This provides a unified framework for deriving updates. First, the inverse efficient class is found. It is then shown that the Broyden efficient class and inverse efficient class are in fact also proper efficient classes. Then, allowing sizing and an additional function in the multicriteria problem, results in a two parameter efficient region of updates that includes many of the updates studied to date, e.g., it includes the Oren-Luenberger self-scaling updates, as well as the Broyden Efficient Class. This efficient region, called the {\em Self-Scaling Efficient Region}, is proper efficient and lies between two curves, where the first curve is determined by the sized SR1 updates while the second curve consists of the optimal conditioned updates. Numerical tests are included that compare updates inside and outside the efficient region. \end{abstract} • STATUS: appeared in SIAM J. Optimization", volume="5", number="1", pages="172-191", year="1995 • DATE OF ENTRY: Oct. 1993 • EXPLICIT SOLUTIONS FOR INTERVAL SEMIDEFINITE LINEAR PROGRAMS • files: explicit.ps.gz and pdf file • FORMAT: gzipped postscript. • EXPLICIT SOLUTIONS FOR INTERVAL SEMIDEFINITE LINEAR PROGRAMS\footnote{This report is available by anonymous ftp at orion.math.uwaterloo.ca in the directory pub/henry/reports.}} • Authors:{ Henry Wolkowicz \thanks{The author thanks The National Science and Engineering Research Council Canada for their support. }\\ University of Waterloo\\ Department of Combinatorics and Optimization \\ Faculty of Mathematics\\ Waterloo, Ontario N2L 3G1, Canada\\ e-mail henry@orion.math.uwaterloo.ca } %\today %\date{May 1993} • Abstract. We consider the special class of semidefinite linear programs $~~(IVP)~~~ \mbox{maximize~} \tr CX \mbox{~~~subject to~~~} L \preceq A(X) \preceq U,$ where$C,X,L,U$are symmetric matrices,$A$is a (onto) linear operator, and$\preceq$denotes the Lo\"ewner (positive semidefinite) partial order. We present explicit representations for the general primal and dual optimal solutions. This extends the results for standard linear programming which appeared in Ben-Israel and Charnes, 1968. This work is further motivated by the explicit solutions for a different class of semidefinite problems presented recently in Yang and Vanderbei, 1993. \end{abstract} {\bf Key words:} Semidefinite linear programming, explicit solutions, Lo\"{e}wner partial order, symmetric positive semidefinite matrices.\\ {\bf AMS 1991 Subject Classification:}\\ Primary: 65K10, Secondary: 90C25,90M45,15A45,47D20 • STATUS: Final version appeared in: Linear Algebra and its Applications, 1996, vol 236 pp 95-104. • Mathematical Review • DATE OF ENTRY: Nov. 1993 • MAX-MIN EIGENVALUE PROBLEMS, PRIMAL-DUAL INTERIOR POINT ALGORITHMS, and TRUST REGION SUBPROBLEMS • files: maxmintrust.ps.gz • maxmintrust.pdf • FORMAT: gzipped postscript. • TITLE: MAX-MIN EIGENVALUE PROBLEMS, PRIMAL-DUAL INTERIOR POINT ALGORITHMS, and TRUST REGION SUBPROBLEMS} • Authors:{Franz Rendl \thanks{Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung.} \and Robert J. Vanderbei \thanks{ Program in Statistics \& Operations Research, Princeton University, Princeton, NJ 08544. Research support by AFOSR through grant AFOSR-91-0359.} \and Henry Wolkowicz \thanks{ Research support by the National Science and Engineering Research Council Canada. } } \date{} \thispagestyle{empty} \begin{center} {\it University of Waterloo\\ Department of Combinatorics and Optimization \\ Faculty of Mathematics\\ Waterloo, Ontario N2L 3G1, Canada\\ e-mail henry@orion.math.uwaterloo.ca \\} \vspace{0.1in} \today \\ \vspace{0.1in} Technical Report CORR 93-30 \end{center} \vspace{0.2in} • Abstract. Two Primal-dual interior point algorithms are presented for the problem of maximizing the smallest eigenvalue of a symmetric matrix over diagonal perturbations. These algorithms prove to be simple, robust, and efficient. Both algorithms are based on transforming the problem to one over the cone of positive semidefinite matrices. One of the algorithms does this transformation through an intermediate transformation to a trust region subproblem. This allows the removal of a dense row. \vspace{2ex} \noindent{\em Key words: Max-min eigenvalue problems, trust region subproblems, Lo\"{e}wner partial order, primal-dual interior point methods, quadratic 0,1 programming, graph bisection.} \vspace{2ex} \noindent{\em AMS 1991 Subject Classification: Primary 65K15, Secondary 49M35, 90C48.} \end{abstract} • STATUS: appeared in Optimization Methods and Software, year = "1995", pages = "1-16", volume = "5" • DATE OF ENTRY: Nov. 1993 • Sizing and Least Change Secant Methods • files: sizing.ps.gz and sizing.pdf • FORMAT: gzipped postscript and pdf. • TITLE: Sizing and Least Change Secant Methods • by J.E. Dennis, Jr.$^{1}${} and H. Wolkowicz$^{2}$\\ \mbox{} \\ \hfill CORR Report 90-02, Jan. 1990 \\ \hfill final revision \today \end{center} \vspace{2.cm} \begin{center} \parbox{12.cm}{ • Abstract. Oren and Luenberger introduced in 1974 a strategy for replacing Hessian approximations by their scalar multiples and then performing quasi-Newton updates, generally least change secant updates like the BFGS or DFP updates. In this paper, the function$\omega(A) = \frac{\trace(A)}{n\:\det\:(A)^{\frac{1}{n}}}$is shown to be a measure of change with a direct connection to the Oren-Luenberger strategy. This measure is interesting because it is related to the$\ell_2$condition number, but it takes all the eigenvalues of A into account rather than just the extremes. If the class of possible updates is restricted to the Broyden class, i.e. scalar premultiples are not allowed, then the optimal update depends on the dimension of the problem. It may, or may not, be in the convex class, but it becomes the BFGS update as the dimension increases. This seems to be yet another explanation for why the optimally conditioned updates are not significantly better than the BFGS update. The theory results in several new interesting updates including a self-scaling, hereditarily positive definite, update in the Broyden class which is not necessarily in the convex class. This update, in conjunction with the Oren-Luenberger scaling strategy at the first iteration only, was consistently the best in our numerical tests. } • STATUS: Appeared in SIGNUM vol 30, issue 5, 1993 pp. 1291-1314 (JSTOR version available) • Mathematical Review • DATE OF ENTRY: Nov. 1993 • springerlink to related paper: "A Study of the Dennis-Wolkowicz Method on Convex Functions" • A new lower bound via projection for the quadratic assignment • files: projqap.ps.gz and projqap.pdf • FORMAT: gzipped postscript and pdf. • TITLE: A new lower bound via projection for the quadratic assignment • Authors: S.W. Hadley*, F. Rendl**, H. Wolkowicz*\\ • Abstract. • New lower bounds for the quadratic assignment problem QAP are presented. These bounds are based on the orthogonal relaxation of QAP. The additional improvement is obtained by making efficient use of a tractable representation of orthogonal matrices having constant row and column sums. The new bound is easy to implement and often provides high quality bounds under an acceptable computational effort. • STATUS: Appeared in Mathematics of Operations Research, 1992, vol 17, no 3, pp 727-739 • Mathematical Review • DATE OF ENTRY: Apr. 1996 • Symmetrization of Nonsymmetric Quadratic Assignment Problems and the Hoffman-{W}ielandt Inequality • files: symmqap.ps.gz; symmqap.pdf • FORMAT: gzipped postscript. • TITLE: Symmetrization of Nonsymmetric Quadratic Assignment Problems and the Hoffman-{W}ielandt Inequality • Authors: S.W. Hadley*, F. Rendl**, H. Wolkowicz*\\ • Abstract. • A technique is proposed to transform a nonsymmetric Quadratic Assignment Problem (QAP) into an equivalent one, consisting of (complex) Hermitian matrices. This technique provides several new {\em Hoffman-Wielandt} type eigenvalue inequalities for general matrices and extends the eigenvalue bound for symmetric QAPs to the general case. • STATUS: Appeared in year="1992", volume="167", pages="53-64", journal="Linear Algebra and its Applications" • Mathematical Review • DATE OF ENTRY: Apr. 1996 • Generalizations of {S}later's constraint qualification for infinite convex programs • files: PAPER01pdf • FORMAT: gzipped pdf. • TITLE: Generalizations of {S}later's constraint qualification for infinite convex programs • Authors: V. Jeyakumar, H. Wolkowicz*\\ • Abstract. • STATUS: Appeared in year="1992", volume="57", pages="85-101", journal= "Mathematical Programming" • Mathematical Review • DATE OF ENTRY: May. 2000 • Bounds for the quadratic assignment problems using continuous optimization • files: bndscont.ps.gz • FORMAT: gzipped postscript. • TITLE: Bounds for the quadratic assignment problems using continuous optimization • Authors: S.W. Hadley*, F. Rendl**, H. Wolkowicz*\\ • Abstract. • The {\it quadratic assignment problem} (denoted$QAP$), in the trace formulation over the permutation matrices, is $\stack{min}{X\in\Pi}~tr(AXB+C)X^{t}.$ Several recent lower bounds for$QAP\$ are discussed. These bounds are obtained by applying continuous optimization techniques to approximations of this combinatorial optimization problem, as well as by exploiting the special matrix structure of the problem. In particular, we apply constrained eigenvalue techniques, reduced gradient methods, subdifferential calculus, generalizations of trust region methods, and sequential quadratic programming.
• STATUS: Appeared in "Integer Programming and Combinatorial Optimization, University of Waterloo Press, editors="W.R. Pulleyblank and Ravi Kannan, 1990, Pages 237-248.
• DATE OF ENTRY: Apr. 1996
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem

• FORMAT: gzipped pdf.
• Number of Pages: 8
• Title: Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• Authors:
• Franz Rendl Technische Universit\"{a}t Graz, Institut f\"{u}r Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f\"{u}r Diskrete Optimierung
• Henry Wolkowicz Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. This author thanks the Department of Civil Engineering and Operations Research, Princeton University, for their support during his stay while on research leave. Thanks also to the National Science and Engineering Research Council Canada for their support.
• Abstract.
• STATUS: Math. Progr., vol 53, 63-78, 1992.
• Mathematical Review
• DATE OF ENTRY: May 2000
• An explicit linear solution for the quadratic dynamic programming problem

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: An explicit linear solution for the quadratic dynamic programming problem
• Authors:
• SUTHERLAND, W.R.S. and Wolkowicz, H. and ZEIDAN, VERA
• Abstract.
• STATUS: JOTA, vol 58, 319--330 1988.
• Mathematical Review
• DATE OF ENTRY: May 2000
• A note on generalized invariant cones and the {K}ronecker canonical form

• FORMAT: pdf.
• Number of Pages: 4
• Title: A note on generalized invariant cones and the {K}ronecker canonical form
• Authors:
• STERN, R.J. and H. Wolkowicz
• Abstract.
• STATUS: LAA, vol 147, 97--100, 1991
• Mathematical Review
• DATE OF ENTRY: May 2000
• Exponential nonnegativity on the ice cream cone

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Exponential nonnegativity on the ice cream cone
• Authors:
• STERN, R.J. and H. Wolkowicz
• Abstract.
• STATUS: SIMAX 12 160-165, 1991
• Mathematical Review
• DATE OF ENTRY: May 2000
• Invariant ellipsoidal cones

• FORMAT: gzipped pdf.
• Number of Pages: 26
• Title: Invariant ellipsoidal cones
• Authors:
• STERN, R.J. and H. Wolkowicz
• Abstract.
• STATUS: LAA 150 81-106, 1991
• Mathematical Review
• DATE OF ENTRY: May 2000
• Zero duality gaps in infinite-dimensional programming

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Zero duality gaps in infinite-dimensional programming
• Authors:
• V. JEYAKUMAR and H. Wolkowicz
• Abstract.
• STATUS: JOTA 67 87--108, 1990
• Mathematical Review
• DATE OF ENTRY: May 2000
• Post-processing piecewise cubics for monotonicity

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Post-processing piecewise cubics for monotonicity
• Authors:
• R. BEATSON and H. Wolkowicz
• Abstract.
• STATUS: SINUM 26 480--502, 1989
• Mathematical Review
• DATE OF ENTRY: May 2000
• Normal matrices

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Normal matrices
• Authors:
• GRONE, B. and JOHNSON, C.R. and MARQUES de SA, E. and Wolkowicz, H.
• Abstract.
• STATUS: LAA 87 213--225, 1987
• Mathematical Review
• DATE OF ENTRY: May 2000
• A note on maximizing the permanent of a positive definite Hermitian matrix, given the eigenvalues

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: A note on maximizing the permanent of a positive definite Hermitian matrix, given the eigenvalues
• Authors:
• GRONE, B. and JOHNSON, C.R. and MARQUES de SA, E. and Wolkowicz, H.
• Abstract.
• STATUS: LAA 87 213--225, 1987
• Mathematical Review
• DATE OF ENTRY: May 2000
• A simple constraint qualification in infinite-dimensional programming

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: A simple constraint qualification in infinite-dimensional programming
• Authors:
• Borwein, J.M. and Wolkowicz, H.
• Abstract.
• STATUS: JOURNAL = {Math. Programming}, FJOURNAL = {Mathematical Programming}, VOLUME = {35}, YEAR = {1986}, NUMBER = {1}, PAGES = {83--96},
• Mathematical Review
• DATE OF ENTRY: May 2000
• A nonlinear equation for linear programming

• FORMAT: pdf.
• Number of Pages: 4
• Title: A nonlinear equation for linear programming
• Authors:
• SMITH, P.W. and Wolkowicz, H.
• Abstract.
• JOURNAL = {Math. Programming}, FJOURNAL = {Mathematical Programming}, VOLUME = {34}, YEAR = {1986}, NUMBER = {2}, PAGES = {235--238},
• Mathematical Review
• DATE OF ENTRY: May 2000
• Nonnegative solutions of a quadratic matrix equation arising from comparison theorems in ordinary differential equations

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Nonnegative solutions of a quadratic matrix equation arising from comparison theorems in ordinary differential equations
• Authors:
• BUTLER, G. and JOHNSON, C.R. and Wolkowicz, H.
• Abstract.
• JOURNAL = {SIAM J. Algebraic Discrete Methods}, FJOURNAL = {Society for Industrial and Applied Mathematics. Journal on Algebraic and Discrete Methods}, VOLUME = {6}, YEAR = {1985}, NUMBER = {1}, PAGES = {47--53},
• Mathematical Review
• DATE OF ENTRY: May 2000
• Lower bounds for the spread of a matrix

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Lower bounds for the spread of a matrix
• Authors:
• JOHNSON, C.R. and KUMAR, R. and Wolkowicz, H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {71}, YEAR = {1985}, PAGES = {161--173},
• Mathematical Review
• DATE OF ENTRY: May 2000
• Numerical decomposition of a convex function

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Numerical decomposition of a convex function
• Authors:
• M. LAMOUREUX and H. Wolkowicz
• Abstract.
• JOURNAL = {J. Optim. Theory Appl.}, FJOURNAL = {Journal of Optimization Theory and Applications}, VOLUME = {47}, YEAR = {1985}, NUMBER = {1}, PAGES = {51--64}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Improving eigenvalue bounds using extra bounds

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Improving eigenvalue bounds using extra bounds
• Authors:
• J. MERIKOSKI and H. Wolkowicz
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {68}, YEAR = {1985}, PAGES = {93--113}
• Mathematical Review
• DATE OF ENTRY: May 2000

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Authors:
• GRONE, B. and JOHNSON, C.R. and MARQUES de SA, E. and Wolkowicz, H.
• Abstract.
• JOURNAL = {Linear and Multilinear Algebra}, FJOURNAL = {Linear and Multilinear Algebra}, VOLUME = {16}, YEAR = {1984}, NUMBER = {1-4}, PAGES = {305--322}
• DOI:10.1080/03081088408817634
• Mathematical Review
• DATE OF ENTRY: May 2000
• Positive definite completions of partial Hermitian matrices

• FORMAT: pdf.
• Number of Pages: 16
• Title: Positive definite completions of partial Hermitian matrices
• Authors:
• GRONE, B. and JOHNSON, C.R. and MARQUES de SA, E. and Wolkowicz, H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {58}, YEAR = {1984}, PAGES = {109--124}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Dimensionality of bi-infinite systems

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Dimensionality of bi-infinite systems
• Authors:
• SMITH, P.W. and Wolkowicz, H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {57}, YEAR = {1984}, PAGES = {115--130}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Bounds for ratios of eigenvalues using traces

• FORMAT: pdf.
• Number of Pages: ?
• Title: Bounds for ratios of eigenvalues using traces
• Authors:
• MERIKOSKI, J. and STYAN, G.P.H. and Wolkowicz, H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {55}, YEAR = {1983}, PAGES = {105--124}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Optimality conditions and shadow prices

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Optimality conditions and shadow prices
• Authors:
• H. Wolkowicz
• Abstract.
• BOOKTITLE = {Mathematical programming with data perturbations, II (Washington, D.C., 1980)}, PAGES = {49--63}, PUBLISHER = {Dekker}, ADDRESS = {New York}, YEAR = {1983}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Facial reduction for a cone-convex programming problem

• FORMAT: pdf.
• Number of Pages: 12
• Title: Facial reduction for a cone-convex programming problem
• Authors:
• Borwein, J.M. and Wolkowicz, H.
• Abstract.
• JOURNAL = {J. Austral. Math. Soc. Ser. A}, FJOURNAL = {Australian Mathematical Society. Journal. Series A}, VOLUME = {30}, YEAR = {1980/81}, NUMBER = {3}, PAGES = {369--380}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Characterization of optimality for the abstract convex program with finite-dimensional range

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Characterization of optimality for the abstract convex program with finite-dimensional range
• Authors:
• Borwein, J.M. and Wolkowicz, H.
• Abstract.
• JOURNAL = {J. Austral. Math. Soc. Ser. A}, FJOURNAL = {Australian Mathematical Society. Journal. Series A}, VOLUME = {30}, YEAR = {1980/81}, NUMBER = {4}, PAGES = {390--411}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Characterizations of optimality without constraint qualification for the abstract convex program

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Characterizations of optimality without constraint qualification for the abstract convex program
• Authors:
• Borwein, J.M. and Wolkowicz, H.
• Abstract. We consider the general abstract convex program (P) minimize f(x), subject to g(x) in -S, where f is an extended convex functional on X, g: X to Y is S-convex, S is a closed convex cone and X and Y are topological linear spaces. We present primal and dual characterizations for (P). These characterizations are derived by reducing the problem to a standard Lagrange multiplier problem. Examples given include operator constrained problems as well as semi-infinite programming problems.
• NOTE = {Optimality and stability in mathematical programming}, JOURNAL = {Math. Programming Stud.}, FJOURNAL = {Mathematical Programming Study}, volume = {19}, YEAR = {1982}, PAGES = {77--100}
• Mathematical Review and direct link to article
• DATE OF ENTRY: May 2000
• Method of reduction in convex programming

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Method of reduction in convex programming
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {J. Optim. Theory Appl.}, FJOURNAL = {Journal of Optimization Theory and Applications}, VOLUME = {40}, YEAR = {1983}, NUMBER = {3}, PAGES = {349--378},
• Mathematical Review
• DATE OF ENTRY: May 2000
• An optimality condition for a nondifferentiable convex program

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: An optimality condition for a nondifferentiable convex program
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {Naval Res. Logist. Quart.}, FJOURNAL = {Naval Research Logistics Quarterly}, VOLUME = {30}, YEAR = {1983}, NUMBER = {3}, PAGES = {415--418}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Some applications of optimization in matrix theory

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Some applications of optimization in matrix theory
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {40}, YEAR = {1981}, PAGES = {101--118}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Convex programs with equivalent duals

• FORMAT: gzipped pdf.
• Number of Pages: ?
• Title: Convex programs with equivalent duals
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {Appl. Math. Notes}, FJOURNAL = {Applied Mathematics Notes}, VOLUME = {5}, YEAR = {1980}, NUMBER = {2}, PAGES = {45--62}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Shadow prices for an unstable convex program

• FORMAT: pdf.
• Number of Pages: ?
• Title: Shadow prices for an unstable convex program
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {Utilitas Math.}, FJOURNAL = {Utilitas Mathematica. A Canadian Journal of Applied Mathematics, Computer Science, and Statistics}, VOLUME = {18}, YEAR = {1980}, PAGES = {119--139}
• Mathematical Review
• DATE OF ENTRY: May 2000
• More bounds for eigenvalues using traces

• FORMAT: pdf.
• Number of Pages: 10
• Title: More bounds for eigenvalues using traces
• (alternate pdf )
• Authors:
• Wolkowicz, H. and STYAN, G.P.H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {31}, YEAR = {1980}, PAGES = {1--17}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Geometry of optimality conditions and constraint qualifications

• FORMAT: pdf .
• Number of Pages: 15 (split)
• Title: Geometry of optimality conditions and constraint qualifications traces
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {Math. Programming}, FJOURNAL = {Mathematical Programming}, VOLUME = {19}, YEAR = {1980}, NUMBER = {1}, PAGES = {32--60}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Bounds for eigenvalues using traces

• FORMAT: pdf.
• Number of Pages: 36
• Title: Bounds for eigenvalues using traces (alternate pdf)
• Authors:
• Wolkowicz, H. and STYAN, G.P.H.
• Abstract.
• JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {29}, YEAR = {1980}, PAGES = {471--506}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Extensions of {S}amuelson's inequality

• FORMAT: gzipped pdf.
• Number of Pages: 2
• Title: Extensions of {S}amuelson's inequality
• Authors:
• Wolkowicz, H. and STYAN, G.P.H.
• Abstract.
• JOURNAL = {Amer. Statist.}, FJOURNAL = {The American Statistician}, VOLUME = {33}, YEAR = {1979}, NUMBER = {3}, PAGES = {143--144}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Calculating the cone of directions of constancy

• FORMAT: gzipped pdf.
• Number of Pages: 4 (split)
• Title: Calculating the cone of directions of constancy
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {J. Optim. Theory Appl.}, VOLUME = {25}, YEAR = {1978}, NUMBER = {3}, PAGES = {451--457}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Calculating the best approximate solution of an operator equation

• FORMAT: gzipped pdf.
• Number of Pages: 32
• Title: Calculating the best approximate solution of an operator equation
• Authors:
• Wolkowicz, H. and S. Zlobec
• Abstract.
• JOURNAL = {Math. Comp.}, VOLUME = {32}, YEAR = {1978}, NUMBER = {144}, PAGES = {1183--1213}
• Mathematical Review
• DATE OF ENTRY: May 2000  (JSTOR version available)
• Regularizing the abstract convex program

• FORMAT: pdf .
• Number of Pages: 36
• Title: Regularizing the abstract convex program
• Authors:
• Borwein, J. and Wolkowicz, H.
• Abstract.
• JOURNAL = {J. Math. Anal. Appl.}, FJOURNAL = {Journal of Mathematical Analysis and Applications}, VOLUME = {83}, YEAR = {1981}, NUMBER = {2}, PAGES = {495--530}
• Mathematical Review
• DATE OF ENTRY: May 2000
• A strengthened test for optimality

• FORMAT: pdf - .
• Number of Pages: 19
• Title: A strengthened test for optimality
• Authors:
• Wolkowicz, H.
• Abstract.
• JOURNAL = {J. Optim. Theory Appl.}, FJOURNAL = {Journal of Optimization Theory and Applications}, VOLUME = {35}, YEAR = {1981}, NUMBER = {4}, PAGES = {497--515}
• Mathematical Review
• DATE OF ENTRY: May 2000
• Cone-convex programming stability and affine constraint functions

• FORMAT: pdf.
• Number of Pages: 19
• Title: Cone-convex programming stability and affine constraint functions
• Authors:
• Borwein J. and Wolkowicz, H.
• Abstract.
• year="1981", booktitle="Generalized Concavity in Optimization and Economics", publisher="Academic Press", pages="379-397", note="invited paper", organization="NATO conference"
• DATE OF ENTRY: May 2000

•