Dynamical method for obtaining global optimal solution of general nonlinear programming problems

• US 20020183987A1
• Filed: 05/04/2001
• Published: 12/05/2002
• Est. Priority Date: 05/04/2001
• Status: Active Grant

• Current Assignee: Bigwood Systems, Incorporated
• Original Assignee: Bigwood Technology, Inc.
• Inventors: Chiang, Hsiao-Dong
• Granted Patent: US 7,277,832 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A method for obtaining a global optimal solution of general nonlinear programming problems includes the steps of first finding, in a deterministic manner, all stable equilibrium points of a nonlinear dynamical system that satisfies conditions (C1) and (C2), and then finding from said points a global optimal solution. A practical numerical method for reliably computing a dynamical decomposition point for large-scale systems comprises the steps of moving along a search path φ_t(x_s)≡{x_s+t×ŝ, tε⁺} starting from x_s and detecting an exit point, x_ex, at which the search path φ_t(x_s) exits a stability boundary of a stable equilibrium point x_s using the exit point X_ex as an initial condition and integrating a nonlinear system to an equilibrium point X_d, and computing said dynamical decomposition point with respect to a local optimal solution x_s wherein the search direction ŝ is e x_d.

Claims

1. A method for obtaining a global optimal solution of general nonlinear programming problems, comprising the steps of:

a) in a deterministic manner, first finding all local optimal solutions; and

b) then finding from said local optimal solutions a global optimal solution.

2. A method for obtaining a global optimal solution of general nonlinear programming problems, comprising the steps of:

a) in a deterministic manner, first finding all stable equilibrium points of a nonlinear dynamical system that satisfies conditions (C1) and (C2); and

b) then finding from said points a global optimal solution.

3. A practical numerical method for reliably computing a dynamical decomposition point for large-scale systems, comprising the steps of:

a) moving along a search path φ

_t(x_s)≡

{x_s+t×

ŝ

, tε

⁺} starting from x_s and detecting an exit point, x_ex, at which said search path φ

_t(x_s) exits a stability boundary of a stable equilibrium point x_s;

b) using said exit point x_ex as an initial condition and integrating a nonlinear system (4.2) to an equilibrium point x_d; and

c) computing said dynamical decomposition point with respect to a local optimal solution x_s wherein said search direction ŝ

is e x_d.

4. The method of claim 3, wherein a method for computing said exit point comprises the step of:

moving along said search path φ

_t(x_s)≡

{x_s+t×

ŝ

, tε

⁺} starting from x_s and detecting said exit point x_ex, which is a first local maximum of an objective function C(x) along said search path φ

_t(x_s).

5. The method of claim 3, wherein a method for computing a minimum distance point (MDP) comprises the steps of:

a)using said exit point x_ex as an initial condition and integrating a nonlinear system (4.2) to a first local minimum of a norm ∥

F(x)∥

, where F(x) is a vector of a vector field (4.2), and a local minimum point is x_d⁰;

b) using said MDP x_d,j^i,0 as an initial guess and solving a set of nonlinear algebraic equations of said vector field (4.2) F(x)=0, wherein a solution is x_d, and a dynamical decomposition point with respect to the local optimal solution x_s and said search path φ

_t(x_s) is x_d.

6. The method of claim 3, wherein a method for computing said exit point comprises the step of computing an inner-product of said search vector and vector field at each time step, by moving along said search path φ

_t(x_s)≡

{x_s+t×

ŝ

, tε

⁺} starting from x_s and at each time-step, computing an inner-product of said search vector ŝ and

vector field F(x), such that when a sign of said inner-product changes from positive to negative, said exit point is detected.

7. The method of claim 3, wherein a method for computing said exit point comprises the step of:

a) moving along said search vector until an inner-product changes sign between an interval [t₁,t₂];

b) applying a linear interpolation to an interval [t₁, t₂], which produces an intermediate time t₀ where an interpolated inner-product is expected to be zero;

c) computing an exact inner-product at t₀, such that if said value is smaller than a threshold value, said exit point is obtained; and

d) if said inner-product is positive, then replacing t₁ with t₀, and otherwise replacing t₂ with t₀ and going to step b).

8. The method of claim 3, wherein a method for computing a minimum distance point (MDP) comprises the steps of:

a) using said exit point as an initial condition and integrating a nonlinear system for a few time-steps;

b) checking convergence criterion, and, if a norm of said exit point obtained in step a) is smaller than a threshold value, then said point is declared as said MDP, and otherwise, going to step b);

c) drawing a ray connecting a current point on a trajectory and a local optimal solution, replacing said current point with a corrected exit point, which is a first local maximal point of objective function along said ray, starting from a stable equilibrium point, and assigning this point to said exit point and going to step a).

9. The method of claim 3, wherein a method for computing said dynamical decomposition point with respect to a stable equilibrium point x_s and a search vector ŝ

, comprises the steps of;

a) moving along said search path φ

_t(x_s)≡

{x_s+t×

ŝ

,tε

⁺} starting from x_s and detecting a moment that an inner-product of said search vector ŝ and

vector field F(x) changes sign, between an interval [t₁,₂], stopping this step if t₁ is greater than a threshold value and reporting that there is no adjacent local optimal solution along this search path, and otherwise, going to step b);

b) applying linear interpolation to said interval [t₁,t₂], which produces an intermediate time t₀ where said interpolated inner-product is expected to be zero, computing an exact inner-product at t₀, and if said value is smaller than a threshold value, said exit point is obtained, and going to step d);

c) if said inner-product is positive, then replacing t₁ with t₀, and otherwise replacing t₂ with t₀ and going to step b);

d) using said exit point as an initial condition and integrating a nonlinear system for a few time-steps;

e) checking convergence criterion, and if a norm of said point obtained in step d) is smaller than a threshold value, then said point is declared as the MDP and going to step g), and otherwise going to step e);

f) drawing a ray connecting a current point on said trajectory and a local optimal solution, replacing said current point with a corrected exit point which is a first local maximal point of objective function along said ray starting from a stable equilibrium point, and assigning this point to said exit point and going to Step d); and

g) using said MDP as an initial guess and solving a set of nonlinear algebraic equations of the vector field (4.2) F(x)=0, wherein a solution is t_d, such that said DDP with respect to a local optimal solution x_s and vector ŝ

is x_d.

10. The method of claim 3, wherein at least one effective local search method is combined with said dynamical trajectory method of claim 3, comprising the steps of:

a) given an initial point, integrating a nonlinear dynamical system described by (4.2) that satisfies condition (C1) from an initial point for a few time-steps to get an end point and then updating said initial point using an endpoint, before going to step b);

b) applying an effective local optimizer starting from said end point in step a) to continue the search process., and if it converges, then stopping, or otherwise, returning to step a).

11. The method of claim 3, wherein said method is used to accomplish a result selected from the group consisting of:

a) escaping from a local optimal solution;

b) guaranteeing the existence of another local optimal solution;

c) avoiding re-visit of a local optimal solution of step b);

d) assisting in searching a local optimal solution of step b); and

e) guaranteeing non-existence of another adjacent local optimal solution along a search path.

12. The method of claim 3, wherein a numerical method for performing a procedure, which searches from a local optimal solution to find another local optimal solution in a deterministic manner, comprises the steps of:

a) moving along a search path starting from x_opt and applying said DDP search method to compute a corresponding DDP, and going to step b), and if a DDP can not be found, then trying another search path and repeating this step;

b) letting said DDP be denoted as x_d., and if x_d has previously been found, then going to step a), otherwise going to step c);

c) computing a DDP-based initial point x₀=x_opt+(1+ε

)(x_d−

x_opt) where ε

is a small number, and applying a hybrid search method starting from x₀ to find a corresponding adjacent local optimal solution.