COWLES FOUNDATION FOR RESEARCH IN
ECONOMICS Box 208281
COWLES FOUNDATION DISCUSSION PAPER NO. 1865R Notes on Computational Complexity of GE Inequalities Donald J. Brown July 2012 This paper is a revision of my paper, CFDP 1865. The principal
innovation is an equivalent reformulation of the decision problem for weak feasibility of
the GE inequalities, using polynomial time ellipsoid methods, as a semidefinite
optimization problem, using polynomial time interior point methods. We minimize the
maximum of the Euclidean distances between the aggregate endowment and the Minkowski sum
of the sets of consumer's Marshallian demands in each observation. We show that this is an
instance of the generic semidefinite optimization problem: inf_{x in K}f(x) =
Opt(K,f), the optimal value of the program,where the convex feasible set K and the convex
objective function f(x) have semidefinite representations. This problem can be
approximately solved in polynomial time. That is, if p(K,x) is a convex measure of
infeasibilty, where for all x, p(K,x) > 0 and p(K,z) =0 iff z in K, then for
every epsilon > 0 there exists an epsilon-optimal y such that p(K,y) <
epsilon and f(y) < epsilon + Opt(K,f) where y is computable in polynomial time
using interior point methods. |
