Generalization of Karmarkar's algorithm to convex homogeneous functions

Research output: Contribution to journalArticle

1 Citation (Scopus)

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)/Πn i=1xi K/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 - Jan 1 1992

Fingerprint

Karmarkar's Algorithm
Homogeneous Function
Convex function
Subspace
Generalization

All Science Journal Classification (ASJC) codes

  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Discrete Mathematics and Combinatorics
  • Modeling and Simulation

Cite this

@article{eb575ab356264c869797e85255304385,
title = "Generalization of Karmarkar's algorithm to convex homogeneous functions",
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)/Πn i=1xi K/n)), and γ = 〈[K + 1)/K]K exp(-1)〉1/n. Karmarkar's algorithm proves the above for the special case where φ is linear.",
author = "Bahman Kalantari",
year = "1992",
month = "1",
day = "1",
doi = "10.1016/0167-6377(92)90039-6",
language = "English (US)",
volume = "11",
pages = "93--98",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "2",

}

Generalization of Karmarkar's algorithm to convex homogeneous functions. / Kalantari, Bahman.

In: Operations Research Letters, Vol. 11, No. 2, 01.01.1992, p. 93-98.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Generalization of Karmarkar's algorithm to convex homogeneous functions

AU - Kalantari, Bahman

PY - 1992/1/1

Y1 - 1992/1/1

N2 - 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)/Πn i=1xi K/n)), and γ = 〈[K + 1)/K]K exp(-1)〉1/n. Karmarkar's algorithm proves the above for the special case where φ is linear.

AB - 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)/Πn i=1xi K/n)), and γ = 〈[K + 1)/K]K exp(-1)〉1/n. Karmarkar's algorithm proves the above for the special case where φ is linear.

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

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

U2 - 10.1016/0167-6377(92)90039-6

DO - 10.1016/0167-6377(92)90039-6

M3 - Article

VL - 11

SP - 93

EP - 98

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -