Generalization of Karmarkar's algorithm to convex homogeneous functions
Let \(\varphi\) be a homogeneous convex function of degree \(K>0\), defined over the positive points of a subspace \(W\) of \(R^ n\) \((n\geq 2)\). Assume \(\{x\in W\mid x>0, \varphi(x)>0\}\neq\emptyset\). Let \(V\) be the set of nonnegative nonzero \(x\in W\) such that \(\varphi(x^ k)\) converges to zero, for some sequence \(0<x^ k\in W\) converging to \(x\). The author proves \(V=\emptyset\) iff for every \(d\in U\) there exists \(0<x_ d\in W\) such that \(e^ T d=e^ T x_ d\) and \(f(x_ d)\leq\gamma f(d)\), where \(e\) is the vector of ones, \(f(x)=\varphi(x)/\left(\prod^ n_{i=1} x_ i\right)^{K/n}\) and \(\gamma=\{[(K+1)/K]^ K\exp(-1)\}^{1/n}\). In the case when \(\varphi\) is linear one recovers Karmarkar's algorithm.
- An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
- Karmarkar's algorithm with improved steps
- A Collinear Scaling Interpretation of Karmarkar’s Linear Programming Algorithm
- scientific article; zbMATH DE number 892328
- On the convexity of the multiplicative version of Karmarkar's potential function
- A new polynomial-time algorithm for linear programming
- An extension of Karmarkar's algorithm for linear programming using dual variables
- An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- Computing Optimal Locally Constrained Steps
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 4197755 (Why is no real title available?)
- Karmarkar's algorithm with improved steps
- Newton’s Method with a Model Trust Region Modification
This page was built for publication: Generalization of Karmarkar's algorithm to convex homogeneous functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197885)
