 |
Semidefinite Programming and Interior-Point Approaches for Combinatorial
Optimization Problems
Titles and/or Abstracts for
May 15- Friday 17, 1996
(before the SIAM Conference on Optimization in Victoria)
to be held The Fields Institute, Toronto, Ontario, Canada
List of Speakers
- Yakov Alber
- Arjan Berkelaar (speaker) and Shuzhong Zhang
- Dimitris Bertsimas
- Ding-Zhu Du
- M. R. Emamy-K.
- Leonid Faybusovich
- Jun Gu
- Christoph Helmberg (speaker), Franz Rendl, R. Weismantel
- Charles Johnson
- Stefan Karisch (speaker) and Franz Rendl
- Philip Klein and Hsueh-I Lu (speaker)
- Kees Roos , Tamas Terlaky, Etienne de Klerk (speaker)
- Monique Laurent
- LE THI Hoai An (speaker) and PHAM DINH Tao
- Chih-Jen Lin and Romesh Saigal (speaker)
- Zhi-Quan Luo (speaker), Jos F. Sturm and Shuzhong Zhang
- Borin Mirkin
- John E. Mitchell
- Jonas MOCKUS, Audris MOCKUS, and Linas MOCKUS (speaker)
- Renato Monteiro
- Manuel A. Nunez (speaker) and Robert M. Freund
- Laura Palagi (speaker) and Stefano Lucidi
- Panos Pardalos and Mauricio G.C. Resende (speaker)
- Gabor Pataki
- PHAM DINH Tao (speaker) and LE THI Hoai An
- Lorant Porkolab (speaker) and Leonid Khachiyan
- M. Ramana
- Franz Rendl (speaker) and Christoph Helmberg
- Kees Roos (speaker), Tamas Terlaky, Etienne de Klerk
- Alexander Shapiro
- D. Goldfarb and Katya Scheinberg (speaker)
- Jos F. Sturm (speaker), Zhi-Quan Luo, and Shuzhong Zhang
- J.P. Warners, Tamas Terlaky(speaker), C. Roos, B. Jansen
- Michael J. Todd (speaker), Kim Chuan Toh, Reha H. Tutuncu
- Lieven
Vandenberghe (speaker), Stephen Boyd, Shao-Po Wu
- Yinyu Ye
- Shuzhong
Zhang (speaker) and Jos F. Sturm
- Yin Zhang
- Qing Zhao (speaker), Stefan E. Karisch, Franz Rend, and Henry Wolkowicz
Ya. I. Alber
Haifa Technion
Department of Mathematics
Haifa, Israel
Visiting Professor in IMPA
(Institute for Pure and Applied Mathematics), Rio de Janeiro, Brazil
alberya@impa.br
The analysis of a convergence, stability and estimates of convergence
rate of iterative methods of optimization, is usually organized by
the following way. The suitable Lyapunov function $W(.)$ is constructed,
and a link between its values on two successive iterations $W_n$ and
$W_(n+1)$ is established. Therefore it is used some information about
parameters of the process $\alpha_n, \beta_n,...,$ about errors of
different subjects - for example, functional, its gradient or subgradient,
set of constrains, etc. - $\gama_n$, and additional information about
the nature of the degeneration of the problem, described by means
of nonlinear function $\Psi_1(W)$; smoothness is described by $\Psi_2(W)$.
In general case, this recurrent link is represented as the following:
(*) W_{n+1} \leq (1+\beta_n) W_n - \alpha_n \Psi(W_n) + \gama_n, n=1,2,...
In the talk, the results of studying such inequalities, including
a convergence of $W_n$ to nought and nonasymptotic estimates of the
convergence rate: $W_n \leq \Hi(n) -> 0$ are going to be revealed.
The results of investigation of (*), with conditions of the complete
lack of information about uniform degeneration's character, are going
to be presented for the first time. I will pay a special attention
to applications of those results to the problems of nonlinear and
stochastic programming and approximation, variational inequalities
and complementarity problems.
-
Convergence Issues and Path-following Algorithms
for Semidefinite Programmin
Arjan Berkelaar (speaker) and Shuzhong Zhang
Econometric Institute
Erasmus University Rotterdam
P.O. Box 1738, 3000 DR Rotterdam
The Netherlands
Recently, Kojima, Shindoh and Hara \cite{KoShHa:94} proposed a family
of primal--dual interior--point algorithms for the monotone semidefinite
linear complementarity problem. These algorithms were further analyzed
by Monteiro \cite{sdp:Monteiro}, who presented a polynomially convergent
long--step path--following algorithm for semidefinite programming.
In this presentation we will discuss some convergence issues related
to these algorithms.
Dimitris Bertsimas
E52-436
School Of Mgmt
MIT
Cambridge, MA 02139
(617) 253-4223
DBERTSIM@ARIS,MIT.EDU
Starting from physical (conservation) laws for stochastic and dynamic
optimization problems arising in manufacturing and communication systems
we propose linear and semidefinite relaxations that provide bounds
for this class of problems. We further propose near-optimal policies
using ideas from infinite linear programming and control theory. Our
algorithm solves large scale problems very efficiently.
Ding-zhu Du
Department Of Computer Science
Institute Of Technology
4-192 EE/CS Building
Minneapolis MN 55455-0159
U.S.A.
fax no.: 612 6250572
phone no.: 612 6254002
E-mail: dzd@cs.umn.edu
In this paper, we study a problem with application in VLSI design.
The problem is formulated as a 0-1 integer programming. We found an
interesting polynomial-time approximation by relaxation method. Both
theoretical and computational results will be presented.
How efficient can we maximize threshold
pseudo-Boolean functions ?
M. R. Emamy-K.
Departments of Mathematics
Box 23355
University of Puerto Rico
Rio Piedras 00931
A well-known open problem posed by P. L. Hammer et. al. as follows:
Is there an algorithm that maximizes threshold pseudo-Boolean functions
in a polynomial number of steps ?
Even though the general problem remains to be open, here we talk about
different subclasses of threshold pseudo-Boolean functions for which
such polynomial algorithm exists.
Infinite-dimensional semidefinite programming:self-concordant
barriers and path-following algorithms.
Leonid Faybusovich,
Notre Dame University
We discuss possible approaches to generalizations of the semidefinite
programming in the more general context of an infinite-dimensional
version of the Nesterov-Nemirovsky scheme. Examples of (infinite-dimensional)
operator domains descibed by semidefinite constraints for which there
exist self-concordant barriers are presented. Path-following algoriths
are considered.
Parallel Algorithms for Satisfiability (SAT)
Problem
Jun Gu, Hong Kong Univ. of Science
and Technology
The satisfiability (SAT) problem is a central problem in mathematical
logic, computing theory, and artificial intelligence. In practice,
the SAT problem is fundamental in solving many practical application
problems. Methods to solve the SAT problem play an important role
in the development of computing theory and intelligent computing systems.
There has been great interest in the design of efficient algorithms
to solve the SAT problem. Since the past decade, a variety of parallel
processing techniques have been developed to solve the SAT problem.
The goal of this paper is to expose the rapidly growing field, to
discuss tradeoff and limitations, and to describe ten state-of-the-art
techniques, both algorithms and special-purpose architectures, for
parallel processing of the satisfiability problem.
Quadratic Knapsack Relaxations Using Cutting
Planes and Semidefinite Programming
Christoph Helmberg (speaker), Franz
Rendl, R. Weismantel (University of Graz)
The quadratic knapsack problem is the easiest case of constrained
0/1 quadratic programming and is extremely difficult to solve by linear
programming alone. Semidefinite programming is well known to provide
powerful relaxations for quadratic 0/1 programming and, as we intend
to show, it is very useful for quadratic knapsack problems as well.
We compare several possibilities for setting up initial relaxations
and show that in the special case of linear cost functions some are
even better than the canonical linear relaxation. We discuss possible
strengthenings of these relaxations by polyhedral cutting plane approaches
in theory and in practice. The main practical difficulty with semidefinite
approaches is the high computational cost involved. These stem from
the factorization of a completely dense symmetric positive definite
matrix with dimension equal to the number of constraints. To keep
the number of constraints small it is of major importance to understand
the interaction and dominance relations between different classes
of cuts. We give several theoretical results in this direction. Finally,
we present computational results of this approach on practical data.
Recent Progress on Matrix Completion
problems
Charles R. Johnson, College
of William and Mary
A matrix completion problem asks under what circumstances a partial
matrix has a completion of a desired type. Theory associated with
the positive definite and related completion problems is the most
well developed. For example, if the pattern of specified off-diagonal
entries corresponds to a chordal graph, then there are simple formulas
for optimal completions; and, if not, simple formulas do not exist,
but there are computational techniques, including important ones based
upon semidefinite programming. Here, we discuss analogous progress
on other completion problems, such as those for totally positive matrices,
P-matrices, inverse M-matrices, completely positive and doubly nonnegative
matrices.
Semidefinite Programming and Graph Equipartition
Stefan Karisch
(speaker) and Franz Rendl (University of Graz)
Semidefinite relaxations are used to approximate the problem of partitioning
a graph into equally sized components. The relaxations extend previous
models, and combine semidefinite and polyhedral approaches. Theoretical
comparisons with other bounds for the graph equipartition problem
based on continuous relaxations are investigated. We show that certain
semidefinite relaxations coincide with eigenvalue approaches proposed
in the literature. We also discuss algorithmic and computational aspects.
Numerical results on graphs with several hundred vertices are given,
and indicate that semidefinite relaxations approximate the equipartition
problem quite well.
Approximation algorithms for semidefinite
programs arising from MAX CUT and COLORING
Philip Klein and Hsueh-I Lu (speaker) (Brown University)
Linear programming has proved a useful tool in the design of approximation
algorithms. Goemans and Williamson showed (1994) that a more general
kind of mathematical programming, namely semidefinite programming,
is similarly useful; they gave an approximation algorithms for MAX
CUT that depends on solving a semidefinite program. Karger, Motwani,
and Sudan then showed (1994) a similar approach yields an approximation
algorithm for graph coloring. In each of these algorithms, the computational
bottleneck is solving the semidefinite program. We show that for constant
$\epsilon$ a $(1+\epsilon)$-approximate solution to these programs
can be obtained in $O(n m \log^3 n)$, where $n$ is the number of nodes
and $m$ is the number of edges.
Method of approximate centers for semidefinite
programming
Kees Roos, Tamas Terlaky, Etienne de Klerk (speaker)
Faculty of Technical Mathematics and Informatics
Delft University of Technology
P.O. Box 5031, 2600 GA Delft, The Netherlands
e--mail
E.deKlerk@twi.tudelft.nl
C.Roos@twi.tudelft.nl
T.Terlaky@twi.tudelft.nl
The success of interior point methods for large--scale linear programming
(LP) has prompted researchers to extend these algorithms to semidefinite
programming (SDP). In this presentation we extend the method of approximate
centers of Roos and Vial to SDP. It is a short--step, path--following,
primal algorithm, and the extention from LP to SDP is surprisingly
straightforward and elegant. The search direction is shown to be a
projection of the scaled Newton direction of the primal barrier function.
A connection between positive semidefinite
and Euclidean distance matrix completion problems
Monique Laurent
Liens
Ecole Normale Superieure
45 ru d'Ulm
75230 Paris Cedex 05, France
laurent@dmi.ens.fr
The positive semidefinite and Euclidean distance matrix completion
problems have received a lot of attention in the literature. Interestingly,
results have been obtained for these two problems that are very similar
in their formulations. Although there is a strong relationship between
positive semidefinite matrices and Euclidean distance matrices, it
was not clear how to link the two completion problems. We show how
the results for the Euclidean distance matrix completion problem can
be derived from the corresponding results for the positive semidefinite
completion problem, using a functional transform introduced by Schoenberg.
An efficient adapted DCA & Branch-and-Bound
algorithm for globally solving large-scale 0-1 quadratic programming
problems
LE THI Hoai An (speaker)
\& PHAM DINH Tao
Mathematical Modelling and Applied Optimization Group
LMI-INSA Rouen - CNRS URA 1378.
BP 08 76131 Mont Saint Aignan, France
lethi@insa-rouen.fr
pham@insa-rouen.fr
We are interested in solving the well-known 0-1 quadratic programming
\[\alpha = \min \{ \frac{1}{2} x^T Qx + q^Tx: \: Ax \leq b, \: x \in
\{0,1\}^n\} \quad (1)\] by applying a combined DCA \& Branch-and-Bound
algorithm (in a continuous approach) to the following equivalent nonconvex
problem \[\alpha = \min \{ \frac{1}{2} x^T (Q-tI)x + (q+(t/2)e)^T
x: \: Ax \leq b, \: x \in [0,1]^n\} \quad (2) \] where $e$ is the
vector of ones and $t \geq t_o >0$. We use rectangular bisection
in the branching procedure while the bounding one proceeds by applying
DCA to (2) from the current best feasible point (for the upper bound)
and by minimizing a well tightened convex underestimation of the objective
function on the current subdivided domain (for the lower bound). As
for DCA ("difference of convex function" optimization algorithm) introduced
by PHAM DINH Tao, it is an efficient local algorithm which produces
quite often a global solution. Finally we present numerical results
for several test problems (0-1 Knapsack problem, Set Covering and
set Packing problems, Facility location problem...) which prove the
efficiency of our method.
An infeasible start predictor corrector
method for semidefinite linear programming
Chih-Jen Lin and Romesh Saigal (speaker)
(University of Michigan)
This talk will consider an infeasible start predictor corrector pathfollowing
method for the semidefinite programming problem. The method will be
shown to converge globally. We do not assume that the dual pair of
semidefinite linear programs have feasible solutions and in a finite
and polynomial number of steps discover if they have no optimum solution
with duality gap zero in a well defined bounded region. The method,
starting with the initial vectors determined by $\rho$, in at most
$O(\mbox{log}(\frac{\delta\rho}{\epsilon}n)$ predictor and corrector
steps will discover either that there are no optimal solutions with
duality gap zero in a well defined bounded region determined by $\rho$
or find a pair of solutions which satisfy approximately the constraints,
the approximation and duality gap determined by $\epsilon$. Here $\delta$
is a polynomial function of the data. We also present some computational
experience with this method.
Superlinear Convergence of a Symmetric Primal-Dual
Path Following Algorithm for Semidefinite Programming
ps file is available
Zhi-Quan Luo (speaker)
(McMaster Univ.)
Jos F. Sturm and Shuzhong Zhang, Erasmus University Rotterdam
This paper establishes the superlinear convergence of a symmetric
primal-dual path-following algorithm for semidefinite programming
under the sole assumption that the semidefinite program has a strictly
complementary primal-dual optimal solution. The interior point algorithm
considered here closely resembles the Mizuno-Todd-Ye predictor-corrector
method for linear programming which is known to be quadratically convergent.
It is shown that when the iterates are well centered the duality gap
is reduced superlinearly after each predictor step. In fact, if each
predictor step is succeeded by $r$ consecutive corrector steps then
the predictor reduces the duality gap at a superlinear rate of $\frac{2}{1+2^{-2r}}$.
The proof relies on a careful analysis of the central path for semidefinite
programming. It is shown that under the strict complementarity assumption,
the primal-dual central path converges to the analytic center of the
primal-dual optimal face, and the distance from any point on the central
path to this analytic center is bounded by the duality gap.
Approximation Clustering: A Mine of Semidefinite
Programming Problems
Boris Mirkin
DIMACS, Rutgers University, USA
and CEMI, Moscow, Russia
mirkin@dimacs.rutgers.edu
Approximation clustering is a set of clustering models and methods
based on approximate decomposing the data table through scalar product
matrices representing weighted subsets, partitions or hierarchies
as the sought clustering structures. Both crisp and fuzzy structures
can be considered. In this framework, the following research subjects
seem of particular interest: (1) developing clustering models that
are adequate statistical models for substantive problems; (2) analyzing
relations between approximation clustering and other data analysis
approaches (first af all, the genuine cluster analysis techniques);
(3) analyzing and solving the corresponding optimization problems.
A dozen of approximation clustering optimization problems will be
reviewed, mostly in the framework of SEFIT, a doubly greedy optimization
strategy developed by the author as fitting into traditional clustering.
Some of the problems are quite known as multi-min-cut and maximum-density-subgraph,
the others are unstudied at all, even those quite similar to the classical
ones.
Using an Interior Point Algorithm in
a Cutting Plane Method for Solving Integer Programming Problems
John E. Mitchell
Amos Eaton 325
Math Sciences
Rensselaer (RPI)
Troy NY 12180 USA
Phone: (518) 276-6915
Fax: (518) 276-4824
Email: mitchj@rpi.edu
WWW: http://www.math.rpi.edu/~mitchj
We continue our investigation of the use of interior point algorithms
to solve the linear programming relaxations in a cutting plane method.
Techniques used include attempting to identify cutting planes early
and storing an old feasible point (for recentering when adding cutting
planes). Computational results are presented for several different
classes of integer programming problems.
BAYESIAN APPROACH TO COMBINATORIAL OPTIMIZATION
ps
file is available
Jonas MOCKUS
Institute of Mathematics and Informatics
Akademijos 4, Vilnius, Lithuani
and
Audris MOCKUS
AT\&T Bell Laboratories
Naperville, IL 60566
and
Linas MOCKUS (speaker)
School of Chemical Engineering, Purdue University
W.Lafayette, IN 47907-1283
We consider the average deviation as a criterion when designing numerical
techniques and algorithms. We call that a Bayesian approach. First
we describe in short the Bayesian approach to the continuous global
optimization. Then we show how to apply the results to the calibration
of parameters of randomized heuristic techniques of combinatorial
optimization.
The new idea of this research is to define an a priori distribution
on a set of heuristic decision rules. The usual way is to define it
on a set of functions to be minimized. The definition of the a priori
distribution on the set of heuristic decision rules helps to include
the expert knowledge and to speed up the search.
We show the advantages and disadvantages of the Bayesian heuristics
approach applying this approach in different problems of combinatorial
and discrete optimization such as knapsack, flow-shop, traveling salesman,
parameter grouping, and scheduling of batch operations.
We describe the software for UNIX and DOS platforms.
We consider the average deviation as a criterion when designing numerical
techniques and algorithms. We call that a Bayesian approach. First
we describe in short the Bayesian approach to the continuous global
optimization. Then we show how to apply the results to the calibration
of parameters of randomized heuristic techniques of combinatorial
optimization.
The new idea of this research is to define an a priori distribution
on a set of heuristic decision rules. The usual way is to define it
on a set of functions to be minimized. The definition of the a priori
distribution on the set of heuristic decision rules helps to include
the expert knowledge and to speed up the search.
We show the advantages and disadvantages of the Bayesian heuristics
approach applying this approach in different problems of combinatorial
optimization such as knapsack, flow-shop, traveling salesman, parameter
grouping, and scheduling of batch operations.
We describe the software for UNIX and DOS platforms.
A latex
file with the abstract and an outline, is available. The file
is 290 lines.
Primal-Dual Path Following Algorithms
for Semidefinite Programming
Renato Monteiro
School of ISyE, Georgia Institute of Technology
Atlanta, GA 30332, USA
monteiro@isye.gatech.edu
This talk deals with a class of primal-dual interior-point algorithms
for semidefinite programming (SDP) which was introduced by Kojima,
Shindoh and Hara. By characterizing their search direction as the
unique solution of a system of linear equations in symmetric variables,
we present: 1) a simplified polynomial convergence proof for their
short-step path following algorithm and, 2) for the first time, a
polynomially convergent long-step path following algorithm for SDP.
We also discuss how our approach can be used to extend many other
feasible and infeasible primal-dual LP methods to SDP.
Condition Measures and Properties of the
Central Trajectory of a Semidefinite Program
Manuel A. Nunez (speaker) and Robert M. Freund,
Operations Research Center
Massachusetts Institute of Technology, Cambridge, MA 02139
Renegar's condition number measures how well conditioned the data
is for a linear program with data d = (A,b,c). We extend this notion
to semidefinite programming and use it to prove characterizations
of the distance to ill-posedness of a given data instance, upper and
lower bounds on sizes of solutions, and rates of change of solutions
along the central trajectory of a semidefinite program.
Trust region Problems: Theoretic Results
and New Algorithmic Developments
Laura Palagi (speaker) and Stefano Lucidi (Universit`a di Roma "La
Sapienza")
ps file is available
We consider a trust region problem, namely the problem of minimizing
a (possibly nonconvex) quadratic function with a quadratic constraint.
We point out some new theoretic properties of the problem. In particular,
we show that (i) given a KKT point that is not a global minimizer,
it is easy to find a "better" feasible point; (ii) strict complementarity
holds at the local-nonglobal minimizer. Moreover, we show that the
original constrained problem is equivalent to the unconstrained minimization
of a piecewise quartic merit function. Using the unconstrained formulation
we give, in the nonconvex case, a new second order necessary condition
for global minimizers. On the basis of the unconstrained formulation,
we define a Truncated Newton scheme particularly suitable for defining
a new efficient algorithm for large scale trust region problems. We
report some numerical experiments obtained by a preliminary matlab
code.
Using linear programming to help solve
quadratic assignment problems
Mauricio G.C. Resende (speaker)
AT&T Bell Laboratories, Murray Hill
and Panos Pardalos, University of Florida, Gainsville.
In this talk, we consider the exact solution of the quadratic assignment
problem. We present a parallel branch and bound algorithm that uses
linear programming to produce very effective lower bounds. Two LP-based
lower bounds are considered, one of which has been shown to produce
100 percent tight lower bounds for all instances of QAPLIB, a standard
library of QAP test problems, having dimension less than or equal
to 12. Since the linear programs are large-scale and highly degenerate,
simplex method LP solvers, such as CPLEX and IBM OSL can solve only
the smallest of instances. Likewise, since the Cholesky factors of
the direction-determining matrices have high levels of fill-in, interior
point implementations that use direct factorizations, such as CPLEX
barrier, IBM OSL barrier, and OB-1, are ineffective. The LP-solver
used in our code uses a preconditioned conjugate gradient algorithm
to approximately compute the interior point directions and has solved
QAP LP-based lower bound linear programs with over 150,000 constraints
and 300,000 variables. We present computational results that show
the effectiveness of these lower bounds.
(Parts of this research have been done jointly with K.G. Ramakrishnan
(AT&T Bell Laboratories), P.M. Pardalos (U. of Florida), Z. Drezner
(California State U. at Fullerton), B. Ramachandran (Purdue U.) and
J.F. Pekny (Purdue U.).)
Cone-LP's and Semidefinite Programs: Geometry
and a Simplex-type Method
Gabor Pataki (University of Waterloo)
We consider optimization problems expressed as a linear program with
a cone constraint. Cone-LP's subsume ordinary linear programs, and
semidefinite programs. We study the notions of basic solutions, nondegeneracy,
and feasible directions, and propose a generalization of the simplex
method for a large class including LP's and SDP's. One key feature
of our approach is considering feasible directions as a sum of {\em
two} directions. In LP, these correspond to variables leaving and
entering the basis, respectively. The resulting algorithm for SDP
inherits several important properties of the LP-simplex method. In
particular, the linesearch can be done in the current face of the
cone, similarly to LP, where the linesearch must determine only the
variable leaving the basis.
D.c. (difference of convex functions) Optimization:
Theory, Algorithms & Aplications
PHAM DINH Tao (speaker) and LE THI Hoai An
Mathematical Modelling and Applied Optimization Group
LMI-INSA Rouen - CNRS URA 1378.
BP 08 76131 Mont Saint Aignan, France
lethi@insa-rouen.fr
pham@insa-rouen.fr
D.c. program is of the form \[\alpha = \inf\{f(x) - h(x): x \in \R^n\}
\hspace{1cm} (P) \] where $g,h$ are convex, lower semicontinuous and
proper on $\R^n$. The function $f$ is called d.c. function and $g,h$
its d.c. components. We present the theory of d.c. programming: d.c.
duality, local \& global optimality conditions and stability of
Lagrangian duality. D.c. programming marks the passage from convex
optimization to nonconvex optimization. This extension is large enough
to cover most real-life problems but not too much for still being
allowed to use the convex analysis tools. We give the description
of DCA (D.c. Algorithm) (based on the d.c. duality and the local optimality
conditions) and its general convergence, in particular the finite
convergence of DCA in d.c. polyhedral programming (i.e. when $g$ or
$h$ is polyhedral convex). D.c. objective function has infinitely
many d.c. decompositions which may have an important influence on
the qualities (robustness, stability, rate of convergence and globality
of sought solutions) of DCA. In pratice rgularization techniques using
the kernel $(\lambda)/2\|.\|^2$ and inf-convolution may provide interesting
d.c. decompositions of objective functions for DCA. In general DCA
converges to a local solution however we observe that it converges
quite often to a global one. So it is particularly interesting to
combine DCA and Branch-and-Bound method for globally solving large-scale
nonconvex programs. Finally some given applications of DCA to solving
Trust Region subproblems, Multidimensional Scaling problem, Nonconvex
quadratic programming problem, Mixed 0-1 quadratic programming in
image restoration processing, Optimization over the Efficient Set
problem, ...) have proved its efficiency, especially in the large-scale
setting.
Bounds on Feasible Solutions of Semidefinite
Programs
Lorant Porkolab (speaker) and Leonid Khachiyan (RUTCOR)
We give upper and lower bounds on solution norms and the sensitivity
of semidefinite programs. We also discuss their complexity implications,
including the polynomial-time solvability of semidefinite programs
with a fixed number of variables or constraints.
Recognition of Polyhedral Semidefinite
Programs
M. Ramana (University of Florida, Gainsville)
A spectrahedron is defined to be a set of the type $\{x|Q(x)\succeq
0\}$, where $Q(x)$ is an affine matrix map. Semidefinite Programming
involves optimizing linear functions over spectrahedra. It is easy
to show that every polyhedron is a spectrahedron. The question investigated
here is characterization and recognition of matrix maps $Q(x)$ for
which the associated spectrahedron is a polyhedron. After developing
a decomposition based characterization, it is shown that the general
recognition problem is NP-Hard. However, under an irredundancy assumption
on the map $Q(x)$, the problem can be solved in randomized polynomial
time. The problem has some connections with the question of when a
given graph is perfect.
Large Scale SDP using eigenvalues
Franz Rendl (speaker) and Christoph Helmberg (University of Graz)
We discuss the problems arising, when solving SDP using interior point
based techniques. An alternative is to use the formulation of the
dual as an eigenvalue optimization problem. The advantage of this
approach lies in the fact, that extreme eigenvalues of symmetric matrices
can be computed without having the matrix explicitely available. Moreover,
the dual does not increase in size, if additional primal constraints
are added. The disadvantages are also obvious. First, eigenvalue optimization
is a nonsmooth problem. Secondly, it is nontrivial to generate a good
primal solution, if the dual problem is not solved exactly. We show
how to handle both issues: the solution of a special linear program
will provide a descent direction, even if the largest eigenvalue is
not simple. The dual of this LP provides a primal solution for the
SDP. We present some preliminary computational experiments of this
approach, applied to the semidefinite relaxation of the max-cut problem
Initialization in semidefinite programming
via a self-dual embbedding
Kees Roos (speaker), Tamas Terlaky, Etienne de Klerk
Faculty of Technical Mathematics and Informatics
Delft University of Technology
P.O. Box 5031, 2600 GA Delft, The Netherlands
e--mail
E.deKlerk@twi.tudelft.nl
C.Roos@twi.tudelft.nl
T.Terlaky@twi.tudelft.nl
Motivated by the success of interior point methods for large--scale
linear programming the field of interior point algorithms for semidefinite
programming has become an active research area. Many interior point
methods for linear programming have now been extended to the more
general semidefinite case, but the initialization problem is still
not well solved for the semidefinite case. We show that the initialization
strategy for linear programming which embeds a given problem and its
dual in a self--dual skew--symmetric problem can be extended in a
natural way to the semidefinite case. In this way the initialization
problem for semidefinite problems can be solved nicely. The method
also provides a solution for the initialization of quadratic programs
and it is applicable as well to more general convex problems with
conic formulation.
SECOND ORDER OPTIMALITY CONDITIONS AND
STABILITY ANALYSIS OF SEMI-DEFINITE PROGRAMS
Alexander Shapiro (Georgia Tech Univ.)
In this talk we discuss second order optimality conditions in semi-definite
programming. In particular we show that the cone of positive semi-definite
matrix has a certain property which allows to close the gap between
second order necessary and second order sufficient conditions. We
also discuss applications of these results to stability analysis of
semi-definite programs.
Interior Point Trajectories in Semidefinite
Programming
D. Goldfarb and K. Scheinberg (speaker)
Columbia University, Dept. of IEOR, New York, NY
We study interior point trajectories in semidefinite programming (SDP)
including the central path of an SDP. This work was inspired by the
seminal work by Megiddo on linear programming trajectories (\cite{M}).
Under an assumption of primal and dual strict feasibility, we show
that the primal and dual central paths exist and converge to the analytic
centers of the optimal faces of, respectively, the primal and the
dual problems. We define a class of trajectories that are similar
to the central path, but can be constructed to pass through any given
interior feasible point and study their convergence. Finally, we relate
these trajectories and the central path to interior point methods
by showing that at any given point along any one of these trajectories,
the direction of the tangent corresponds to a direction of an interior
point method. We also consider the limiting behavior of the derivatives
associated with these trajectories.
Duality and self-duality for semidefinite
and conic convex programming
ps file is available
Zhi-Quan Luo (McMaster Univ.)
Jos F. Sturm (speaker) and Shuzhong Zhang, Erasmus University Rotterdam
It is known that in semidefinite and conic convex programming, we
have to distinguish between strong versus weak infeasibility, and
strong duality versus the existence of a complementary pair, whereas
such distinctions do not exist for linear programming. We show that
a generalization of the self-dual feasibility model of Goldman and
Tucker can only give (1) a complementary solution, (2) a certificate
of strong infeasibility or (3) show that the problem is neither strongly
infeasible nor endowed with a complementary pair. However, we propose
an extended self-dual program with a trivial complementary solution
and the following properties: Any weakly centered sequence converging
to a complementary pair either induces a sequence converging to a
certificate of strong infeasibility, or it induces a sequence of primal-dual
pairs for which the amount of constraint violation converges to zero,
and the corresponding objective values are in the limit not worse
than the optimal objective value(s). We also generalize the stopping
rules of Todd and Ye, so that precise conclusions can be drawn based
on an approximate solution to the extended self-dual program.
KEY WORDS: conic convex programming, semidefinite programming, duality,
self-duality.
Potential reduction algorithms for structured
combinatorial optimization problems
J.P. Warners, T. Terlaky(speaker), C. Roos, B. Jansen
Department of Statistics, Probability and Operations Research
Faculty of Technical Mathematics and Informatics
Delft University of Technology
P.O. Box 5031, 2600 GA Delft, The Netherlands.
Tel.: (015)2782547, FAX: (015)2787255
e-mail: t.terlaky@twi.tudelft.nl
Recently Karmarkar proposed a potential reduction algorithm for binary
feasibility problems. In this paper we point out a practical drawback
of his potential function and we propose a modified potential function
that is computationally more attractive. As the main result of the
paper, we will consider a special class of binary feasibility problems,
and show how problems of this class can be reformulated as nonconvex
quadratic optimization problems. The reformulation is very compact
and a further interesting property is, that (instead of just one)
multiple solutions may be found by optimizing it. We introduce a potential
function to optimize the new model. Finally, we report on computational
results on several instances of the graph coloring and frequency assignment
problem, comparing the three potential functions.
Michael J. Todd (speaker), School of OR, Cornell University
Kim Chuan Toh, Center for Applied Mathematics, Cornell University
Reha H. Tutuncu, School of OR, Cornell University
Nesterov and Todd discuss several path-following and potential-reduction
interior-point methods for certain convex programming problems. In
the special case of semidefinite programming, we discuss how to compute
the corresponding directions efficiently and how to view them as Newton
directions.
Determinant Maximization with linear matrix
inequality constraints
gzipped ps file
is available
Lieven Vandenberghe (speaker), Stephen Boyd, Shao-Po Wu
Information Systems Laboratory, Durand 109
Department of Electrical Engineering
Stanford University
Stanford, CA 94305
The problem of maximizing the determinant of a matrix subject to linear
matrix inequalities arises in many fields, including computational
geometry, statistics, system identification, experiment design, and
information and communication theory. It can also be considered as
a generalization of the semidefinite programming problem. We give
an overview of the applications of the determinant maximization problem,
pointing out simple cases where specialized algorithms or analytical
solutions are known. We then describe an interior-point method, with
a simplified analysis of the worst-case complexity and numerical results
that indicate that the method is very efficient, both in theory and
in practice. Compared to existing specialized algorithms (where they
are available), the interior-point method will generally be slower;
the advantage is that it handles a much wider variety of problems.
On the complexity of approximating a KKT point
of quadratic programming
Yinyu Ye, Iowa State University
We present a potential reduction algorithm to approximate a Karush-Kuhn-Tucker
(KKT) point of general quadratic programming. We show that the algorithm
is a fully polynomial-time approximation scheme, and its running-time
dependency on accuracy $\epsilon\in (0,1)$ is $O((1/\epsilon)\log(1/\epsilon)\log(\log(1/\epsilon)))$,
compared to the previously best-known result $O((1/\epsilon)^2)$.
Furthermore, the limit of the KKT point satisfies the second-order
necessary optimality condition of being a local minimizer.
Symmetric primal-dual path following algorithms
for SDP
ps file is
available
Jos F. Sturm and Shuzhong Zhang (speaker) (Erasmus University Rotterdam)
We present a symmetric primal-dual transformation for SDP. In this
approach, standard techniques for analyzing primal-dual path following
algorithms for linear programming can be easily adapted to the case
of SDP. More properties of the SDP problems under this interpretation
will be discussed.
Some Thoughts on Primal-Dual Interior-Point
Methods for Semidefinite Programming
Yin Zhang (University of Maryland Baltimore County)
We plan to discuss issues in formulation, complexity analysis and
computation of primal-dual interior-point methods for semidefinite
programming. We will focus on a class of primal-dual methods that
can be viewed as perturbed and damped, interior-point Newton or composite
Newton method applied to some form of optimality system. We will discuss
some critical computational issues and present preliminary numerical
results.
Semidefinite Programming Relaxations for
the Quadratic Assignment Problem
Qing Zhao (speaker)
University of Waterloo, Department of
Combinatorics and Optimization, Faculty of Mathematics,
Waterloo, Ontario, N2L 3G1 Canada
Stefan E. Karisch
Technische Universit\"at Graz, Institut f\"ur Mathematik,
Kopernikusgasse 24, A-8010 Graz, Austria
Franz Rend
Technische Universit\"at Graz, Institut f\"ur Mathematik,
Kopernikusgasse 24, A-8010 Graz, Austria
Henry Wolkowicz
University of Waterloo, Department of
Combinatorics and Optimization, Faculty of Mathematics,
Waterloo, Ontario, N2L 3G1 Canada
Semidefinite programming relaxations for the quadratic assignment
problem QAP are derived using the dual of the Lagrangian dual of appropriate
equivalent representations of QAP. These relaxations result in the
interesting, special, case where only the dual problem of the relaxations
have strict interior, i.e. the Slater's constraint qualification does
not hold for the primal problem. Although there is no duality gap
in theory, this indicates that the relaxations cannot be solved in
a numerically stable way. By exploring the geometrical structure,
we are able to find projectey semidefinite programming relaxations,
which can be further tightened by using cutting planes on the minimal
face. The new resulting relaxations, and their duals, satisfy the
Slater's constraint qualification, and so can be solved numerically.
Numerical results are presented which indicate that the described
methods are very promising.
|
|
