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). Let φ be a homogeneous function of degree p > 0, K a pointed closed convex cone, W a subspace, and F a θ-logarithmically homogeneous barrier for K◦. HP tests the existence of a nontrivial zero of φ over W ∩ K. SP, and HSP test the existence of the minimizer of ψ = φ + F, and X = φ/ exp(−pF/θ) over W ∩ K◦, respectively. ASP tests the solvability of the scaling equation (SE), a fundamental equation inherited from properties of homogeneity and those of the operator-cone, T (K) = {D ≡ F′′(d)−1/2 : d ∈ K◦}. Each D induces a scaling of φ′(d) (or φ′′(d)), and SE is solvable if and only if there exists a fixed-point under this scaling. In case K is a symmetric cone, the fixed-point is its center, e. 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 solving NP-complete problems. Our 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 and allow 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. Using the scaling dualities, we describe algorithms that attempt to solve SP, HSP, or ASP. If any of these problems is unsolvable, our attempt leads to a solution of HP. Our scaling dualities give nontrivial generalization of the arithmetic-geometric mean, the 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 which result 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 only 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. We prove that if φ is β-compatible with F, then ǫ-approximate versions of HP, SP, and HSP are all solvable in polynomial-time. Additionally, if the ratio kDk/kdk is uniformly bounded, ASP is also solvable in polynomial-time. The latter result extends the polynomial-time solvability of matrix scaling equation (even in the presence of W) to general cases of SE over the nonnegative cone, or the semidefinite cone, or the second-order cone.