</a>Polyhedral computing: optimizing responses to complexity

Polyhedral Empowerment of Networks through Symmetry: psycho-social implications for organization and global governance (Part #8)

[Parts: First | Prev | Next | Last | All] [Links: To-K | From-K | From-Kx | Refs ]

The set of feasible solutions of a linear optimization problem is a convex polyhedron. Specially structured variants of these problems define polytopes with special structures. In this way the theory and algorithms of linear optimization are inherently linked to polyhedral theory and properties of convex bodies.

The generic issues posed by the above concerns were brought to a focus at the Centre de recherches mathématiques (University of Montreal) in the form of a semester on Polyhedral Computation Combinatorial Optimization (2006) presented as follows:

The last 15 years have seen significant progress in the development of general purpose algorithms and software for polyhedral computation e.g. finding lattice points, enumerating vertices, extreme rays and facets, and triangulating polyhedra. Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general purpose algorithms. They are, however, highly structured and attention has turned to exploiting this structure, particularly symmetry. Initial applications of this approach have permitted computations previously far out of reach, but much remains to be understood and validated experimentally. This workshop intends to bring together researchers with both theoretical and computational expertise with polyhedral computation.

Polyhedral computation addresses the computational complexity of solving problems associated with convex polyhedra and search for efficient algorithms. One of the most fundamental problems is the vertex enumeration problem that is to list all vertices of a convex polytope given as the solution set to a system of m linear inequalities in d-variables -- as succinctly presented by Jakub Marecek (Polyhedral Approach to Multicriterial Optimization, 2006). It is in this sense that polyhedral approaches are fundamental to decision-making under uncertainty, if only in the field of economics (Andreas Eicchorn, et al. Polyhedral Risk Measures and Langrangian Relaxation in Electricity Portfoloio Optimization, 2005).

More generally it is worth considering the possibility that an appropriate polyhedral configuration of criteria, opportunities and constraints constitutes a comprehensible, credible "solution" to any strategic dilemma. The argument here, notably in the light of the "epistemic" framing provided by Roth (above), is that it is precisely the polyhedral coherence (through symmetry effects) that renders a solution both understandable and memorable as a gestalt that "works". Thus what is otherwise understood through the intuitionist school of mathematics is echoed in how a viable solution is apprehended beyond that discipline. This possibility is clearly of significance to governance and to that to which the governed are asked to subscribe -- and to the manner in which a complex solution can be communicated (notably in the light of Atkin's arguments regarding the communicability of insights).

How should governance envisage optimizing the multicriteria decision-making challenges of the future -- given the computing resources on which it can call -- in a manner to render the "solutions" comprehensible and credible to all concerned?

In purely material terms, such arguments are of course consistent with the aesthetic appeal of sacred geometry as a response to architectural and design challenges. The question is how such polyhedral configuration might prove significant in psycho-social organization and knowledge structure design, notably when it takes virtual form on the web (cf Sacralization of Hyperlink Geometry, 1997; Spherical Configuration of Categories -- to reflect systemic patterns of environmental checks and balances, 1994; Spherical Configuration of Interlocking Roundtables: internet enhancement of global self-organization through patterns of dialogue, 1998).

[Parts: First | Prev | Next | Last | All] [Links: To-K | From-K | From-Kx | Refs ]