Notes on Computational Complexity of GE Inequalities

Donald J. Brown ()
Additional contact information
Donald J. Brown: Dept. of Economics, Yale University, https://economics.yale.edu/people/emeritus/donald-j-brown

No 1865R, Cowles Foundation Discussion Papers from Cowles Foundation for Research in Economics, Yale University

Abstract: 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) equivalent to 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)

Keywords: GE Inequalities; Polynomial solvability; Semidefinite Programming (search for similar items in EconPapers)
JEL-codes: D51 D58 (search for similar items in EconPapers)
Pages: 19 pages
Date: 2012-07, Revised 2012-08
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://cowles.yale.edu/sites/default/files/files/pub/d18/d1865-r.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cwl:cwldpp:1865r

Ordering information: This working paper can be ordered from
Cowles Foundation, Yale University, Box 208281, New Haven, CT 06520-8281 USA
The price is None.

Access Statistics for this paper

More papers in Cowles Foundation Discussion Papers from Cowles Foundation for Research in Economics, Yale University Yale University, Box 208281, New Haven, CT 06520-8281 USA. Contact information at EDIRC.
Bibliographic data for series maintained by Brittany Ladd ().