#Linear Programming -
faint obsidianBOT
wheat token
a vector can be seen as representing a linear form (for a given basis, the linear form x -> <a, x> (where <., .> is the dot product)). All nonzero linear forms are of rank 1
all hyperplanes are kernels of linear forms (and vice versa). Therefore hyperplanes are vector spaces of dimension n-1 by the rank formula
wheat token
a vector can be seen as representing a linear form (for a given basis, the linea...
"hyperplane in question being H = {x, where a_t * x = 0}, both 'a' and 'x' belonging to R_n"
Therefore you are actually describing all hyperplanes in this exemple
because vectors ~ linear forms ~ hyperplanes (where ~ means bijection, because the set of all hyperplanes isn't a vector space so there can't be an isomorphism)
vagrant panther
i see\
thank you
not sure if i understand why the set of all hyperplanes isn't a vector space
apologies but I have yet to brush up on the requisite linear algebra for this linear programming course
wheat token
not sure if i understand why the set of all hyperplanes isn't a vector space
you'd have to define addition and scalar multiplication of hyperplanes. So unless you do so, and come up with a structure that makes sense, then it can't have that structure because there's no operations to talk about
vagrant panther
thoughts
wheat token
Use the first characterization
If you don't see how it's useful, make a drawing. Both of the characterization and of the property you're trying to prove
||x = 1/2(x+d) + 1/2(x-d)||
vagrant panther
that is helpful
I am bad at visualizing this stuff, that seems to be a problem
there was another part to this question
where it said
Show that x is an extreme point of P if and only if there exists a hyperplane H given by H = {x ∈ Rn : a⊺x = β} such that H ∩ P = {x} and a⊺y ≤ β for all y ∈ P.
i was wondering if proof by contradiction is a good idea here
for the first half of this question
like assuming x is an extreme point and then assuming H ∩ P = {x,k}
where k is not ax extreme point, then trying to proof that cant ben true
or is that an invalid approach
proof by contrapositive seems too complicated here
vagrant panther
wheat token
thoughts
Honestly, I've never studied extremal points or done any sort of geometry in high dimension. So I don't have a clue what the second characterization is (even the Ax <= b part: this feels like a half image, so a half vector plane, which doesn't sound right for a polyhedron, but I don't even know how you order vectors here). However since Ax <= b and a^T x <= beta look similar, maybe look into a possible rephrasing of that property ? But honestly idk since I never studied this
vagrant panther
okay
tawny mist
Anyway state definition of an extreme point
vagrant panther
a point that cannot be stated in terms of two distinct points in the same polyhedron
with the coefficients of those respective points being k and 1-k respectively
k between 0 and 1 inclusive
tawny mist
so what are you using to prove
vagrant panther
theres the other definition that uses rank but i dont really understand it
i didnt prove it
vagrant panther
i was thinking using just rhe definitom of an extreme point but it seems like i might also have to use the characterization thats mentioned in the first screenshot
but idk how to use it
like it makes intuitive sense the intersection of the hyperplane and polyhedron would just be the extreme point
but i dont have the required linear algebra knowledge to proceed
tawny mist
can you use optimisation itself
because a standard method of equivalence between the two
is to use optimisation itself
vagrant panther
whoopsie
Linear Programming -
might be a really dumb question
but in the context of Duality
my book stated this
I thought the lower bound needed to be as small as possible since we are minimizing?
vagrant panther
hmmm
larger lower bound is in terms of |absolute numbers| or
a general number
lets say the lower bound is 5, so is -10 considered larger
tawny mist
larger lower bound is in terms of |absolute numbers| or
No
The real numbers are totally ordered
And they are fine as the containing set of objective values
(along with +, - infty)
vagrant panther
then it seems to be the opposite of what we should be doing for a min problem? wouldnt a smaller lower bound imply a smaller feasible solution
tawny mist
Well I'll give you an example
Although I wanted you to think of it first
Suppose I achieve, for a minimisation problem, a value of 5
For feasible x
What's a good lower bound?
Is it -infty?
tawny mist
What about -5
vagrant panther
i suppose -5
tawny mist
Suppose I know the lower bound is -5
vagrant panther
so we;re basically limiting our set of solutions
tawny mist
And my current feasible solution gives a value of 5
That means I have only 10 more to go as improvement at best
vagrant panther
i was just thinking of it from the perspective of a 'better value'
vagrant panther
but i suppose that makes sense
tawny mist
I no longer need to search any more in my set
vagrant panther
yesh
tawny mist
That's what duality is telling you
In Linear Programming duality is very powerful
Also because (linear) duality can be used/abused to get many results by itself
vagrant panther
should I get into the nitty gritty of it and try to understand the reasoning behind how we obtain the dual or just follow the table
tawny mist
That's what duality is telling you
Because of how weak duality holds
tawny mist
should I get into the nitty gritty of it and try to understand the reasoning beh...
You should try to get as much as you can
I've done this for longer and I feel like I need to brush up
but if I did it properly when I started I would have less issues
vagrant panther
thing is I havent done lin alg in a long time, so reading notation like this takes up so much time, I feel like its better to just jump to exampls and get used to it
rather than trying to get skillfull at the formal stuff
tawny mist
Well it's theory
If you have a solver and the problem is linear
You probably can just call .dual()
lol
vagrant panther
no, its a math course
vagrant panther
idk whats that
tawny mist
Key result is max flow min cut
But don't worry about it
If you can go from a standard problem, to Lagrangian, to getting a dual problem, that's a key foundation in understanding
tawny mist
That's sad
vagrant panther
they're just focusing on developing problems and solving them
like practical applicaitons i suppose
although the convexity stuff was kind of different i guess
next up is integer problems
tawny mist
Convexity has its own analysis
vagrant panther
im kind of fucked in this course tbh
tawny mist
I wasn't taught much integer theory
I think what most people do is learn relaxation, learn some cuts
tawny mist
im kind of fucked in this course tbh
Well, whether this matters depends on what you want to do in the future
vagrant panther
I am not doing any math certainly so I just wanna get a good score at any cost
vagrant panther
I think what most people do is learn relaxation, learn some cuts
yeah
well.. I am doing coding theory the last math course I will ever take
hopefully not too heavily built upon this
probably not at all
vagrant panther
having a hard time figuring out
the dualof this LP
i have written it in a normal LP form where in i have expressed in terms of vectors and matricies
but cant figure out the OF of the Dual
should i introduct another variable?
vagrant panther
nevermind
serene spear
.close
faint obsidianBOT
Solved
serene spear
you deleted the question and said nevermind, I thought you were done
were you not
ah, you posted the wrong thing. Ill reopen
.unsolved
faint obsidianBOT
Unsolved
serene spear
just a heads up though, it will look like you ditched the thread though since you deleted the OP
vagrant panther
how do i fix that
serene spear
you dont
vagrant panther
ive been using this forum for weeks
vagrant panther
whats the problem with it having no OP
forums are confusing
is it harder for new people to find it?
serene spear
many people just delete their original message when theyre done because they were either cheating or dont know how to close the channel
so something that looks like this many will assume are inactive or finished
vagrant panther
i see
serene spear
if you don't have any particular attachment to this thread in particular you can just open a new one
vagrant panther
i just had another question so i thought no point keeping tje OP as one question
serene spear
The point of the threads is one question per thread
you shuold be opening new ones anyway
serene spear
(after marking your old ones as closed)
vagrant panther
i thought it was for topics not covered in any channels
serene spear
It is, but its meant to be more directed
nothing wrong with using it like this though I guess
you will have the problem of a misleading (or in this case nonexistent) preview
may hurt the odds of others participating
vagrant panther
i see
serene spear
your choice though, good luck!