Support NeoGAF

[Kieli]

Hey guys, I'm back with a proof of the Strong Duality Theorem. I understand everything BUT the following sentence:

Let "y sub 0" be a vector of size m x 1. Let the transpose of "y sub 0" be a candidate optimal solution for the dual problem of some primal.

Thus, the transpose of "y sub 0" = (C sub b)^T (B)^-1 where "C sub b" represents a m x 1 matrix consisting of the coefficients of the basic variables (for this dictionary) and where B is the submatrix of the matrix A consisting of the columns of A that correspond to a basic variable (i.e. if x sub 3 is a basic variable, then the third column of A is part of B).

This line, I do not get: transpose of "y sub 0" = (C sub b)^T (B)^-1. Like, where did it come from? My prof randomly says that the candidate solution equals this, but how does he know that?

 

[Kieli]

As well, I have written in the notes the following line:

The optimal solution for the dual problem is simply the negative of the coefficients of z (the objective function) of the primal optimal dictionary.

However, the professor wrote an example of a linear program with 3 variables and 3 constraints (therefore it also has 3 slack variables).

Say the objective function for the optimal primal dictionary is z = 20 - 2x_1 - 4x_3 - 6 x_5.

Why isn't the dual optimal solution then [2 4 6]? Apparently the dual solution is negative of the coefficients of the slack variable (for the original primal). What the heck?

 

[Ultryx]

I'd like some precalculus help if someone would like to offer assistance. I'll forewarn you that mathematics is my single worst subject. You really have to talk to me like I'm five and assume I know nothing.

An open rectangular box is to be made from a piece of cardboard 26 inches wide and 26 inches long by cutting a square from each corner and bending up the sides.

(a) Express the volume V of the box as a function of the size x of the cutout.

V(x)=x(26-2x)^2 (in^3)

I got this part, but I don't know how to solve this second part here.

(b) Approximate the dimensions of the box with the largest volume (round your answers to one decimal place).

height= _______ in
width= _______ in
length= _______ in

 

[Kazerei]

So you've learned all about derivatives and optimization, yes? Volume is a function of x, and you want to find x where the volume is maximized. So take the derivative of V(x), set it equal to zero, and solve for x. Note that you'll get two possible values for x, one is a local maximum, the other is a local minimum.

 

[Ultryx]

So you've learned all about derivatives and optimization, yes? Volume is a function of x, and you want to find x where the volume is maximized. So take the derivative of V(x), set it equal to zero, and solve for x. Note that you'll get two possible values for x, one is a local maximum, the other is a local minimum.

I have no idea what a derivative is. This is like the final "testing problem" on my assignment and the assignment has nothing like this on it so I'm really confused. Same person said that on another place I asked and I just don't know.

 

[Kieli]

So, you're given an optimal dictionary and you want to get to the original LP that generated it.

Would you use the special "formulas"

x_b = (B^-1)b - (B^-1)(N)x_n
z = (c_b)(B^-1)b + (c_n - (c_b)(B^-1)(N))x_n to get back to the original linear program?

 

[Kieli]

So you've learned all about derivatives and optimization, yes? Volume is a function of x, and you want to find x where the volume is maximized. So take the derivative of V(x), set it equal to zero, and solve for x. Note that you'll get two possible values for x, one is a local maximum, the other is a local minimum.

He doesn't need to take a derivative (he's doing pre-calc...). He just needs to find a constraint for the problem and plug it into the volume equation. The constraint comes from the quantity of materials.

The volume function, itself, is simply V = width * height * length.

 

[Kazerei]

I have no idea what a derivative is. This is like the final "testing problem" on my assignment and the assignment has nothing like this on it so I'm really confused. Same person said that on another place I asked and I just don't know.

Hmm, interesting. What else have you learned in this class, or what are the other problems on this assignment? Perhaps you are expected to graph the function?

He doesn't need to take a derivative (he's doing pre-calc...). He just needs to find a constraint for the problem and plug it into the volume equation. The constraint comes from the quantity of materials.

The volume function, itself, is simply V = width * height * length.

Huh, I've totally forgotten what pre-calc was like. It looks like a very standard optimization problem where you take the derivative and find the zeroes.

 

[Tawpgun]

Is there anyway to memorize the trig integrals and derivatives?

 

[Ultryx]

He doesn't need to take a derivative (he's doing pre-calc...). He just needs to find a constraint for the problem and plug it into the volume equation. The constraint comes from the quantity of materials.

The volume function, itself, is simply V = width * height * length.

I know the answer will contain two of the same answers and one different one.

So, you're given an optimal dictionary and you want to get to the original LP that generated it.

Would you use the special "formulas"

x_b = (B^-1)b - (B^-1)(N)x_n
z = (c_b)(B^-1)b + (c_n - (c_b)(B^-1)(N))x_n to get back to the original linear program?

I'll have to check this out!

Hmm, interesting. What else have you learned in this class, or what are the other problems on this assignment? Perhaps you are expected to graph the function?

Lots of stuff, but it's only week 3 of class.

 

[Kieli]

I'll have to check this out!

Wait, you're taking linear programming? It's an upper-year/graduate Math course. How did you take this without taking calculus, lol?

 

[Kieli]

Is there anyway to memorize the trig integrals and derivatives?

Unfortunately, you'll have to rote-memorize the standard derivatives and the standard trig integrals.

You can always make up mnemonics if they help, though, "Low d-high minus high-d low, square the bottom and there you go" for the quotient rule (where low d-high means denominator multipled by derivative of numerator).

 

[simplayer]

I'll have to check this out!

He was just talking out loud to himself about his own problem, not yours. ;p

 

[Ultryx]

Wait, you're taking linear programming? It's an upper-year/graduate Math course. How did you take this without taking calculus, lol?

I thought you were referring to me! Sorry! Haha.

 

[leroidys]

As well, I have written in the notes the following line:

The optimal solution for the dual problem is simply the negative of the coefficients of z (the objective function) of the primal optimal dictionary.

However, the professor wrote an example of a linear program with 3 variables and 3 constraints (therefore it also has 3 slack variables).

Say the objective function for the optimal primal dictionary is z = 20 - 2x_1 - 4x_3 - 6 x_5.

Why isn't the dual optimal solution then [2 4 6]? Apparently the dual solution is negative of the coefficients of the slack variable (for the original primal). What the heck?

One or more optimal solutions corresponds to b^T in the dual, but may be any 3 vectors that are the optimal solution. It's not just a straight up transpose of the primal vectors.

It made more sense for me writing out everything symbolically in a tableau to get the dual primal relationship.

So, you're given an optimal dictionary and you want to get to the original LP that generated it.

Would you use the special "formulas"

x_b = (B^-1)b - (B^-1)(N)x_n
z = (c_b)(B^-1)b + (c_n - (c_b)(B^-1)(N))x_n to get back to the original linear program?

I'm not sure what you mean here. There isn't really a way to recover a specific tableau .

However, if you know that a region of your 'c' forms an identity matrix in the original (with zeros in the corresponding columns of the objective function), you can simply glean from there how the original tableau was transformed to optimal, and then reverse engineer the process (which can be done in a single matrix multiplication).

 

[meadowrag]

how i'm gonna integrate this?

x(sqrt(x-1))dx

 

[Orrichio]

how i'm gonna integrate this?

x(sqrt(x-1))dx

IBP?

 

[simplayer]

how i'm gonna integrate this?

x(sqrt(x-1))dx

Integrate by parts?

 

[TUSR]

yeah parts will solve that easily, i just did it. holla what you got as an answer

 

[Kieli]

One or more optimal solutions corresponds to b^T in the dual, but may be any 3 vectors that are the optimal solution. It's not just a straight up transpose of the primal vectors.

It made more sense for me writing out everything symbolically in a tableau to get the dual primal relationship.



I'm not sure what you mean here. There isn't really a way to recover a specific tableau .

However, if you know that a region of your 'c' forms an identity matrix in the original (with zeros in the corresponding columns of the objective function), you can simply glean from there how the original tableau was transformed to optimal, and then reverse engineer the process (which can be done in a single matrix multiplication).

Hey Leroidys, thanks for your help. Unfortunately, my prof will not cover the Tableau format. We are working strictly with matrices.

Also, I'm not quite sure I understand your explanation regarding how to figure out the dual solution from the primal. I thought we just had to flip a sign on the values of the primal slack variables to get the dual optimal solution.

If I can't do that, then I'm forced to go through an algorithm (which I can do, but don't understand what's going on) that uses complementary slackness to generate an optimal solution for the dual given a candidate primal optimal solution. It seems like a lot of work when this same algorithm is better used to generate a certificate of optimality for the candidate primal solution rather than trying to find the corresponding dual-optimal solution.

 

[meadowrag]

oh we aint learned IBP yet i'm supposed to use substitution but i found the same question on a yahoo answer jaun so i got it now but thanks

 

[leroidys]

Hey Leroidys, thanks for your help. Unfortunately, my prof will not cover the Tableau format. We are working strictly with matrices.

Also, I'm not quite sure I understand your explanation regarding how to figure out the dual solution from the primal. I thought we just had to flip a sign on the values of the primal slack variables to get the dual optimal solution.

If I can't do that, then I'm forced to go through an algorithm (which I can do, but don't understand what's going on) that uses complementary slackness to generate an optimal solution for the dual given a candidate primal optimal solution. It seems like a lot of work when this same algorithm is better used to generate a certificate of optimality for the candidate primal solution rather than trying to find the corresponding dual-optimal solution.

That sucks, tableaus make it so much easier.

It's been a few quarters and I sold my book so I can't go back and check, but as far as I remember the last paragraph is correct. The dual/primal relationship in that way doesn't seem super useful, but it can be useful if you have some sort of pathological problem, such as 10k constraints in 4 variables => 4 constraints in 10k variables to save a lot of computing.

 

[meadowrag]

if i'm doing an area between curves problem ...

and i'm integrating with respect to y...

and the majority of the area is to the left of the y-axis..

should my area be positive or negative?

 

[Memento_Mori15]

if i'm doing an area between curves problem ...

and i'm integrating with respect to y...

and the majority of the area is to the left of the y-axis..

should my area be positive or negative?

Positive.

 

[meadowrag]

damn i wonder why my answer is fucked up then...

I'm doing area between x = y^2 - 4y and x = 2y - y^2 from 0 to 3

I did

(y^2 - 4y) - (2y - y^2) dy

y^2 - 4y - 2y + y^2 dy

2y^2 - 6y dy

2y^3/3 - 6y^2/2

18 - 27

-9

 

[simplayer]

damn i wonder why my answer is fucked up then...

I'm doing area between x = y^2 - 4y and x = 2y - y^2 from 0 to 3

I did

(y^2 - 4y) - (2y - y^2) dy

y^2 - 4y - 2y + y^2 dy

2y^2 - 6y dy

2y^3/3 - 6y^2/2

18 - 27

-9

2y-y^2 is more positive in the y=0..3 range than y^2-4y. So you need to subtract y^2-4y from 2y-y^2

 

[meadowrag]

why though

they gave me a graph and since i'm doing it with respect to y i flipped the graph over so the y-axis is where the x-axis usually is and from 0 to 3 y^2 - 4y is on top.

 

[simplayer]

why though

they gave me a graph and since i'm doing it with respect to y i flipped the graph over so the y-axis is where the x-axis usually is and from 0 to 3 y^2 - 4y is on top.

Let's take a few points

Let y = 0, 1, 2, 3

For x = y^2 -4y; x(0) = 0, x(1) = -3, x(2) = -4, x(3) = -3

For x = 2y-y^2; x(0) = 0, x(1) = 1, x(2) = 0, x(3) = -3

Don't trust graphs they give you, they're generally not representative of the curve.

 

[jerry1594]

Can someone explain transformations to me? I'm really lacking a base for what I'm covering right now (something I am working on), so please, could you explain it to me in the simplest way you can.

 

[TUSR]

Can someone explain transformations to me? I'm really lacking a base for what I'm covering right now (something I am working on), so please, could you explain it to me in the simplest way you can.

what kind of transformations, the more details the better answer you shall receive

 

[Leezard]

Can someone explain transformations to me? I'm really lacking a base for what I'm covering right now (something I am working on), so please, could you explain it to me in the simplest way you can.

Essentially the point is that you have a problem that is difficult to solve in standard space, so you transform the problem into a transformed space where the problem is easy to solve. Then you sometimes want to inverse transform, if possible, the solution back to regular space.

 

[Partial Gamification]

Think about the geometry, it provides a good conceptual space to visualize what's happening. Common transformations are; translation, rotation, reflection, and dilation. Shapes respectively; slide, spin, flip, and size.

Graphing an equation, y=mx+b, the b can be shifted to zero by translating the graph (-b) so the equation becomes y=mx. When x=0 then y=0, as opposed to x=0 then y=b. It can convenient be to start from (0,0) but this is simplistic and situational.

There are integral transforms and linear transforms too and they all just transform the given into a solvable state. Leezard sums it up nicely, and TUSR has a good question: what type of transformation are you working with?

 

[hateradio]

Discrete math. :|

So uh, help?

1. Explain why the divisibility relation | does not define a partial ordering on the set Z of integers.

Is it because of zero or negative numbers?

2. Let a relation R be defined on the set of real numbers as follows: x R y ⇔ 2x + y = 3. Prove that this relation is antisymmetric.

 

[Exuro]

Need help with what seems like a really simple probabilistics question.

So I have 3 cars that have 2, 4, and 5 seats. 9 people are going on a ski trip. How many combinations are there total for how they can drive to the slopes?

I assume all of the cars must be taken and that the people are not unique and so since this is a simple problem I can count them all out and get 5 but what method would I use in the case this was a much bigger problem and counting would become cumbersome?

Edit: The professor clarified and the people are unique. I only know of n choose r but am not sure how to apply this to this problem.

 

[alex chilton]

I'm self studying calculus 1 right now. How important is it to know how to do proofs? I keep reading them but immediately I forget them cause I'm using shortcuts to figure them most problems out. Should I be taking the time to memorize them?

 

[Therion]

Discrete math. :|

So uh, help?

1. Explain why the divisibility relation | does not define a partial ordering on the set Z of integers.

Is it because of zero or negative numbers?

2. Let a relation R be defined on the set of real numbers as follows: x R y ⇔ 2x + y = 3. Prove that this relation is antisymmetric.

1. Take a look at antisymmetry with the examples you mention.
2. Suppose xRy and yRx, so
2x + y = 3
x + 2y = 3
Solve for x and y.

 

[simplayer]

Need help with what seems like a really simple probabilistics question.

So I have 3 cars that have 2, 4, and 5 seats. 9 people are going on a ski trip. How many combinations are there total for how they can drive to the slopes?

I assume all of the cars must be taken and that the people are not unique and so since this is a simple problem I can count them all out and get 5 but what method would I use in the case this was a much bigger problem and counting would become cumbersome?

Edit: The professor clarified and the people are unique. I only know of n choose r but am not sure how to apply this to this problem.

I think this is how you would do it.

There's three ways we can fill up the cars in general:
Stuff Car_2Seat and Car_4Seat and leave the rest to Car_5Seat
OR
Stuff Car_4Seat and Car_5Seat and leave no one in Car_2Seat -> This leads to an impossibility so this gets knocked out (no one to drive Car_2Seat, and all must go)
OR
Stuff Car_5Seat and Car_2Seat and the rest in Car_4Seat

For the first scenario, we have 9choose2 possibilities for Car_2Seat and 7choose4 possibilities for Car_4Seat and 1 possibility for Car_5Seat (there's only one way to stuff 3 people in a 5 seater if we don't care about arrangement)

For the second scenario we don't care because it's impossible given the constraints.

For the third scenario we have 9choose5 for Car_5Seat, 4choose2 for Car_2Seat and 1 possibility for Car_4Seat (again, same reasoning as above).

So our total number will be Scenario1 plus Scenario3:

(9 2)*(7 4) + (9 5)*(4 2) = 2016.

Maybe.

 

[Exuro]

I think this is how you would do it.

There's three ways we can fill up the cars in general:
Stuff Car_2Seat and Car_4Seat and leave the rest to Car_5Seat
OR
Stuff Car_4Seat and Car_5Seat and leave no one in Car_2Seat -> This leads to an impossibility so this gets knocked out (no one to drive Car_2Seat, and all must go)
OR
Stuff Car_5Seat and Car_2Seat and the rest in Car_4Seat

For the first scenario, we have 9choose2 possibilities for Car_2Seat and 7choose4 possibilities for Car_4Seat and 1 possibility for Car_5Seat (there's only one way to stuff 3 people in a 5 seater if we don't care about arrangement)

For the second scenario we don't care because it's impossible given the constraints.

For the third scenario we have 9choose5 for Car_5Seat, 4choose2 for Car_2Seat and 1 possibility for Car_4Seat (again, same reasoning as above).

So our total number will be Scenario1 plus Scenario3:

(9 2)*(7 4) + (9 5)*(4 2) = 2016.

Maybe.

Hey thanks for replying. Our professor reemailed and said that the seats were unique and not the people. Wouldn't this make it pretty easy and just make it 8 choose 6? Since all cars must drive 3 spaces and 3 people are removed and we're left with 6 people and 8 spots?

 

[simplayer]

I'm self studying calculus 1 right now. How important is it to know how to do proofs? I keep reading them but immediately I forget them cause I'm using shortcuts to figure them most problems out. Should I be taking the time to memorize them?

What do you want to do?

If you're going to go further in math, learn how to do proofs.

If you're not going further in math (like, you're just applying math), don't worry too much. It's always good to learn that sort of problem solving though.

 

[simplayer]

Hey thanks for replying. Our professor reemailed and said that the seats were unique and not the people. Wouldn't this make it pretty easy and just make it 8 choose 6? Since all cars must drive 3 spaces and 3 people are removed and we're left with 6 people and 8 spots?

Ya, sounds right.

 

[Exuro]

Ya, sounds right.

Awesome thanks for the input.

 

[Ourobolus]

I'm self studying calculus 1 right now. How important is it to know how to do proofs? I keep reading them but immediately I forget them cause I'm using shortcuts to figure them most problems out. Should I be taking the time to memorize them?

Calc 1-3 doesn't typically deal with proofs. It's when you start getting into things like Real and Complex Analysis that proofs are a major part.

 

[Kieli]

Given a LP, is there a way to check whether it is infeasible or unbounded without resorting to simplex method (in fact, you're not even allowed to use it).

The only possible thing I can think of is to add up the constraints such that I can get all the coefficients in front of the decision variables to be larger than the coefficients of the objective function (hence, I can provide an upper bound). This allows me to solve the second question (i.e. is it unbounded?).

I don't know how to solve the first question though (determining if it's infeasible). I mean, I can check if the dual is unbounded (in which case the primal is infeasible), but that's still using simplex.

 

[terrdactycalsrock]

If someone could help me, I would appricate it.

the question is: 15as-20bs + 6at^2 - 8bt^2

the instructions say "Factor by grouping"

But I know you cant factor different variables togather.....so I dont know

 

[cpp_is_king]

If someone could help me, I would appricate it.

the question is: 15as-20bs + 6at^2 - 8bt^2

the instructions say "Factor by grouping"

But I know you cant factor different variables togather.....so I dont know

Not sure what you mean by "you cant factor different variables together", but the key is to find two or three terms that you can factor something out of, and then just try it.

The 6at^2 - 8bt^2 stands out like a sore thumb because they both have t^2 in them. If you factor that you get:

2t^2(3a - 4b)

Now what's left over is 15as - 20bs

Factoring that gives 5s(3a - 4b)

So now you have 5s(3a - 4b) + 2t^2(3a - 4b)

Now there's 2 terms, both with a (3a - 4b), so you can factor that whole thing out and get:

(3a - 4b)(5s + 2t^2)

 

[terrdactycalsrock]

Oh, I wasn't realizing that you could just take out an S or a T. Thanks cpp_is_king!

 

[harriet the spy]

Given a LP, is there a way to check whether it is infeasible or unbounded without resorting to simplex method (in fact, you're not even allowed to use it).

The only possible thing I can think of is to add up the constraints such that I can get all the coefficients in front of the decision variables to be larger than the coefficients of the objective function (hence, I can provide an upper bound). This allows me to solve the second question (i.e. is it unbounded?).

I don't know how to solve the first question though (determining if it's infeasible). I mean, I can check if the dual is unbounded (in which case the primal is infeasible), but that's still using simplex.

You can answer those questions by solving LPs, which you can solve using a different method than the simplex, but I assume that’s not what you meant.
In general, for some specific problems you can exhibit certificates of unboundedness or infeasibility, but finding those certificates really is not so different from solving LPs.

For infeasibility, you can use Fourier-Motzkin elimination, but it’s not very efficient.

 

[RELAYER]

I'm doing volume of revolution problem.

the function is x = y - y^2
The only boundary given is x = 0.
I'm supposed to rotate around y-axis.

I don't get it because the parabola just goes forever in the negative x direction.

edit: derp

 

[M.D]

I have this equation that

The only instruction is to "solve the system of equations"

y=-x^2+6x
y=x+4

What exactly am I supposed to do here? Find the intersection of the parabola and the line?

 

[TUSR]

I have this equation that

The only instruction is to "solve the system of equations"

y=-x^2+6x
y=x+4

What exactly am I supposed to do here? Find the intersection of the parabola and the line?

find x?