[Technical Field]

[0001] This present disclosure relates generally to machine control, and more particularly to a system and a method for controlling an operation of a machine according to a task.

[Background Art]

[0002] Quadratic program is a process of solving certain mathematical optimization problems involving quadratic functions. Specifically, the quadratic program involves optimizing (minimize or maximize) a multivariate quadratic function subject to constraints on variables. Quadratic programming arises as subproblems when solving nonlinear programming.

[0003] The quadratic program is widely used for optimization-based control and estimation methods, such as model predictive control (MPC) and moving horizon estimation (MHE). One of the main advantages of these methods is their systematic way of incorporating a dynamic model of a system, limitations in form of inequality constraints, and performance metrics in form of a cost function. At each sampling instant, a model-based predictive controller or estimator solves a multi-stage dynamic optimization problem that minimizes a particular cost function subject to a discrete-time description of the system dynamics and the inequality constraints. A block-sparse quadratic program structure arises in linear or linear time-varying formulations of predictive control and estimation. A similarly structured QP forms subproblems within a sequential quadratic programming (SQP) method for nonlinear optimal control. [0004] To that end, a number of methods have been developed to solve the quadratic program. Examples of the methods for solving the quadratic program include an interior point method, an active set method, an augmented Lagrangian method, and a conjugate gradient or gradient projection method. However, the quadratic program is difficult to solve due to its potential nonconvexity and the constraints. To address such a problem, a number of methods reformulate the quadratic program into a different space and solve the reformulated quadratic program. For example, the augmented Lagrangian method solves Lagrangian dual of the quadratic program.

[0005] However, while the reformulation of the quadratic program may address some difficulties, another complication still exists, viz., the quadratic program may not have a feasible solution at all. The infeasibility can be caused by situations when the constraints defining different feasible sets do not intersect. For example, the quadratic program may be subject to equality and inequality constraints defining two feasible sets. When the two feasible sets do not intersect, the quadratic program is infeasible. Hence, a critical feature required for solving the quadratic program is detection of the infeasibility of the quadratic program.

[Summary of Invention]

[0006] It is an object of some embodiments to provide a system and a method for detecting infeasibility of an original quadratic program (QP). The original QP optimizes an objective function subject to constraints. The constraints may include equality constraints and inequality constraints. Additionally or alternatively, it is object of some embodiments to provide such a system and a method that can determine a solution of the original QP if the original QP is feasible. Additionally, it is object of some embodiments to determine a control command to a machine based on the solution of the original QP, and control the machine based on the control command determined based on the solution of the original QP.

[0007] Some embodiments are based on the realization that additionally or alternatively to reformulating the original QP into a different space, it is possible to reformulate constraints into a different space of higher dimensions to ensure that all possible sets defined by different constraints intersect at least at one point. The rationale here is that if an optimal solution of the QP is found to be at that point, solution of the original QP is infeasible. The infeasibility is detected based on convergence of iteration rather than divergence as before. The feasibility detection based on convergence is more efficient and computationally cheaper.

[0008] For example, some embodiments, lift the inequality constraints and the equality constraints into a lifted space having a dimension higher than a dimension of an original space of the original QP by a lifting operation. The lifting operation introduces an additional non-negative variable such that a subspace defined by the equality constraint in the lifted space intersects a subspace defined by the inequality constraint in the lifted space at least at a point of origin of the lifted space. In such a manner, the infeasibility of the original QP can be detected when the solution of the QP in the lifted space has the value of the additional non-negative variable equal to zero.

[0009] Different lifting operations can be used to transform the constraints from the original space into the lifted space of higher dimensions. Examples of the lifting operations include multiplication of the constraints with one or multiple additional variables defining new dimensions, affine or non- affine transformations of the constraints, and the like.

[0010] Some embodiments select such a lifting operation that has a corresponding projection operation that reverses the effects of the lifting operation. For example, if the lifting operation includes multiplication of values in the original space with the additional non-negative variable, the projecting operation includes dividing values in the lifted space by the additional nonnegative variable. Similarly, when the lifting operation includes addition of values in the original space by the additional non-negative variable, the projecting operation includes subtraction of the additional non-negative variable from the values in the lifted space.

[0011] Some embodiments are based on the recognition that in order to use the constraints in the lifted space, there is a need to transform the original QP from the original space to the lifted space. However, the lifting operation used for lifting the constraints is not directly applicable for lifting the objective function of the original QP since the objective function has quadratic terms and linear terms. Multiplying the quadratic terms by the additional non-negative variable results in an objective function that is a degree 3 polynomial and no longer a quadratic program. In other words, direct application of the lifting operation to the original QP is not possible.

[0012] However, some embodiments are based on a realization that regardless of structure of the original QP lifted in the lifted space, a relationship between the optimal solution in the original space and the optimal solution in the lifted space is governed by the lifting operation. Further, the optimal solutions, while unknown, should satisfy first-order optimality conditions. Moreover, the lifting operation for the constraints, while not applicable to the QP objective function, is applicable to the first-order optimality conditions.

[0013] To that end, some embodiments, after lifting the constraints into the lifted space with the lifting operation, transform the objective function of the original QP in the original space into a quadratic objective function involving variables of the original QP and the additional non-negative variable. The quadratic objective function subject to the lifted equality and inequality constraints forms a homogeneous QP in the lifted space such that first-order optimality conditions of the homogeneous QP correspond to first-order optimality conditions of the original QP lifted in the higher space by the lifting operation.

[0014] Further, the homogeneous QP is solved to produce a solution in the lifted space. If the value of the additional non-negative variable in the solution in the lifted space equals to zero, then, the machine is controlled according to an infeasibility protocol. If the value of the additional nonnegative variable in the solution in the lifted space is not equal to zero, then, the solution in the lifted space is projected into the original space using a projection operation reversing the lifting operation, to produce a solution of the original QP. For example, if the equality constraints are lifted in the lifted space by scaling the equality constraints with the additional non-negative variable, then the solution in the lifted space is projected to the original space by dividing the solution in the lifted space with the additional non-negative variable.

[0015] Further, in some embodiments, a control command is determined based on the solution of the original QP. Further, the machine is controlled based on the control command determined based on the solution of the original QP.

[0016] Different embodiments use different formulations of the homogeneous QP. Any formulation of the homogeneous QP is valid as long as the first-order optimality conditions of the homogeneous QP correspond to the first-order optimality conditions of the original QP lifted in the higher space by the lifting operation. However, some embodiments can impose additional rules on the formulation of the homogeneous QP for different computational and optimization reasons. For example, in one embodiment, the original QP is transformed such that the solution of the homogeneous QP in the lifted space is negative for positive values of the additional non-negative variable. This rule ensures that the optimal value in the lifted space for the feasible original QP problem does not have the value of the additional non-negative variable equal to zero.

[0017] Accordingly, one embodiment discloses a controller for controlling an operation of a machine according to a task. The controller comprises a memory configured to store executable instructions, and a processor configured to execute the executable instructions to cause the controller to: collect a feedback signal indicative of a current state of the operation of the machine; formulate an original quadratic program (QP) for optimizing an objective function subject to equality constraints and inequality constraints on one or a combination of state and control variables of the machine based on the task and the current state of the operation of the machine; lift the equality constraints and the inequality constraints into a lifted space having a dimension higher than a dimension of an original space of the original QP by a lifting operation introducing an additional non-negative variable such that a subspace defined by the equality constraints in the lifted space intersects a subspace defined by the inequality constraints in the lifted space at least at a point of origin of the lifted space; transform the objective function of the original QP into a quadratic objective function involving variables of the original QP and the additional non-negative variable, wherein the quadratic objective function subject to the lifted equality and inequality constraints forms a homogeneous QP in the lifted space such that first-order optimality conditions of the homogeneous QP correspond to first-order optimality conditions of the original QP lifted in the higher space by the lifting operation ; solve the homogeneous QP to produce a solution in the lifted space; control the machine according to an infeasibility protocol when a value of the additional non- negative variable in the solution in the lifted space equals zero; and otherwise project the solution in the lifted space into the original space using a projection operation reversing the lifting operation to produce a solution of the original QP; and control the machine using a control command determined based on the solution of the original QP.

[0018] Accordingly, another embodiment discloses a method for controlling an operation of a machine according to a task. The method comprises collecting a feedback signal indicative of a current state of the operation of the machine; formulating an original quadratic program (QP) for optimizing an objective function subject to equality constraints and inequality constraints on one or a combination of state and control variables of the machine based on the task and the current state of the operation of the machine; lifting the equality constraints and the inequality constraints into a lifted space having a dimension higher than a dimension of an original space of the original QP by a lifting operation introducing an additional non-negative variable such that a subspace defined by the equality constraints in the lifted space intersects a subspace defined by the inequality constraints in the lifted space at least at a point of origin of the lifted space; transforming the objective function of the original QP into a quadratic objective function involving variables of the original QP and the additional non-negative variable, wherein the quadratic objective function subject to the lifted equality and inequality constraints forms a homogeneous QP in the lifted space such that first-order optimality conditions of the homogeneous QP correspond to first-order optimality conditions of the original QP lifted in the higher space by the lifting operation; solving the homogeneous QP to produce a solution in the lifted space; controlling the machine according to an infeasibility protocol when a value of the additional non-negative variable in the solution in the lifted space equals zero; and otherwise projecting the solution in the lifted space into the original space using a projection operation reversing the lifting operation to produce a solution of the original QP; and controlling the machine using a control command determined based on the solution of the original QP. [0019] Accordingly, yet another embodiment discloses a non-transitory computer-readable storage medium embodied thereon a program executable by a processor for performing a method for controlling an operation of a machine according to a task. The method comprises collecting a feedback signal indicative of a current state of the operation of the machine; formulating an original quadratic program (QP) for optimizing an objective function subject to equality constraints and inequality constraints on one or a combination of state and control variables of the machine based on the task and the current state of the operation of the machine; lifting the equality constraints and the inequality constraints into a lifted space having a dimension higher than a dimension of an original space of the original QP by a lifting operation introducing an additional non-negative variable such that a subspace defined by the equality constraints in the lifted space intersects a subspace defined by the inequality constraints in the lifted space at least at a point of origin of the lifted space; transforming the objective function of the original QP into a quadratic objective function involving variables of the original QP and the additional non-negative variable, wherein the quadratic objective function subject to the lifted equality and inequality constraints forms a homogeneous QP in the lifted space such that first-order optimality conditions of the homogeneous QP correspond to first-order optimality conditions of the original QP lifted in the higher space by the lifting operation; solving the homogeneous QP to produce a solution in the lifted space; controlling the machine according to an infeasibility protocol when a value of the additional non-negative variable in the solution in the lifted space equals zero; and otherwise projecting the solution in the lifted space into the original space using a projection operation reversing the lifting operation to produce a solution of the original QP; and controlling the machine using a control command determined based on the solution of the original QP. [0020] The presently disclosed embodiments will be further explained with reference to the attached drawings. The drawings shown are not necessarily to scale, with emphasis instead generally being placed upon illustrating the principles of the presently disclosed embodiments.

[Brief Description of Drawings]

[0021]

[Fig. 1A]

FIG. 1A illustrates an environment for controlling an operation of a machine according to a task, according to some embodiments of the present disclosure. [Fig. 1B]

FIG. 1B shows a block diagram of a controller for controlling the operation of the machine, according to an embodiment of the present disclosure.

[Fig. 1C]

FIG. 1C shows an example of infeasible original quadratic program (QP), according to an embodiment of the present disclosure.

[Fig. 1D]

FIG. 1D illustrates a transformation of an objective function of an original QP into a quadratic objective function, according to an embodiment of the present disclosure.

[Fig. 1E]

FIG. 1E shows a block diagram for solving a homogeneous QP to produce a solution in a lifted space and controlling the machine based on the solution in the lifted space, according to an embodiment of the present disclosure.

[Fig. 2]

FIG. 2 shows a block diagram a for determining a scalar of a quadratic term of an additional non-negative variable, according to an embodiment of the present disclosure.

[Fig. 3] FIG. 3 shows a schematic of an original QP, first-order optimality conditions of the original QP, and infeasibility conditions of the original QP, according to an embodiment of the present disclosure.

[Fig. 4]

FIG. 4 shows a schematic of a homogeneous QP and first-order optimality conditions of the homogeneous QP, according to an embodiment of the present disclosure.

[Fig. 5]

FIG. 5 shows an Interior Point Method (IPM) algorithm for determining the solution of the homogeneous QP, according to an embodiment of the present disclosure.

[Fig. 6]

FIG. 6 shows a schematic of Active-Set Method (ASM) for determining the solution of the homogeneous QP, according to an embodiment of the present disclosure.

[Fig. 7]

FIG. 7 shows a schematic of Alternating Direction Method of Multipliers (ADMM) for determining the solution of the homogeneous QP, according to an embodiment of the present disclosure.

[Fig. 8]

FIG. 8 shows an algorithm for solving Linear Conic Programs (LCP), according to an embodiment of the present disclosure.

[Fig. 9]

FIG. 9 shows a block diagram of a model predictive controller (MPC) for determining a control command, according to some embodiments of the present disclosure.

[Fig. 10A] FIG. 10A shows a schematic of a vehicle including the controller for controlling the vehicle, according to some embodiments of the present disclosure.

[Fig. 10B]

FIG. 10B shows a schematic of interaction between the controller and controllers of the vehicle, according to some embodiments of the present disclosure.

[Fig. 10C]

FIG. 10C shows a schematic of a path and/or motion planning for the vehicle, according to some embodiments of the present disclosure.

[Fig. 11A]

FIG. 11A shows schematics of a spacecraft predictive control problem, according to some embodiments of the present disclosure.

[Fig. 11B]

FIG. 11B shows schematics of a spacecraft predictive control problem, according to some embodiments of the present disclosure.

[Fig. 12A]

FIG. 12A shows schematics for controlling of a vapor compression system (VCS) by the controller, according to some embodiments of the present disclosure.

[Fig. 12B]

FIG. 12B shows schematics for controlling of a vapor compression system (VCS) by the controller, according to some embodiments of the present disclosure.

[Fig. 13]

FIG. 13 shows a block diagram of an overall method for controlling an operation of a machine according to a task, according to an embodiment of the present disclosure. [Fig. 14]

FIG. 14 shows a block diagram of an overall method for controlling an operation of a machine according to a task, according to an embodiment of the present disclosure.

[Description of Embodiments]

[0022] In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present disclosure. It will be apparent, however, to one skilled in the art that the present disclosure may be practiced without these specific details. In other instances, apparatuses and methods are shown in block diagram form only in order to avoid obscuring the present disclosure.

[0023] As used in this specification and claims, the terms “for example,” “for instance,” and “such as,” and the verbs “comprising,” “having,” “including,” and their other verb forms, when used in conjunction with a listing of one or more components or other items, are each to be construed as open ended, meaning that that the listing is not to be considered as excluding other, additional components or items. The term “based on” means at least partially based on. Further, it is to be understood that the phraseology and terminology employed herein are for the purpose of the description and should not be regarded as limiting. Any heading utilized within this description is for convenience only and has no legal or limiting effect.

[0024] FIG. 1A illustrates an environment 100 for controlling an operation of a machine 103 according to a task, according to some embodiments of the present disclosure. A controller 101 is operatively connected to the machine 103. The controller 101 is configured to control the operation of the machine 103 according to the task. Examples of the machine 101 may include a vehicle (e.g., an autonomous vehicle), a robotic assembly, a legged robot, a motor, an elevator door, a HVAC (Heating, Ventilating, and Air-Conditioning) system, or the like. For example, the vehicle may be selfdriving car, aircraft, spacecraft, dynamically positioned ships, or the like. Examples of the operation of the machine 103 may include, but are not limited to, operating the vehicle according to a specific objective, operating the HVAC system according to specific parameters, operating a robot arm according to a specific assembly task, and opening/closing elevator doors.

[0025] Further, the machine 103 is connected to the controller 101 via a state estimator 105. In some implementations, the controller 101 is programmed according to a model 107 of the machine 103. The machine model 107 can include a set of mathematical equations that describe how a state(s) of the machine 103 changes over time as functions of current and previous inputs and previous outputs of the machine 103. According to an embodiment, the state of the machine 103 is any information, in general time varying, for instance an appropriate subset of current and previous inputs and outputs, that, together with the model 107 of the machine 103 and future inputs , can uniquely define a future motion of the machine 103. The machine model 107 can include constraints 109 that represent physical and operational limitations of the machine 103.

[0026] During operation, the controller 101 receives a command 115 indicating a desired behavior of the machine 103. The command can be, for example, a motion command. In response to receiving the command 115, the controller 101 generates a control command 111 that serves as an input for the machine 103. In response to the input, the machine 103 produces an output 113. Based on measurements of the output 113 of the machine 103, the state estimator 105 estimates a state 117 of the operation of the machine 103. The estimated state 117 is fed to the controller 101 as a feedback signal. The estimated state 117 may correspond to a current state of the operation of the machine 103. [0027] The machine 103, as referred herein, can be any system or device controlled by input signals (e.g., input 111), possibly associated to physical quantities such as voltages, pressures, forces, torques, and to return some controlled output signals (e.g., output 113), possibly associated to physical quantities such as currents, flows, velocities, positions indicative of a transition of a state of the machine 103 from a previous state to the current state.

[0028] The state estimator 105 can be implemented in hardware or as a software program executed in a processor, either the same or a different processor from the controller 101, which at fixed or variable control period sampling intervals receives the outputs of the machine 103 and determines, using new and the previous output measurements, the estimated state 117 of the machine 101. The controller 101 can be implemented in hardware or as a software program executed in a processor, e.g., a microprocessor. An exemplar implementation of the controller 101 is described below in FIG. 1B.

[0029] FIG. 1B shows a block diagram of the controller 101, according to an embodiment of the present disclosure. The controller 101 includes a processor 119 and a memory 121. The processor 119 may be a single core processor, a multi-core processor, a computing cluster, or any number of other configurations. The memory 121 may include random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory systems. Additionally, in some embodiments, the memory 121 may be implemented using a hard drive, an optical drive, a thumb drive, an array of drives, or any combinations thereof.

[0030] The processor 119 may collect a feedback signal indicative of a current state of the operation of the machine 103. Further, the processor 119 formulates an original quadratic program (QP) for optimizing an objective function subject to constraints. The constraints may include equality constraints and inequality constraints on one or a combination of state and control variables of the machine 103 based on the task and the current state of the operation of the machine 103. A general form of the original QP is given as

[0031] In Equation (1), variables x are of dimension n i.e. the QP has n optimization variables. The objective function has a quadratic term and a linear term (q ^T x). Factor is included for reasons of consistency with literature and can also be absorbed within a matrix Q if necessary. The objective function is subject to linear equality constraints Ax = b where dimension of b is m, i.e. a number of equality constraints is m, and inequality constraints x ≥ 0 (i.e., nonnegative bounds are imposed on x).

[0032] The original QP may solved using methods such as, but not limited to, an interior point method, an active set method, an augmented Lagrangian method, and a conjugate gradient or gradient projection method. However, the original QP is difficult to solve due to its potential non-convexity and the constraints. To address such a problem, the original QP is reformulated into a different space and the reformulated QP is solved. For example, the augmented Lagrangian method solves Lagrangian dual of the quadratic program.

[0033] However, while the reformulation of the original QP may address some difficulties, another complication still exists, viz., the original QP may not have a feasible solution at all. The infeasibility can be caused by situations when the constraints defining different feasible sets do not intersect. For example, the original QP may be subject to equality and inequality constraints defining two feasible sets. When the two feasible sets do not intersect, the original QP is infeasible. [0034] FIG. 1C shows an example infeasible original QP, according to an embodiment of the present disclosure. The original QP may include two dimensions, i.e., x ₁ 123 and x ₂ 125. In other words, the original QP is two dimensional. In this case, constraints, e.g., inequality constraint x ₁ , x ₂ ≥ 0 and equality constraint x ₁ + x ₂ = — 1, do not intersect and thus no feasible point exists.

[0035] Some embodiments are based on the realization that additionally or alternatively to reformulating the original QP into a different space, it is possible to reformulate the constraints into a different space of higher dimensions to ensure that all possible sets defined by different constraints intersect at least at one point. The rationale here is that if an optimal solution of the original QP is found to be at that point, solution of the original QP is infeasible.

[0036] For example, in an embodiment, the processor 119 lifts the inequality constraints (e.g., x ₁ , x ₂ ≥ 0) and the equality constraints (e.g., x ₁ + x ₂ = — 1) into a lifted space 129 having a dimension higher than a dimension of an original space of the original QP by a lifting operation 127. For instance, the lifted space 129 has three dimensions, namely, x ₁ 123, x ₂ 125, and 131, whereas the original space of the original QP is two dimensional, i.e., x ₁ 123 and x ₂ 125. The lifting operation 127 introduces an additional non-negative variable such that a subspace defined by the equality constraint in the lifted space 129 intersects a subspace defined by the inequality constraint in the lifted space at least at a point of origin 129 of the lifted space 129. In such a manner, the infeasibility of the original QP can be detected when the solution of the QP in the lifted space 129 has the value of the additional non-negative variable equal to zero.

[0037] Different lifting operations can be used to transform the constraints from the original space into the lifted space 129 of higher dimensions. Examples of the lifting operations include multiplication of the constraints with one or multiple additional variables defining new dimensions, affine or non-affine transformations of the constraints, and the like.

[0038] Some embodiments select such a lifting operation that has a corresponding projection operation that reverses the effects of the lifting operation. For example, if the lifting operation 127 includes multiplication of values in the original space with the additional non-negative variable, the projecting operation includes dividing values in the lifted space 129 by the additional non-negative variable. Similarly, when the lifting operation 127 includes addition of values in the original space by the additional non-negative variable, the projecting operation includes subtraction of the additional non- negative variable from the values in the lifted space 129.

[0039] Some embodiments are based on the recognition that in order to use the constraints in the lifted space 129, there is a need to transform the original QP from the original space to the lifted space 129. However, the lifting operation 127 used for lifting the constraints is not directly applicable for lifting the objective function of the original QP since the objective function has quadratic terms and linear terms. Multiplying the quadratic terms by the additional non-negative variable results in an objective function that is a degree 3 polynomial and no longer a quadratic program. In other words, direct application of the lifting operation 127 to the original QP is not possible.

[0040] However, some embodiments are based on a realization that regardless of structure of the original QP lifted in the lifted space 129, a relationship between the optimal solution in the original space and the optimal solution in the lifted space 129 is governed by the lifting operation 127. Further, the optimal solutions, while unknown, should satisfy first-order optimality conditions. Moreover, the lifting operation 127 for the constraints, while not applicable to the QP objective function, is applicable to the first-order optimality conditions. Based on such a realization, the objective function of the original QP is transformed into a quadratic objective function as described below in FIG. 1D.

[0041] FIG. 1D illustrates the transformation of the objective function of the original QP into the quadratic objective function, according to an embodiment of the present disclosure. After lifting the constraints into the lifted space 129, the processor 119 transforms 133 an objective function 135 of the original QP into a quadratic objective function 137 involving variables of the original QP and the additional non-negative variable The quadratic objective function 137 subject to the lifted equality and inequality constraints 139 forms a homogeneous QP 141 in the lifted space 129 such that first-order optimality conditions 143 of the homogeneous QP 141 correspond to first-order optimality conditions 145 of the original QP lifted in the higher space by the lifting operation 127.

[0042] Further, the processor 119 solves the homogeneous QP 141 to produce a solution in the lifted space and, subsequently, controls the machine 103 based on the solution in the lifted space, as described below in FIG. 1E.

[0043] FIG. 1E shows a block diagram for solving the homogeneous QP 141 to produce the solution in the lifted space and controlling the machine 103 based on the solution in the lifted space, according to an embodiment of the present disclosure. At block 147, the processor 147 solves the homogeneous QP to produce a solution in the lifted space.

[0044] At block, 149 the processor determines if a value of the additional non-negative variable in the solution in the lifted space equals to zero. If the value of the additional non-negative variable in the solution in the lifted space equals to zero, then, at block 151, the processor 119 controls the machine 103 according to an infeasibility protocol. The infeasibility protocol can be to use an alternate method of controlling the machine ignoring some of the inequality constraints or relaxing the inequality constraints. One type of relaxing the inequality constraints may be to remove the nonnegativity bounds.

[0045] If the value of the additional non-negative variable in the solution in the lifted space is not equal to zero, then, at block 153, the processor 119 projects the solution in the lifted space 129 into the original space using a projection operation reversing the lifting operation, to produce a solution of the original QP. For example, if the equality constraints are lifted in the lifted space 129 by scaling the equality constraints with the additional non-negative variable, then the solution in the lifted space 129 is projected to the original space by dividing the solution in the lifted space with the additional non- negative variable.

[0046] At block 155, the processor 119 determines a control command based on the solution of the original QP. Further, at block 157, the processor 119 controls the machine 103 based on the control command determined based on the solution of the original QP.

[0047] The formulation of the original QP and the homogeneous QP 141 is mathematically described below.

Original QP

A general form of the original QP may be given as where y is of dimension n _y , a number of equality constraints A ^eq y = b ^eq is of dimension m ^eq , a number of inequality constraints b ^in,lb ≤ A ⁱⁿ y ≤ b ^in,ub is of dimension m ⁱⁿ , and lb, ub are n _y dimension lower and upper bounds on variable y.

[0048] The formulation in equation (1) is generic and can be obtained for example from the more general formulation in equation (2) by introducing additional variables as described in Equation (3) and Equation (4). The formulation in equation (2) is converted by adding additional variables for the constraints, so that the inequality constraints in equation (2) are converted to equality constraints, as where variables s ⁱⁿ are additional variables of dimension m ⁱⁿ . Equation (3) is a formulation with equality constraints and lower, upper bounds on the variables. New variables w ^l , w ^u each of dimension n _y + m ⁱⁿ and additional equality constraints are introduced as

[0049] The formulation in equation (4) has 2(n _y + m ⁱⁿ ) variables,

(m ^eq + m ⁱⁿ + n _y + m ⁱⁿ ) equality constraints and nonnegative bounds on all the variables. The variables and constraints in the original QP in equation (1) can be readily deduced from the formulation in equation (4), demonstrating that the original QP in equation (1) can be readily obtained from the general QP formulation in equation (2).

Homogeneous QP

[0050] Different embodiments use different formulations of the homogeneous QP. Any formulation of the homogeneous QP is valid as long as the first-order optimality conditions of the homogeneous QP correspond to the first-order optimality conditions of the original QP lifted in the higher space by the lifting operation.

[0051] However, some embodiments can impose additional rules on the formulation of the homogeneous QP for different computational and optimization reasons. For example, in one embodiment, the original QP is transformed such that the solution of the homogeneous QP in the lifted space is negative for positive values of the additional non-negative variable. This rule ensures that the optimal value in the lifted space for the feasible original QP problem does not have the value of the additional variable equal to zero.

[0052] Additionally or alternatively, some embodiments impose additional requirements on values of constants in the homogeneous QP. For example, in one embodiment, the homogeneous QP includes a quadratic term of the additional non-negative variable scaled with a scalar. The quadratic term of the additional non-negative variable is added to the original QP in order to ensure that the additional non-negative variable can take a positive value at an optimal solution of the homogeneous QP when the original QP is feasible.

[0053] FIG. 2 shows a block diagram 200 for determining the scalar of the quadratic term of the additional non-negative variable, according to an embodiment of the present disclosure. At block 201, the processor 119 determines a lower bound of an objective value at the solution of the original QP to ensure that the additional non-negative variable can take a positive value at an optimal solution of the homogeneous QP when the original QP is feasible. Further, at block 203, the processor 119 determines the scalar based on the lower bound. For example, in one embodiment, the scalar is a positive value greater than two times the negative of the lower bound. This is advantageous because it is sufficient to ensure that the additional non-negative variable will be positive at the optimal solution to the homogeneous QP. [0054] For example, in one embodiment, the homogeneous QP includes a quadratic term of the original QP, a linear term of the original QP scaled by the additional non-negative variable, a quadratic term of the additional nonnegative variable scaled by a scalar selected to be greater than two times the negative of the lower bound of the original QP and a negative linear term of the additional positive variable. This formulation of the homogeneous QP is advantageous because it is still quadratic, and hence the legacy methods for solving the original QP are applicable to solve the homogeneous QP. Also, this formulation ensures the correspondence of the lifted optimality conditions and has an optimal value for positive additional variables when the original QP is feasible. For example, the homogeneous QP may be given as where θ, κ > 0 are parameters. The equality constraints in the homogeneous QP are obtained by multiplying right hand side of the equality constraints in the original QP (1) with the additional non-negative variable The additional non-negative variable is a single additional variable. The linear term (q ^T x) in the objective function of the original QP is transformed to a quadratic term by multiplying it with The objective function in the homogeneous QP also includes a quadratic term in the additional non-negative variable T that is given by The objective function in the homogeneous QP also includes a linear term

[0055] In Equation (5), the multiplication of the right hand side of the equality constraint is termed the lifting of the equality constraint in the original QP to obtain the equality constraints in the lifted space of x and the additional non-negative variable A key property of the lifted equality constraint Ax = is that x = 0, is feasible for the lifted equality constraint and the nonnegativity constraints in the homogeneous QP. This ensures that the homogeneous QP is always feasible. Hence, an optimal solution of the homogeneous QP is readily obtained.

[0056] If the original QP is infeasible, then there does not exist a such that In this case, only points that are feasible in the homogeneous QP are the points where Thus, the infeasibility of the original QP can be determined if solving the homogeneous QP obtains an optimal solution with the additional non-negative variable equal to zero at the optimal solution.

[0057] If the original QP is feasible, then there exists an optimal solution x* of the original QP and satisfies the first-order optimality conditions where λ*, v* are Lagrange multipliers for the equality constraints and bounds in the original QP.

[0058] FIG. 3 shows a schematic of an original QP 301, first-order optimality conditions of the original QP 303, and infeasibility conditions of the original QP 305, according to an embodiment of the present disclosure. According to an embodiment, if the original QP 301 is feasible and x* solves the original QP, then there exists (x*, λ*, v*) satisfying the first-order optimality conditions of the original QP 303. If the original QP 301 is infeasible, then there exists (λ*, v*) satisfying the infeasibility conditions of the original QP 305.

[0059] Further, according to some embodiments, a point satisfies the first-order optimality conditions for the homogeneous QP if the following conditions are satisfied where ξº, ζ° are Lagrange multipliers for the lifted equality constraints and bound constraints on x in the homogeneous QP. The Lagrange multiplier ωº is for the nonnegativity on the additional non-negative variable.

[0060] The multiplication of the linear term in the objective function of the original QP by the additional non-negative variable to lift the linear term in the original QP to a quadratic term in the homogeneous QP ensures that the first condition in equation (7) is linear. This allows any solution (x*, λ*, v*) can now be lifted to such that it satisfies the first three conditions in equation (7). The homogeneous QP and the first-order optimality conditions of the homogeneous QP 401 are described below in FIG. 4.

[0061] FIG. 4 shows a schematic of a homogeneous QP 401 and first- order optimality conditions 403 of the homogeneous QP 401 , according to an embodiment of the present disclosure. According to some embodiments, if the original QP 301 is feasible and x* solves the original QP 301, then there exists satisfying first-order optimality conditions 403 of the homogeneous QP 401 with Further, satisfies the first-order optimality conditions of the original QP 303. According to some other embodiments, if the original QP 301 is infeasible, then there exists satisfying first-order optimality conditions 403 of the homogeneous QP 401 with xº = 0, Further, satisfies the infeasibility conditions of the original QP 305. [0062] In order to ensure that exists, parameter θ (also referred to as scalar) in the homogeneous QP 403 is chosen to satisfy θ + (x*) ^T Qx* + 2q ^T x* > 0. Equation (8)

[0063] Since x* is not known apriori, choose θ + 2LBObj > 0 where LBObj ≤ (x*) ^T Qx* + 2q ^T x* , i.e. LBObj is a lower bound on an objective value of the original QP.

[0064] In one embodiment, the lower bound on the objective value of the original QP is obtained by solving an equality constraint problem

[0065] The optimization problem in equation (9) is obtained from the original QP by ignoring the bound constraints. Thus, optimal solution to equation (9) is a lower bound to the original QP which is more constrained.

[0066] Some embodiments are based on realization the homogeneous QP (e.g., the homogeneous QP 401) may be solved using algorithms that are used to solve the original QP. To that end, the algorithms that solve the original QP can now be applied to the homogeneous QP to determine the solution of the homogeneous QP. As described, the solution of the homogeneous QP, which always exists, can then be used to determine if the original QP has an optimal solution or is infeasible. Let a point solve the homogeneous QP which always exists since the homogeneous QP is always feasible. If then the original QP can be declared to be infeasible. If then the solution to the original QP is obtained by the projection operation defined as In an embodiment, the projection operation transforms a solution of the first-order conditions of the homogeneous QP whenever the additional non-negative variable is positive, to satisfy the first-order conditions of the original QP. [0067] In an embodiment, an Interior Point Method (IPM) is employed to determine the solution of the homogeneous QP. The IPM that is used to solve the homogeneous QP is identical to the IPM that can be used for the original QP. The IPM aims to obtain a solution to the first-order stationary conditions in equation (7). Quantities are defined as where e represents a vector all ones of dimension n. Residual is defined as

[0068] FIG. 5 shows an IPM algorithm 500 for determining the solution of the homogeneous QP, according to an embodiment of the present disclosure. At step 501, is chosen such that and termination tolerance considered as ∈ > 0. At step 503, k and μ ⁰ are set as k =

0 and Further, an iterative procedure is conducted until

[0069] In an iteration of the iterative procedure, at step 505 a search direction d ^k is computed. At step 507, a step α ^k ∈ (0,1] is computed to move along the direction d ^k such that x ^k + [0070] At step 509, is set as Further, at step 511, k and μ ^k+1 are set as k = k + 1 and μ ^k+1 =

[0071] In one embodiment, m the direction d ^k is obtained by solving a linear system where Diag(a) is a diagonal matrix with elements of vector a on the diagonal.

[0072] Additionally, in an embodiment, Active-Set Method (ASM) is employed to determine the solution of the homogeneous QP. ASM proceeds by choosing a subset of bounds as being satisfied as equality. Using the chosen subset, an equality constrained QP is solved. If multipliers for chosen bound constraints that satisfy as equality are all nonnegative and the rest of the bound constraints are also satisfied, then an obtained solution is optimal. If not, constraints with negative multipliers are dropped and then infeasible constraints are added. In the following, an active set at a point is defined as

[0073] A working set at a point denoted as {1, ... , n + 1} such that the constraints Ax = b and x _i = 0 for i ∈ W is linearly independent. The Equality constraint QP (EQP) corresponding to active constraints in W is defined as

[0074] The solution to EQP(W) is denoted as x(W) and multiplier ξ (W) for equality constraints, bound multipliers ζ(W), ω(W).

[0075] FIG. 6 shows a schematic of the ASM 600, according to an embodiment of the present disclosure. At step 601, is chosen as and termination tolerance considered as ∈ > 0. At step 603, W ⁰ is chosen as and k is set as k = 0. Further, an iterative procedure is conducted. In an iteration of the iterative procedure, at step 605, EQP(W ^k ) is solved to obtain solution and multipliers for i ∈ W ^k . If any then at step 607 W ^k+1 is set as W ^k+1 = W ^k \ {i} for some , else if there exists the bound constraint is violated then at step 609 W ^k+1 is set as W ^k+1 = W ^k U {i} for such an i.

[0076] Additionally or alternatively, in an embodiment, Alternating Direction Method of Multipliers (ADMM) is employed to determine the solution of the homogeneous QP. The ADMM splits the solution of the homogeneous QP into two parts which are admittedly easier to solve and then alternates between the two while updating a multiplier that connects the two parts. There are several approaches for splitting the solution of the homogeneous QP. For example, in an embodiment, in which a first part of the two parts includes equality constrained program and a second part of the two parts is projection onto nonnegative orthant. The first part is

The second part is [0077] FIG. 7 shows a schematic of the ADMM 700 applied to the homogeneous QP, according to an embodiment of the present disclosure. At step 701, ^are chosen and termination criteria considered as ∈ > 0. Further, an iterative procedure is conducted. In an iteration of the iterative procedure, at step 703, ADMM-1 is solved to obtain x ^k+1 , T ^k+1 . At step 705, ADMM-2 is solved to obtain At step 707,

Multipliers are updated as then at step 709 the iteration is stopped, else, at step 711 the next iteration is initiated by setting k = k + 1. In one embodiment, parameter β is changed at every iteration.

[0078] Some embodiments are based on realization that, in addition to the original QP, Linear Conic Programs (LCP) can also be solved as the original QP is solved (as described in FIGS. 1C-1E). LCP are optimization problems with linear objective, linear equality constraints and conic constraints. In an embodiment, LCP is formulated as where is a pointed, convex cone which includes an origin. The cone can be one of nonnegative orthant, second-order cone, or semidefinite cone. LCP can be solved using proximal point method. Accordingly, the LCP is reformulated as where p > 0 is a parameter and x ^prox is also a parameter called as proximal point. [0079] Prox-LCP( x ^prox ) is an optimization problem to which homogenization techniques developed for the original QP can be applied. For instance, consider the following reformulation of Prox-LCP( x ^prox ) to Homogeneous Proximal-LCP (HProx-LCP(x ^prox )) given by where θ, κ > 0 are parameters and is an additional nonnegative variable. As in the HQP, the additional nonnegative variable is used to lift the equality to the higher dimension. The parameter θ is chosen So that θ + 2ObjLB(x ^prox ) > 0 Equation (12) where ObjLB(x ^prox ) is a lower bound estimate on the HProx-LCP(x ^prox ). Such a lower bound estimate can be obtained by solving equality constrained problem obtained after ignoring the conic constraints

[0080] LCP can be solved by an algorithm described below in FIG. 8. [0081] FIG. 8 shows an algorithm 800 for solving LCP, according to an embodiment of the present disclosure. At step 801, the algorithm 800 includes choosing x ^prox ' ⁰ , p > 0, K > 0. Further, an iterative procedure is conducted. In an iteration of the iterative procedure, at step 803, the parameter θ is computed using Equation (12) and (13) for x ^prox = x ^prox,k . At step 805, (HProx- LCP(x ^prox,k )) is solved to obtain an optimal solution If then LCP is infeasible, and the iteration is stopped at step 807. Further, at step

809, if then the optimal solution to LCP is and the iteration is stopped, else, at step 811 the next iteration is initiated by setting X ^prox,k+1 = x ^*,k and k = k + 1. [0082] In some implementations, the controller 101 is implemented as a model predictive controller (MPC). The MPC solves a constrained optimal control structured quadratic programming problem (OCP-QP) (e.g. equation (5)) in order to determine the control command at each control time step.

[0083] FIG. 9 shows a block diagram of the MPC for determining the control command, according to some embodiments of the present disclosure. The MPC is configured to solve a constrained optimal control structured quadratic programming problem (OCP-QP) in order to determine the control command, given the current state 117 of the operation of the machine 103 and the command 115. At block 901, an objective function, equality and inequality constraints are generated using the dynamical model and constraints of the machine 103. Some embodiments are based on a linear-quadratic objective function 905a, an initial state value condition 905b, a dynamical model of the machine that results in linear equality constraints 905c, linear inequality constraints 905d and, such that the OCP-QP needs to be solved at each control time step. The OCP-QP may be based on OCP-QP matrices 911 and OCP-QP vectors 913. Examples of the OCP-QP matrices 911 include Hessian matrices, e.g., Q _k , R _k and S _k and constraint Jacobian matrices, e.g., Examples of the OCP-QP vectors 913 include gradient vectors, e.g., q _k and r _k and constraint evaluation vectors, e.g., a _k and d _k .

[0084] In some embodiments, to solve the OCP-QP, exact or approximate state and/or control values over a prediction time horizon from the previous control time step are used as a solution guess in order to reduce the computational effort of solving the OCP-QP at the current control time step. Such a concept of computing a solution guess from the solution information at the previous control time step 310 is called warm-starting or hot-starting. To that end, at block 903, optimal control solution information of the previous control time step is read from memory (e.g., memory 121), and, at block 905, the OCP-QP is solved to determine a solution vector 907 that includes a sequence of control commands. At block 909, the solution vector 907 may be used to update and/or store the sequence of control commands for the next control time step.

[0085] FIG. 10A shows a schematic of a vehicle 1001 including the controller 101, according to some embodiments of the present disclosure. As used herein, the vehicle 1001 can be any type of wheeled vehicle, such as a passenger car, bus, or rover. Also, the vehicle 1001 can be an autonomous or semi-autonomous vehicle. For example, some embodiments control the motion of the vehicle 1001. Examples of the motion include lateral motion of the vehicle 1001 controlled by a steering system 1003 of the vehicle 1001. In one embodiment, the steering system 1003 is controlled by the controller 101. Additionally or alternatively, the steering system 1003 can be controlled by a driver of the vehicle 1001.

[0086] The vehicle 1001 can also include an engine 1006, which can be controlled by the controller 101 or by other components of the vehicle 1001. The vehicle can also include one or more sensors 1004 to sense the surrounding environment. Examples of the sensors 1004 include distance range finders, radars, lidars, and cameras. The vehicle 1001 can also include one or more sensors 1005 to sense its current motion quantities and internal status. Examples of the sensors 1005 include global positioning system (GPS), accelerometers, inertial measurement units, gyroscopes, shaft rotational sensors, torque sensors, deflection sensors, pressure sensor, and flow sensors. The sensors provide information to the controller 101. The vehicle can be equipped with a transceiver 1007 enabling communication capabilities of the controller 101 through wired or wireless communication channels.

[0087] FIG. 10B shows a schematic of interaction between the controller 101 and controllers 1020 of the vehicle 1001, according to some embodiments. For example, in some embodiments, the controllers 1020 of the vehicle 1001 are steering controller 1025 and brake/throttle controllers 1030 that control rotation and acceleration of the vehicle 1001. In such a case, the controller 101 outputs control commands to the controllers 1025 and 1030 to control a state of the vehicle 1001 such as acceleration, orientation, and the like, for controlling motion of the vehicle 1001. The controllers 1020 can also include high-level controllers, e.g., a lane-keeping assist controller 1035 that further process the control commands of the controller 101. In both cases, the controllers 1020 maps use the control commands of the controller 101 to control at least one actuator of the vehicle 1001, such as the steering wheel and/or the brakes of the vehicle 1001, in order to control the motion of the vehicle 1001.

[0088] FIG. 10C shows a schematic of an autonomous or semi- autonomous vehicle 1050 controlled by the controller 101, for which a dynamically feasible, and often optimal trajectory 1055 can be computed by using principles of some embodiments. The generated trajectory 1055 aims to keep the vehicle 1050 within particular road bounds 1052, and aims to avoid other uncontrolled vehicles, i.e., obstacles 1051 for the controlled vehicle 1050. In some embodiments, each of the obstacles 1051 can be represented by one or multiple inequality constraints in a time or space formulation of the original QP. The controlled vehicle 1050 can make decisions in real time such as, e.g., pass another vehicle on the left or on the right side or instead to stay behind another vehicle within the current lane of the road 1052.

[0089] FIG. 11A and FIG. 11B show a spacecraft 1102 equipped with a plurality of actuators such as thrusters 1150 and momentum exchange devices 1151, according to some embodiments of the present disclosure. Examples of the momentum exchange devices 1151 include reaction wheels (RWs) and gyroscopes. The spacecraft 1102 is a vehicle, vessel, or machine designed to fly in outer space whose operation changes quantities such as a position of the spacecraft, its velocities, and its attitude or orientation, in response to commands that are sent to the actuators. When commanded, the actuators impart forces on the spacecraft 1102 that increase or decrease the velocity of the spacecraft 1102 and thus cause the spacecraft 1102 to translate its position, and, when commanded, the actuators also impart torques on the spacecraft 1102, which cause the spacecraft 1102 to rotate and thereby change its attitude or orientation. As used herein, the operation of the spacecraft 1102 is determined by the operation of the actuators that determine a motion of the spacecraft 1102 that changes such quantities.

[0090] The spacecraft 1102 flies in outer space along an open or closed orbital path 1160 around, between, or near one or more gravitational bodies such as the Earth 1161, moon, and/or other celestial planets, stars, asteroids, comets. Usually, a desired or target position 1165 along the orbital path is given. A reference frame 1170 is attached to a desired position 1165, where origin of the reference frame, i.e., the all zeros coordinates in that reference frame are coordinates of the desired position 1165 at all times.

[0091] The spacecraft 1102 is subject to various disturbance forces 1114. The disturbance forces 1114 can include forces that were not accounted for when determining the orbital path 1160 for the spacecraft 1102. The disturbance forces act on the spacecraft 1102 to move the spacecraft 1102 away from the desired position 1165 on the orbital path 1160. These forces can include, but are not limited to, gravitational attraction, radiation pressure, atmospheric drag, non-spherical central bodies, and leaking propellant. Thus, the spacecraft 1102 can be at a distance 1167 away from the desired position 1165.

[0092] Because of the disturbance forces, it is not always possible to keep the spacecraft 1102 at the desired position 1165 along its orbit. As such, it is desired that the spacecraft 1102 instead remains within a window 1166 with specified dimensions 1164 around the desired position 1165. To that end, the spacecraft 1102 is controlled to move along any path 1180 that is contained within the window. In this example, the window 1166 has a rectangular shape, but the shape of the window can vary for different embodiments.

[0093] The spacecraft 1102 is also often required to maintain a desired orientation. For example, a spacecraft- fixed reference frame 1174 is required to be aligned with a desired reference frame such as an inertial reference frame 1171 that is fixed relative to distant stars 1172, or a reference frame 1173 that is always oriented in a manner that points towards the Earth 1161. However, depending on the shape of the spacecraft 1102, different disturbance forces 1114 can act non-uniformly on the spacecraft 1102, thereby generating disturbance torques, which cause the spacecraft 1102 to rotate away from its desired orientation. In order to compensate for the disturbance torques, the momentum exchange devices 1151 such as reaction wheels are used to absorb the disturbance torques, thus allowing the spacecraft 1102 to maintain its desired orientation. So that the momentum exchange devices 1151 do not saturate, and thereby lose the ability to compensate for the disturbance torques, their stored momentum must be unloaded, e.g., by reducing spin rates of the reaction wheels. Unloading the momentum exchange devices 1151 imparts an undesired torque on the spacecraft 1102. Such an undesired torque is also compensated for by the thrusters.

[0094] In some embodiments, the controller 101 is configured to determine control commands for the spacecraft 1102, based on the solution of the original QP, which causes the spacecraft 1102 to remain outside of a particular zone 1185 with specified dimensions, close to the desired position 1165 along the orbit 1160. The latter zone can be either fixed in time or it can be time varying and is often referred to as an exclusion zone 1185, for which the corresponding inequality constraints can be modeled within the original QP formulation. In this example, the exclusion zone 1185 has a rectangular shape, and it is positioned in a comer of the desired window 1166, but the shape and position of the exclusion zone within the desired target window can vary for different embodiments.

[0095] FIG. 12A shows a schematic of a vapor compression system 1200 controlled by a controller 101, according to some embodiments of the present disclosure. According to an embodiment, the controller 101 includes a predictive controller, such as a controller implementing a model predictive control (MPC). The controller 101 is communicatively coupled to the vapor compression system 1200. The vapor compression system (VCS) 1200 can include an indoor heat exchanger 1220 located in an indoor space or zone 1250, an outdoor unit heat exchanger 1230 located in an ambient environment, a compressor 1210 and an expansion valve 1240. A thermal load 1215 acts on the indoor space or zone 1250.

[0096] Additionally, the VCS 1200 can include a flow reversing valve 1255 that is used to direct high pressure refrigerant exiting compressor to either the outdoor unit heat exchanger 1230 or the indoor unit heat exchanger 1220, and direct low pressure refrigerant returning from either the indoor unit heat exchanger 1220 or the outdoor unit heat exchanger 1230 to inlet of the compressor. In the case where high pressure refrigerant is directed to the outdoor unit heat exchanger 1230, the outdoor unit heat exchanger 1230 acts as a condenser and the indoor unit acts as an evaporator, wherein the VCS 1200 rejects heat from the zone 1250 to the ambient environment, which is operationally referred to as “cooling mode.” Conversely, in the case where the high pressure refrigerant is directed to the indoor unit heat exchanger 1220, the indoor unit heat exchanger 1220 acts as a condenser and the outdoor unit heat exchanger 1230 acts as an evaporator, extracting heat from the ambient environment and pumping this heat into the zone 1250, which is operationally referred to as “heating mode.”

[0097] FIG. 12B shows an example of configuration of signals, sensors, and the controller 101 used in the VCS 1200, according to some embodiments of the present disclosure. The controller 101 reads information from sensors 1270 configured to measure various temperatures, pressures, flow rates or other information about the operation of the VCS 1200, including measurable disturbances such as ambient air temperature. The controller 101 can be provided with setpoints 1266 that represent desired values of measured signals of the process such as a desired zone temperature. The setpoints 1266 may be obtained from a thermostat, wireless remote control, or internal memory or storage media. The controller 101 then computes control commands such that some measured outputs are driven to their setpoints. The computed control commands can include an indoor unit fan speed 1280, an outdoor unit fan speed 1281, a compressor rotational speed 1282, an expansion valve position 1283, and a flow reversing valve position 1284. In this manner, the controller 101 controls operation of the VCS 1200 such that the setpoint values are achieved in presence of disturbances 1268, such as a thermal load, acting on the VCS 1200.

[0098] Some embodiments are based on the realization that the controller 101 can also be used to control a power system. For instance, the original QP solved by the controller 101 can be derived for power grid control. Optimal Power Flow (OPF) is crucial in power system operation and planning. OPF is widely used in planning problems, or to determine optimal generation schedules in active and reactive power at operational level that minimize operational system costs subject to grid constraints. In both domains, for planning and operation, it is crucial to determine tractable formulations of the OPF problems, as they are often intertemporal coupled in form of multi-period OPF problems. Linear OPF approximations that work in full decision variable space and capture power losses are employed in power grid operations.

[0099] According to an embodiment, the linear approximation problem for a power grid with i ∈ N buses in the power grid which are connected to generators and loads may be given by where is the active power at the bus i and Φ _i is voltage angle at the bus i. The P ^D are demands at the buses in power grid network. The equality constraints are voltage flow constraints. Final constraints are lower and upper bounds on the generator active powers.

[0100] The controller 101 determines a solution of the linear approximation problem. The solution of the linear approximation problem may include a value of the active power at the bus i.

[0101] FIG. 13 and FIG. 14 show a block diagram of an overall method 1300 for controlling an operation of a machine according to a task, according to an embodiment of the present disclosure. At block 1301, the method 1300 includes collecting a feedback signal indicative of a current state of the operation of the machine. At block 1303, the method 1300 includes formulating an original quadratic program (QP) for optimizing an objective function subject to subject to constraints. The constraints may include equality constraints and inequality constraints on one or a combination of state and control variables of the machine based on the task and the current state of the operation of the machine.

[0102] At block 1305, the method 1300 includes lifting the equality constraints and the inequality constraints into a lifted space having a dimension higher than a dimension of an original space of the original QP by a lifting operation. The lifting operation introduces an additional non-negative variable such that a subspace defined by the equality constraints in the lifted space intersects a subspace defined by the inequality constraints in the lifted space at least at a point of origin of the lifted space.

[0103] At block 1307, the method 1300 includes transforming the objective function of the original QP into a quadratic objective function involving variables of the original QP and the additional non-negative variable. The quadratic objective function subject to the lifted equality and inequality constraints forms a homogeneous QP in the lifted space such that first-order optimality conditions of the homogeneous QP correspond to first-order optimality conditions of the original QP lifted in the higher space by the lifting operation.

[0104] At block 1309, the method 1300 includes solving the homogeneous QP to produce a solution in the lifted space.

[0105] At block 1311, the method 1300 includes determining if a value of the additional non-negative variable in the solution in the lifted space equals to zero. If the value of the additional non-negative variable in the solution in the lifted space equals to zero, then, at block 1313, the method 1300 includes controlling the machine 103 according to an infeasibility protocol.

[0106] If the value of the additional non-negative variable in the solution in the lifted space is not equal to zero, then, at block 1315, the method 1300 includes projecting the solution in the lifted space into the original space using a projection operation reversing the lifting operation, to produce a solution of the original QP. For example, if the equality constraints are lifted in the lifted space by scaling the equality constraints with the additional non-negative variable, then the solution in the lifted space is projected to the original space by dividing the solution in the lifted space with the additional non-negative variable. [0107] At block 1317, the method 1300 includes determining a control command based on the solution of the original QP. Further, at block 1319, the method 1300 includes controlling the machine based on the control command determined based on the solution of the original QP.

[0108] The description provides exemplary embodiments only, and is not intended to limit the scope, applicability, or configuration of the disclosure. Rather, the following description of the exemplary embodiments will provide those skilled in the art with an enabling description for implementing one or more exemplary embodiments. Contemplated are various changes that may be made in the function and arrangement of elements without departing from the spirit and scope of the subject matter disclosed as set forth in the appended claims.

[0109] Specific details are given in the following description to provide a thorough understanding of the embodiments. However, understood by one of ordinary skill in the art can be that the embodiments may be practiced without these specific details. For example, systems, processes, and other elements in the subject matter disclosed may be shown as components in block diagram form in order not to obscure the embodiments in unnecessary detail. In other instances, well-known processes, structures, and techniques may be shown without unnecessary detail in order to avoid obscuring the embodiments. Further, like reference numbers and designations in the various drawings indicated like elements.

[0110] Also, individual embodiments may be described as a process which is depicted as a flowchart, a flow diagram, a data flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. In addition, the order of the operations may be rearranged. A process may be terminated when its operations are completed but may have additional steps not discussed or included in a figure. Furthermore, not all operations in any particularly described process may occur in all embodiments. A process may correspond to a method, a function, a procedure, a subroutine, a subprogram, etc. When a process corresponds to a function, the function’s termination can correspond to a return of the function to the calling function or the main function.

[0111] Furthermore, embodiments of the subject matter disclosed may be implemented, at least in part, either manually or automatically. Manual or automatic implementations may be executed, or at least assisted, through the use of machines, hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine readable medium. A processor(s) may perform the necessary tasks.

[0112] Various methods or processes outlined herein may be coded as software that is executable on one or more processors that employ any one of a variety of operating systems or platforms. Additionally, such software may be written using any of a number of suitable programming languages and/or programming or scripting tools, and also may be compiled as executable machine language code or intermediate code that is executed on a framework or virtual machine. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.

[0113] Embodiments of the present disclosure may be embodied as a method, of which an example has been provided. The acts performed as part of the method may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in an order different than illustrated, which may include performing some acts concurrently, even though shown as sequential acts in illustrative embodiments. [0114] Further, embodiments of the present disclosure and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Further some embodiments of the present disclosure can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of, data processing apparatus. Further still, program instructions can be encoded on an artificially generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, which is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them.

[0115] According to embodiments of the present disclosure the term “data processing apparatus” can encompass all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

[0116] A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub programs, or portions of code.

[0117] A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, and any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data.

[0118] Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB) flash drive, to name just a few. [0119] To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g,, a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.

[0120] Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

[0121] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a clientserver relationship to each other.

[0122] Although the present disclosure has been described with reference to certain preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the present disclosure. Therefore, it is the aspect of the append claims to cover all such variations and modifications as come within the true spirit and scope of the present disclosure.