Method and system for optimization of general problems

US 7,072,723 B2
Filed: 12/23/2003
Issued: 07/04/2006
Est. Priority Date: 10/23/2002
Status: Expired due to Fees

First Claim

Patent Images

1. An optimization system comprising:

a computer system that runs a computer program; and

an optimization program thatreceives an optimization problem;

parameterizes the optimization problem using a continuous iteration parameter to produce a continualized optimization problem;

employs a method for solving the continualized optimization problem that provides a trajectory towards an optimum for the optimization problem;

formulates a number of parameters of the optimization problem as control variables to provide an iterative method for computing the control variables to steer the trajectory within a specified volume that includes an optimal trajectory, the trajectory therefore a near-optimal trajectory; and

iteratively computes a near-optimal trajectory to obtain a solution within a specified interval that includes the optimum in the large, the solution therefore a near-optimal solution.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

Embodiments of the disclosed inventinn include optimization methods and systems that receive a mathematical description of a system, in symbolic form, that includes decision variables of various types, including real-number-valued, integer-valued, and Bloolean-valued decision variables, and that may also include a variety of constraints on the values of the decision variables, including inequality and equality constraints. The objective function and constraints are incorporated into a global objective function. The global objective function is transformed into a system of differential equations in terms of continuous variables and parameters, so that polynomial-time methods for solving differential equations can be applied to calculate near-optimal solutions for the global objective function.

42 Citations

View as Search Results

35 Claims

1. An optimization system comprising:
- a computer system that runs a computer program; and
  
  an optimization program thatreceives an optimization problem;
  
  parameterizes the optimization problem using a continuous iteration parameter to produce a continualized optimization problem;
  
  employs a method for solving the continualized optimization problem that provides a trajectory towards an optimum for the optimization problem;
  
  formulates a number of parameters of the optimization problem as control variables to provide an iterative method for computing the control variables to steer the trajectory within a specified volume that includes an optimal trajectory, the trajectory therefore a near-optimal trajectory; and
  
  iteratively computes a near-optimal trajectory to obtain a solution within a specified interval that includes the optimum in the large, the solution therefore a near-optimal solution.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
- - 2. The optimization system of claim 1 wherein the optimization program receives a symbolically expressed optimization problem.
  - 3. The optimization system of claim 2 wherein the optimization program, after receiving the symbolically expressed optimization problem:
    - produces from the received optimization problem a standard-form, symbolic representation of the optimization problem.
  - 4. The optimization system of claim 3 wherein the standard-form, symbolic representation of the optimization problem can be expressed as $\underset{x, s, z}{minimize}$
    - ⁢
      
      F ⁡
      
      ( x , s , z , u , r ) = z - ∑
      
      i ⁢
      
      ⁢
      
      u i ⁢
      
      B ⁡
      
      ( g i ⁡
      
      ( x , s , z , r ) ) . where the function F is a function over decision variables x, binding variables s, an envelope variable z, a vector u of barrier-function coefficients that comprise a number of control variables, and a vector r of binding variable coefficients that comprise a number of control variables, and the g_iare expressions defining inequality constraints, and wherein the standard-form, symbolic representation of the optimization problem can be more compactly expressed as $\underset{y}{minimize} F (y, u, r)$ $with [\begin{matrix} x \\ s \\ z \end{matrix}] = y [\begin{matrix} u_{0} \\ u_{1} \\ ⋮ \\ u_{m + 2 k} \end{matrix}] = u [\begin{matrix} r_{0} \\ r_{1} \\ ⋮ \\ r_{2 k - 1} \end{matrix}] = r$ where m is the number of inequality constraints prior to conversion of equality constraints to inequality constraints, k is the number of converted inequality constraints, y, referred to as the “
      
      state vector,”
      
      is a vector of decision variables x, binding variables s, and the envelope variable z, the vector u is a vector of barrier-function coefficients, and the vector r is a vector of binding variable coefficients.
  - 5. The optimization system of claim 4 wherein the optimization program parameterizes the optimization problem using a continuous iteration parameter to produce a continualized optimization problem by parameterizing iteration functions φ
    - _kby which a next state vector y_k+1can be calculated from a current state vector y_kas follows;
      
      y_k+1=y_k+φ
      
      _k(y_k, r_k,u_k)where k=0, 1, . . . , k_convergence.
  - 6. The optimization system of claim 5 wherein the optimization program parameterizes the iterative functions φ
    - _kby introducing a continuous iteration parameter τ
      
      , where τ
      
      ranges from 0 to an iteration horizon T, and parameterizing vector functions y,u, and r by the continuous iteration variable τ
      
      .
  - 7. The optimization system of claim 6 wherein the function F is expressed in terms of the continuous iteration variable τ
    - as F(y(τ
      
      ),u(τ
      
      ), r(τ
      
      )).
  - 8. The optimization system of claim 7 wherein the iteration y_k+1=y_k+Ψ
    - _k(y_k,r_k,u_k) is transformed to a first order differential equation $\frac{ⅆ y}{ⅆ τ} = Θ (y (τ), u (τ), r (τ))$ in which the variable y is the dependent variable and u, and r are control variables to provide a method for computing efficient optimization trajectories as solutions of the differential equation, where 0≦
      
      τ
      
      ≦
      
      T.
  - 9. The optimization system of claim 8 wherein Newton'"'"'s method is used to transform φ
    - to the first order differential equation;
      
      $\frac{ⅆ y}{ⅆ τ} = H^{- 1} (y (τ), u (τ), r (τ)) G (y (τ), u (τ), r (τ))$ where the partial derivative vector G is defined as $G (y (τ), u (τ), r (τ)) = {(\frac{\partial F (y (τ), u (τ), r (τ))}{\partial y (τ)})}^{T}$ and the Hessian matrix H is a matrix of size N×
      
      N, defined as $\begin{matrix} H (y (τ), u (τ), r (τ)) = {[\frac{\partial G}{\partial y}]}^{T} (y (τ), u (τ), r (τ)) \\ = [\begin{matrix} \frac{\partial G_{0}}{\partial y_{0}} & \frac{\partial G_{1}}{\partial y_{0}} & \frac{\partial G_{2}}{\partial y_{0}} & \dots & \frac{\partial G_{N - 1}}{\partial y_{0}} \\ \frac{\partial G_{0}}{\partial y_{1}} & \frac{\partial G_{1}}{\partial y_{1}} & \frac{\partial G_{2}}{\partial y_{1}} & \dots & \frac{\partial G_{N - 1}}{\partial y_{1}} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \frac{\partial G_{0}}{\partial y_{N - 1}} & \frac{\partial G_{1}}{\partial y_{N - 1}} & \frac{\partial G_{2}}{\partial y_{N - 1}} & \dots & \frac{\partial G_{N - 1}}{\partial y_{N - 1}} \end{matrix}] \\ (y (τ), u (τ), r (τ)) . \end{matrix}$
  - 10. The optimization system of claim 8 wherein the optimization program:
    - computes control variables so as to optimize performance of the optimization program.
  - 11. The optimization system of claim 10 wherein the optimization program computes control variables so as to optimize performance of the optimization program by:
    - formulating an optimization problem for optimizing the control variables;
      
      formulating an iteration for computing the optimization variables; and
      
      continualizing the iteration using a second continuous iteration variable.
  - 12. The optimization system of claim 4 wherein the optimization program employs a method for solving the continualized optimization problem that provides a trajectory towards a minimum solution for the optimization problem by transforming the continualized optimization problem to an ordinary differential equation that expresses a normalized rate of change of the state vector y with respect to the continuous iteration variable τ
    - ;
      
      $\frac{ⅆ y}{ⅆ τ} = - \frac{H^{- 1} G}{G^{T} H^{- 1} G} (y (τ), u (τ), r (τ))$ where the partial derivative vector G is defined as $G (y (τ), u (τ), r (τ)) = {(\frac{\partial F (y (τ), u (τ), r (τ))}{\partial y (τ)})}^{T}$ and the Hessian matrix H is a matrix of size N×
      
      N, defined as $\begin{matrix} H (y (τ), u (τ), r (τ)) = {[\frac{\partial G}{\partial y}]}^{T} (y (τ), u (τ), r (τ)) \\ = [\begin{matrix} \frac{\partial G_{0}}{\partial y_{0}} & \frac{\partial G_{1}}{\partial y_{0}} & \frac{\partial G_{2}}{\partial y_{0}} & \dots & \frac{\partial G_{N - 1}}{\partial y_{0}} \\ \frac{\partial G_{0}}{\partial y_{1}} & \frac{\partial G_{1}}{\partial y_{1}} & \frac{\partial G_{2}}{\partial y_{1}} & \dots & \frac{\partial G_{N - 1}}{\partial y_{1}} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \frac{\partial G_{0}}{\partial y_{N - 1}} & \frac{\partial G_{1}}{\partial y_{N - 1}} & \frac{\partial G_{2}}{\partial y_{N - 1}} & \dots & \frac{\partial G_{N - 1}}{\partial y_{N - 1}} \end{matrix}] \\ (y (τ), u (τ), r (τ)) \end{matrix}$ alternatively expressed as $\frac{ⅆ y}{ⅆ τ} = \frac{w (τ)}{ρ (y (τ), u (τ), r (τ))}$ $where w (τ) = H^{- 1} G (y (τ), u (τ), r (τ)) and$ $ρ (y (τ), u (τ), r (τ)) = G^{T} H^{- 1} G (y (τ), u (τ), r (τ)) .$
  - 13. The optimization system of claim 12 wherein the optimization program transforms the optimization problem into a control problem, providing an iterative method for computing control variables to steer the trajectory in a near-optimal fashion, by embodying the optimization problem into a control problem $\min_{u, r}$
    - J ⁡
      
      ( u ⁡
      
      ( τ
      
      ) , r ⁡
      
      ( τ
      
      ) , T ) = ∫
      
      0 T ⁢
      
      ⅆ
      
      τ
      
      + 1 2 ⁢
      
      G T ⁢
      
      QG ⁡
      
      ( y ⁡
      
      ( T ) , u ⁡
      
      ( T ) , r ⁡
      
      ( T ) ) with respect to u(τ
      
      ), r(τ
      
      ), τ
      
      ε
      
      [0, T], where, Q is a symmetric positive definite matrix, subject to the constraints;
      
      $\begin{matrix} \frac{\partial y}{\partial τ} = \frac{w (τ)}{ρ (y (τ), u (τ), r (τ))} for τ \in [0, T] & (1) \\ u_{1} \in (0, u_{\max_{i}}) \forall i & (2) \\ u_{i} (τ + Δ τ) \leq u_{i} (τ) \forall i & (3) \\ r_{i} \in [r_{\min_{i}}, \infty) \forall i & (4) \\ r_{i} (τ + Δ τ) \geq r_{i} (τ) \forall i & (5) \end{matrix}$ to provide an optimal control policy u*(τ
      
      ) and r*(τ
      
      ) to force the objective function F to a local minimum through an optimal state-vector-change trajectory y*(τ
      
      ).
  - 14. The optimization system of claim 13 wherein the optimal control policy u*(τ
    - ) and r*(τ
      
      ) τ
      
      ε
      
      [0, T] for finding an optimal state-vector-change optimization trajectory y*(τ
      
      ) is obtained from the Hamiltonian $H = 1 - p^{T} (τ) \frac{w (τ)}{ρ (y (τ), u (τ), r (τ))}$ that has a minimum value as a function of u and r at u*(τ
      
      ) and r*(τ
      
      ),u*(τ
      
      ) optimal when a continuous costate function p(τ
      
      ) exists such that the derivatives of the state and costate functions y(τ
      
      ) and p(τ
      
      ) are, for all τ
      
      ε
      
      [0, T];
      
      $\frac{ⅆ y^{*} (τ)}{ⅆ τ} = \frac{\partial H (y^{*} (τ), u^{*} (τ), p (τ))}{\partial p}$ $\frac{ⅆ p (τ)}{ⅆ τ} = \frac{\partial H (y^{*} (τ), u^{*} (τ), p (τ))}{\partial y}$ satisfying the boundary conditions;
      
      $y^{*} (0) = y_{0}$ $p (T) = \frac{\partial G^{T} (y (T), u (T), r (T)) QG (y (T), u (T), r (T))}{\partial y}$ $for all u (τ), H (y^{*} (τ), u^{*} (τ), p (τ)) \leq H (y^{*} (τ), u (τ), p (τ)) .$
  - 15. The optimization system of claim 13 wherein the wherein the optimization program transforms the optimization problem into a control problem, providing an iterative method for computing control variables to steer the trajectory in a near-optimal fashion, the control problem summarized as $ⅆ$
    - y * ⅆ
      
      τ
      
      = - w ρ
      
      $\frac{ⅆ p}{ⅆ τ} = \frac{\partial}{\partial y} (\frac{w}{ρ}) p (τ)$ $y^{*} (0) = y_{0}$ $p (T) = H (T) QG (T)$ $p^{T} \frac{w (y^{*} (τ), u^{*} (τ), r^{*} (τ))}{ρ (y^{*} (τ), u^{*} (τ), r^{*} (τ))} \geq p^{T} \frac{w (y^{*} (τ), u (τ), r (τ))}{ρ (y^{*} (τ), u (τ), r (τ))}$ where y*(τ
      
      ) is a near-optimal state-vector trajectory, y₀is an initial state vector, p(τ
      
      ) is a costate function,u*(τ
      
      ) and r*(τ
      
      ) are optimal control policies, Q is a symmetric positive definite matrix, and τ
      
      ε
      
      [0, T].
  - 16. The optimization system of claim 2 wherein the optimization program produces from the received optimization problem a standard-form, symbolic representation of the optimization problem by:
    - converting non-real-number decision variables within the received optimization problem to real-number decision variables.
  - 17. The optimization system of claim 16 wherein converting non-real-number decision variables within the received optimization problem to real-number decision variables further includes:
    - coverting each Boolean decision variable b_ito an equivalent floating-point value y_iin the range [0,1] and with an additional constraint y_i(1−
      
      y_i)=0 that forces the floating-point variable y_ito have one of the two values 0 or 1; and
      
      converting each integer decision variable to an equivalent base-2 polynomial with k terms, where k is approximately equal to the base-2 logarithm of the maximum value that the integer decision variable can have, and representing the base-2 polynomial with k terms with k floating-point variables y₀, y₁, . . . y_k−
      
      1, all within the range [0,1] along with K constraints in the form y_i(1−
      
      y_i)=0.
  - 18. The optimization system of claim 2 wherein the optimization program produces from the received optimization problem a standard-form, symbolic representation of the optimization problem by:
    - converting real-number decision variables to floating point decision variables.
  - 19. The optimization system of claim 2 wherein the optimization program produces from the received optimization problem a standard-form, symbolic representation of the optimization problem by:
    - converting equality constraints to inequality constraints.
  - 20. The optimization system of claim 19 wherein converting equality constraints to inequality constraints further includes:
    - for each equality constraint h_j(x), converting h_j(x) to two inequality constraints and adding a third inequality constraint, as follows;
      
      $h_{j} (x) \to [\begin{matrix} h_{j} (x) + s_{j} \geq 0 \\ - h_{j} (x) + s_{j} \geq 0 \end{matrix}] \to [\begin{matrix} g_{m + j} (x, s_{j}) \\ g_{m + j + 1} (x, s_{j}) \end{matrix}] s_{j} \geq 0$ where m is the number of inequality constraints prior to conversion of equality constraints to inequality constraints and the s_jare binding variables.
  - 21. The optimization system of claim 2 wherein the optimization program produces from the received optimization problem a standard-form, symbolic representation of the optimization problem by:
    - adding an envelope variable; and
      
      formulating barrier functions to represent effects of the constraints on the trajectory towards an optimum for the optimization problem.
  - 22. The optimization system of claim 21 wherein adding an envelope variable further includes:
    - adding an envelope variable z along with an additional constraint to the optimization problem {tilde over (C)}(x) that results from converting equality constraints to inequality constraints, the variable z defined as z≧
      
      {tilde over (C)}(x) and the inequality constraint defined as z−
      
      {tilde over (C)}(x)≧
      
      0.
  - 23. The optimization system of claim 21 wherein adding barrier functions further comprises adding a barrier function −
    - u_iB(g_i) for each constraint g_i.
  - 24. The optimization system of claim 23 wherein the barrier functions have the form −
    - u_ilog(g_i) for each constraint g_i.
  - 25. The optimization system of claim 1 further including:
    - repair functionality that uses an original near-optimal solution for optimization problem to produce a continuous, repaired, extended near-optimal solution.
  - 26. The optimization system of claim 25 wherein the repair functionality uses the original near-optimal solution for optimization problem to produce a continuous, repaired, extended near-optimal solution by:
    - extending the original near-optimal solution in time;
      
      optionally taking into account events that have occurred since the original near-optimal solution for the optimization problem was calculated;
      
      optionally fixing, over particular time intervals, certain state variables of the original near-optimal solution for the optimization problem;
      
      optionally altering decision-variable values and constraints originally employed to calculate the original near-optimal solution for optimization problem; and
      
      minimizing changes in the state functions of the repaired, extended near-optimal solution with respect to the original near-optimal solution for optimization problem in order to minimize disruption.
  - 27. The optimization system of claim 25 wherein extending the original near-optimal solution in time further includes:
    - using the control functions of the original near-optimal solution and integrating partial differential equations for the state function of the original near-optimal solution in order to extend, at time t₁, the original near-optimal solution over a time interval of length Δ
      
      T from time t₁−
      
      Δ
      
      T+T to time t₁−
      
      Δ
      
      T+T.
  - 28. The optimization system of claim 25 wherein taking into account events that have occurred since the original near-optimal solution for the optimization problem was calculated further includes:
    - approximating all of the events, at time t₁, that happened during the time interval of length Δ
      
      T from time t₁−
      
      Δ
      
      T to time t₁as a single event and using that single event to modify the initial conditions for the original near-optimal solution as a step in computing the continuous, repaired, extended near-optimal solution.
  - 29. The optimization system of claim 25 wherein fixing, over particular time intervals, certain state variables of the original near-optimal solution for the optimization problem further includes:
    - identifying state variables to be fixed for particular time intervals from time t₁to time t₁+T;
      
      computing the continuous, repaired, extended near-optimal solution so that, for each identified state variable, the values computed for the identified state variable for the, repaired, extended near-optimal solution are the same as the values computed for the original near-optimal solution for the optimization problem.
  - 30. The optimization system of claim 29 wherein altering decision-variable values and constraints originally employed to calculate the original near-optimal solution for optimization problem further includes:
    - fixing variable over fenced intervals.
  - 31. The optimization system of claim 30 wherein minimizing changes in the state functions of the repaired, extended near-optimal solution with respect to the original near-optimal solution for optimization problem in order to minimize disruption further includes:
    - minimizing the variation of non-fenced variables over the time interval T.
  - 32. The optimization system of claim 29 wherein minimizing changes in the state functions of the repaired, extended near-optimal solution with respect to the original near-optimal solution for optimization problem in order to minimize disruption further includes:
    - analytically extending a nominal solution of the optimization problem from time t₁+T to time t₁+T+Δ
      
      T.
  - 33. The optimization system of claim 32 wherein minimizing changes in the state functions of the repaired, extended near-optimal solution with respect to the original near-optimal solution for optimization problem in order to minimize disruption further includes:
    - prioritizing variables with respect to particular intervals for modification.
  - 34. The optimization system of claim 29 wherein minimizing changes in the state functions of the repaired, extended near-optimal solution with respect to the original near-optimal solution for optimization problem in order to minimize disruption further includes:
    - modifying criteria constraints while extending the solution for the incremental optimization problem.

35. A method for optimizing a symbolically expressed optimization problem, the method comprising:
- receiving the symbolically expressed optimization problem;
  
  transforming the symbolically expressed optimization problem to a standard-form, symbolic representation of the optimization problem;
  
  parameterizing the standard-form optimization problem using a continuous iteration parameter to produce a continualized optimization problem;
  
  employing a method for solving the continualized optimization problem that provides a trajectory towards an optimum for the optimization problem;
  
  formulating a number of parameters of the optimization problem as control variables to provide an iterative method For computing the control variables to steer the trajectory within a specified volume that includes an optimal trajectory, the trajectory Therefore a near-optimal trajectory; and
  
  iteratively computes a near-optimal trajectory to obtain a solution within a specified interval that includes the optimum in the large.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Clearsight Systems, Inc.
Original Assignee
Clearsight Systems, Inc.
Inventors
Brayman, Vladimir, Kohn, Wolf
Primary Examiner(s)
Picard, Leo
Assistant Examiner(s)
Rapp, Chad

Application Number

US10/745,394
Publication Number

US 20050102044A1
Time in Patent Office

924 Days
Field of Search

700/21, 700 28- 33, 700/82, 700/99, 700/34
US Class Current

700/28
CPC Class Codes

G05B 13/024   in which a parameter or coe...

G06F 17/11   for solving equations , e.g...

G06N 5/01   Dynamic search techniques; ...

Method and system for optimization of general problems

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

42 Citations

35 Claims

Specification

Solutions

Use Cases

Quick Links

Method and system for optimization of general problems

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

42 Citations

35 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links