Tuesday, April 25, 2006

The benefit 'Dummy'

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.

1 comment:

Anonymous said...

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.