Patent Document ID: 7991713
Application ID: 12019532
Patent Flag: 1

Claim One:
1. A method for providing an approximate solution x − , y − to a minimax problem represented by an m by n matrix A=[a i,j], 1≦i≦m and 1≦j≦n, wherein a number T of iterations of a code loop for reducing a duality gap is provided, comprising: accessing the matrix A from a data store operatively communicating with one or more computer processors, wherein the entries of A are representative of evaluations for a plurality of different circumstances; storing in the data store an initial candidate of x=(x 1 , x 2 ,. .. x n ) which is an approximation of x − , and an initial candidate y=(y 1 , y 2 ,. .. , y m ) which is an approximation of y − ; repeating the steps A through G following with a previously determined candidate approximation x for x − , and a previously determined candidate approximation y for y − , wherein at least one repetition of steps A through G is performed by the one or more computer processors; (A) determining at least one estimate ν for an equilibrium point of the minimax problem, the estimate being dependent upon x, y, and A; (B) first obtaining for x at least one adjustment Δx=(Δx 1 , Δx 2 , Δx 3 ,. .. , Δx n ), wherein at least some Δx j , 1≦j≦n, is dependent upon a difference between: a function dependent upon ν, and a result that is dependent upon members of the matrix A and y; (C) second obtaining for y at least one adjustment Δy=(Δy 1 , Δy 2 , Δy 3. .. , Δy m ), wherein at least some Δy i , 1≦i≦m, is dependent upon a difference between: a function dependent upon ν, and a result that is dependent upon members of the matrix A and x; (D) first computing, using at least one of the computer processors, an additional candidate approximation for x − as a combination of x and Δx; (E) second computing, using at least one of the computer processors, an additional candidate approximation for y − as a combination of y and Δy; (F) updating the approximation of x − with the additional candidate approximation for x − when a predetermined relationship holds between: a result of a predetermined function dependent upon Ax, and, a result of a predetermined function dependent upon a matrix product of A and the additional candidate approximation for x − ; and (G) updating the approximation of y − with the additional candidate approximation for y − when a predetermined relationship holds between: a result of a predetermined function dependent upon y′A, and, a result of a predetermined function dependent upon a matrix product of the additional candidate approximation for y − and A; wherein after the repeating step, the values for x − and y − provide the solution to the minimax problem represented by the matrix A.