DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
The Amendment filed 9 April 2025 has been entered. Claims 1-2 and 4-6 remain pending in the application. Applicant’s amendment to claim 4 overcomes the 112(b) rejection previously set forth in the Non-Final Office Action mailed 10 January 2025.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitations are:
generation unit to generate an active constraint set based on the inequality constraint set and the initial solution. The structure for a “generation unit” is being interpreted as the inputs and outputs of FIG. 3 element 21, along with the FIG. 4 components. And specification paragraphs [0075]-[0079] providing the computational steps for initializing the active set (FIG. 9, S11-S13) and incremental building of the active set (FIG. 9 S14-S17).
search unit to find a solution of a simultaneous linear equation generated based on the active constraint set and the evaluation function. The structure for a “search unit” is being interpreted as the inputs and outputs of FIG. 3 element 22, along with specification paragraph [0043] describing the computation steps for minimizing evaluation function J (equation 8).
updating unit to update the active constraint set based on the solution obtained by the search unit. The structure for an “updating unit” is being interpreted as the inputs and outputs of FIG. 3 element 23, along with specification paragraph [0096] providing the algorithmic step of checking and acting on the Lagrange multipliers.
addition determination unit to determine whether or not the inequality constraint set includes a first inequality constraint that satisfies a condition for addition to the active constraint set. The structure for an “addition determination unit” is being interpreted as the input and output of FIG. 4 element 113, along with specification paragraph [0050] providing the steps for checking inequality constraints by plugging values into formula 11, as implemented in FIG. 9 S14.
linear dependence determination unit to determine whether or not the first inequality constraint that satisfies the condition is linearly dependent on one or more second inequality constraints included in the active constraint set. The structure for a “linear dependence determination unit is being interpreted as the input and output of FIG. 4 element 114, along with specification paragraphs [0081]-[0082] providing the implementation steps of FIG. 9 S15 -S16. And specification paragraphs [0058]-[0066] describing the FIG. 5-7 implementation, using a two-part test for linear dependence.
active constraint addition unit to add, to the active constraint set, the first inequality constraint determined by the linear dependence determination unit as being not linearly dependent on the one or more second inequality constraints. See comments under 112(a) and 112(b).
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 1 and 6 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. Claims 2 and 4 inherit the same deficiency as claim 1 based on dependence. The claims contain subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention. Claim limitation: “active constraint addition unit” in claims 1 and 6 invokes 35 USC 112(f) or pre-AIA 35 USC 112, sixth paragraph. However, the written description fails to provide an adequate description of the structure, material, or acts to perform the claimed functions of these limitations. See rejection under 35 USC 112(b) below for further details as to the requirement of a respective algorithm.
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1 and 6 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention. Claims 2 and 4 inherit the same deficiency as claim 1 based on dependence. Claim 1 and 6 limitation an “active constraint addition unit” invokes 35 USC 112(f) or pre-AIA 35 USC 112, sixth paragraph. However, the written description fails to disclose the corresponding structure, material or acts for performing the entire claimed function. Specification paragraph [0105] merely restates the function to be performed (“to add”) without providing any algorithm or step-by-step procedure for how the addition occurs. Specification paragraphs [0092]-[0096] describe updating the active set in broad terms (obtaining w from y), but do not describe how the active constraint addition unit performs the steps of incorporating the new constraint into the data structure representing the active set. For example, the specification does not explain how constraints are indexed, stored, or flagged in memory, nor does it explain steps for how the system modifies that data structure when a new constraint is deemed independent. Without implementation details, there is no meaningful corresponding structure disclosed beyond a general-purpose computer as the structure designed to perform the “add” function (MPEP 2181(II)(B)). Thus, the description provides merely the high-level result of updating, not the steps required to support the claimed unit.
The following is a quotation of 35 U.S.C. 112(d):
(d) REFERENCE IN DEPENDENT FORMS.—Subject to subsection (e), a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
The following is a quotation of pre-AIA 35 U.S.C. 112, fourth paragraph:
Subject to the following paragraph [i.e., the fifth paragraph of pre-AIA 35 U.S.C. 112], a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
Claim 2 is rejected under 35 U.S.C. 112(d) or pre-AIA 35 U.S.C. 112, 4th paragraph, as being of improper dependent form for failing to further limit the subject matter of the claim upon which it depends. Claim 2 merely restates the same two-part test already incorporated into claim 1’s means-plus-function limitation. It fails to add any further limitation beyond what is already claimed by the linear dependence determination unit of claim 1, as interpreted as the structure in the specification (see 112(f) above). Applicant may cancel the claim(s), amend the claim(s) to place the claim(s) in proper dependent form, rewrite the claim(s) in independent form, or present a sufficient showing that the dependent claim(s) complies with the statutory requirements.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-2 and 3-6 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea (math) without significantly more.
Claim 1
Step 1: Claim 1 falls within a statutory category of patentable subject matter under 35 USC 101:
a machine.
Step 2A prong 1: Claim 1 is directed to an abstract idea. Claim 1 recites mathematical concepts
including finding an optimal solution of a convex quadratic programming problem, an evaluation function (mathematical function), an inequality constraint set (mathematical relationship), an initial solution of the convex quadratic programming problem (mathematical input), a generation unit (selecting constraints from inequalities to define a subset relationship between variables is merely using a mathematical relationship), a search unit (solving a system of linear equations is an algebraic computation), an addition determination unit (evaluating whether an inequality satisfies a condition is merely a mathematical relationship between variables), a linear dependence determination unit (checking for vector/constraint dependence is an algebraic relationship between variables), an active constraint addition unit (updating the set with new inequality variables based on results is a mathematical calculation), and establish[ing] one or more linear dependence flags for one or more elements which have non-zero coefficients and for which no linear dependence flags have been established (tracking dependence conditions), and determin[ing] that the first inequality constraint is linearly dependent on the one or more second inequality constraints, when the one or more linear dependence flags are established for all of the one or more elements included in the first inequality constraint and having the non-zero coefficients (decision rule based on algebraic relationships).
Step 2A prong 2: Claim 1 recites the following additional elements: a computing device, an interface to obtain [inputs], a processor, and linear dependence flags. A computing device, an interface, and a processor are recited at a high level of generality (i.e. as generic computer components) such that they amount to no more than components comprising mere instructions to apply the exception. See MPEP 2106.05(f). Accordingly, these additional elements do not integrate the abstract idea(s) into a practical application because they do not impose any meaningful limits on practicing the abstract idea(s). An interface “to obtain” is a pre-solution activity to gather data, which is insignificant extra-solution activity (MPEP 2106.05(g)). And using a flags as signal markers to mark states of variables during execution is an instruction to implement the mathematical algorithm on a generic computer. See MPEP 2106.05(f). For these reasons, claim 1 does not integrate the abstract idea into a practical application.
Step 2B: as discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned computer elements (a computing device, an interface, a processor, and data markers) amount to no more than components comprising mere instructions to apply the exception. Mere instructions to apply an exception using generic computer components cannot provide an inventive concept. Additionally, with regards to “an interface to obtain” an input, per MPEP 2106.05(d)(II), the courts have recognized the following computer functions as well-understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity: Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); TL/ Communications LLC v. AV Auto. LLC, 823 F.3d 607,610, 118 USPQ2d 1744, 1745 (Fed. Cir. 2016) (using a telephone for image transmission); OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d 1090, 1093 (Fed. Cir. 2015) (sending messages over a network); buySAFE, Inc. v. Google, Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014) (computer receives and sends information over a network). Here, the interface is merely performing a generic function by receiving and forwarding data. Claim 1 considered as a whole does not amount to significantly more than the judicial exception.
Claim 2 is rejected for at least the reasons set forth with respect to claim 1.
Under step 2A prong 1, claim 2 further limits the mathematical concepts of claim 1 by determining that the first inequality constraint is linearly dependent on the one or more second inequality constraints (mathematical relationship), when one or more elements included in each of the one or more second inequality constraints and having non-zero coefficients are a subset of one or more elements included in the first inequality constraint and having non-zero coefficients (subset determination using a mathematical coefficient analysis), when the number of the one or more elements included in the one or more second inequality constraints and having the non-zero coefficients is more than or equal to the number of the one or more elements included in the first inequality constraint and having the non-zero coefficients (mathematical comparison).
Claim 2 contains no further additional elements that would require further consideration under Step 2A Prong 2 and Step 2B.
Claim 4 is rejected for at least the reasons set forth with respect to claim 1.
Under step 2A prong 1, claim 2 further limits the mathematical concepts of claim 1 by, in the initial solution (mathematical sequencing), preferentially adding a third inequality constraint to the active constraint set (prioritized constraint addition), the added third inequality constraint being a constraint that is included in the inequality constraint set (mathematical relationship) and that is deviated the most from its corresponding constraint value at each prediction time (calculation and comparison).
Claim 4 contains no further additional elements that would require further consideration under Step 2A Prong 2 and Step 2B.
Claim 5 is directed to a method that would be practiced by the device of claim 1. All steps recited in claim 5 are practiced by the device of claims 1. The claim 1 analysis equally applies to claim 5.
Claim 6
Step 1: Claim 6 falls within a statutory category of patentable subject matter under 35 USC 101:
A machine.
Step 2A prong 1: Claim 6 is directed to an abstract idea. Claim 6 recites mathematical concepts
Including finding an optimal solution of a convex quadratic programming problem, an evaluation function (mathematical function), an inequality constraint set (mathematical relationship), an initial solution of the convex quadratic programming problem (mathematical input), a generation unit (selecting constraints from inequalities to define a subset relationship between variables is merely using a mathematical relationship), a search unit (solving a system of linear equations is an algebraic computation), an addition determination unit (evaluating whether an inequality satisfies a condition is merely a mathematical relationship between variables), a linear dependence determination unit (checking for vector/constraint dependence is an algebraic relationship between variables), an active constraint addition unit (updating the set with new inequality variables based on results is a mathematical calculation), and in the initial solution (mathematical sequencing), preferentially adding a third inequality constraint to the active constraint set (prioritized constraint addition), the added third inequality constraint being a constraint that is included in the inequality constraint set (mathematical relationship) and that is deviated the most from its corresponding constraint value at each prediction time (calculation and comparison).
Step 2A prong 2: Claim 6 recites the following additional elements: a computing device, an interface to obtain [inputs], and a processor. These elements amount to no more than components comprising mere instructions to apply the exception. See MPEP 2106.05(f). Accordingly, these additional elements do not integrate the abstract idea(s) into a practical application because they do not impose any meaningful limits on practicing the abstract idea(s). Furthermore, an interface “to obtain” is a pre-solution activity to gather data, which is insignificant extra-solution activity (MPEP 2106.05(g)). For these reasons claim 6 fails to integrate the judicial exception into a practical application.
Step 2B: as discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned computer elements (a computing device, an interface, and a processor) amount to no more than components comprising mere instructions to apply the exception. Mere instructions to apply an exception using generic computer components cannot provide an inventive concept. Additionally, with regards to “an interface to obtain” an input, per MPEP 2106.05(d)(II), the courts have recognized the following computer functions as well-understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity: Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); TL/ Communications LLC v. AV Auto. LLC, 823 F.3d 607,610, 118 USPQ2d 1744, 1745 (Fed. Cir. 2016) (using a telephone for image transmission); OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d 1090, 1093 (Fed. Cir. 2015) (sending messages over a network); buySAFE, Inc. v. Google, Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014) (computer receives and sends information over a network). Here, the interface is merely performing a generic function by receiving and forwarding data. Claim 1 considered as a whole does not amount to significantly more than the judicial exception.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-2 and 5 are rejected under 35 U.S.C. 103 as being unpatentable over Mustafa et al. US Patent No. 8,600,525 B1 (hereinafter "Mustafa") in view of Das US Pub. No. 2004/0162709 A1 (hereinafter "Das”) in further view of MathWorks, Inc. "sprank - Structural rank" MATLAB documentation, R2012b. Internet Archive Wayback Machine (hereinafter "MATLAB”), in further view of T. Achterberg (2007), Constraint Integer Programming. PhD thesis. 10.14279/depositonce-1634 (hereinafter "Achterberg”).
Regarding claim 1, Mustafa teaches:
a computing device (Fig. 1 and col. 5 lines 2-15; regarding a control system 104 which includes one or more computing devices) for finding an optimal solution (Figure 3: 310 RETURN OPTIMAL SOLUTION) of a quadratic programming problem (col. 8 lines 27-28 "The method 200 can be used, for example, to solve the QP problem in Equation (14)").
Mustafa further teaches: the computing device comprising: an interface (col. 5 lines 8-10 "The control system 104 also includes at least one network interface", col. 6 lines 23-26 "the methods 200-400 are described as being performed by the control system 104 in the system 100 of FIG.1. However, the methods 200-400 could be performed by any other suitable device(s) and in any other suitable systems.") to obtain (Figure 2: 202 "RECEIVE AND ANALYZE INPUT DATA", col 8 lines 48-55 "As shown in FIG. 2, input data is received and analyzed at step 202. This could include, for example, the control system 104 receiving measurement data from one or more of the sensor arrays 126-128. This could also include the control system 104 receiving or generating a Hessian matrix and actuator constraint matrices associated with the process being controlled. The input data could involve any suitable process being controlled”) an evaluation function (col. 6 line 27 through col. 8 line 14 "…formulated as a linear inequality‐constrained QP problem;” data inputs from the sensors into the control system are modeled, evaluated, and tuned using mathematical functions and expressions to formulate an initial QP problem), an inequality constraint set (Fig. 2, col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set"), and an initial solution of the quadratic programming problem (Fig. 3 and col. 9 lines 38-39 “step 302 indicates that a prior solution is available, and a warm start may occur,” col. 14 lines 24-25 "identifying an initial solution to a quadratic programming (QP) problem"); and
a processor (Fig. 5, col. 13 lines 10-15 "The QP solver 502 could represent a standalone device or be integrated into another device or system, such as a control system. The QP solver 502 could be implemented in any suitable manner, such as using at least one processing device, at least one memory, and at least one network interface") to find the optimal solution (Figure 3: 310 RETURN OPTIMAL SOLUTION) based on the evaluation function (col. 6 line 27 through col. 8 line 14 "…formulated as a linear inequality‐constrained QP problem;” data inputs from the sensors into the control system are modeled, evaluated, and tuned using mathematical functions and expressions to formulate an initial QP problem), the inequality constraint set (col. 8 lines 51-54 describing actuator constraint matrices, Fig. 2, col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set"), and the initial solution obtained by the interface (Fig. 3 element 302 and col. 9 lines 38-39 “step 302 indicates that a prior solution is available, and a warm start may occur,” col. 14 lines 24-25 "identifying an initial solution to a quadratic programming (QP) problem"), wherein the processor comprises
a generation unit to generate an active constraint set based on the inequality constraint set and the initial solution (col. 9, lines 45-48 "In some embodiments, for instance, the optimal solution to the previous QP problem is used to identify active constraints and initialize an active set and other related variables at step 314,” col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set”),
a search unit to find a solution of a simultaneous linear equation (Abstract, col. 10 line 58 “Once the full and partial step lengths are calculated…” through col. 11 line 33 “…it can be solved in various ways, such as by triangular factorization or Gaussian elimination”, and col. 8 describing minimizing a quadratic function subject to linear constraints, with G strictly positive Hessian, as equivalent to equation 8) generated based on the active constraint set (col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set”) and the evaluation function (col. 6 line 27 through col. 8 line 14 "…formulated as a linear inequality‐constrained QP problem;” data inputs from the sensors into the control system are modeled, evaluated, and tuned using mathematical functions and expressions to formulate an initial QP problem), and
an updating unit to update the active constraint set based on the solution obtained by the search unit (col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set,” (FIGURE 2 arrow circles back to 216: VIOLATED CONSTRAINT(S)), the generation unit comprises
an addition determination unit to determine whether or not the inequality constraint set includes a first inequality constraint that satisfies a condition (col. 8 line 47 "Violated constraint: Any constraint subject to
A
i
∆
U
(
k
)
>
b
i
” col. 9, lines 52-53 "A determination is made whether there are any violated constraints at step 216”, FIG. 2 step 216 as performing test for addition to set) for addition to the active constraint set (col. 14 line 48 “adding the selected violated constraint to the active set,” FIGURE 2: 216 VIOLATED CONSTRAINT(S)),
determining whether or not the first inequality constraint that satisfies the condition is linearly dependent on one or more second inequality constraints included in the active constraint set (Col. 10 lines 61-64 "If both
τ
f
and
τ
p
equal infinity (∞), it can imply that the current solution is infeasible. If only
τ
f
equals infinity, the selected violated constraint can be linearly dependent on at least one of the constraints in
A
w
", col. 12 lines 29-39 describing that Mustafa relies on a Schur complement formulation, which implicitly assumes that the constraints in the active set are linearly independent), and
an active constraint addition unit to add, to the active constraint set (Col. 9, lines 50-55 "where any violated constraints are brought into the active constraint set of the solution. A determination is made whether there are any violated constraints at step 216. If not, the method 200 ends as there are no additional constraints to be brought into the active constraint set of the solution,” col. 11 line 16 "add the violated constraint to
A
w
,” col. 8 line 33 “
A
w
,
b
w
: active constraint set”), the first inequality constraint not linearly dependent on the one or more second inequality constraints (col. 10 lines 63-64 "the selected violated constraint can be linearly dependent on at least one of the constraints in
A
w
").
While Mustafa provides an example where the Hessian matrix is symmetric and strictly positive definite (Col. 8, lines 15-16), Mustafa does not explicitly characterize the problem as a convex quadratic programming problem. Additionally, Mustafa frames the linear dependence check as a safeguard and not as the mechanism functioning as a linear dependence determination unit. And Mustafa is silent as to computational markers to track linear dependence.
However, in the same field of endeavor, Das teaches a computing device for finding an optimal solution of a convex quadratic programming problem. (Das [0013] “attain a feasible and optimal solution” and [0009] “The mechanism of searching for the optimal active set or the set of binding constraints described herein can be applied to any convex optimization problem, including convex quadratic programming”).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the solution process of Mustafa with the convex quadratic programming formulation as disclosed by Das. Doing so would aid in achieving accurate performance in feedback control frameworks (Das [0023] describing accuracy required in feedback control). And modifying with Das’s convex quadratic implementation would have been obvious since Das in the same field of quadratic programming solvers for model predictive control (Das [Background]).
Das further teaches a mechanism for checking for linear dependence (Das [0013] “The present invention provides a mechanism for detecting linear dependency in the set of active constraints in an iteration without prior pre-processing using the steps in the current factorization”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the quadratic programming solver of Mustafa to incorporate the linear dependence detection mechanism of Das. Doing so would improve robustness by handling degeneracy directly during iterative updates, rather than rely on a separate pre-processing step (Das [abstract] describing that the method is “designed to deal with degenerate constraints as the required factorizations are performed and as degeneracy emerges, and not via a mostly unnecessary pre-process step”).
Das is silent as to the subset operations and does not disclose a two-part subset and cardinally test.
In the same field of numerical linear algebra and sparse matrix analysis, MATLAB teaches a linear dependence determination through its structural rank function “sprank” (MATLAB “sprank(A) is the structural rank of the sparse matrix A” thereby operating as a subset check by identifying whether a new row introduces novel nonzero column positions, and performs the cardinality comparison by assessing whether the row contributes enough distinct nonzeros to increase rank).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the active-set quadratic programming solver of Mustafa in view of the linear dependence detection mechanism of Das to further incorporate the structural rank analysis of MATLAB’s sprank. Such a combination would have been obvious as structural rank analysis operates on sparse matrices without requiring conversion to full matrices, and provides an upper bound on numerical rank (MATLAB sprank(A) >= rank(full(A))). Applying this check would aid in accelerating the active set method by providing fast pre-filtering, thereby reducing computational costs.
While Mustafa and Das in view of MATLAB teaches a linear dependence determination unit that determines if the first inequality constraint is linearly dependent on the one or more second inequality constraints, the combination is silent as to the computational markers used to track the linear dependence.
However, in the same field of endeavor, Achterberg teaches wherein in order of one or more constraint numbers of the one or more second inequality constraints (Achterberg pg. 87 “Each linear constraint possesses a “propagated” flag” and pg. 88 Algorithm 7.1 “For all variables xj with aj > 0:” then “For all variables xj with aj < 0:” thereby processing constraint elements in order), the algorithm establishes one or more linear dependence flags for one or more elements which have non-zero coefficients (Achterberg page 87 “The flag will be automatically reset to 0 … whenever a bound of a variable with a non-zero coefficient
a
j
≠
0
is modified” and the “event handler catches all bound changes that are applied on variables that appear with non-zero coefficient
a
j
≠
0
in the constraint”, thereby flags are tied to elements with non-zero coefficients) and for which no linear dependence flags have been established (Achterberg pg. 87 “flag which is initially set to 0” and “if the flag is set to 1, we can skip”, thereby only processing if not already flagged, and pg. 88 “Algorithm 7.1 “If the constraint is already marked as propagated, abort.”) and the algorithm determines when the one or more linear dependence flags are established for all of the one or more elements included in the first inequality constraint and having the non-zero coefficients (Achterberg pg. 88 Algorithm 7.1 steps 5-6 decision based on all relevant non-zero coefficient elements).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the linear dependence detection of Mustafa and Das in view of MATLAB to further incorporate the propagated flags as disclosed by Achterberg. Doing so would aid in avoiding redundant processing of constraint elements, as Achterberg discloses that flags enable the system to “skip the domain propagation for this constraint” when elements have already processed (Achterberg pg. 87). Such a modification would have been obvious to a person of ordinary skill in the art since Achterberg operates within the same field of mathematical optimization and addresses the underlying problem of efficiency processing linear constraints with non-zero coefficients to avoid redundant computation.
Regarding claim 2, Mustafa and Das in view of MATLAB, in further view of Achterberg teach the computing device according to claim 1.
While Mustafa teaches a linear dependence check, Mustafa does not teach a mechanism incorporating a two-step process.
However in the same field of endeavor, Das teaches a mechanism to test for linear dependence (Das [0013] “The present invention provides a mechanism for detecting linear dependency in the set of active constraints in an iteration without prior pre-processing using the steps in the current factorization”).
The motivation to combine provided with respect to claim 1 applies equally to claim 2.
In the same field of endeavor, MATLAB teaches a linear dependence determination using a two-step process through its structural rank function “sprank” (MATLAB “sprank(A) is the structural rank of the sparse matrix A”).
The motivation to combine provided with respect to claim 1 applies equally to claim 2.
MATLAB further discloses one or more elements included in each of the one or more second inequality constraints and having non-zero coefficients are a subset of one or more elements included in the first inequality constraint and having non-zero coefficients (MATLAB example shows sprank analyzing a matrix where rows share nonzero column positions).
and when the number of the one or more elements included in the one or more second inequality constraints and having the non-zero coefficients is more than or equal to the number of the one or more elements included in the first inequality constraint and having the non-zero coefficients (MATLAB example shows sprank comparing structural verses numerical rank).
The motivation to combine provided with respect to claim 1 applies equally to claim 2.
With regards to Claim 5, Mustafa teaches:
a computing method (Mustafa Fig. 1, col. 5 lines 2-15; regarding a control system 104 which includes one or more computing devices, col. 2 lines 34-36 “FIGS. 2 through 4 illustrate an example method for efficient quadratic programming (QP) solving for process control and optimization”) for finding an optimal solution (Figure 3: 310 RETURN OPTIMAL SOLUTION) of a quadratic programming problem by a computer (col. 8 lines 27-28 "The method 200 can be used, for example, to solve the QP problem in Equation (14),”col. 2 lines 4-20 regarding a computer readable medium), the computing method comprising:
generating an active constraint set based on an inequality constraint set and an initial solution in the quadratic programming problem (col. 9, lines 45-48 "In some embodiments, for instance, the optimal solution to the previous QP problem is used to identify active constraints and initialize an active set and other related variables at step 314,” col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set”);
finding a solution of a simultaneous linear equation (col. 10 line 58 “Once the full and partial step lengths are calculated…” through col. 11 line 33 “…it can be solved in various ways, such as by triangular factorization or Gaussian elimination”) generated based on the active constraint set (col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set”) and an evaluation function in the quadratic programming problem (col. 6 line 27 through col. 8 line 14 "…formulated as a linear inequality‐constrained QP problem;” data inputs from the sensors into the control system are modeled, evaluated, and tuned using mathematical functions and expressions to formulate an initial QP problem); and
updating the active constraint set based on the solution obtained by the finding of the solution (col. 9 lines 49-52 “an iterative process using a dualfeasible active-set algorithm then occurs, where any violated constraints are brought into the active constraint set,” (FIGURE 2 arrow circles back to 216: VIOLATED CONSTRAINT(S)), wherein the generating comprises
determining whether or not the inequality constraint set includes a first inequality constraint that satisfies a condition (col. 8 line 47 "Violated constraint: Any constraint subject to
A
i
∆
U
(
k
)
>
b
i
” col. 9, lines 52-53 "A determination is made whether there are any violated constraints at step 216”) for addition to the active constraint set (col. 14 line 48 “adding the selected violated constraint to the active set,” FIGURE 2: 216 VIOLATED CONSTRAINT(S)),
determining whether or not the first inequality constraint that satisfies the condition is linearly dependent on one or more second inequality constraints included in the active constraint set (Col. 10 lines 61-64 "If both
τ
f
and
τ
p
equal infinity (∞), it can imply that