DIMACS TR: 98-38
On the Arithmetic-Geometric Mean Inequality
and Its Relationship to Linear Programming,
Matrix Scaling, and Gordan's Theorem
Author: Bahman Kalantari
ABSTRACT
It is a classical inequality that the minimum of the ratio of the
(weighted) arithmetic mean to the geometric mean of a set of positive
variables is equal to one, and is attained at the center of the
positivity cone. While there are numerous proofs of this fundamental
homogeneous inequality, in the presence of an arbitrary subspace,
and/or the replacement of the arithmetic mean with an arbitrary linear
form, the new minimization is a nontrivial problem. We prove a
generalization of this inequality, also relating it to linear
programming, to the diagonal matrix scaling problem, as well as to
Gordan's theorem. Linear programming is equivalent to the search for
a nontrivial zero of a linear or positive semidefinite quadratic form
over the nonnegative points of a given subspace. The goal of this
paper is to present these intricate, surprising, and significant
relationships, called {\it scaling dualities}, and via an elementary
proof. Also, to introduce two conceptually simple polynomial-time
algorithms that are based on the scaling dualities, significant
bounds, as well as Nesterov and Nemirovskii's machinery of
self-concordance. The algorithms are simultaneously applicable to
linear programming, to the computation of a separating hyperplane, to
the diagonal matrix scaling problem, and to the minimization of the
arithmetic-geometric mean ratio over the positive points of an
arbitrary subspace. The scaling dualities, the bounds, and the
algorithms are special cases of a much more general theory on convex
programming, developed by the author. For instance, via the scaling
dualities semidefinite programming is a problem dual to a
generalization of the classical trace-determinant ratio minimization
over the positive definite points of a given subspace of the Hilbert
space of symmetric matrices.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-38.ps.gz
DIMACS Home Page