DIMACS TR: 98-37
Scaling Dualities and Self-Concordant Homogeneous Programming
in Finite Dimensional Spaces
Author: Bahman Kalantari
ABSTRACT
In this paper first we 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-37.ps.gz
DIMACS Home Page