JP4329933B2 - Quadratic programming solver - Google Patents

Description

  In the present invention, a quadratic programming problem (an evaluation function is given by a quadratic expression and a constraint expression is given by a linear expression) that needs to be solved when making an optimal plan or performing optimal control. The present invention relates to a quadratic programming solving apparatus for solving the problem.

A quadratic programming problem with equality constraints is expressed as follows:
[Secondary programming problem with equality constraints]
Min f (x)
Subject to:
Hx = b where f (x) = p ^t x + 0.5x ^t Qx
Q: Symmetric matrix

In the conventional solution to this problem, the variable correction amount d for approaching the optimal solution is given by solving the correction equation (1) below (see, for example, Non-Patent Document 1). In addition, in order to match with general expressions related to optimization, the sign of μ ^* is defined in reverse with Non-Patent Document 1.

By the way, a general quadratic programming problem includes inequality constraints as follows.
[General secondary planning problems]
Min f (x)
Subject to:
H ₁ x = b _{1
b 2min ≦ H 2 x ≦ b} 2max
x _min ≤ x ≤ x _max

The above general quadratic programming problem can be converted into the following form having only equality constraints and upper and lower limit constraints for variables by introducing slack variable s.
Min f (x)
Subject to:
H ₁ x = b ₁
H ₂ x−s = 0
x _min ≤ x ≤ x _{max
b 2min} ≦ s ≦ b _2max

From the above, the original variable x and the introduced slack variable s are combined and expressed as x, and the original equality constraint is combined with the equality constraint created from the inequality constraint by introducing the slack variable. By expressing the whole as Hx = b, a general quadratic programming problem is converted into the following form.
Min f (x)
Subject to:
Hx = b
x _min ≤ x ≤ x _max

In order to apply the above-mentioned [equal constraint quadratic programming problem] to the transformed quadratic programming problem, the boundary of the upper and lower limit constraints in the optimal solution in the variable x It is necessary to convert the inequality constraint on the variable x _k assumed to be above into an equality constraint of x _k = f _k and no other upper and lower limit constraints.

By this conversion, the correction equation that gives the variable correction amount d for approaching the optimal solution is expressed by the following equation (2). By solving this equation, the correction direction changes from the variable correction amount d for approaching the optimal solution. I want. In the following equation (2), the correction amount d is data having a direction along with the size. In addition, “1” represented in bold is a matrix in which only the k-th element is 1 by converting the inequality constraint for the _k -th variable x _k into an equality constraint of x _k = f _k . Is shown.

"Optimization Handbook" (Asakura Shoten) 174 pages (2.7) formula

  However, the prior art has the following problems. In the conventional quadratic programming problem solving method, as described above, a modified equation of a dimension determined by “the number of variables + the number of equality constraints + the number of variables assumed to be on the boundary of upper and lower limit constraints” is solved. Furthermore, it is necessary to obtain the correction direction from the variable correction amount d for approaching the optimal solution, and there is a problem that the processing time becomes long.

  The present invention has been made to solve the above-described problems, and an object thereof is to obtain a quadratic programming method solving apparatus that solves a quadratic programming problem at high speed.

  The quadratic programming solving apparatus according to the present invention includes an input means for setting an equation of a quadratic programming problem including a functional inequality constraint, and a modified equation generated by converting the functional inequality constraint into a functional equality constraint. A storage unit having a modified equation storage file that stores variable history data storage files that store variable value history, and upper and lower limit constraint value storage files that store upper and lower limit constraint values of variables, and a functional inequality constraint Introduce slack variables to quadratic programming equations that contain them, convert them into quadratic programming equations that include functional equality constraints, and new variable upper and lower bound constraints, and limit upper and lower bound constraints The initial value in the upper and lower limit constraints is set for the conversion means to be stored in the reduction value storage file and the new variable having the upper and lower limit constraints. Identify hypothetical variables, generate modified equations using Lagrangian multipliers for the equality constraints and upper and lower bound constraints of the identified variables, store the initial values set in the variable history data storage file, and modify the generated modified equations Calculates the correction amount of the variable to approach the optimum solution by solving the correction equation stored in the correction equation storage file based on the latest data in the variable history data storage file and the correction equation generation means stored in the equation storage file And a new amount after correction that falls within the upper and lower limit constraints based on the correction amount calculated by the correction amount calculation unit and the upper and lower limit constraint values stored in the upper and lower limit constraint value storage file. Variable change means for obtaining variables and updating the variable history data storage file of the storage unit, and stored in the variable history data storage file If the variable convergence state is determined based on the number of history data and a predetermined convergence determination value and it is determined that the variable has not converged, the updated variable history data is stored in the correction amount calculation means. Iterative processing determining means for determining that the processing is to be ended when it is determined that the variable has converged again when solving the correction equation stored in the correction equation storage file based on the latest data of the file, and the iterative processing And an optimal solution output unit that extracts and outputs the latest variable from the variable history data storage file of the storage unit as an optimal solution when the determination unit determines that the processing is completed. A reduced modified equation storage file for storing reduced modified equations of small dimensions, and from the modified equations stored in the modified equation storage file, A variable that is assumed to be on the boundary of the upper and lower limit constraints, and a reduced modified equation with a small dimension that eliminates the Lagrange multipliers for the upper and lower bound constraints are generated, and the generated reduced modified equation is stored in the reduced modified equation storage file of the storage unit A reduction correction equation generating means for causing the optimum amount solution by solving the reduction correction equation stored in the reduction correction equation storage file based on the latest data in the variable history data storage file of the storage unit. The amount of correction of the variable for approaching is calculated, the iterative process determination means determines the convergence state of the variable based on the history data of the variable stored in the variable history data storage file and a predetermined convergence determination value, When it is determined that the variables have not converged, the updated variable history data storage file is sent to the reduced correction equation generating means. It is intended to produce again reduced modified equation based on the latest data and the correction equation stored in the correction equation stored file Le.

  According to the present invention, it is possible to generate a reduced correction equation having a smaller dimension than the original correction equation, and to obtain a variable correction amount for approaching an optimal solution by solving the generated reduced correction equation. A quadratic programming solving apparatus that solves a problem at high speed can be obtained.

  Hereinafter, a preferred embodiment of a quadratic programming solving apparatus of the present invention will be described with reference to the drawings. The quadratic programming solving apparatus of the present invention reduces the time required for the arithmetic processing by introducing a reduced correction equation when the optimum solution of the quadratic programming problem is obtained by repeatedly correcting the variables, thereby speeding up the calculation. It is characterized by figure.

Embodiment 1 FIG.
FIG. 1 is a configuration diagram of a quadratic programming solving apparatus according to Embodiment 1 of the present invention. The quadratic programming solving apparatus 10 includes an input unit 11, a conversion unit 12, a correction equation generation unit 13, a storage unit 14, a reduced correction equation generation unit 15, a correction amount calculation unit 16, a variable change unit 17, and an iterative process determination unit 18. And optimal solution output means 19.

  The input means 11 is an input means for reading an equation of a quadratic programming problem including a functional inequality constraint into the quadratic programming solving apparatus 10. The converting means 12 introduces slack variables into the functional inequality constraints, thereby converting the equations of the quadratic programming problem set by the input means into functional equality constraints and new variable upper and lower limit constraints. It is a conversion means. Here, the new variable is a variable that combines the original variable and the slack variable.

  The correction equation generation means 13 sets a variable that is assumed to be on the boundary of the upper and lower limit constraints in the optimal solution for the new variable having the upper and lower limit constraints, and sets the variable for approaching the optimal solution of the quadratic programming problem. It is a production | generation means which produces | generates the correction equation for calculating | requiring the correction amount.

  The storage unit 14 includes a correction equation storage file that stores correction equations, a reduced correction equation storage file that stores reduction correction equations, a variable history data storage file that stores variable values, and upper and lower limit systems that store upper and lower limit constraint values. A storage unit having an approximate value storage file.

  Based on the correction equation generated by the correction equation generation unit 13, the reduced correction equation generation unit 15 deletes the variable assumed to be on the boundary of the upper and lower limit constraints in the optimal solution and the Lagrange multiplier corresponding to the variable. Thus, the generation means generates a reduced correction equation with a small dimension. The correction amount calculating means 16 is a calculating means for obtaining a variable correction amount for approaching an optimal solution by solving a reduced correction equation.

  Based on the correction amount calculated by the correction amount calculation unit 16 and the upper and lower limit constraint values stored in the upper and lower limit constraint value storage file, the variable changing unit 17 increases and decreases in the variable correction and the optimal solution of the quadratic programming problem. This is means for specifying a new variable that is assumed to be on the boundary of the limit constraint and updating the variable history data storage file in the storage unit 14.

  The iterative process determination means 18 determines the convergence state of the variable based on the variable history data stored in the variable history data storage file, and determines whether or not the iterative process for calculating the optimum solution should be executed. Means. When iterative processing is necessary, the iterative processing determination means 18 uses the latest data in the updated variable history data storage file and the correction equation stored in the correction equation storage file to the reduced correction equation generation means 15. Based on this, the reduced correction equation is generated again.

  Furthermore, the optimum solution output means 19 takes out the latest variable updated from the variable history data storage file of the storage unit 14 as the optimum solution and outputs it when the repetition processing determination means 18 determines that the repetition processing is not necessary. It is means to do. In this way, the optimum solution is calculated by repeating a series of processes until the iterative process determining means 18 determines that the iterative process is not necessary.

  Next, the optimal solution calculation process based on the above-described reduced correction equation will be described in detail using a flowchart. FIG. 2 is a flowchart of the solution finding process in the quadratic programming method solving apparatus 10 according to the first embodiment of the present invention. First, the input unit 11 of the quadratic programming solving apparatus 10 reads an equation of a quadratic programming problem including a functional inequality constraint as a problem for which an optimal solution is to be obtained (step S201).

  The conversion means 12 converts the functional inequality constraints into functional equality constraints by introducing slack variables into the functional inequality constraints included in the equations of the read quadratic programming problem. Upper and lower limit constraints relating to a new variable that is a combination of the variable and the slack variable are set, and the upper and lower limit constraint values are stored in the upper and lower limit constraint value storage file in the storage unit 14 (step S202).

Subsequently, the correction equation generation means 13 in the [general quadratic programming problem], the upper left part of the equation (2) shown above as the correction equation for obtaining the variable correction amount d for approaching the optimal solution matrix J (Q, H, matrix of ^{H t)} to generate a (step S203).

  Further, the modified equation generating means 13 initializes the variable x without departing from the upper and lower limit constraints of the variable. In the setting of this variable, by setting a value equal to the upper limit value or the lower limit value of the upper / lower limit constraint, it can be specified as “a variable assumed to be on the boundary of the upper / lower limit constraint in the optimal solution” (step S204). ). Unless the optimal solution of the quadratic programming problem close to the target problem is already known, unless it is possible to appropriately set “variables that are assumed to be on the boundary of upper and lower limit constraints in the optimal solution” As an initial value of the variable, an intermediate value of the upper and lower limit constraints of the variable is set. As described above, the correction equation generation unit 13 generates the upper left partial matrix of the correction equation shown in Expression (2) by the processing of steps S203 and S204, and stores the generated partial matrix in the correction equation storage file.

  Next, the reduced corrected equation generating means 15 calculates the right side of the corrected equation of Equation (2), that is, the gradient g of the evaluation function and the error c of the functional equation constraint (Step S205). Subsequently, the reduced correction equation generating unit 15 generates a reduced correction equation using the calculated partial matrix J, gradient g, and error c of the functional equation constraint, and the reduced correction equation is stored in the storage unit 14. The data is stored in the reduced correction equation storage file (step S206).

Here, the generation of the reduced correction equation and the calculation of the Lagrange multiplier λ ^* will be described in detail. The original correction equation is the equation (2) shown above. In the correction amount d that is an unknown quantity of this correction equation, the element corresponding to the variable x _k that is assumed to be on the boundary of the variable upper and lower limit constraints is 0 (that is, the correction amount is 0). Since it is self-evident, it is erased. Further, a Lagrange multiplier λ ^* for the upper and lower limit constraints of x _k is obtained later, and rows affected by λ ^* are also deleted. As a result of these eliminations, the correction equation of equation (2) becomes the following reduced correction equation (3).

The matrix on the left-hand side of this reduced correction equation (3) is affected by the element of column k (shown by a dashed line) corresponding to the variable assumed to be on the boundary of the variable upper and lower constraints, and λ ^* Therefore, the element (indicated by a broken line) in row k to be erased is set to zero. However, the diagonal term is considered to have a non-zero element. The k-th element (indicated by a broken line) on the right side of the reduction correction equation (3) is also set to zero. Thus, the reduced correction equation (3) assigned 0 is a reduced correction equation that obtains the same solution as when the rows and columns are deleted. Note that there may be a plurality of column / row pairs to be erased.

By solving equation (3), d and μ ^* are obtained. Further, from the expression (2), the relationship of the following expression (4) is obtained with respect to g on the right side.

Therefore, λ ^* can be obtained from the following equation (5).

Through the above-described processing, it is possible to generate a reduced correction equation and calculate a Lagrange multiplier λ ^* . Then, it returns to description after step S207. Prior to solving the reduced correction equation (3), the correction amount calculation means 16 triangulates the matrix on the left side of the reduced correction equation (step S207). Subsequently, the correction amount calculation means 16 solves the reduced correction equation (3) to obtain a variable correction amount d and a Lagrange multiplier μ ^* for the functional equation constraint (step S208).

Subsequently, when the variable changing unit 17 corrects d for all the variables x, the variable changing unit 17 determines whether or not the deviation exceeds the upper and lower limit constraints (step S209). When it is determined that no deviation occurs, the variable changing unit 17 obtains a Lagrange multiplier λ ^* for the variable upper and lower limit constraints by the above-described method (step S210). Further, the variable changing unit 17 corrects the correction amount d calculated for all the variables x (step S211).

Subsequently, the variable changing unit 17 uses the result of the Lagrangian multiplier λ ^* calculated in step S210 to remove the restriction among the variables on the boundary between the upper and lower limits (that is, the upper limit value or the lower limit value is set). Check whether there is a variable that improves the evaluation function value by changing the value of the variable being changed to a value within the upper or lower limit constraint that is not the upper limit value or the lower limit value by modifying the value with a predetermined value ( Step S212). If there is such a variable, the variable changing means 17 deletes such a variable from “variables assumed to be on the boundary of the upper and lower limit constraints in the optimal solution” (step S213), and stores variable history data. Update file data.

  In step S213, when the data of the variable history data storage file is updated by the variable changing unit 17, the iterative processing determining unit 18 determines that it is necessary to repeatedly calculate the correction amount, and the reduced correction equation. The generation means 15 is made to generate the reduced correction equation again based on the latest data in the updated variable history data storage file and the correction equation stored in the correction equation storage file. As a result, the processing after step S205 is repeated, and the calculation of the optimum solution is continued.

  On the other hand, if it is determined in step S212 that there is no variable whose evaluation function value is improved by removing the constraint among the variables on the boundary of the upper and lower limit constraints by the variable changing unit 17, the iterative process determining unit 18 Determines that an optimal solution has been obtained. Thereafter, the optimum solution output means 19 takes out the latest variable value from the updated variable history data storage file as the optimum solution, and ends the processing (step S214).

  The iterative process determination unit 18 determines in step S212 that there is no variable whose evaluation function value is improved by removing the constraint among the variables on the boundary of the upper and lower limit constraints by the variable changing unit 17. Convergence determination is performed based on a predetermined convergence determination value and variable history data stored in the variable history data storage file. If the variable has not converged, a process of repeating step S205 and subsequent steps is performed again. It is also possible to add.

  In order to check whether there is a variable whose evaluation function value is improved by removing the constraint among the variables on the boundary of the upper and lower limit constraints, it can be performed as follows.

If the element of the Lagrange multiplier λ ^* corresponding to the variable on the boundary of the upper limit constraint (ie, the variable for which the upper limit value is set) has a negative value, or the variable on the boundary of the lower limit constraint (ie, the lower limit value) If the elements of the Lagrangian multiplier λ ^* corresponding to the variable) are positive, it is possible to improve the evaluation function value by removing the restrictions on these variables. Therefore, these variables are determined to be excluded from “variables assumed to be on the boundary of the upper and lower limit constraints in the optimal solution”. In order to remove the constraint of the variable, it is possible to obtain a value within the upper / lower limit constraint that is not the upper limit value or the lower limit value by correcting a predetermined amount.

  On the other hand, if it is determined in the previous step S209 that d has been corrected for all the variables x and the variables exceed the upper and lower limit constraints and a deviation occurs, the variable changing means 17 newly The variable x is corrected in the d direction until a variable on the boundary of the upper and lower limit constraints appears, and the variable that newly becomes the value on the boundary of the upper and lower limit constraint is displayed on the boundary of the upper and lower limit constraints. It is added to “a variable assumed to exist” (step S215).

  Specifically, the variable correction in step S215 is performed as follows. The calculated correction amount d can be regarded as a vector having data for variable elements. When a new correction correction amount is obtained by multiplying this vector by a coefficient of less than 1, the maximum variable is set so that all the variables corrected by the correction correction amount are within the upper and lower limit constraints. By obtaining the coefficients, it is possible to create a state in which all the corrected variables are within the upper and lower limit constraints and at least one variable is on the boundary of the upper and lower limit constraints.

  Subsequently, the variable changing unit 17 removes the assumption that the variable is assumed to be on the boundary of the upper / lower limit constraint in the “variable assumed to be on the boundary of the upper / lower limit constraint in the optimal solution”, that is, the upper limit value or the lower limit value. By moving the variable away from the constraint, it is checked whether there is a variable in which the error of the functional equation constraint (the sum of the absolute values of the errors of each functional equation constraint equation) decreases (step S216).

  If there is no corresponding variable, the variable changing unit 17 determines that there is no possible solution (a solution satisfying the constraint), and does not update the data in the variable history data storage file. It is determined that the process is not performed, and the process is terminated (step S217). In this case, the optimum solution output means 19 outputs that there is no possible solution.

  On the other hand, if there is a corresponding variable, the variable changing means 17 deletes such a variable from “a variable assumed to be on the boundary of the upper and lower limit constraints in the optimal solution” (step S218), and variable history data. Update the data in the storage file.

  Then, the iterative process determination means 18 determines that it is necessary to repeat the calculation of the correction amount, and gives the reduced correction equation generation means 15 the latest data and correction equation in the updated variable history data storage file. A reduced correction equation is generated again based on the correction equation stored in the storage file. As a result, the processing after step S205 is repeated, and the calculation of the optimum solution is continued.

  According to the first embodiment, a reduced correction equation having a small dimension is generated based on the correction equation and the value of the variable, and a variable correction amount for approaching an optimal solution is obtained based on the generated reduced correction equation. By repeatedly correcting the variables, it is possible to obtain an optimal solution of the secondary programming problem with high-speed processing with a small amount of calculation.

Embodiment 2. FIG.
In the second embodiment, a method will be described in which a variable assumed to be on the boundary of the upper and lower limit constraints is specified based on the calculation result of the error of the functional equation constraint, and a reduced correction equation having a smaller dimension is obtained. FIG. 3 is a configuration diagram of a quadratic programming solving apparatus according to Embodiment 2 of the present invention. The quadratic programming solving apparatus according to the second embodiment further includes a functional equality constraint storage file in the storage unit 14 as compared with the quadratic programming solving apparatus according to the first embodiment shown in FIG. ing.

  FIG. 4 is a flowchart of the solution finding process in the quadratic programming method solving apparatus according to the second embodiment of the present invention. In the second embodiment, the processes in steps S216 to S218 of the first embodiment shown in FIG. 2 are replaced with new processes, and only the flowchart of the replaced processes is shown in FIG.

  In the second embodiment, when converting the quadratic programming problem into a functional equation constraint, the converting unit 12 stores the functional equation constraint in a functional equation constraint storage file in advance. Shall. This process is not described in FIG. 4, and this process is performed in step S202 in the flowchart of FIG. 2 of the first embodiment.

  The variable changing means 17 sets the element of d corresponding to the variable to 0 for the variable newly assumed to be on the boundary of the upper and lower limit constraints determined in the process of step S215 of FIG. (Step S401). Subsequently, the variable changing unit 17 obtains the error e of the functional equation constraint extracted from the functional equation constraint storage file using the variable set in step S401 (step S402). Here, the error e is the sum of absolute values of errors of each functional equation constraint equation.

  Subsequently, the variable changing unit 17 sets the new variable after the assumption correction when it is assumed that the variable x is corrected in the d direction until a variable that is assumed to be on the boundary of the upper and lower limit constraints appears. By using this, an error e ′ of the functional equation constraint is obtained (step S403). Note that the calculation of the new variable after the assumption correction can be performed in the same manner as the processing described in step S215 of the first embodiment.

  Further, the variable changing unit 17 determines e ′ <e for the error e obtained in step S402 and the error e ′ obtained in step S403 (step S404). When it is determined that the relationship of e ′ <e is established, the variable changing unit 17 actually adopts the new variable after the assumption correction obtained in the above step S403, and “the boundary of the upper and lower limit constraints in the optimum solution” A variable assumed to be above is added (step S405). Then, the variable changing unit 17 returns to step S401 to try further correction of the variable x, and performs the subsequent processing again.

  On the other hand, if it is determined in step S404 that the relationship of e ′ <e is not established, the variable changing unit 17 ends the process without adopting the new variable after the assumption correction obtained in step S403 described above. To do. Then, the iterative process determination unit 18 determines that it is necessary to repeatedly calculate the correction amount, and instructs the reduced correction equation generation unit 15 to update the latest data and the correction equation in the updated variable history data storage file. A reduced correction equation is generated again based on the correction equation stored in the storage file. As a result, the processing after step S205 is repeated, and the calculation of the optimum solution is continued.

  According to the second embodiment, it is possible to set a plurality of variables that are assumed to be on the boundary of the upper and lower limit constraints based on the calculation result of the error of the functional equality constraint. An optimal solution can be calculated. Furthermore, it is possible to increase the correction amount of the variable x per process for obtaining the correction amount d that requires processing time, and it is possible to shorten the entire processing time for solving the quadratic programming problem.

Embodiment 3 FIG.
In the third embodiment, a quadratic programming solving apparatus that achieves a reduction in processing time by not performing triangulation processing that requires a large processing time every time when solving a reduced correction equation will be described. FIG. 5 is a configuration diagram of a quadratic programming solving apparatus according to Embodiment 3 of the present invention. Compared with the quadratic programming method solving apparatus in the first embodiment shown in FIG. 1, the quadratic programming method solving apparatus in the third embodiment further includes a triangulation decomposition history data storage file in the storage unit 14. Yes.

  FIG. 6 is a flowchart of a solution finding process in the quadratic programming method solving apparatus according to the third embodiment of the present invention. In the third embodiment, the processes of steps S207 and S208 of the first embodiment shown in FIG. 2 are replaced with new processes, and only the flowchart of the replaced processes is shown in FIG.

  As described above, after the reduced correction equation is generated by the reduced correction equation generating unit 15 in step S206 of FIG. 2, the correction amount calculating unit 16 determines whether the triangulation of the left side of the reduced correction equation has been performed in the past. Is determined (step S601). Here, the triangulated decomposition history data is stored in the triangulated decomposition history data storage file of the storage unit 14 by the correction amount calculating means 16 every time triangulation is performed in step S605 described later.

  This triangulation history data includes data on the reduced correction equation that is the source of the triangulation, the results of the triangulation for the reduced correction equation, and the variables that are assumed to be on the boundary of the upper and lower limits in solving the reduced correction equation. Yes. The correction amount calculating means 16 can determine past triangulation information based on this triangulation history data.

  If it is determined in step S601 that the triangulation has been performed in the past based on the triangulation decomposition history data, the correction amount calculation means 16 further stores the reduced correction equation stored in the reduced correction equation storage file, the triangle By comparing the previous reduced correction equations in the decomposition history data, it is determined whether the triangular decomposition of the left side of the reduced correction equations stored in the reduced correction equation storage file has been performed in the past (step S602).

  In step S602, if it is determined that the triangulation of the reduced correction equation to be solved this time (that is, the reduced correction equation stored in the reduced correction equation storage file) has already been performed in the previous process, the correction amount calculation is performed. On the boundary of the upper and lower limit constraints in the previous triangulation history data stored in the triangulation history data storage file, the means 16 is assumed to be on the upper and lower limit constraints boundary in the solution of the current reduced correction equation. Compare with a variable that you have assumed. Then, the correction amount calculation means 16 determines whether or not there is only one difference in variables that is assumed to be on the boundary between the upper and lower limit constraints (step S603).

In step S603, when it is determined that the difference in variable is only one element based on the history data, the correction amount calculation unit 16 diverts the previous triangulation result without performing triangulation again. Then, the reduced correction equation is solved to obtain the variable correction amount d and the Lagrange multiplier μ ^* for the functional equation constraint, and then the process proceeds to step S209 in FIG. 2 (step S604). This specific solution will be described later.

  On the other hand, if it is determined in step S601 that triangulation has not been performed in the past, if it is determined in step S602 that triangulation has not been performed, or if it is determined in step S603 that the difference in variables is not only one element In step S605, the correction amount calculation unit 16 performs triangulation on the left side of the current reduced correction equation.

  In step S605, the correction amount calculation unit 16 stores the triangulation decomposition history data in the triangulation decomposition history data storage file of the storage unit 14 every time triangulation is performed.

Further, the correction amount calculation means 16 solves the reduced correction equation using the triangulation result to obtain the variable correction amount d and the Lagrange multiplier μ ^* for the functional equation constraint (step S606), and then the step of FIG. The process proceeds to S209, and the subsequent processing is continued.

  In this way, if it is judged that the triangulation of the current reduced correction equation is not necessary and the result of the triangulation of the previous reduced correction equation can be diverted, the current reduced correction equation is solved without performing the triangulation again. Therefore, the number of triangulations requiring a large processing time is reduced, and the overall time for solving the quadratic programming problem can be shortened.

  Here, the solution that does not use the triangulation in step S604 described above will be described next. If the difference between the variable assumed to be on the boundary of the upper and lower limit constraints is only one element at the time when the previous reduced correction equation is created and the current reduced correction equation is created, the correction amount calculation means 16 By this process, the reduced correction equation can be solved without performing triangulation.

  When the difference in the variable that is assumed to be on the boundary of the upper and lower limit constraints is only one element, the matrix on the left side of the reduced correction equation changes only in one row and one column. For this reason, without using a new triangulation by using a formula representing a change in the inverse matrix when one row of the matrix changes and a formula representing a change in the inverse matrix when one column of the matrix is changed. It becomes possible to solve the reduced correction equation.

The formula showing the change of the inverse matrix when one column of the matrix changes is expressed as the following equation (6).
_{^{Z C -1 = Z -1 -αZ -1}} u k r k t (6)
However, Z _C ⁻¹ : Inverse matrix after column k of matrix Z has changed
Z ⁻¹ : inverse matrix of matrix Z
u _k : vector representing the amount of change of column k with respect to matrix Z
r _k ^t : the k-th row of Z ⁻¹
α: 1 / (1 + r _k ^t u _k )

Above r _k ^t, when the shape of the matrix as the reduced modified equation is a symmetric matrix can be determined by solving the following equation (7).
Zr _k = e _k (7)
However, _ek is a vector in which the kth element is 1 and all other elements are 0.

Similarly, the formula showing the change of the inverse matrix when one row of the matrix is changed is expressed as the following equation (8).
Z _R ⁻¹ = Z ⁻¹ −βs _k v _k ^t Z ⁻¹ (8)
Where Z _R ⁻¹ : inverse matrix after row k of matrix Z has changed
Z ⁻¹ : inverse matrix of matrix Z
v _k ^t : vector representing the amount of change of row k with respect to matrix Z
s _k : the k-th column of Z ⁻¹
α: 1 / (1 + v _k ^ts _k )

The above-described s _k can be obtained by solving the following equation (9) when the shape of the matrix is a symmetric matrix like the reduced correction equation.
Zs _k = e _k (9)
However, _ek is a vector in which the kth element is 1 and all other elements are 0.

  From the relationship of the above formulas (6) to (9), the inverse matrix when one row and one column are changed is represented by the following formula (10).

However, Z _CR ⁻¹ : Inverse matrix after column k and row k of matrix Z have changed
s _{k: k-th} column of _{^{[Z -1 -αZ -1 u k r}} k t]
u _k : a vector representing the amount of change of column k with respect to matrix Z
r _k ^t : the k-th row of Z ⁻¹
α: 1 / (1 + r _k ^t u _k )

S _k described above can be obtained by solving the following equation (11).
Zs _k = e _k −αu _k r _k ^t e _k (11)

Thus, Z _CR ^-1 can be expressed as Z ^-1 . Therefore, a linear equation relating Z _CR is by solving the linear equations relating Z, it is possible to solve the following procedure.

Let the equation to be solved be the following equation (12).
Z _CR y = w (12)
When this is solved for y, the following equation (13) is obtained.

  Here, y ′ is represented by the following formula (14).

  In this case, y 'is obtained as a solution of the following equation (15) for Z.

  As a result, y is calculated by the following equation (16).

  According to the third embodiment, the correction amount calculating means determines a case where the triangulation is not required in solving the reduced correction equation based on the triangulation decomposition history data, and diverts the triangulation using the previous triangulation decomposition result. Reduce correction equations can be solved without doing so. As a result, when the optimum solution is obtained by iterative calculation, the number of triangulations requiring a large processing time can be reduced, and the overall time for solving the quadratic programming problem can be shortened.

Embodiment 4 FIG.
In the fourth embodiment, a power system including a plurality of generators is taken up as a specific target to which the quadratic programming solving apparatus of the present invention is applied, and an optimal solution calculation process in this power system will be described. FIG. 7 is an explanatory diagram when the quadratic programming method solution is applied to the power system in the fourth embodiment of the present invention.

  This power system has three generators of generator 1 to generator 3 and supplies power to a load via two transmission lines. The generator 1 can output power from 2 MW to 10 MW, the generator 2 can output power from 5 MW to 20 MW, and the generator 3 is a generator that can output power from 10 MW to 30 MW. .

  In addition, 50 MW of power is supplied to the load via two power transmission lines. In FIG. 7, the two transmission lines connecting the generator and the load transmit the output of the generator 3 and the transmission line of the facility capacity 25 MW for transmitting the sum of the outputs of the generator 1 and the generator 2. It consists of a power transmission line with an installation capacity of 30 MW.

Further, the power generation costs C1 to C3 of the generators _{1 to 3} are given by secondary equations as shown in the following equations (17) to (19), where the outputs of the respective generators are x1 to x3. Assuming that
C1 = 10 + 110x ₁ + 0.1x ₁ ² (17)
C2 = 20 + 120x ₂ + 0.2x ₂ ² (18)
C3 = 30 + 130x ₃ + 0.3x ₃ ² (19)

In order to minimize the power generation cost based on the various constraints as described above, the secondary plan solving apparatus of the present invention is applied. The optimization problem that can be handled by the quadratic programming solving apparatus of the present invention needs to be expressed by the following equation as described above.
Min f (x)
Subject to:
H ₁ x = b _{1
b 2min ≦ H 2 x ≦ b} 2max
x _min ≤ x ≤ x _max
^{However, f (x) = p t} x + 0.5x t Qx

  When the optimization problem related to the power system shown in FIG. 7 is expressed by the form f (x) of the above equation, the following equation (20) is obtained.

  Note that there is no zero-order term on the right side of the above equation (20). This is because the 0th-order term does not change depending on changes in variables, and therefore it is not necessary to consider the 0th-order term when obtaining the optimum solution.

H ₁ x = b ₁ is expressed by the following equation (21) as an equality constraint representing the supply and demand balance.

_{Further, b 2min ≦ H 2 x ≦} b 2max is the relationship between the installed capacity of the transmission line, the following equation (22).

Further, x _min ≦ x ≦ x _max is expressed by the following equation (23) from the outputs of the generators 1 to 3.

  Thus, the quadratic programming solving apparatus according to the present invention described in the first to third embodiments is applied to the problem of minimizing the power generation cost of the electric power system expressed by the equations (20) to (23). Thus, an optimal solution can be obtained.

  According to the fourth embodiment, the problem of minimizing the total power generation cost of the power system while complying with various restrictions is expressed in the form of input data required by the quadratic program solving apparatus of the present invention. An optimal solution can be obtained using the quadratic program solving apparatus.

It is a block diagram of the quadratic programming solving apparatus in Embodiment 1 of this invention. It is a flowchart of the solution processing in the quadratic programming method solution apparatus of Embodiment 1 of the present invention. It is a block diagram of the quadratic programming method solution apparatus in Embodiment 2 of this invention. It is a flowchart of the solution processing in the quadratic programming method solution apparatus of Embodiment 2 of this invention. It is a block diagram of the quadratic programming method solution apparatus in Embodiment 3 of this invention. It is a flowchart of the solution process in the quadratic programming method solution apparatus of Embodiment 3 of this invention. It is explanatory drawing in the case of applying a quadratic programming method solution to the electric power system in Embodiment 4 of this invention.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 Secondary programming solution apparatus, 11 Input means, 12 Conversion means, 13 Correction equation generation means, 14 Storage part, 15 Reduction correction equation generation means, 16 Correction amount calculation means, 17 Variable change means, 18 Iteration process determination means, 19 Optimal solution output means.

Claims (5)

Input means for setting equations for quadratic programming problems including functional inequality constraints;
A modified equation storage file that stores a modified equation generated by converting the functional inequality constraint into a functional equation constraint, a variable history data storage file that stores a history of variable values, and upper and lower limit constraints of the variable A storage unit having upper and lower limit constraint value storage files for storing values;
Slack variables are introduced into the quadratic programming problem equations including the functional inequality constraints, and converted into quadratic programming problem equations including the functional equality constraints and upper and lower bound constraints of the new variables. Conversion means for storing limit constraint values in the upper and lower limit constraint value storage file;
For the new variable having upper and lower limit constraints, an initial value in the upper and lower limit constraint is set, and a variable that is assumed to be on the boundary of the upper and lower limit constraint in the optimal solution of the quadratic programming problem is specified, A modified equation is generated using a Lagrange multiplier for the identified equation equality constraint and upper and lower limit constraints, the set initial value is stored in the variable history data storage file, and the generated modified equation is stored in the modified equation. Modified equation generation means for storing in a storage file;
A correction amount calculating means for calculating a correction amount of a variable for approaching the optimal solution by solving a correction equation stored in the correction equation storage file based on the latest data of the variable history data storage file;
Based on the correction amount calculated by the correction amount calculation means and the upper and lower limit constraint values stored in the upper and lower limit constraint value storage file, a new variable after correction that falls within the range of the upper and lower limit constraints is obtained. Variable changing means for updating the variable history data storage file of the storage unit;
Determine the convergence state of the variable based on the history data of the variable stored in the variable history data storage file and a predetermined convergence determination value, and when it is determined that the variable has not converged, the correction amount calculation When the means is again executed to solve the correction equation stored in the correction equation storage file based on the latest data of the updated variable history data storage file, and when it is determined that the variable has converged Repetitive process determining means for determining to end the process;
An optimal solution output means for extracting and outputting the latest variable as an optimal solution from the variable history data storage file of the storage unit when it is determined by the iterative processing determination means that the processing has been completed; In legal solution equipment,
The storage unit further includes a reduced correction equation storage file that stores a reduced correction equation having a smaller dimension than the correction equation,
From the modified equation stored in the modified equation storage file, a variable that is assumed to be on the boundary of the upper and lower limit constraints, and a reduced modified equation with a small dimension that eliminates the Lagrange multiplier for the upper and lower constraint, A reduced correction equation generating means for storing the generated reduced correction equation in the reduced correction equation storage file of the storage unit;
The correction amount calculating means solves the reduced correction equation stored in the reduced correction equation storage file based on the latest data in the variable history data storage file of the storage unit, thereby changing the variable for approaching the optimal solution. Calculate the correction amount,
The iterative process determining means determines a variable convergence state based on variable history data stored in the variable history data storage file and a predetermined convergence determination value, and determines that the variable has not converged. When the reduced correction equation generating means regenerates the reduced correction equation based on the updated data in the updated variable history data storage file and the correction equation stored in the correction equation storage file. Characteristic quadratic programming solver. In the quadratic programming solving apparatus according to claim 1,
The variable changing means, when the correction of the total amount of the correction amount calculated by the correction amount calculation means is performed for each variable, and when all the corrected variables are within the upper and lower limit constraints, The variable history data storage file is updated with the corrected variable as the new variable value, and when at least one of the corrected variables exceeds the upper and lower limit constraints, the coefficient less than 1 that is equal to all the correction amounts The variable history data is stored by calculating a new variable after correction by calculating the maximum coefficient that does not exceed the upper and lower limit constraints after correcting each variable using the correction correction amount obtained by multiplying A quadratic programming solving apparatus characterized by updating a file. In the quadratic programming solving apparatus according to claim 2,
The storage unit further includes a functional equation constraint storage file that stores functional equation constraints.
The converting means stores the converted functional equation constraint in the functional equation constraint storage file,
The variable changing means, when the total amount of the correction amount calculated by the correction amount calculating means is corrected for each variable, when at least one of the corrected variables exceeds the upper and lower limit constraints Find the maximum coefficient that does not exceed the upper and lower limit constraints after correcting each variable using the correction correction amount obtained by multiplying all correction amounts by an equal coefficient less than 1. After the variable history data storage file is updated by obtaining a new variable after correction by the above, the function type etc. using the variables of the variable history data storage file and the function type equation constraints of the function type equation constraint storage file The error of the equation constraint is calculated as the first error, and is further calculated by the assumption correction correction amount obtained by multiplying the variable not equal to the boundary of the upper and lower limit constraints by an equal coefficient less than 1. A new variable after hypothesis correction is obtained by obtaining the maximum coefficient that does not exceed the upper and lower limit constraints after correcting these variables, and the new variable after the hypothesis correction and the functional equation constraint storage An error of the functional equation constraint is calculated as a second error using the functional equation constraint of the file, and if the first error is larger than the second error, a new one after the assumption correction is performed A quadratic programming solving apparatus, wherein the variable history data storage file is updated with a variable. In the quadratic programming solving apparatus according to any one of claims 1 to 3,
The storage unit stores a triangular decomposition history data used for triangulation decomposition history data used to store a triangulation result used in solving the reduced correction equation and a variable assumed to be on the boundary of upper and lower limit constraints in solving the reduced correction equation. Further comprising
The correction amount calculating means stores the triangular decomposition history data in the triangular decomposition history data storage file every time the triangular decomposition is performed in solving the reduced correction equation, and the upper and lower limit constraints are solved in the solution of the current reduced correction equation. The variable assumed to be on the boundary is compared with the variable assumed to be on the upper / lower limit constraint boundary in the previous triangulation history data stored in the triangulation history data storage file. When it is determined that there is only one difference in the variable assumed to be on the boundary, the triangulation in the previous triangulation history data stored in the triangulation history data storage file in solving the current reduced correction equation A quadratic programming solving apparatus characterized by calculating a correction amount using a result. In the quadratic programming solving apparatus according to any one of claims 1 to 4,
The variable changing means, when the correction of the total amount of the correction amount calculated by the correction amount calculation means is performed for each variable, and when all the corrected variables are within the upper and lower limit constraints, The variable history data storage file is updated with the corrected variable as the new variable value, the Lagrange multiplier for the upper and lower limit constraints is obtained using the corrected variable, and the Lagrange multiplier has a negative value and corresponds. Some variables are assumed to be upper bounds for upper and lower bound constraints, or the Lagrange multipliers have a positive value and the corresponding variable is assumed to be the lower bound for upper and lower bound constraints If there is something, remove these variables from the variable assumed to be on the boundary of the upper and lower limit constraints, change the value of the variable and update the variable history data storage file of the storage unit,
The iterative processing determining means determines that the iterative processing is to be performed when there is a variable excluded by the variable changing means, and notifies the reduced correction equation generating means of the updated variable history data storage file. The reduced correction equation is generated again based on the data of the correction equation and the correction equation stored in the correction equation storage file, and if there is no variable excluded by the variable changing means, it is determined that an optimal solution has been obtained and the iterative process is not performed. A quadratic programming solver characterized by:

Images