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}<br /> x &amp;\text{if } x \ge 0\\<br /> 0 &amp;\text{otherwise}<br /> \end{cases}

x^- = \begin{cases}<br /> -x &amp;\text{if } x \le 0\\<br /> 0 &amp;\text{otherwise}<br /> \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}<br /> x &amp;\text{if } x \ge 0\\<br /> 0 &amp;\text{otherwise}<br /> \end{cases}

x^- = \begin{cases}<br /> -x &amp;\text{if } x \le 0\\<br /> 0 &amp;\text{otherwise}<br /> \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 &gt; 0 \rightarrow y^{+} = y That is wrong. Y is unrestricted and will take a positive sign only when y^{+} &gt; y^{-} and negative only when y^{+} &lt; 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}<br /> x &amp;\text{if } x \ge 0\\<br /> 0 &amp;\text{otherwise}<br /> \end{cases}

x^- = \begin{cases}<br /> -x &amp;\text{if } x \le 0\\<br /> 0 &amp;\text{otherwise}<br /> \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^{+} &gt; y^{-} and negative only when y^{+} &lt; 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^{+} &gt; y^{-} and negative only when y^{+} &lt; 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^+ &lt; 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.