Machine Learning with Knowledge under Infinitely Many Constraints
Zhenan Fan, Jiyoung (Haesol) Im, Tyler Weames, Henry Wolkowicz, Yong Zhang,
Zirui Zhou, August 2022, Paper ID: 6399, Thirty-Seventh AAAI Conference
on Artificial Intelligence, Microsoft CMT, (PC.LP IPM Benchmark
Problems)
MSc thesis of Mike Froh, title:
Trust Region Subproblems and Linear Least-Squares Regularization,
Dec, 2003
MSc thesis of Nathan Krislock, title:
Numerical solution of semidefinite least squares problems. Master's
thesis, University of British Columbia, 2003. (supervisor Jim Varah)
(
pdf file)
Journal Special Issue on Semidefinite Programming, editors P. PARDALOS
and H. Wolkowicz,
Kluwer Academic Publishers,
J. Combinatorial Optimization, volume 2.1, 1998.
Book:: Quadratic assignment and related problems, editors P. PARDALOS and
H. Wolkowicz, Publisher, American Mathematical
Society,
DIMACS Series in Discrete
Mathematics and Theoretical Computer Science volume 16, 1994.
Mathematical Review
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; appeared Jun/14
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",
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.
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.
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.
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}
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.
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.
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
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.
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.
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.
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.
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.
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.
Title:
On Efficient Semidefinite Relaxations for Quadratically Constrained
Quadratic Programming
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.
Title:
On Efficient Semidefinite Relaxations for Quadratically Constrained
Quadratic Programming
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.
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
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.
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.
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.
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.
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.
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
Generating Hard Instances of SDP:
The two MATLAB files: (i)
rungenHard.m (which uses
writesdpa.m from
CSDP webpage to get both SeDuMi format and .dat-s format), and (ii)
genHardSDP.m,
generate hard instances of SDP. These are SDP problems where strict
complementarity fails.
This tar file contains the MATLAB mat files with the
test problems gap0 to gap24 used in
the research report
genhardsdp.pdf.
Title:
Regularization Using a Parameterized Trust Region Subproblem
(Master's thesis of Oleg Grodzevich) (/mopta01mfiles.d/oleg.d)
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.
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.
Title:
Regularization Using a Parameterized Trust Region Subproblem
(/mopta01mfiles.d/oleg.d)
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
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
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
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$.
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.
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.
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.
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.
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"
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.
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 OMS Vol 19 No 1 Feb 2004, pp41-67
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.
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.
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: appeared in EJOR, 2002, vol 143, no 2, pgs 356-364
DATE OF ENTRY: Dec 3, 1999, revised on Dec 5, 2001
Matrix Completion Problems, November, 1999.
FORMAT: in
Handbook of SDP, Kluwer Academic changed to Springer, 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.
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.
available by anonymous ftp at www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL: http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
proccambridge.ps
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.
available by anonymous ftp at www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL:
http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
applhandbk.ps
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.
available by anonymous ftp at www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL: http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
strengthMC.ps
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
G. GRUBER and S. KRUK and F. RENDL and H. Wolkowicz
available by anonymous ftp at www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL: http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
presolving.ps
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
Kurt Anstreicher, Xin Chen, Henry Wolkowicz, and Ya-Xiang Yuan
available by anonymous ftp at www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL: http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
sdptrsqap.ps
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.
University of Waterloo
Department of Combinatorics and Optimization
Waterloo, Ontario N2L 3G1, Canada
available by anonymous ftp at www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL: http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
dualityencycl.ps
To appear in the Encyclopedia of Optimization
STATUS: to appear.
DATE OF ENTRY: June 1, 1998
On Lagrangian Relaxation of Quadratic Matrix
Constraints, 1999
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 www.math.uwaterloo.ca, in directory
pub/henry/reports and also with URL: http://www.math.uwaterloo.ca:80/~hwolkowi/henry/reports/
qqplagrng.ps
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".
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
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.
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
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
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.
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.
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.
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.
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
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.
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)
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.
strong duality for semidefinite programming
Authors:
Ramana/Tuncel/Wolkowicz
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.
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.
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@www.math.uwaterloo.ca
and URL: http://www.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.
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.
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
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.
A related semidefinite programming, SDP, code for the max-cut problem
using the HKM direction:
matlab code maxcut.m for the SDP relaxation of the Max Cut problem
is available.
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
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.
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",
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.
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)
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.
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.
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.
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
EXPLICIT SOLUTIONS FOR INTERVAL SEMIDEFINITE LINEAR PROGRAMS\footnote{This
report is available by anonymous ftp at www.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@www.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.
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@www.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"
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)
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
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"
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
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.
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},
JOURNAL = {J. Optim. Theory Appl.},
FJOURNAL = {Journal of Optimization Theory and Applications},
VOLUME = {47},
YEAR = {1985},
NUMBER = {1},
PAGES = {51--64}
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}
JOURNAL = {J. Optim. Theory Appl.},
FJOURNAL = {Journal of Optimization Theory and Applications},
VOLUME = {40},
YEAR = {1983},
NUMBER = {3},
PAGES = {349--378},
JOURNAL = {J. Optim. Theory Appl.},
FJOURNAL = {Journal of Optimization Theory and Applications},
VOLUME = {35},
YEAR = {1981},
NUMBER = {4},
PAGES = {497--515}
Back
to the home page of Henry Wolkowicz
or