Notes on Computational Complexity of GE Inequalities
CFDP Revision Date
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 semideﬁnite 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 semideﬁnite 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 semideﬁnite 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 iﬀ z in K , then for every ε > 0 there exists an epsilon-optimal y such that p ( K,y ) ≤ ε and f ( y ) ≤ ε + Opt ( K,f ) where y is computable in polynomial time using interior point methods.
Brown, Donald J., "Notes on Computational Complexity of GE Inequalities" (2012). Cowles Foundation Discussion Papers. 2227.