A Theorem of the Alternative for Multihomogeneous Functions and Its Relationship to Diagonal Scaling of Matrices

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

We prove that, given a multihomogeneous function satisfying some initial conditions, either it has a certain nonnegative zero over a given subspace, or an associated logarithmic barrier function has a constrained stationary point. Under convexity precisely one of these conditions is satisfied. The main ingredients of the proof are the derivation of significant properties of the constrained stationary points of the logarithmic barrier function, and their relationship to corresponding points of an associated Karmarkar potential function. Corollaries of the theorem include a duality for Karmarkar's canonical linear program, which happens to be a stronger version of Gordan's theorem; a more general duality than an existing one concerning the diagonal scaling of symmetric matrices, also shown to be a stronger version of Gordan's theorem; and a diagonal scalability result for a class of multihomogeneous polynomials which is more general than a previously known result on the scalability of positive multidimensional matrices. We also give an algorithmic proof of the theorem of the alternative through a projective algorithm which is a generalization of a modified Karmarkar linear programming algorithm, and in the context of nonnegative matrix scaling becomes a variant of the well-known RAS algorithm.

Original languageEnglish (US)
Pages (from-to)1-24
Number of pages24
JournalLinear Algebra and Its Applications
Volume236
DOIs
StatePublished - Mar 15 1996

Fingerprint

Theorems of the Alternative
Logarithmic Barrier Function
Stationary point
Scaling
Scalability
Duality
Theorem
Nonnegative Matrices
Potential Function
Symmetric matrix
Linear Program
Convexity
Linear programming
Corollary
Initial conditions
Non-negative
Subspace
Polynomial
Polynomials
Zero

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this

@article{bd5e2ae651e74f3da111fba894efd33b,
title = "A Theorem of the Alternative for Multihomogeneous Functions and Its Relationship to Diagonal Scaling of Matrices",
abstract = "We prove that, given a multihomogeneous function satisfying some initial conditions, either it has a certain nonnegative zero over a given subspace, or an associated logarithmic barrier function has a constrained stationary point. Under convexity precisely one of these conditions is satisfied. The main ingredients of the proof are the derivation of significant properties of the constrained stationary points of the logarithmic barrier function, and their relationship to corresponding points of an associated Karmarkar potential function. Corollaries of the theorem include a duality for Karmarkar's canonical linear program, which happens to be a stronger version of Gordan's theorem; a more general duality than an existing one concerning the diagonal scaling of symmetric matrices, also shown to be a stronger version of Gordan's theorem; and a diagonal scalability result for a class of multihomogeneous polynomials which is more general than a previously known result on the scalability of positive multidimensional matrices. We also give an algorithmic proof of the theorem of the alternative through a projective algorithm which is a generalization of a modified Karmarkar linear programming algorithm, and in the context of nonnegative matrix scaling becomes a variant of the well-known RAS algorithm.",
author = "Bahman Kalantari",
year = "1996",
month = "3",
day = "15",
doi = "10.1016/0024-3795(94)00162-6",
language = "English (US)",
volume = "236",
pages = "1--24",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - A Theorem of the Alternative for Multihomogeneous Functions and Its Relationship to Diagonal Scaling of Matrices

AU - Kalantari, Bahman

PY - 1996/3/15

Y1 - 1996/3/15

N2 - We prove that, given a multihomogeneous function satisfying some initial conditions, either it has a certain nonnegative zero over a given subspace, or an associated logarithmic barrier function has a constrained stationary point. Under convexity precisely one of these conditions is satisfied. The main ingredients of the proof are the derivation of significant properties of the constrained stationary points of the logarithmic barrier function, and their relationship to corresponding points of an associated Karmarkar potential function. Corollaries of the theorem include a duality for Karmarkar's canonical linear program, which happens to be a stronger version of Gordan's theorem; a more general duality than an existing one concerning the diagonal scaling of symmetric matrices, also shown to be a stronger version of Gordan's theorem; and a diagonal scalability result for a class of multihomogeneous polynomials which is more general than a previously known result on the scalability of positive multidimensional matrices. We also give an algorithmic proof of the theorem of the alternative through a projective algorithm which is a generalization of a modified Karmarkar linear programming algorithm, and in the context of nonnegative matrix scaling becomes a variant of the well-known RAS algorithm.

AB - We prove that, given a multihomogeneous function satisfying some initial conditions, either it has a certain nonnegative zero over a given subspace, or an associated logarithmic barrier function has a constrained stationary point. Under convexity precisely one of these conditions is satisfied. The main ingredients of the proof are the derivation of significant properties of the constrained stationary points of the logarithmic barrier function, and their relationship to corresponding points of an associated Karmarkar potential function. Corollaries of the theorem include a duality for Karmarkar's canonical linear program, which happens to be a stronger version of Gordan's theorem; a more general duality than an existing one concerning the diagonal scaling of symmetric matrices, also shown to be a stronger version of Gordan's theorem; and a diagonal scalability result for a class of multihomogeneous polynomials which is more general than a previously known result on the scalability of positive multidimensional matrices. We also give an algorithmic proof of the theorem of the alternative through a projective algorithm which is a generalization of a modified Karmarkar linear programming algorithm, and in the context of nonnegative matrix scaling becomes a variant of the well-known RAS algorithm.

UR - http://www.scopus.com/inward/record.url?scp=0347304804&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347304804&partnerID=8YFLogxK

U2 - 10.1016/0024-3795(94)00162-6

DO - 10.1016/0024-3795(94)00162-6

M3 - Article

VL - 236

SP - 1

EP - 24

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -