Generalization of Karmarkar's algorithm to convex homogeneous functions

Bahman Kalantari

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Let φ be a convex homogeneous function of degree K > 0 defined over the positive points of a subspace W of Rn, n ≥ 2. Assume φ(x) > 0 for some 0 < ε{lunate} W. Let V be the set of nonnegative nonzero x ε{lunate} W such that φ(x)k converges to zero, for some sequence 0 < x k ε{lunate} W converging to x. We prove V is nonempty if and only if for every 0 < ε{lunate} W satisfying φ(d) > 0, there exists 0 < xd ε{lunate} W such that eTd = eTxd and f(xd) ≤ γf(d), where e is the vector of ones, f(x) = φ(x)/Πni=1xiK/n)), and γ = 〈[K + 1)/K]K exp(-1)〉1/n. Karmarkar's algorithm proves the above for the special case where φ is linear.

Original languageEnglish (US)
Pages (from-to)93-98
Number of pages6
JournalOperations Research Letters
Volume11
Issue number2
DOIs
StatePublished - Mar 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • Karmarkar's algorithm
  • homogeneous functions

Fingerprint

Dive into the research topics of 'Generalization of Karmarkar's algorithm to convex homogeneous functions'. Together they form a unique fingerprint.

Cite this