Formulating and solving a Linear/Quadratic Mixed Constraint Problem for a Single Variable using ADMM

116 Views Asked by At

I've recently come across an optimization problem of the form (in matlab, [] indicating a matrix):

Minimize: f(x)

f(x)=sum(x) or sum(x.^2)

Under the constraints:

  1. [C+]*x>=d+
  2. [C-]*x<=d-
  3. A*x=b

While there are different ways to solve this type of problem, I would like to use ADMM. I am new to optimization and have been following this guide to a similar problem: https://towardsdatascience.com/an-admm-newton-method-for-inequality-constrained-optimization-37a470c58a5c

In block matrix form (and matlab notation), I have formulated the problem as:

let: A'=[C+;C-;A]
In my case: A'=[I;-I;A]

let: s'=[s+;s-;0] Where s+ and s- are slack variables for the inequality constraints

let: c=[d+;d-;b]

Together, the constraints are:

[A']*x-s'-c=0


In keeping with the hyperlink above, I am performing ADMM using the scaled formulation of ADMM using the vector u as a scaled lagrange multiplier.

Taken from the source linked above, here are the update equations I am following:

Equations (Don't have enough reputation to link picture directly)

With the exception that I am utilizing: [A']*x-s' in place of [A]*x in the image above


I have adapted the problem into an algorithm in Matlab, but the algorithm only appears to find a solution that is bound by the inequality constraints, but fails to be bound to [A]*x=b

As far as I can tell, having 0 at the tail of s' should guarantee that [A]*x=b, yet the algorithm seems to ignore the constraint entirely. Is there an additional update step for equality conditions in ADMM?

I, like the link, am using a Newton solver to identify minimums, both by line-search and by single-step Newton-step, and confirm it is working properly.


In conclusion, I would like to know:

  1. If this formulation is a valid one for ADMM?
  2. If there are additional steps required to simultaneously solve a problem that has both equality and inequality constraints?

I apologize for the somewhat strange formatting of this question. I'm not sure how to stop the editor from removing the formatting whitespace.

I can provide the matlab code if this would help as well.