Today's nonlinear class, I learned a trick by creating dummy variables and constrains to decompose the problem.
The original problem is
min f_1(x) - f_2(x)
st. x \in X_1 \cap X_2
Then we can transform it to
min f_1(y) - f_2(z)
st. y = z
y \in X_1 and z \in X_2
Then we can write the dual of transformed problem and do the decomposition.
Suppose f_1 and f_2 is convex.
We imagine the geometric meaning, for each Lagrange vector for the constrain y = z. We can find the corresponding tangent lines of the f_1 and -f_2. If their x happens to be the same, then we done. Otherwise we update Lagrange vectors. The way to update Lagrange vector is based on sign of difference of two tangent points.
Subscribe to:
Post Comments (Atom)
1 comment:
This is very similar to a technique from IP called Lagrangian Decomposition (also sometimes called Variable Splitting). There are some interesting theoretical results about it; see Cornuejols, Sridharan, and Thizy, EJOR, 1991 and Guignard and Kim, Math Programming, 1987.
Post a Comment