Speaker: Farid Alizadeh, Faculty of Management, Rutgers University

Abstract: We will present a framework which proofs of polynomiality of interior point algorithms from semidefinite programming can be extended to optimization problems over almost all symmetric cones. We show that the toolbox of techniques used in such analysis, various inequalities involving norms, definitions of neighborhoods, etc., are extendible, almost verbatim, to class of almost all symmetric cones. As a byproduct, we show that Monteiro's analysis of the short step primal-dual algorithms for the class of Monteiro-Zhang family of directions, extends to almost all symmetric cones, including the Lorenz cone. Thus his primal-dual analysis applies in particular to convex quadratically constrained quadratic programming. (Joint work with Stefan Schmieta)

Speaker: Kurt Anstreicher

Abstract: A recent paper with H. Wolkowicz showed that a well-known eigenvalue bound for the Quadratic Assignment Problem (QAP) actually corresponds to a semidefinite relaxation. However, for the eigenvalue bound to be computationally useful, linear equalities corresponding to the assignment constraints must first be projected out. The resulting "projected eigenvalue bound" is among the best known bounds for the QAP, especially considering computational efficiency. In this talk we show that the projected eigenvalue bound also corresponds to a semidefinite relaxation of the original QAP.

Speaker: Steven Benson

Abstract: We apply a dual scaling algorithm to solve the positive semidefinite relaxation of large scale combinatorial problems. The algorithm can exploit the structure and sparsity of a variety of combinatorial problems. Coupled with randomized and heuristic methods, we report computational results of graph partitioning problems with dimension up to 10,000.

Speaker: Dimitris Bertsimas

We construct new semidefinite programming relaxations for stochastic optimization problems that give considerably more powerful bounds than linear programming relaxations. We apply these ideas to the problem of optimizing multiclass queueing networks that are stochastic and dynamic generalizations of job shop scheduling problems. The central idea for obtaining these bounds comes from the classical moment problem in probability theory. Starting from the moment problem, we also apply convex and semidefinite programming methods to obtain optimal bounds in probability theory. As an example, we show that the classical Chebyshev bound can in fact be improved.

Speaker: Jeffrey O. Coleman

Abstract: A systematic approach is presented to the design of (FIR) digital filters. Specifications are formulated as restrictions on the power gains of a model systems driven by random processes. Each power gain resulting from a system model and associated input-process spectral density results in a distinct and intuitive meaningful performance index. Real or complex single or parallel filters with linear or nonlinear phase or Nyquist properties are easily handled. Preliminary extension of the approach to beamformer design for narrowband antenna arrays (work joint with R. Vanderbei) will be discussed.

Speaker: E. de Klerk

Abstract: Semidefinite programming (SDP) relaxations -- in conjunction with randomized rounding schemes -- yield 7/8 and 0.931 approximation algorithms for MAX-3-SAT and MAX-2-SAT respectively. In spite of these powerful theoretical results, it not clear if SDP can be used as a practical tool for solving MAX-SAT problems to optimality.

The purpose of this talk is two-fold. We will review the known relaxations and present some new results on the quality of a specific SDP relaxation of the SAT problem. In particular, we will show that the SDP relaxation identifies unsatisfiable 2-SAT formulas as well as unsatisfiability of "pigeonhole" formulas in polynomial time. In the second instance, we will discuss sparsity issues in solving the various relaxations, and present some numerical results.

This is joint work with H. van Maaren and J.P. Warners

Speaker: Leonid Faybusovich

Abstract: We discuss a numerical integration procedure for affine-scaling vector fields which is based on the specific properties of its solutions. This leads to a new exterior-point algorithm even for the linear programming case. A generalization for the symmetric programming problem is also presented.

Speaker: Robert M. Freund

Abstract: We study various measures of conditioning of conic linear systems (and SDP as a special case), including $\sigma_A$ (Ye), ${\cal C}(A,b)$ (Renegar), and $\bar\chi_A$, and a new measure $\mu_{A,b}$. We study the relations between these condition measures, and show that $\mu_{A,b}$ generalizes $\sigma_A$ and dominates ${\cal C}(A,b)$ for SDP and general convex problems. We demonstrate connections between these condition numbers, geometric properties of feasible regions, and the efficiency of algorithms. We show that there exists an (optimal) pre-conditioner $\bar B$, for which the condition number of the pre-conditioned system satisfies $\frac{1}{\mu_{A,b}}\le{\cal C}(\bar BA,\bar Bb)\le\sqrt{m}\cdot\frac{1}{\mu_{A,b}}$. We also discuss the computational complexity of computing this pre-conditioner.

Speaker: Osman Guler

Abstract: Symmetric cones are the nicest convex cones in interior point mehods. Their distinguishing properties are reflected in the self concordant barrier functions that they admit. In this talk, we discuss the algebraic, geometric, and duality properties of these barrier functions. We also discuss how some of the useful properties of the barrier functions extend to some larger, but still useful convex cones. Finally, some open problems will be listed.

Speaker: Bill Hager

Abstract: A quadratic programming formulation is given for the problem of partitioning the vertices of a graph into $k$ sets, each set of given size, in order to minimize the number of edges connecting different sets. This formulation leads to simple bounds on the number of edges in the best partition. The minimizing vector is related to an eigenvector (Fiedler vector) corresponding to the second smallest eigenvalue of the graph's Laplacian. Necessary and sufficient conditions characterizing local minima of the quadratic program are given. The effect of diagonal perturbations on the number of local minimizers is investigated using a test problem from the literature.

Speaker: Christoph Helmberg

Abstract: The duals of many current semidefinite relaxations of combinatorial optimization problems are equivalent to eigenvalue optimization problems. For problems of this kind approximate solutions can be computed efficiently with the spectral bundle method.

We explain the basic ideas underlying this method, show how inequality constraints can be incorporated efficiently, and investigate possibilities for extracting primal information. We also discuss the first steps towards cutting plane algorithms based on the spectral bundle method. Numerical examples will illustrate the efficacy of the approach in particular for large scale problems.

Speaker: Florian Jarre

Abstract: In many applications, semidefinite programs with nonlinear equality constraints arise. These problems are nonconvex, and the common interior-point results no longer apply. To solve such problems we propose an interior-point method in which the usual linear systems of the Newton step and of the predictor step are replaced by simple quadratically constrained quadratic programs. These QQP's are of a special structure and can be solved directly. In addition, the QQP's allow for a special line search which effects that the algorithm is applicable to nonconvex programs. Some convergence results are given, and preliminary numerical examples show the behaviour of the QQP-steps for some solving certain biaffine matrix inequalities.

Speaker: Bahman Kalantari

Abstract: We first prove four fundamental theorems of the alternative, called scaling dualities, characterizing exact and approximate solvability of four significant conic problems in finite dimensional spaces, defined as: homogeneous programming (HP), scaling problem (SP), homogeneous scaling problem (HSP), and algebraic scaling problem (ASP), the problem of testing the solvability of the scaling equation (SE), a fundamental equation inherited from properties of homogeneity. These four problems together with the scaling dualities offer a new point of view into the theory and practice of convex and nonconvex programming. Nontrivial special cases over the nonnegative orthant include: testing if the convex-hull of a set of points contains the origin (equivalently, testing the solvability of Karmarkar's canonical LP), computing the minimum of the arithmetic-geometric mean ratio over a subspace, testing the solvability of the diagonal matrix scaling equation (DADe=e), as well as NP-complete problems. The scaling dualities closely relate these seemingly unrelated problems. Via known conic LP dualities, convex programs can be formulated as HP. Scaling dualities go one step further, allowing us to view HP as a problem dual to the corresponding SP, HSP, or ASP. This duality is in the sense that HP is solvable if and only if the other three are not. Our scaling dualities give nontrivial generalization of the arithmetic-geometric mean, trace-determinant, and Hadamard inequalities; matrix scaling theorems; and the classic duality of Gordan. We describe potential-reduction and path-following algorithms for these four problems, resulting in novel and conceptually simple polynomial-time algorithms for linear, quadratic, semidefinite, and self-concordant programming. Furthermore, the algorithms are more powerful than their existing counterparts, since they also establish the polynomial-time solvability of the corresponding SP, HSP, as well as many cases of ASP. The scaling problems either have not been addressed in the literature, or have been treated in very special cases. The algorithms are based on the scaling dualities, significant bounds obtained in this paper, properties of homogeneity, as well as Nesterov and Nemirovskii's machinery of self-concordance. In particular, our results extend the polynomial-time solvability of matrix scaling equation (even in the presence of a subspace) to general cases of SE over the nonnegative cone, or the semidefinite cone, or the second-order cone.

Speaker: Masakazu Kojima

Abstract: Based on the authors' previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, we discuss their implementable variants for general quadratic optimization problems. These problems have a linear objective function to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, discretization'' and localization,'' into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish: Given any open convex set U containing the feasible region F, an implementable discretization of the SSDP (or SSILP) Relaxation Method generates a compact convex relaxation C of F inside the open set U in a finite number of iterations. The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish: Given any positive number epsilon, an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method generates an upper bound of the objective values within epsilon of their maximum in a finite number of iterations.

Speaker: Zhi-Quan Luo

Abstract: The design of orthogonal waveforms for digital communications is formulated as a semidefinite programme. The formulation exploits the problem structure and incorporates both semidefinite and second order cone constraints. The designs include finding filters which achieve: a) the minimal bandwidth' for a given filter length; b) the minimal length for a given bandwidth; or c) the maximal robustness to timing error for a given bandwidth and length. The resulting waveforms have substantially improved performance over the chip' waveforms specified in recent standards for digital mobile telecommunications.

Speaker: Renato Monteiro

Abstract: We present an algorithm for solving the positive semidefinite relaxation of the maximum cut problem. We give some numerical results to compare our method to other well-known algorithms for solving this special semidefinite program. Our preliminary computational results with our method are quite encouraging.

Speaker: Masakazu Muramatsu

Abstract: We found a class of semidefinite programming problems whose optimal solutions can be obtained directly, i.e., without using iterative methods. Our class includes the similar classes proposed by Vanderbei and Yang, and Wolkowicz, and also a part of Ohara's family as special cases. The key observation for direct solvability of these problems is really simple, which will be presented at the talk.

Speaker: Gabor Pataki

Abstract: We address the following question:

Given a closed convex cone K, and a linear mapping M, under what conditions is MK closed ?

Besides being simple, the closedness of the image is also fundamental in convex analysis, mainly in duality theory. For a given conic linear system, the existence of an objective function, such that the resulting conic program has a gap with its dual, reduces to the above question.

Two kinds of sufficient, and seemingly unrelated conditions have been known for a long time: the polyhedrality of the cone, or the existence of a Slater-point in its polar intersected with the nullspace of M^T. Giving a simple, necessary, and sufficient condition has been a long standing open question.

In this work, we make a step towards resolving this question. We give a simple condition for the closedness of the image, which

- Unifies and generalizes the polyhedrality and Slater conditions.

- Is sufficient for any K and M.

- Is necessary and sufficient for a large class of cones, including the nonnegative orthant, semidefinite, second order, and l_p cones.

Speaker: Lorant Porkolab

Abstract: We consider the general semidefinite optimization problem: Compute the infimum of a linear objective function of an $n \times n$ symmetric positive semidefinite matrix satisfying a given system of $m$ linear constraints; if the infimum is attained, find the least-norm optimal solution. Assuming that the input data is real, we show that the above optimization problem can be solved in $mn^{O(n^2)}$ arithmetic operations in the real number model of computation. Moreover, if the input coefficient are integers of binary length $l$, the required accuracy of arithmetic operations does not exceed $ln^{O(n^2)}$ bits. These bounds on arithmetic operations, stated for the real number model of computation, include our earlier results on the complexity of feasibility testing for semidefinite programs with integer input coefficients. In addition, the above bounds also imply a strongly polynomial linear-time algorithm for semidefinite optimization in fixed dimension, an extension of the well-known result of Megiddo for linear programming over the reals. Another corollary of our bounds are nearly tight estimates on the algebraic degrees and logarithmic heights of the infimum and coordinates of the least-norm optimal solution.

Michael L. Overton (Courant Institute, NYU)

Abstract. We present a condition number for semidefinite programs under the assumption of primal and dual nondegeneracy and strict complementarity, bounding the change in the solution of a semidefinite program induced by a sufficiently small perturbation in the problem data. The key tool is the application of Kantorovich's theorem to the nonlinear system of equations defining the optimality conditions. The condition number involves several quantities, one of which is the limit of the norm of the inverse of the Schur complement matrix used by interior point methods. The condition number extends to block-diagonal semidefinite programs and quadratic cone programs, and reduces to a well known bound in the special case of nondegenerate linear programs (in this case, the limit of the norm of the inverse of the Schur complement matrix is zero). We discuss how the bound changes when the nondegeneracy conditions are relaxed. For randomly generated semidefinite programs, not only do the nondegeneracy conditions hold with probability one, but experiments show that the ranks of the solution matrices fall in the middle of the range permitted by the nondegeneracy conditions with surprisingly high probability. However, for semidefinite programs arising in applications, it often happens that either the primal or dual nondegeneracy condition fails to hold.

This work is joint with M. Nayakkankuppam (Courant Institute, NYU).

Speaker: Florian Potra

Abstract: The talk is based on some results obtained jointly with Nate Brixius and Rongqin Sheng on two nonsymmetric search directions for semidefinite programming, called the XZ and ZX search directions. They are derived from a nonsymmetric formulation of the semidefinite programming problem. The XZ and ZX directions are well defined if both X and Z are positive definite matrices, where X may be nonsymmetric. We present an algorithm using the XZ and ZX directions alternately following the Mehrotra predictor-corrector framework. Numerical results show that the XZ/ZX algorithm, in many cases, requires less CPU time than the XZ+ZX method of Alizadeh, Overton, and Haeberly (AHO) while achieving similar accuracy.

Speaker: Franz Rendl

Abstract: We consider semidefinite programs, where the matrices defining the problem come from some association scheme. We show that in this case the SDP can be solved through a simple LP. We further show applications of this result in the context of the Max-Cut problem.

This is joint work with Michel Goemans

Jim Renegar

Abstract: Many of us consider the papers of Nesterov and Todd on self-scaled cones as some of the seminal work on interior-point methods in this decade. Unfortunately, those papers are quite difficult to read. Consequently, it is a relatively small number of optimizers who thoroughly understand the theory. The number has increased somewhat thanks to Faybusovich's approach using Jordan algebras. However, a development which seems well-motivated to a wide audience of optimizers is still missing. In this talk I will discuss self-scaled cones from a perspective I hope the audience will find more well-motivated.

Speaker: Kees Roos

Inspired by a recent paper of Kruk et al. we propose a new primal-dual search direction for a central-path-following method for solving semidefinite optimization problems. The search direction can be considered as a Newton direction. It is scale invariant and coincides with the usual primal-dual directions in the linear case. It is well-defined for every primal-dual pair of feasible iterates and differs from the search directions used up till know in the literature. We show that it yields a polynomial-time method when the subsequent targets on the central path are chosen appropriately.

Speaker: Katya Scheinberg

Abstract: We present several product form factorization approaches for taking advantage of sparsity in solving second order cone programming problems by interior point methods. These approaches are numerically stable in contrast with the commonly used Schur complement (Sherman-Morrison-Woodbury) approach.

Speaker: Stefan Schmieta, RUTCOR, Rutgers University

Abstract: In this talk we present a study of implementing a primal-dual interior point algorithm for optimization problems with convex quadratically constrained quadratic programs. In particular we focus on using sparse factorization methods. We describe two extreme situations: One involving few constraints, but each possibly with a large matrix, and one with many constraints, but each with a small matrix. We show that in these two extreme situations two (radically different) sparse factorizations techniques may be employed. We present computational results. (Joint work with Farid Alizadeh)

Speaker: Tamas Terlaky

Abstract: In this talk some duality issues related to second-order cone (SOC) reformulations of quadratically constraint quadratic problems (QCQP) are discussed. It is shown that conic reformulations of QCQP may lead to duality gap, while a direct gap-free dual for QCQP is available.

In the second part of the talk equivalent convex reformulations of SOCP are presented. The reformulations are solvable in polynomial time as well. Comparative computational results are presented on realistic test problems.

Speaker: Michael Todd

Abstract: We discuss a number of issues related to mostly primal-dual interior-point methods for semidefinite programming, including the work involved at each iteration and the ability to obtain certificates of infeasibility. We give computational results of the code SDPT3 of Toh, Todd, and Tutuncu on problems from SDPLIB-1.1.

Speaker: Takashi Tsuchiya

Abstract: We study primal-dual path-following algorithms for second-order cone programming (SOCP) based on an analogue of the MZ-family of search directions for SDP. Making use of the underlying structure of Euclidean Jordan Algebra, we prove $O(\sqrt{n}\log\varepsilon^{-1})$ iteration-complexity bounds for the short-step path-following algorithm and the predictor-corrector algorithm, where $n$ is the number of second-order cones and $\varepsilon$ is the required precision described in terms of the ratio of the final duality gap to the initial duality gap. Since the MZ-family includes the AHO direction, our result implies polynomial convergence of the primal-dual path-following algorithms for SOCP using the AHO direction. This is a joint work with Renato Monteiro of Georgia Institute of Technology.

Speaker: Paul Tseng

Abstract: We consider a technique for accelerating local convergence of primal-dual interior point methods for NLP and SDP. This technique, based on implicitly identifying the active constraints and working with the corresponding reduced KKT system, is relatively inexpensive to implement and can yield local superlinear convergence without requiring strict complementarity of the solution.

Speaker: Levent Tuncel

Abstract: We first show the exact equivalence of semi-infinite convex quadratically constrained relaxations and the semi-infinite semidefinite programming relaxations of closed, nonconvex sets. This result generalizes and strengthens the main results of Fujie and Kojima (1997). We then generalize two lift-and-project methods of Lov{\'a}sz and Schrijver (1991) to compute the convex hull of any compact set in an Euclidean Space (therefore, our algorithms in principle, can be used to solve {\em any} optimization problem in an Euclidean Space). We create a hierarchy of valid inequalities for compact sets and then determine the class of valid inequalities for which the strongest convergence results apply. We show that our convergence results are the best possible within this hierarchy of valid inequalities. Even though our algorithms are conceptual, we can show that via a discretization procedure, they can all be implemented on a computer without sacrificing much of the theoretical convergence properties. This is the subject of the next talk by Masakazu Kojima. These implementable versions use only standard linear programming algorithms or standard semidefinite programming algorithms as subroutines.

Speaker: Vera Kovacevic-Vujcic

Abstract: We present a SDP model for solving the traveling salesman problem. Numerous experimental results with randomly generated examples show that the proposed SDP relaxation gives considerably better bounds than the well-known two-matching and 1-tree relaxations.

Speaker: Robert Vanderbei

Abstract: Many nonlinear optimization problems can be cast as second-order cone programming problems. In this paper, we discuss a broad spectrum of such applications. For each application, we consider various formulations, some convex some not, and study which ones are amenable to solution using a general-purpose interior-point solver {\sc loqo}. We also compare with other commonly available nonlinear programming solvers.

Speaker: David P. Williamson, IBM T.J. Watson Research Center

Abstract: In this talk I will review results using semidefinite programming to devise approximation algorithms for problems in combinatorial optimization. An approximation algorithm is an algorithm which runs in polynomial time and is guaranteed to find a solution whose value is within a given factor of the value of an optimal solution. Semidefinite programming has been used to find significantly improved approximation algorithms (in terms of nearness to optimality) for the maximum cut, maximum satisfiability, quadratic programming, and graph coloring problems, as well as some others. After reviewing this work, I will briefly discuss some recent work in complexity theory which casts some interesting light on the strengths and limitations of this approach.

Speaker: Henry Wolkowicz

Abstract: Lagrangian duality lies behind efficient algorithms for convex minimization problems. Lagrangian relaxation provides lower bounds for nonconvex problems, where the quality of the lower bound depends on the duality gap. For quadratically constrained quadratic programs, the dual of the Lagrangian dual is equivalent to the semidefinite relaxation. Thus, the Lagrangian relaxation can be efficiently computed using primal-dual interior-point methods for the SDP relaxation.

Quadratically constrained quadratic programs (QQP) 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 nice duality results already fail for the two trust region subproblem. However, the Lagrangian relaxation provides excellent bounds for many QQPs, e.g. max-cut, graph partitioning, and quadratic assignment problems.

Speaker: Guoliang Xue

Abstract: Steiner minimum trees with $\lambda_\sigma$-distance routing have been studied by many researchers. We have the rectlinear case when $\lambda = 2$, and the Euclidean case when $\lambda = \infty$. In recent years, there have been increased interest in cases where $\lambda$ is an integer greater than $2$. Several MST-based heuristic algorithms have been proposed to solve this more general problem. In this paper, we concentrate on the case where $\lambda = 4$. This corresponds to $45^o$ routing. We present a primal-dual potential reduction algorithm which computes an $(1+\epsilon)$-approximation to the shortest network under a given tree topolgy interconnecting $n$ terminal points in $O(n^{1.5} (\log n + \log \frac{1}{\epsilon}))$ time. This is an extension of the algorithm proposed by Xue and Ye for the Euclidean case.

Speaker: Yinyu Ye

Abstract: We consider the problem of approximating the global maximum of a quadratic program (QP) subject to convex non-homogeneous quadratic constraints. We prove an approximation quality bound that is related to a symmetry measure of the convex feasible set; and it is the currently best for approximating certain problems, such as quadratic optimization over the assignment polytope, according to the best of my knowledge.

Speaker: Shuzhong Zhang

Abstract: In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation. For a special subclass of the problems we show that the SDP relaxation provides an exact optimal solution. Another subclass, which is ${\cal NP}$-hard, guarantees that the SDP relaxation yields an approximate solution with a worst-case performance ratio of $0.87856...$. This is a generalization of the well-known result of Goemans and Williamson for the maximum-cut problem. Finally, we discuss extensions of these results in the presence of a certain type of sign restrictions.

Speaker: Yin Zhang

Abstract: The problem of finding the maximally inscribing ellipsoid for a given polytope has many important potential applications. Although several polynomial-time algorithms have been proposed for this problem, to our best knowledge few computational results have been reported. In this talk, we describe several formulations of primal-dual interior-point algorithms and present our preliminary numerical results.

Speaker: Michael Zibulevsky

Abstract: We present generalization of Penalty/Barrier and Augmented Lagrangian algorithms for Semidefinite Programming. This allows to use, among others, logarithmic, shifted logarithmic, exponential and a very effective "mixed quadratic-logarithmic" penalty/barrier functions. We show correspondence between the suggested Augmented Lagrangian algorithm for Semidefinite Programming and its dual counterpart, resulting in a proximal-like maximization algorithm with nonquadratic prox-kernel. We present a dual bound for the objective function, which is produced by the conjugate penalty/barrier function. As a tool for unconstrained minimization, we use Newton method with frozen Hessian''.Computational results for Robust Control and Stable Truss Topology Design problems show high efficiency of the algorithm. Typically 5-20 Hessian evaluations are sufficient to achieve high accuracy of the solution.