Equivalent Reformulations

0

In this lecture, we talk about equivalent reformulations, that are reformulations done on the initial problem of the form

(1)

A very interesting question is the following. Assume we got two problems and that are equivalent problems. Are their duals, (hereby denoted by and , respectively) the same ? The given lecture gives many examples to show that in many cases, it happens that the dual problems could be very different. We will discuss three main types of equivalent reformulations that are

• Introducing new variables to the problem
• Transforming the cost into another proportional cost (i.e. an increasing function of the cost)
• Absorbing constraints into the domain of the cost, a.k.a. implicit constraints.

Introducing New Variables

We start our lecture by talking about introducing auxiliary variables to the main problem. Assume the following unconstrained minimization problem

(2)

A very easy achieved equivalent problem is to replace by and impose as a new constraint to the problem, namely

(3)

To get the dual problems, we first need the Lagrangian dual functions. For problem (1), the dual problem is clearly

(4)

where is the optimal value of . However, the dual problem of is achieved by first computing the Lagrangian function that is

(5)

Next, we have to pass through the Lagrangian dual function that is

(6)

The term is clearly in the general case except for the more interesting case when , in which case the infimum becomes 0, so the above reads

(7)

where is the conjugate function of . Finally the dual becomes

(8)

Indeed, and are very different. The lecture deals with two applications of the above concept by considering two different forms of , that are : and .

Cost Transformation

The second type of reformulation is by simply transforming the cost, i.e. instead of maximizing , you maximize , or more generally speaking, you can maximize where is an increasing function of . Let me show you an example, where we have the following unconstrained minimization problem

(9)

The dual problem of the above is

(10)

where is the optimal value of . Now consider the transformed cost problem as

(11)

The Lagrangian of the above problem is

(12)

Now let’s compute the Lagrange dual problem as

(13)

As previously we can say that

(14)

where we will be interested in the case where , otherwise there’s nothing to optimize. So,

(15)

where is the dual norm of . Finally, the dual problem is

(16)

which is very different from .

Constraint Absorption

The last type of reformulation we discuss is by absorbing constraints to the cost, or more formally speaking, thru implicit constraints. Let’s see an example

(17)

which is the same as

(18)

The Lagrangian of the above problem is

(19)

where

(20)

Now computing the Lagrangian dual function as

(21)

where

(22)

As previously, we will be interested in the case where , hence

(23)

Finally the dual problem here is

(24)

Now let us absorb the “box” constraints in the cost of as

(25)

where

(26)

The Lagrangian function above is

(27)

where we show in the lecture why

and hence the dual problem becomes the following unconstrained maximization problem

which is very different from