Efficient Simplex-Like Methods for Equilibria of Nonsymmetric Analog Networks

Publisher Website
Google Scholar
Abstract
What is the complexity of computing equilibria for physically implementable analog networks (Hopfield 1984; Sejnowski 1981) with arbitrary connectivity? We show that if the amplifiers are piecewise-linear, then such networks are instances of a game-theoretic model known as polymatrix games. In contrast with the usual gradient descent methods for symmetric networks, equilibria for polymatrix games may be computed by vertex pivoting algorithms similar to the simplex method for linear programming. Like the simplex method, these algorithms have characteristic low order polynomial behavior in virtually all practical cases, though not certain theoretical ones. While these algorithms cannot be applied to models requiring evolution from an initial point, they are applicable to “clamping” models whose input is expressed purely as a bias. Thus we have an a priori indication that such models are computationally tractable.

This publication has 16 references indexed in Scilit: