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

• US 7,277,832 B2
• Filed: 05/04/2001
• Issued: 10/02/2007
• Est. Priority Date: 05/04/2001
• Status: Expired due to Fees

• Current Assignee: Bigwood Systems, Incorporated
• Original Assignee: Bigwood Technology, Inc.
• Inventors: Chiang, Hsiao-Dong
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US09/849,213
• Publication Number:
  US 20020183987A1
• Time in Patent Office: 2,342 Days
• Field of Search: 703/2, 703 6- 22, 705/8, 700 28- 55, 700/19, 706/13, 706/19, 706/46, 706/10, 717/104
• 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 path is x_d.

Claims

1. A practical numerical computer-implemented method for reliably computing a dynamical decomposition point of a stable equilibrium point for large-scale nonlinear systems, comprising the steps of:

a) given a stable equilibrium point x_s;

b) 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;

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

d) computing said dynamical decomposition point with respect to the stable equilibrium point x_s, wherein said search path is x_d; and

e) displaying the dynamical decomposition point.

2. The method of claim 1, wherein a method for computing said exit point of the nonlinear system comprises the step of moving along said search path φ

_t(x_s)≡

{x_s+t×

ŝ

, tε

⁺} starting from X₅ 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).

3. The method of claim 1, wherein a method for computing a dynamical decomposition point comprises the steps of:

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

F(x)∥

along the corresponding trajectory, where F(x) is a vector field of the nonlinear system, and letting the point at which the first local minimum of ∥

F(x)∥

occurs be denoted x_d⁰, and is called the minimum distance point (MDP); and

b) using said MDP x_d⁰ as an initial guess and solving a set of nonlinear algebraic equations of said vector field 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.

4. The method of claim 1, wherein a method for computing said exit point with respect to a stable equilibrium point of the nonlinear system and a search vector comprises the step of computing an inner-product of said search vector and the vector field of the nonlinear system 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.

5. The method of claim 1, wherein a method for computing said exit point of the nonlinear system with respect to a stable equilibrium point and a search vector comprises the steps of:

a) moving from said stable equilibrium point along said search vector until an inner-product of said search vector and the vector field of the nonlinear system changes sign between an interval [t₁, t₂];

b) applying a linear interpolation to an interval [t₁, t₂], which produces an intermediate time to 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).

6. The method of claim 1, wherein a method for computing a minimum distance point (MDP) of the nonlinear system satisfying required conditions comprises the steps of:

a) using said exit point as an initial condition and integrating the nonlinear system for a few time-steps, and letting the end point be denoted as the current exit point;

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

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

7. The method of claim 1, wherein a method for computing said dynamical decomposition point of the nonlinear system satisfying required conditions 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

the vector field F(x) of the nonlinear system changes sign, between an interval [t₁,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, otherwise, going to step b);

b) applying linear interpolation to said interval [t₁,t₂], which produces an intermediate time to 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 the nonlinear system for a few time-steps, and letting the end point be denoted as the current exit point;

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

f) drawing a ray connecting a current exit point on said trajectory and a stable equilibrium point, replacing said current exit point with a corrected exit point which is a first local maximal point of objective function along said ray starting from the 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 of the nonlinear system F(x)=0, wherein a solution is t_d, such that said DDP with respect to a stable equilibrium point x_s and search vector ŝ

is x_d.

8. A hybrid search computer-implemented method for obtaining a local optimal solution of a general unconstrained nonlinear programming problem starting from any initial point, comprising the steps of:

a) given an initial point x₀;

b) integrating a nonlinear dynamical system that satisfies required conditions from said initial point x₀ to obtain a trajectory φ

_t(x₀) for n time-steps, n being an integer, and recording the last time-step point as the end point, and if it converges to a local optimal solution, then stopping, otherwise, going to step (c);

c) monitoring a desired convergence performance criterion along the trajectory φ

_t(x₀) in terms of the rate of decreasing values in the objective function under study, and if the desired criterion is satisfied, then using the end point of trajectory φ

_t(x₀) as the initial point and going to step (b), otherwise, going to step (d); and

d) applying an effective local optimizer (i.e., a method to find a local optimal solution) from said end point in step (b) to continue the search process, and if it finds a local optimal solution, then displaying the local optimal solution and stopping, otherwise, setting the end point of trajectory φ

_t(x₀) as the initial point, namely x₀, and going to step (b).

9. The method of claim 8, wherein in step (a) the initial point x₀ is given by a method comprising the steps of:

a) moving along a search path starting from a local optimal solution x_opt and applying a DDP search method to compute a corresponding DDP, and if a DDP can be found, then going to step (b), otherwise, 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); and

c) setting 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.

10. A computer-implemented method for obtaining a global optimal solution of unconstrained nonlinear optimization problems, comprising the steps of:

a) choosing a starting point;

b) applying the hybrid search method of claim 8 using said starting point to find a local optimal solution x_s⁰;

c) setting j=0, V_s={x_s⁰}, V_new^j={x_s⁰} and V_d{φ

};

d) wherein set V_new^j+1={φ

} and for each local optimal solution in V_new^j (i.e., x_s^j), performing steps (e) through (k);

e) defining a set of search vectors S_i^j, i=1, 2, . . . , m_j, and setting i=1;

f) if i>

m_j, then going to step (1);

otherwise, applying a DDP search method along the search vector S_i^j to find a corresponding dynamical decomposition point (DDP), and if a DDP is found, then going to step (g), otherwise, setting i=i+1 and going to step (f);

g) letting the found DDP be denoted as x_d,i^j, checking whether it belongs to the set V_d, i.e., x_d,i^jε

V_d?, and if it does, then setting i=i+1 and going to step (f), otherwise setting V_d=V_d∪

{x_d,i^j} and going to step (h);

h) for the DDP x_d,i^j, performing steps (i) through (j) to find a corresponding adjacent local optimal solution;

i) letting x_0,i^j=x_s^j+(1+ε

)(x_d,i^j−

x_s^j), where ε

is a small number;

j) applying said hybrid search method using x_0,i^j as the initial condition to find the corresponding local optimal solution, and letting it be denoted as x_s,jⁱ;

k) checking whether x_s,jⁱ has been found before, i.e., x_s,jⁱε

V_s?, and if it has already been found, then setting i=i+1 and going to step (f), otherwise, setting V_s=V_s∪

{x_s,jⁱ} and V_new^j+1=V_new^j+1∪

{x_s,jⁱ} and setting i=i+1 and going to step (f);

l) examining the set of all newly computed local optimal solutions, V_new^j+1, and if V_new^j+1 is non-empty, then setting j=j+1 and proceeding to step (d), otherwise proceeding to the next step;

m) identifying the global optimal solution from said set of local optimal solutions V_s by comparing their corresponding objective function values in set V_s and;

n) displaying the global optimal solution.

11. A computer-implemented method for obtaining a global optimal solution of a constrained nonlinear programming problem, comprising the steps of:

a) Phase I;

finding all feasible components of the constrained nonlinear programming problem wherein one effective local method is combined with said dynamical trajectory method, comprising the following steps to find a feasible solution of the constrained optimization problem;

i) given an initial point x₀;

ii) integrating a nonlinear dynamical system that satisfies required conditions from said initial point to obtain a trajectory φ

_t(x₀) for n time-steps, n is an integer, and recording the last time-step point as the end point, and if it converges to a feasible solution, then stopping, otherwise, going to step (iii);

iii) monitoring a desired convergence performance criterion in the objective function ∥

H(x)∥

, a vector norm of H(x) in the constrained optimization problem, and if the desired criterion is satisfied, then using the end point of trajectory φ

_t(x₀) as the initial point and going to step (ii), otherwise, going to step (iv); and

iv) applying an effective method from the said end point in step (b) to continue the search process, and if it finds a feasible solution of the constrained optimization problem then stopping, otherwise, setting the end point of trajectory φ

_t(x₀) in step (ii) as the initial point and going to step (ii); and

b) Phase II;

finding all local optimal solutions for the constrained nonlinear programming problem in each feasible component;

c) choosing a global optimal solution for the constrained nonlinear programming problem from the local optimal solutions found in step (b); and

d) displaying the global optimal solution for the constrained nonlinear programming problem.

12. The method of claim 11, comprising the steps of:

a) approaching a path-connected feasible component of a constrained optimization problem; and

b) escaping from said path-connected feasible component and approaching another path-connected feasible component of said constrained optimization problem.

13. The method of claim 11, comprising the steps of:

a) approaching a stable equilibrium manifold of a nonlinear dynamical system satisfying required conditions; and

b) escaping from said stable equilibrium manifold and approaching another stable equilibrium manifold of said nonlinear dynamical system satisfying said conditions.

14. The method of claim 13, comprising the steps of:

a) choose a starting point;

b) initialization j=0;

c) applying a hybrid search method for Phase I using said starting point to find a feasible point in a (path-connected) feasible component, setting a point so found as an initial point, and applying the hybrid search method for Phase II to find a local optimal solution x_s,0^j;

d) starting from said initial point x_s,0^j, applying a numerical method for Phase II to find all local optimal solutions in said feasible component and recording them as the set V_s^j and set V_s=V_s∪

V_s^j;

e) for the local optimal solution x_s,0^j, defining a set of search vectors S_i^j, i=1, 2, . . . , k_j;

f) if i>

k_j, then going to step (1), otherwise, going to step (g);

g) for each search vector S_i^j, applying a reverse-time trajectory method to find a point lying in an unstable equilibrium manifold of a system, and if a point is found, letting it be denoted as x_d,jⁱ, and going to step (h), otherwise setting i=i+1 and going to step (f);

h) setting x_0,jⁱ=x_s^j+(i+ε

)(x_d,jⁱ−

x_s^j), where ε

is a small number and x_s^j is a local optimal solution selected in step (e), and applying the hybrid search method for Phase II using x_0,jⁱ as the initial point to find a point lying in a stable equilibrium manifold of system satisfying required conditions, and letting the solution be denoted as x_s,j⁰;

i) starting from said initial point x_s,j⁰ and applying the hybrid search method of step (b) of claim 11 to find a local optimal solution in said (path-connected) feasible component x_s,j⁰;

j) checking whether x_s,0^j+1 has been found before, i.e. x_s,0^j+1ε

V_s?, and if it has been bound before (i.e., the said feasible component has been visited before), then setting i=i+1 and going to step (f), otherwise setting V_s=V_s∪

{x_s,0^j} and V_new^j+1=V_new^j+1∪

{x_s,0^j+1} and going to step (k);

k) starting from said initial point x_s,0^j+1, applying a numerical method for Phase II to find all local optimal solutions in said feasible component and recording them in the set V_s^j+1, set V_s=V_s∪

V_s^j+1 and setting i=i+1 and going to step (f);

l) examining the set of all newly computed local optimal solutions V_new^j+1, and if V_new^j+1 is empty, then going to the next step, otherwise, setting j=j+1 and going to step (e); and

m) identifying the global optimal solution from said set of local optimal solutions V_s by comparing their objective function values.

15. The method of claim 11, comprising the steps of:

a) starting from a point in a feasible component and approaching a local optimal solution located in said feasible component of an optimization problem; and

b) escaping from said local optimal solution and approaching another local optimal solution of said feasible component of said optimization problem.

16. The method of claim 11, comprising the steps of:

a) in a deterministic manner, first finding all stable equilibrium manifolds of a nonlinear dynamical system that satisfies required conditions;

b) in a deterministic manner, finding all stable equilibrium points of a nonlinear dynamical system that satisfies said conditions; and

c) then from said stable equilibrium point, finding a global optimal solution.

17. The method of claim 16, comprising the steps of:

a) given a feasible solution of constrained nonlinear programming problem;

b) finding a stable equilibrium point of a nonlinear dynamical system satisfying required conditions;

c) moving from said stable equilibrium point to a dynamical decomposition point, in order to escape from a local optimal solution; and

d) approaching another stable equilibrium point of said nonlinear dynamical system satisfying said conditions in the same path-connected feasible component, via said dynamical decomposition point.

18. A hybrid search method for Phase II of claim 11, comprising the following steps to find a local optimal solution of the constrained optimization problem:

a) given a feasible point x₀;

b) integrating a nonlinear dynamical system that satisfies required conditions from said initial point to obtain a trajectory φ

_t(x₀) for n time-steps, n is an integer, and recording the last time-step point as the end point, and if it converges to a local optimal solution, then stopping, otherwise, going to step (c);

c) monitoring a desired convergence performance criterion in an objective function C(x), and if the desired criterion is satisfied, then using the end point of trajectory φ

_t(x₀) as the initial point and going to step (b), otherwise, going to step (d); and

d) applying an effective method from the said end point in step (b) to continue the search process, and if it finds a feasible solution of the constrained optimization problem then stopping, otherwise, setting the end point of trajectory φ

_t(x₀) in step (b) as the initial point and going to step (b).

19. A numerical method for Phase II of claim 11, comprising the following steps to find all the local optimal solutions in said path-connected feasible component:

a) given an initial point lying in said path-connected feasible component;

b) initialization;

c) applying a hybrid search method for Phase II using the initial point to find a local optimal solution x_s⁰, and setting j=0, V_s={x_s⁰}, V_new,II^j={x_s⁰} and V_d={φ

};

d) for each local optimal solution in V_new^j(i.e., x_s^j), performing steps (e) through (k);

e) defining a set of search vectors S_i^j, i=1, 2, . . . , m_j, and setting i=1;

f) if i>

m_j, then going to step (1), otherwise, applying a DDP search method, wherein a nonlinear dynamical system satisfies required conditions to find a corresponding dynamical decomposition point (DDP), and if a DDP is found, then going to step (g), otherwise, setting i=i+1 and going to step (f);

g) letting the found DDP be denoted as x_d,i^j, checking whether it belongs to the set V_d, i.e., x_d,i^jε

V_d?, and if it does, then setting i=i+1 and going to step (f), otherwise setting V_d=V_d∪

{x_d,i^j} and going to step (h);

h) for the DDP x_d,i^j, performing steps (i) through (j) to find a corresponding adjacent local optimal solution;

i) setting x_0,i^j=x_s^j+(1+ε

)(x_d,i^j−

x_sⁱ), where ε

is a small number;

j) applying a hybrid search method using x_0,i^j as the initial condition to find the corresponding local optimal solution, and letting it be denoted as x_s,jⁱ;

k) checking whether x_s,jⁱ has been found before, i.e. x_s,jⁱε

V_s?, and if it has already been found, then setting i=i+1 and going to step (f), otherwise, setting V_s=V_s∪

{x_s,jⁱ} and V_new^j+1=+V_new^j+1∪

{x_s,jⁱ} and setting i=i+1 and going to step (f); and

l) examining the set of all newly computed local optimal solutions V_new,II^j+1, and if V_new,II^j+1 is non-empty, then setting j=j+1 and proceeding to step (d), otherwise outputting all the local optimal solutions in said path-connected feasible component contained in set VS and stopping the process.

20. A computer-implemented method for obtaining the global optimal solution of constrained nonlinear programming problems, comprising the steps of:

a) using a transformation technique to transform a constrained optimization problem into an unconstrained optimization problem, then applying the following steps to find the global optimal solution of the unconstrained optimization problem;

b) choosing a starting point;

c) apply a hybrid search method using said starting point to find a local optimal solution x_s⁰;

d) setting j=0, V_s={x_s⁰}, V_new^j{x_s⁰} and V_d={φ

};

e) setting V_new^j+1={φ

} and for each local optimal solution in V_new^j (i.e., x_s^j), performing steps (e) through (k);

f) defining a set of search vectors S_i^j, i=1, 2, . . . , m_j, and setting i=1;

g) if i>

m_j, then going to step (1), otherwise, applying the DDP search method of claim 15 along the search vector S_i^j to find a corresponding dynamical decomposition point (DDP), and if a DDP is found, then going to step (g), otherwise, setting i=i+1 and going to step (f);

h) letting the found DDP be denoted as x_d,i^j, checking whether it belongs to the set V_d, i.e., x_d,i^jε

V_d?, and if it does, then setting i=i+1 and going to step (f), otherwise setting V_d=V_d∪

{x_d,i^j} and going to step (h);

i) for the DDP x_d,i^j, performing steps (i) through (j) to find a corresponding adjacent local optimal solution;

j) setting x_0,i^j=x_s^j+(1+ε

)(x_d,i^j−

x_s^j), where ε

is a small number;

k) applying a hybrid search method using x_0,i^j as the initial condition to find the corresponding local optimal solution, and letting it be denoted as x_s,jⁱ;

l) checking whether x_s,jⁱ has been found before, i.e. x_s,jⁱε

V_s?, and if it has already been found, then setting i=i+1 and going to step (f), otherwise, setting V_s=V_s∪

{x_s,jⁱ} and V_new^j+1=V_new^j+1∪

{x_s,jⁱ} and setting i=i+1 and going to step (f);

m) examining the set of all newly computed local optimal solutions, V_new^j+1, and if V_new^j+1 is non-empty, then setting j=j+1 and proceeding to step (d), otherwise proceeding to the next step;

n) identifying the global optimal solution from said set of local optimal solutions V_s by comparing their corresponding objective function values in set V_s; and

o) displaying the global optimal solution.