MATLAB: How to use quadprog to handle soft constraints

boundsconstraintshardoptimizationOptimization Toolboxsoft

How can soft constraints of the form
   Ax <= b
be handled using "quadprog"?
Soft constraints correspond to some variable values that are penalized in the objective function if the constraints on the variables are not satisfied.

Best Answer

The following is a possible workaround for implementing soft constraints.
We have an objective function
     min 0.5 x'Hx + f'x (1)
with linear constraints in the form:
      A*x <= b (2)
In this form the constraints are hard constraints because vector "x" must satisfy the inequality. If we introduce the slack variable "y>=0", rewrite the inequality constraint as
     A*x - y <= b (3)
and penalize "y" in the objective function as
     min 0.5 (x'Hx + y'Ry) (4)
then the constraint (2) in the form (3) becomes a soft constraint.
If "x" exists that satisfies (2) then optimal value of "y" in (3) will be 0. In case there is no "x" that satisfies (2), then the optimal value of "y" will not be zero but will be smallest to satisfy (3).
Starting with "H, f, A, b, x" values corresponding to (1) and (2), we can define the following variables to solve for (3) and (4):
1. Goal is to find the values for a new optimization variable "X" which is defined as:
      X = [x; y]; % we are appending the new variable "y" at the end of the original variable "x"
2. Define new "H1" matrix as:
      H1 = blkdiag(H, R*ones(size(b, 1))); % we are adding a minimization term of y'Ry by extending the original H matrix
3. Define new "f1" vector as:
      f1 = [f; zeros(size(b, 1), 1)]; % the linear part of the objective function remains the same
4. Define new "A1" matrix as:
      A1 = [[A -ones(size(A, 1), size(b, 1))]; [zeros(size(b, 1), size(x,1)) - eye(size(b,1))]]; 
      % this corresponds to converting the hard constraints "Ax <= b" to soft constraints "Ax-y <= b"
      % also adds the constraints " y >= 0"  in the form of " - y <= 0"
5. The "b" variable remains unchanged.
6. Finally, the new optimization problem is to execute:
      X = quadprog(H1, f1, A1, b);
and we will receive both "x" and "y" values in "X".
Note that similar formulations can also be implemented to incorporate soft* *constraints in other optimization problems as well using different MATLAB optimization functions.
Related Question