Patent ID: 8078558
Filing Date: 2011-12-13
Classification: G06F,G06Q

Abstract:
1. In industrial applications, a method for deriving the one or more global extrema of an optimization problem that can be reduced to an objective function of n variables to be minimized or maximized subject to a finite number m of functional equality or inequality constraints on the variables, where n and m are non-negative integers, said method comprising the steps of: receiving, via a first input device linked to a computer processor, a description of the objective function, the m inequality and equality constraint functions and the n variables; establishing, by a computer processor, a check-list set E indexing potential Karush Kuhn Tucker (KKT) local extrema points and the order in which they are computed by ranking them in groups E(p) from the ones having the least number p of active inequality constraints to the ones having the most number of active inequality constraints, resulting in parent or ancestor-descendant relationships where a parent or ancestor active constraints are always part of the active constraints set of a descendant; establishing, by the computer processor, an exclusion or pruning check-list set Ep indexing the potential KKT local extrema points, which along with descendants must be excluded from further consideration as candidate global extremum point; and transmitting, by an output device linked to the computer processor, the one or more optimal solutions yielded upon exhausting the comparison of the KKT local extrema points indexed by E not included in Ep; deriving, by the computer processor, the KKT equations and inequalities from the input descriptions as well as the second order optimality conditions; computing, by the computer processor, each candidate local extremum point indexed in the list E that is not excluded in Ep, where each such computation further yields information as to whether the candidate local extremum is admissible, whether their indexing parameter should be added to Ep and within which scope, and when further descendants might still need to be computed, yield intermediary parameters to facilitate such computation; comparing by the computer processor, the extremum value associated with an admissible local extremum point with that of any previously computed or assigned and if found to be an improvement, storing it so that the one or more extrema points stored in the computer memory are always associated with the optimal value among all admissible extrema computed up to that point; yielding, upon exhausting all values indexed in E not excluded by Ep, the stored one or more extrema points with the associated optimal value.