# 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)/Π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 language English (US) 93-98 6 Operations Research Letters 11 2 https://doi.org/10.1016/0167-6377(92)90039-6 Published - Mar 1992

### Fingerprint

Karmarkar's Algorithm
Homogeneous Function
Convex function
Subspace
Generalization

### All Science Journal Classification (ASJC) codes

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

### Keywords

• Karmarkar's algorithm
• homogeneous functions

### 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)/Π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.",
keywords = "Karmarkar's algorithm, homogeneous functions",
author = "Bahman Kalantari",
year = "1992",
month = "3",
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",

}

In: Operations Research Letters, Vol. 11, No. 2, 03.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/3

Y1 - 1992/3

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)/Π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.

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)/Π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.

KW - Karmarkar's algorithm

KW - homogeneous functions

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

AN - SCOPUS:0347974316

VL - 11

SP - 93

EP - 98

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -