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.