A selection of my papers
Last updated 

Here are the abstracts of a selected list of publications.  This list is updated every several months and so may not be completely up to date. Send me e-mail at  alizadeh@rutcor.rutgers.edu  to get any paper you cannot find below.
 
 

Selected papers

  • Title: A Sublinear-Time Randomized Parallel Algorithm for the Maximum Clique Problem in Perfect  Graph
  • Absract: We will show that Lovasz number of graphs may be computed using interior-point methods. This technique will require $O(\sqrt {|V|})$ iterations, each consisting of matrix operations which have polylog parallel time complexity. In case of perfect graphs Lovasz number equals the size of maximum clique in  the graph and thus may be obtained in sublinear parallel time. By using the isolating lemma, we get a Las Vegas randomized parallelalgorithm for constructing the maximum clique in perfect graphs.
  • Title: Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology
  • Abstract: A fundamental tool for exploring the structure of a long DNA sequence is to construct a ``library'' consisting of many cloned fragments of the sequence. Each fragment can be replicated indefinitely and then ``fingerprinted'' to obtain partial information about its structure. A common type of fingerprinting is restriction fingerprinting, in which an enzyme called a restriction nuclease cleaves the fragment wherever a particular short sequence of nucleotides (letters `A', `G', `C', and `T') occurs, and the lengths of the resulting pieces are measured. An important combinatorial problem is to determine, from such fingerprint information, the most probable arrangement of the cloned fragments along the overall sequence. However, for a given arrangement, even the likelihood function involves a complicated multifold integral and therefore difficult to compute. We propose an approximation to the likelihood function and develop local search algorithms based on this approximate objective function. Our local search techniques are extensions of similar strategies for the traveling-salesperson problem. We provide some computational results which support our choice of objective function. We also briefly study alternative approaches based on pairwise probabilities that two fragments overlap.
  • Title:  Physical Mapping  of Chromosomes Using Unique Probes
  • Abstract: The goal of physical mapping of the genome is to reconstruct a strand of DNA given a collection of overlapping fragments, or clones, from the strand.  We present several algorithms to infer how the clones overlap, given data about each clone.  We focus on data used to map human chromosomes 21 and Y, in which relatively short substrings, or probes, are extracted from the ends of clones.  The substrings are long enough to be unique with high probability.  The data we are given is an incidence matrix of clones and probes. In the absence of error, the correct placement can be found easily using a PQ-tree.  The data is never free from error, however, and algorithms are differentiated by their performance in the presence of errors.  We approach errors from two angles: by detecting and removing them, and by using algorithms which are robust in the presence of errors.
  • Title: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
  • Abstract:  We study the {\em semidefinite programming problem} (SDP), i.e the optimization problem of a linear function of a symmetric matrix subject to linear equality constraints and the additional condition that the matrix be positive semidefinite. First we review the classical cone duality as is specialized to SDP. Next we present an interior point algorithm which converges to the optimal solution in polynomial time. The approach is a direct extension of Ye's projective method for linear programming. We also argue that any known interior point methods for linear programs can be transformed in a mechanical way to algorithms for SDP with proofs of convergence and polynomial time complexity also carrying over in a similar fashion. Finally we study the significance of these results in a variety of combinatorial optimization problems including the general 0-1 integer programs, the maximum clique and maximum stable set problems in perfect graphs, the maximum $k$-partite subgraph problem in graphs, and various graph partitioning and cut problems. As a result, we present barrier oracles for certain combinatorial optimization problems (in particular, clique and stable set problem for perfect graphs) whose linear programming formulation requires exponentially many inequalities. Existence of such barrier oracles refutes the commonly believed notion that in order to solve a combinatorial optimization problem with interior point methods, one needs its linear programming formulation explicitly.
  • Title: Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
  • Abstract: Primal-dual interior-point path-following methods for semidefinite programming (SDP) are considered.  Several variants are discussed, based on Newton's method applied to three equations: primal feasibility, dual feasibility, and some form of centering condition. The focus is on three such algorithms, called respectively the $XZ$, $XZ+ZX$ and $Q$ methods. For the $XZ+ZX$ and $Q$ algorithms, the Newton system is well-defined and its Jabobian is nonsingular at the solution, under nondegeneracy assumptions. The associated Schur complement matrix has an unbounded condition number on the central path, under the nondegeneracy assumptions and an additional rank assumption. Practical aspects are discussed, including Mehrotra predictor-corrector variants and issues of numerical stability. We observe that the $XZ+ZX$ method is more robust than the $XZ$ and Nesterov-Todd methods with respect to its ability to step close to the boundary, that it converges more rapidly, and that it achieves higher accuracy.
  • Title: Complementarity and Nondegeneracy in Semidefinite Programming
  • Abstract:  Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP.  The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutions $X$ and $Z$. This is in contrast with LP where nondegeneracy assumptions exactly determine the numbercomplementarity all hold generically. Numerical experiments suggest probability distributions for the ranks of $X$ and $Z$ which are consistent with the nondegeneracy conditions.
  • Title: Primal-Dual Interior Point Algorithms for Convex Quadratically Constrained and Semidefinite Optimization Problems
  • Abstract:  In this paper we examine primal--dual interior point methods for optimization problems over the semidefinite cone and the $p$-cones (in particular the ``ice cream cone"). We study similarities and differences of such interior point methods with the analogous algorithms for linear programming.
  • Title: Optimization with Semidefinite, Quadratic and  Linear Constraints
  • Abstract: We consider optimization problems where variables have either linear, or convex quadratic or semidefinite constraints. First, we define and characterize primal and dual nondegeneracy and strict complementarity conditions. Next, we develop primal-dual interior point methods for such problems and show that in the absence of egeneracy these algorithms are numerically stable. Finally we describe an implementation of our method and present numerical experiments with both degenerate and nondegenerate problems.
  • Title:Associative Algebras, Symmetric Cones and Polynomial Time Interior Point Algorithms
  • Abstract:  We present a generalization of Monteiro's polynomiality proof of a large class of primal-dual interior point algorithms for semidefinite programs. We show that this proof, essentially verbatim, applies to all optimization problems over symmetric cones, that is those cones that can be derived from classes of normed associative algebras and certain Jordan algebras obtained from them. As a consequence, we show that Monteiro's proof can be extended to convex quadratically constrained quadratic optimization problems. We also extend the notion of Zhang family of algorithms, and show that it can be applied to all symmetric cones, in particular the quadratic cone.

  •