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