Titles and/or Abstracts for

Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems

Wednesday May 15- Friday 17, 1996
(before the SIAM Conference on Optimization in Victoria)

to be held at

The Fields Institute
Toronto, Ontario, Canada

Last Updated 5/7/1996

Please

tell me if there are any problems.

Please send us the URL for your paper, if it is available. (I will add it to the title of your talk below.)
Please check the schedule for the time of your talk. Please tell us if there are any problems or changes to be made.

List of Speakers

List of Abstracts

RECURRENCE INEQUALITIES IN OPTIMIZATION

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 Programming

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.
Bounds and policies for dynamic optimization via semidefinite and infinite linear programming

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.
On Floorplan Design and Optimization

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.
On the Nesterov-Todd direction in semidefinite programming
compressed ps file is available

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.

A proceedings of refereed invited papers is planned. In addition we will have a special issue of J. of Comb. Opt.

This directory