Methods and apparatus for efficient allocation of resources by optimizing nonlinear, convex functions with linear constraints

摘要

A method and apparatus is described for optimally allocating resources. The optimal allocation is done by minimizing a cost (which is a convex non-linear function of various allocation variables) subject to different constraints (which are linear functions of the allocation variables). The method initially picks a state of the above variables (x₀) in the interior of the solution polytope (where the constraints are satisfied) and computes successive states x₁,x₂,···, which progressively reduces the cost of allocation. The above iteration stops when suitable stopping rules are met.;The method employs (i) an affine scaling transformation (a variant of Karmarkar's projective transformation) of the linear constraints, (ii) an ellipsoid to sphere transformation of the curved cost surfaces, (iii) a potential search scheme on the curved constant cost surfaces, (iv) an affine scale adjustment mechanism, and (v) a line-search scheme.