System and method for non-linear modeling

• US 7,774,179 B2
• Filed: 09/30/2008
• Issued: 08/10/2010
• Est. Priority Date: 01/25/2006
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Guirguis, Georges H.
• Primary Examiner(s): Shah; Kamini S
• Assistant Examiner(s): DAY, HERNG DER
• Application Number:
  US12/241,795
• Publication Number:
  US 20090030662A1
• Time in Patent Office: 679 Days
• Field of Search: 703/2, 703/6
• US Class Current: 703/2
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A computer-implemented system and method of non-linear modeling in a computer system having a limited precision processor is provided. A non-linear model is initialized by forming an objective function having one or more functional components and a marginal variance matrix. The model is then iteratively solved using the computer processor until it has converged to a feasible solution. In doing so, the feasibility of computing the objective function is evaluated by determining if the marginal variance matrix is positive definite, thereby indicating whether or not the computer processor is capable of calculating a feasible solution to the non-linear model. If the marginal variance matrix is positive definite, then the objective function and its gradient are computed using the marginal variance matrix. If the marginal variance matrix is not positive definite, then a surrogate marginal variance matrix is constructed that is positive definite and a surrogate objective function is constructed having components continuous first derivatives. The surrogate objective function and its gradient are then computed using the surrogate marginal variance matrix.

Claims

1. A computer-implemented system, including a non-linear optimizer for use with a limited precision computer processor executing a calling procedure that generates a plurality of model parameters and requests a solution to a non-linear model from the non-linear optimizer, comprising:

one or more computer-readable storage mediums containing software instructions executable on the limited precision computer processor to cause the limited precision computer processor to perform operations including;

initializing the non-linear model by forming an objective function (F) having functional components (F₁, F₂, F₃ . . . ) and a marginal variance matrix (V) using a plurality of input parameters to the model stored in a memory coupled to the limited precision computer processor;

wherein the objective function (F) is described in terms of the marginal variance matrix (V), and wherein the marginal variance matrix (V) comprises a plurality of eigenvalues based on the input parameters to the model;

iteratively solving the non-linear model using the limited precision computer processor until the model has converged to a feasible solution, comprising;

evaluating the feasibility of computing the objective function by determining if the marginal variance matrix (V) is positive definite, thereby indicating whether the limited precision processor is capable of evaluating the feasible solution to the objective function;

responsive to the marginal variance matrix (V) being positive definite, executing a first set of computer software instructions using the limited precision computer processor that calculate the objective function (F) and its gradient using the marginal variance matrix (V); and

responsive to the marginal variance matrix (V) not being positive definite, executing a second set of computer software instructions using the limited precision computer processor that;

construct a surrogate marginal variance matrix (V⁺) that is positive definite;

construct a surrogate objective function (F⁺) in which the functional components (F₁, F₂, F₃ . . . ) of the objective function are replaced with surrogate functional components (F₁⁺, F₂⁺, F₃⁺, . . . ) having continuous first derivatives;

calculate the surrogate objective function (F⁺) and its gradient using the surrogate marginal variance matrix (V⁺); and

storing the objective function and its gradient or the surrogate objective function and its gradient.

2. The system of claim 1, wherein evaluating includes determining whether any of the eigenvalues in the marginal variance matrix (V) are greater than or equal to a positive threshold value.

3. The system of claim 1, wherein evaluating includes determining whether any of the eigenvalues in the marginal variance matrix (V) are less than a positive threshold value.

4. The system of claim 1, further comprising:

outputting the calculations of the objective function (F) and the surrogate objective function (F⁺) to a graphical display device coupled to the computer processor.

5. The system of claim 1, wherein the surrogate marginal variance matrix is constructed by substituting a positive threshold value for any eigenvalue in the marginal variance matrix that is less than the positive threshold value.

6. The system of claim 1, wherein the surrogate functional components are continuous functions.

7. The system of claim 1, wherein the functional components (F₁, F₂, F₃ . . . ) and the surrogate functional components (F₁⁺, F₂⁺, F₃⁺, . . . ) are defined by the following equation:

8. The system of claim 7, wherein the surrogate vector of eigenvalues λ

⁺ is constructed using the following equation;

λ

_i⁺=max(λ

_i,ε

), where ε

is a small positive value.

9. The system of claim 1, wherein the calling procedure is a data mining procedure, a risk modeling procedure, a time series modeling procedure, or a statistical modeling procedure.

10. A computer-implemented method of non-linear modeling in a computer system having a limited precision computer processor, comprising:

initializing, on the limited precision computer processor, a non-linear model by forming an objective function (F) having functional components (F₁, F₂, F₃ . . . ) and a marginal variance matrix (V) using a plurality of input parameters to the model stored in a memory coupled to the limited precision computer processor;

wherein the objective function (F) is described in terms of the marginal variance matrix (V), and wherein the marginal variance matrix (V) comprises a plurality of eigenvalues based on the input parameters to the model;

iteratively solving the non-linear model using the limited precision computer processor until the model has converged to a feasible solution, comprising the steps of;

evaluating the feasibility of computing the objective function by determining if the marginal variance matrix (V) is positive definite, thereby indicating whether the limited precision processor is capable of evaluating the feasible solution to the objective function;

if the marginal variance matrix (V) is positive definite, then executing a first set of computer software instructions using the limited precision computer processor that calculate the objective function (F) and its gradient using the marginal variance matrix (V); and

if the marginal variance matrix (V) is not positive definite, then executing a second set of computer software instructions using the limited precision computer processor that;

(a) construct a surrogate marginal variance matrix (V⁺) that is positive definite;

(b) construct a surrogate objective function (F⁺) in which the functional components (F₁, F₂, F₃ . . . ) of the objective function are replaced with surrogate functional components (F₁⁺, F₂⁺, F₃⁺. . . ) having continuous first derivatives;

(c) calculate the surrogate objective function (F⁺) and its gradient using the surrogate marginal variance matrix (V⁺); and

storing the objective function and its gradient or the surrogate objective function and its gradient.

11. The computer-implemented method of claim 10, wherein the evaluating step determines whether any of the eigenvalues in the marginal variance matrix (V) are greater than or equal to a positive threshold value.

12. The computer-implemented method of claim 10, wherein the evaluating step determines whether any of the eigenvalues in the marginal variance matrix (V) are less than a positive threshold value.

13. The computer-implemented method of claim 12, wherein the positive threshold value is about 10⁻

7.

14. The computer-implemented method of claim 10, further comprising:

during the iteratively solving step, outputting the calculations of the objective function (F) and the surrogate objective function (F⁺) to a graphical display device coupled to the limited precision computer processor.

15. The computer-implemented method of claim 10, wherein the surrogate marginal variance matrix is constructed by substituting a positive threshold value for any eigenvalue in the marginal variance matrix that is less than the positive threshold value.

16. The computer-implemented method of claim 10, wherein the surrogate functional components are continuous functions.

17. The computer-implemented method of claim 10, wherein the functional components (F₁, F₂, F₃ . . . ) and the surrogate functional components (F₁⁺, F₂⁺, F₃⁺. . . ) are defined by the following equation:

18. The computer-implemented method of claim 17, wherein the surrogate vector of eigenvalues λ

⁺ is constructed using the following equation;

λ

_i⁺=max(λ

_i,ε

), where ε

is a small positive value.