Method for solving quadratic programs for convex sets with linear equalities by an alternating direction method of multipliers with optimized step sizes

A method for controlling a machine by solving a convex quadratic program (QP) for a convex set, wherein constraints of the QP include a set linear equalities and a set of linear inequalities, wherein the solving uses an Alternating Direction Method of Multipliers (ADMM), wherein variables of the convex QP include a linear subspace constrained variable vector and a set constrained variable vector indicating desired behavior of the machine, comprising iterative steps:

• solving, using a processor, the linear subspace constrained variable vector while keeping the set constrained variable vector fixed using an optimal step size and a Lagrangian multiplier;
• solving, using the processor, the set of constrained variable vector while keeping the linear subspace constrained variable vector fixed using the optimal step size and the Lagrangian multiplier, wherein the solving for the set constrained variable vector minimizes a Lagrangian augmented quadratic objective function depending on the Lagrange multiplier and the linear subspace constrained variable vector subject to the set of linear equality constraints and the set of inequality constraints;
• updating the Lagrangian multiplier;
• repeating for a next iteration until either a termination condition for a feasible solution is satisfied or a termination condition for an infeasible solution is satisfied to produce a QP solution including one or combination of values of the linear subspace constrained variable vector and the set of constrained variable vector;
• and
• controlling the machine using the QP solution.

A method for controlling a machine by solving a convex quadratic program (QP) for a convex set, wherein constraints of the QP include a set linear equalities and a set of linear inequalities, wherein the solving uses an Alternating Direction Method of Multipliers (ADMM), wherein variables of the convex QP include a linear subspace constrained variable vector and a set constrained variable vector indicating desired behavior of the machine, comprising iterative steps:

• solving, using a processor, the linear subspace constrained variable vector while keeping the set constrained variable vector fixed using an optimal step size and a Lagrangian multiplier;
• solving, using the processor, the set of constrained variable vector while keeping the linear subspace constrained variable vector fixed using the optimal step size and the Lagrangian multiplier;
• updating the Lagrangian multiplier;
• repeating for a next iteration until either a termination condition for a feasible solution is satisfied or a termination condition for an infeasible solution is satisfied to produce a QP solution including one or combination of values of the linear subspace constrained variable vector and the set of constrained variable vector, wherein the termination condition for infeasible solution satisfies a tolerance greater than zero of a maximum of a normed change in set constrained variable vector from a current value to a value at a previous iteration, a normed change in the linear subspace constrained variable vector from a current value to a value at a previous iteration, a normed change in the Lagrange multiplier variable from a current value to a value at a previous iteration along the null space of the equality constraints and deviation from 0 of the angle between the Lagrange multiplier and the vector resulting from a difference of the linear subspace constrained variable vector and set constrained variable vector at the current value, and a difference of the linear subspace constrained variable vector and set constrained variable vector at the current value have element-wise a same sign as the Lagrange multiplier;
• and
• controlling the machine using the QP solution.

A method for controlling a machine by solving a convex quadratic program (QP) for a convex set, wherein constraints of the QP include a set linear equalities and a set of linear inequalities, wherein the solving uses an Alternating Direction Method of Multipliers (ADMM), wherein variables of the convex QP include a linear subspace constrained variable vector and a set constrained variable vector indicating desired behavior of the machine, comprising iterative steps:

• solving, using a processor, the linear subspace constrained variable vector while keeping the set constrained variable vector fixed using an optimal step size and a Lagrangian multiplier;
• solving, using the processor, the set of constrained variable vector while keeping the linear subspace constrained variable vector fixed using the optimal step size and the Lagrangian multiplier, wherein the QP is for a model predictive controller, wherein the solving comprises:
• solving the QP, wherein variables include a linear subspace constrained variable vector of system states, controls, and, optionally, outputs and constrained outputs along a prediction interval, and a set constrained auxiliary variable vector of a same size as the linear subspace constrained variable vector, wherein the linear subspace constraints are equations of prediction model dynamics along the prediction interval, and the set constraints are the upper and lower bounds on the system states, controls, and, optionally, the output and the constrained outputs along the prediction interval;
• updating the Lagrangian multiplier;
• repeating for a next iteration until either a termination condition for a feasible solution is satisfied or a termination condition for an infeasible solution is satisfied to produce a QP solution including one or combination of values of the linear subspace constrained variable vector and the set of constrained variable vector;
• and
• controlling the machine using the QP solution.

A method for controlling a machine by solving a convex quadratic program (QP) for a convex set, wherein constraints of the QP include a set linear equalities and a set of linear inequalities, wherein the solving uses an Alternating Direction Method of Multipliers (ADMM), wherein variables of the convex QP include a linear subspace constrained variable vector and a set constrained variable vector indicating desired behavior of the machine, comprising iterative steps:

• solving, using a processor, the linear subspace constrained variable vector while keeping the set constrained variable vector fixed using an optimal step size and a Lagrangian multiplier;
• solving, using the processor, the set of constrained variable vector while keeping the linear subspace constrained variable vector fixed using the optimal step size and the Lagrangian multiplier, wherein the QP is for machine learning with a support vector machine, the solving comprising:
• solving the QP, wherein variables include a linear subspace constrained variable of a size of a normal vector for a hyperplane separating samples and slack variables for margin constraints wherein the linear subspace constraints are the margin constraints augmented by the slack variables, and a set constrained variable vector has a same size as the hyperplane and the slack variables, and wherein the normal vector is unconstrained, and the slack variables are constrained to be nonnegative;
• updating the Lagrangian multiplier;
• repeating for a next iteration until either a termination condition for a feasible solution is satisfied or a termination condition for an infeasible solution is satisfied to produce a QP solution including one or combination of values of the linear subspace constrained variable vector and the set of constrained variable vector;
• and
• controlling the machine using the QP solution.

A method for controlling a machine by solving a convex quadratic program (QP) for a convex set, wherein constraints of the QP include a set linear equalities and a set of linear inequalities, wherein the solving uses an Alternating Direction Method of Multipliers (ADMM), wherein variables of the convex QP include a linear subspace constrained variable vector and a set constrained variable vector indicating desired behavior of the machine, comprising iterative steps:

• solving, using a processor, the linear subspace constrained variable vector while keeping the set constrained variable vector fixed using an optimal step size and a Lagrangian multiplier;
• solving, using the processor, the set of constrained variable vector while keeping the linear subspace constrained variable vector fixed using the optimal step size and the Lagrangian multiplier, wherein the QP is for compressive sensing, the solving comprising:
• solving, using the processor, the QP wherein variables include the linear subspace constrained variable vector of a size of a signal vector that is to be determined, wherein the linear subspace constrained variable vector includes measurements constraints, and a set constrained variable vector of the same size as the signal vector, wherein the linear subspace constrained variable vector constrains the linear subspace constrained variable by applying a shrinkage operator;
• updating the Lagrangian multiplier;
• repeating for a next iteration until either a termination condition for a feasible solution is satisfied or a termination condition for an infeasible solution is satisfied to produce a QP solution including one or combination of values of the linear subspace constrained variable vector and the set of constrained variable vector;
• and
• controlling the machine using the QP solution.