What is the objective function in optimization?

[flyingpig]

http://web.mit.edu/15.053/www/AMP-Chapter-04.pdf

Go to page 8/45

Where it tackles on the case of y being an unrestricted variable. They have the following

$$y_i = y_i^+ - y_i^-$$

WHat do the plus and minus thing mean? It says they are both positive in page 9/45.

Thank you

 

[Mark44]

I don't think it means anything other than as a way to distinguish two sets with m variables, all using essentially the same name.

IOW, y₁⁺, y₂⁺, ..., y_m⁺ are the dual variables associated with the first m constraints, while y₁^-, y₂^-, ..., y_m^- are the dual variables associated with the second m constraints.

 

[flyingpig]

My prof said something about representing their absolute values, but it doesn't make sense to have subtraction

 

[awkward]

A common usage is

$$x^+ = \begin{cases} x &\text{if } x \ge 0\\ 0 &\text{otherwise} \end{cases}$$

$$x^- = \begin{cases} -x &\text{if } x \le 0\\ 0 &\text{otherwise} \end{cases}$$

 

[flyingpig]

So if x => 0, then x^+ is x and x^-1 = 0

So x^+ - 0 = x^+

If x <=0, then x^- = -x and x^+ = 0

0 - (-x) = x, but x<=0, so that doesn't work

 

[awkward]

Flyingpig,

I don't understand what you mean by "doesn't work".

$$x = x^+ - x^-$$

in all cases. You just showed that.

 

[flyingpig]

No but x can't be negative. I just showed in

0 - (-x) = x, but x <=0,

 

[Pyrrhus]

It depends on the context. For the LP, especially if you are using Simplex or another method that requires the decision variables to be positive, it is a way of allowing a variable that can also be negative.

$$\sum_{i}^{m} b_{i} y_{i} = \sum_{i}^{m} b_{i} y^{+}_{i} - \sum_{i}^{m} b_{i} y^{-}_{i}$$

So now $y_{i}$ is unrestricted.

 

[flyingpig]

Why can't you do addition?

 

[Pyrrhus]

Why can't you do addition?

You have $y_{i}$ by the algorithm is required that $y_{i} \geq 0 \forall i$, but for your problem $y_{i}$ is unrestricted, so you can write that as the difference of two other variables that are nonpositive.

 

[flyingpig]

$$x^+ = \begin{cases} x &\text{if } x \ge 0\\ 0 &\text{otherwise} \end{cases}$$

$$x^- = \begin{cases} -x &\text{if } x \le 0\\ 0 &\text{otherwise} \end{cases}$$

But this inequality says otherwise and I showed it that y can be negative

So if x => 0, then x^+ is x and x^-1 = 0

So x^+ - 0 = x^+

If x <=0, then x^- = -x and x^+ = 0

0 - (-x) = x, but x<=0, so that doesn't work

 

[Pyrrhus]

But this inequality says otherwise and I showed it that y can be negative

This is not right, you are simply replacing a decision variable with 2 other decision variables where the relation is $y = y^{+} - y^{-}$.

There is no relation that when $y > 0 \rightarrow y^{+} = y$ That is wrong. Y is unrestricted and will take a positive sign only when $y^{+} > y^{-}$ and negative only when $y^{+} < y^{-}$. Also, $y^{+} \geq 0$ and $y^{-} \geq 0$ by the assumptions of the problem.

Awkward wrote another convention for the + that is unrelated to your LP problem. I am surprised you did not notice this?. Another convention for + is $(t -a)^{+} = Max(t-a,0)$.

 

[awkward]

No but x can't be negative. I just showed in

0 - (-x) = x, but x <=0,

Yes, you showed $$x^+ - x^-$$ is equal to x when x is positive or zero, and it's equal to x when x is negative. So it's equal to x in all cases.

That's the point.

 

[flyingpig]

Yes, you showed $$x^+ - x^-$$ is equal to x when x is positive or zero, and it's equal to x when x is negative. So it's equal to x in all cases.

That's the point.

But what a Standard Form LOP, we want x > 0

 

[flyingpig]

A common usage is

$$x^+ = \begin{cases} x &\text{if } x \ge 0\\ 0 &\text{otherwise} \end{cases}$$

$$x^- = \begin{cases} -x &\text{if } x \le 0\\ 0 &\text{otherwise} \end{cases}$$

Oh wait...

If x happens to even contradict one of these conditons

$$x = x^+$$
$$x = x^-$$

Because the other one becomes 0! But that still doesn't explain the preference for subtraction over addition.

Here take this one for instance

Max

$$z = 5x_1 + 4x_2 + 3x_3$$

s.t
$$3x_1 + 3x_2 + x_3 \leq 5$$
$$4x_1 + 6x_2 + 3x_3 \geq 2$$
$$x_1 + 2x_3 = 4$$

$$x_1, x_2, \geq 0$$

So for that annoying x_3 constraints I get (by putting this in Standard Form)

$$3x_1 + 3x_2 + (x_3 ^+ + x_3^-) \leq 5$$
$$-4x_1 - 6x_2 - 3(x_3 ^+ + x_3^-) \leq -2$$
$$x_1 + 2(x_3 ^+ + x_3^-) \leq -4$$
$$-x_1 - 2(x_3^+ + x_3^-) \geq 4$$
$$x_3 = x_3 ^+ - x_3 ^-$$

 

[Pyrrhus]

flyingpig, do you even read what I've said?

Go back to your book and read about the inclusion of unrestricted decision variables in a linear program, and also re-read Simplex then come back for questions again. You've not grasped anything I've said.

What part of this you don't understand? BOTH ARE NONNEGATIVE by the assumption in the LP!.

Y is unrestricted and will take a positive sign only when $y^{+} > y^{-}$ and negative only when $y^{+} < y^{-}$. Also, $y^{+} \geq 0$ and $y^{-} \geq 0$ by the assumptions of the problem.

 

[flyingpig]

flyingpig, do you even read what I've said?

Go back to your book and read about the inclusion of unrestricted decision variables in a linear program, and also re-read Simplex then come back for questions again. You've not grasped anything I've said.

Our book doesn't talk about special examples and yes I have read everyone else is saying, but it may not have gotten through my head. I am sorry, I am slow.

What part of this you don't understand? BOTH ARE NONNEGATIVE by the assumption in the LP!.

Y is unrestricted and will take a positive sign only when $y^{+} > y^{-}$ and negative only when $y^{+} < y^{-}$. Also, $y^{+} \geq 0$ and $y^{-} \geq 0$ by the assumptions of the problem.

Exactly, y can be negative. In the case of $$y^+ < y^-$$, this is not the goal of maxing LOP (most of the time).

 

[Pyrrhus]

LOP? you mean the objective function? The goal of Max the objective function is to obtain the highest value within the constraint set.