On a characterization of convexity-preserving maps, Davidon’s collinear scalings and Karmarkar’s projective transformations

摘要

In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace of ℝ m into ℝ n as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977 for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of this note is to point this out.