linear programming

Question 1

linear programming intro:

Answer 1

convex optimisation problem to minimise f(x) subject to g1<=0 … gm(x)<=0, x in Ω where Ω is convex and all functions are convex, linear programming means all functions are linear and Ω=Rn

Question 2

convex hull:

Answer 2

convS of a set S, the intersection of all convex sets containing S, so s=convS if S is convex

Question 3

convex combination:

Answer 3

linear combo (k)Σ(i=1)λixi such that λi>=0 and (k)Σ(i=1)λi=1

Question 4

convex hulls and combos:

Answer 4

convex sets are closed under convex combos, the set of all convex combos of points in a set S is the convex hull of S

Question 5

hyperplane:

Answer 5

H={x in Rn: ⟨a,x⟩=b=a^(T)x}, so a solution set, it’s convex

Question 6

halfspace:

Answer 6

a hyperplane divides Rn into two sides, which are these
H-={x in Rn: ⟨a,x⟩<=b}, H+={x in Rn: ⟨a,x⟩>=b}, these are convex also

Question 7

2d version of hyperplane separation theorem:

Answer 7

C is a nonempty closed convex set, x Not in C, then there exists a point y* in C such that ||x-y||=min||x-y||, equivalent to saying y=argmin||x-y||, minimising the distance between them
also for all z in C, ⟨z-y,x-y⟩<=0 (so z-y* and x-y* form an obtuse angle) - look in the notes for visual for this but essentially x-y* is perpendicular to the edge of C and z is in C so ofc the angle is obtuse it has to be at least 90 degrees

Question 8

continuous function on a closed bounded set:

Answer 8

must attain a max and a min in that set

Question 9

hyperplane separation theorem:

Answer 9

let C be a closed convex set, x Not in C, then there exists a hyperplane H such that C within intH- and x in intH+
essentially you can draw a line between the edge of C and x

Question 10

linear programming:

Answer 10

maximise ⟨c,x⟩ subject to Ax<=b, A in R^(mxn), x,c in Rn, b in Rm, inequality means each inequality in each row

Question 11

feasible set:

Answer 11

F={x in Rn: Ax<=b}, set of all possible candidates, always convex but can be empty

Question 12

polyhedron:

Answer 12

the set of all feasible sets

Question 13

how to check if a lin programming problem has a solution:

Answer 13

either find a vector from F or show that assuming Ax<=b has a solution makes a contradiction so F must be empty, ⟨λ,Ax⟩<=⟨λ,b⟩ find λ such that (m)Σ(i=1)λiai=0 and ⟨λ,b⟩<0, if this answer makes no sense rewrite this with more detail I just don’t know if we need it all, if it makes sense remove this disclaimer lmao