Search directions in pattern search via rotation

• US 7,606,780 B1
• Filed: 09/12/2007
• Issued: 10/20/2009
• Est. Priority Date: 12/17/2004
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: Kumar, Rakesh, Carlson, Jared
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/900,787
• Time in Patent Office: 769 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

In performing a pattern search algorithm to find an optimal solution for an optimization, using a set of positive basis vectors that is non-maximal like a set of minimal positive basis vectors as search directions can sometimes causes the algorithm to converge at a non-optimal solution, like a horse saddle. The present invention provides a method to overcome this deficiency by rotating the vectors and hence increase the number of search directions.

Claims

1. A method for improving performance of a pattern search that seeks a solution to an optimization problem in a technical computing environment on a computing device, comprising:

identifying, with the computing device in the technical computing environment, a first set of vectors that form a positive basis for use with the optimization problem, the first set of vectors associated with an origin;

rotating the first set of vectors, using the computing device, to obtain a second set of vectors that form a positive basis for use with the optimization problem, the second set of vectors associated with the origin;

applying a first point, associated with the origin, to a function to generate a first output, using the computing device, the function representing the optimization problem;

applying, using the computing device, alternately the first set of vectors and the second set of vectors as search directions in the pattern search to find a second point that, when applied to the function, yields a more favorable output than the first output to improve performance of the pattern search in the technical computing environment on the computing device; and

storing the second point in a storage.

2. A method as defined in claim 1 further comprising:

with the computing device, using the second point as the origin for the first set of vectors and the second set of vectors in a successive iteration.

3. A method as defined in claim 2 further comprising:

with the computing device, determining a solution of the optimization problem is found when a stopping condition is reached.

4. A method as defined in claim 3 wherein the stopping condition includes a condition where a pattern size is smaller than a predetermined value, the pattern size being a distance along the search directions from the origin.

5. A method as defined in claim 1 wherein the first set of vectors are rotated according to a random angle.

6. A method as defined in claim 1 wherein the first set of vectors is a set of minimal n+1 positive basis vectors in an n-dimensional space.

7. A computer-readable medium comprising computer-executable instructions that when executed cause a computing device to perform the following functions to improve performance of a pattern search that seeks a solution to an optimization problem in a technical computing environment:

identifying, with the computing device in the technical computing device, a first set of vectors that form a positive basis for use with the optimization problem, the first set of vectors associated with an origin;

rotating the first set of vectors, using the computing device, to obtain a second set of vectors that form a positive basis for use with the optimization problem, the second set of vectors associated with the origin;

applying a first point, associated with the origin, to a function to generate a first output, using the computing device, the function representing the optimization problem;

applying, using the computing device, alternately the first set of vectors and the second set of vectors as search directions in the pattern search to find a second point that, when applied to the function, yields a more favorable output than the first output to improve performance of the pattern search in the technical computing environment on the computing device; and

storing the second point in a storage.

8. A computer-readable medium as defined in claim 7 further comprising instructions that when executed cause the computing device to perform:

using the second point as the origin for the first set of vectors and the second set of vectors in a successive iteration.

9. A computer-readable medium as defined in claim 8 further comprising instructions that when executed cause the computing device to perform:

determining a solution of the optimization problem is found when a stopping condition is reached.

10. A computer-readable medium as defined in claim 9 wherein the stopping condition includes a condition where a pattern size is smaller than a predetermined value, the pattern size being a distance along the search directions from the origin.

11. A computer-readable medium as defined in claim 7 wherein the first set of vectors are rotated according to a random angle.

12. A computer-readable medium as defined in claim 7 wherein the first set of vectors is a set of minimal n+1 positive basis vectors in an n-dimensional space.

13. An apparatus comprising:

means for identifying, using an optimization module to find a solution of an optimization problem and to save computation time of the solution in a technical computing environment, a first set of vectors that form a positive basis for use with the optimization problem, the first set of vectors associated with an origin, the optimization module adaptable to be included as part of an application running in the technical computing environment;

means for rotating the first set of vectors to obtain a second set of vectors that form a positive basis for use with the optimization problem, the second set of vectors associated with the origin;

means for applying a first point, associated with the origin, to a function to generate a first output, the function representing the optimization problem; and

means for applying alternately the first set of vectors and the second set of vectors as search directions in a pattern search to find a second point that, when applied to the function, yields a more favorable output than the first output.

14. An apparatus as defined in claim 13 further comprising:

means for using the second point as the origin for the first set of vectors and the second set of vectors in a successive iteration.

15. An apparatus as defined in claim 14 further comprising:

means for determining a solution of the optimization is found when a stopping condition is reached.

16. An apparatus comprising:

a memory; and

a processor configured to;

identify, using an optimization module to find a solution of an optimization problem and to save a computation time of the solution in a technical computing environment, a first set of vectors that form a positive basis for use with the optimization problem, the first set of vectors associated with an origin, the optimization module adaptable to be included as part of an application running in the technical computing environment;

rotate the first set of vectors to obtain a second set of vectors that form a positive basis for use with the optimization problem, the second set of vectors associated with the origin;

apply a first point, associated with the origin, to a function to generate a first output, the function representing the optimization problem;

apply alternately the first set of vectors and the second set of vectors as search directions in a pattern search to find a second point that, when applied to the function, yields a more favorable output than the first output; and

store the second point in the memory.

17. An apparatus as defined in claim 16 wherein the processor is further configured to:

use the second point as the origin for the first set of vectors and the second set of vectors in a successive iteration.

18. In a technical computing environment, a method implemented in a computing device, comprising:

finding, using the computing device, a first set of vectors that form a positive basis for use with the optimization problem;

rotating the first set of vectors, using the computing device, to obtain a second set of vectors that form a positive basis for use with the optimization problem;

applying a point, representing an origin associated with the first set of vectors and the second set of vectors, to a function to generate a first output, using the computing device, the function representing the optimization problem;

applying the second set of vectors as search directions in a pattern search to find a first set of points, using the computing device;

applying the first set of points to the function to generate a first set of outputs, using the computing device;

identifying an output in the first set of outputs that is more favorable than the first output, using the computing device, to improve performance of the pattern search in the technical computing environment on the computing device; and

storing the output in a storage.

19. A computer-implemented method as defined in claim 18 further comprising:

using a point, associated with the identified output in the first set of outputs, as the origin for the first set of vectors and the second set of vectors in a successive iteration.

20. A computer-readable medium comprising computer-executable instructions that when executed cause a computing device to perform:

finding, using the computing device, a first set of vectors that form a positive basis for use with the optimization problem;

rotating the first set of vectors, using the computing device, to obtain a second set of vectors that form a positive basis for use with the optimization problem;

applying a point, representing an origin associated with the first set of vectors and the second set of vectors, to a function to generate a first output, using the computing device, the function representing the optimization problem;

applying the second set of vectors as search directions in a pattern search to find a first set of points, using the computing device;

applying the first set of points to the function to generate a first set of outputs, using the computing device;

identifying an output in the first set of outputs that is more favorable than the first output, using the computing device, to improve performance of the pattern search in the technical computing environment on the computing device; and

storing the output in a storage.

21. A computer-readable medium as defined in claim 20 wherein the computer-readable medium further includes instructions that when executed cause the computer to perform:

using a point, associated with the identified output in the first set of outputs, as the origin for the first set of vectors and the second set of vectors in a successive iteration.