Geometry and Linear Programming Basics Flashcards
What are the 3 components of optimisation problems:
Decisions: variables we can change to influence the outcome
Constraints: we have to abide by
Objective: typically want to maximise or minimise
What is a deterministic model?
A model where we have all the information.
How are decision variables typically labelled in optimisation problems?
x1, … xn E R (real numbers)
How are objective functions typically labelled in optimisation problems?
f(x1, …xn): R^n –> R
function takes several real numbers and retruns a real number
How are constraints typically labelled in optimisation problems?
typically labelled gi(x1, …, xn) <= ci
gi(x1, …, xn) : Rn → R where 1 <= i <= m
If you choose two vertices that are non parallel what will you identify?
A corner in your feasible region, which may give the optimal solution depending on if your minimising or maximising in the objective
How can you find the optimal solution in a feasible region?
How is this a valid method, when the feasible region has an infinite number of points/the problem is continuous:
- By going through all the vertices of the polyhedron/polytope in the feasible region.
- Even though this is a continuous problem, this is a valid method because the number of vertices is discrete (it becomes a discrete problem.
What are the definitions of decision variables, objective function and constraints for a Linear Optimisation Problem : LP?
Variables: x1,…, xn
Objective: c1x1 + c2x2 + … + cnxn
where x is a decision variable, c is a scalar constant
Constraints: Ax <= b
- Can be solved in polynomial time
What is it called if we have an LP where the decision variables can only be integers:
ILP: Integer Linear Programming
- decision variables: x1,…, xn ∈ Z
- this is NP-complete
What is a property of LPs?
They have local and global optimums
What is a global optimum?
A point of a function: f(x*) <= f(x) for all values of x
- if we’re minimising, it’s a point that has the minimum value of the function f across the entire domain of f
What is a local optimum?
A point of a function: f(x’) <= f(x) for all x with |x’-x| <= e
- where there’s no better solution in the immediate neighbourhood. So for some value ε, if point x is within the distance of ε it’ll be >= x’.
What is the class of problems where every local minimum is a global minimum?
Convex optimisation problems
What is the definition of a convex set?
- A set is a convex set if all the points on the line connecting any two points in the set are also in the set
- the connecting line is known as a line of convex combinations, expressed as for all (x, y ∈ X), (0 ≤ λ ≤ 1) → λx + (1 − λ)y ∈ X
What is a convex function?
- A convex function is where the domain is a convex set, and the function satisfies:
For all (x, y ∈ X) and (0 ≤ λ ≤ 1) where:
f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y)
It’s a convex function if for any two points in the domain and λ is between 0 and 1, if we take the function value at the convex combination of x and y, this has to be less than or equal to the convex combination of the function values for x and y.
How can you tell if a function is convex or concave?
- A convex function curves upwards: u, so a chord between two points on the function will be larger or equal to the convex function
- A concave function curves downwards: n, so a chord between two points on the function will be less than or equal to the convex function
How would we know if a function f is concave ?
If -f is convex (curves upwards)
What is convex optimisation?
- Where the objective function f is convex and the set of feasible solutions X are convex
- for these problems every local optimum is a global optimum
What is the proof that in convex optimisation problems, every local optimum is a global optimum:
Prove by contrapositive:
- if a convex function exists where there’s a local f(x’) and global f(x) optimum, we’d get a chord between the two points.
- as it’s a convex function, we can represent the two points as convex combinations on the chord as f(λx + (1-λ)x’) and the chord as λf(x*) + (1-λ)f(x’), however as the function line is above the chord it doesn’t satisfy the definition of a convex function
If you have an LP where all the constraints are in the form Ax ≥ b, what can you write this as:
a matrix/vector multiplication of the constraints
Why do we like to have LPs in normal form?
It’s restrictive and therefore easier to work with
Describe the features of a general form LP:
- objective =: min or max c^T*x
where x = (x1,x2,…xn) - x is a column vector (matrix of n rows and 1 column)
- c is a cost vector, which we transpose, so we can perform matrix multiplication
- 3 classes of constraints: greater equal, equality and lesser equal
- aiTx ≥ bi : ai is a vector of coefficients, multiplied by the decision vector x, which has to be greater than constant value bi
also have sign constraints on decision variables x1 >= 0
What are variables that are unrestricted called?
free variables
Describe the features of a canonical form LP:
- more restricted version of a general LP
- objective function stays the same
- constraints can only be greater than or equal constraints
- all variables must be non-negative
How can we re-write a canonical form LP:
- take coefficients of left hand sides inequalities and set them as rows of a matrix A
- write right hand sides as vector b
- decision variables as vector x
- since only greater than or equal constraints now:
Ax ≥ b
Describe the features of a standard form LP:
- same objective as general form LP
- constraints of form Ax = b, A is matrix of coefficients of left hand of constraint, x is decision vector, b is vector of right hand of constraints
- all variables are non-negative values (so all inequality signs must be replaced by =, apart from in non-negativity constraints)
How do remove inequality signs when transforming a general form LP into a standard form LP?
- We introduce slack and surplus variables
- for a constraint x1 ≥ 4 then x1 - S = 4
- for a constraint x1 ≤ 4 then x1 + S = 4
How can we re-write a standard form LP:
Ax = b, where x x ≥ 0
- as all left hand sides of constraints = right hand sides of
What are piecewise linear convex functions?
- approximations of convex functions
- formed of the maximum of a number of convex functions
What are solution spaces?
They are the feasible regions where if a solution if found inside it, it is a feasible solution
What is the formal definition of a hyperplane:
Where a is a vector of real numbers and b is a real number:
the set {x ∈ R^n | a^T*x = b}
What is the formal definition of a halfspace:
where a is a vector of real numbers and b is a real number:
the sets {x ∈ R^n | a^Tx ≥ b} and {x ∈ R^n | a^Tx ≤ b} are half spaces of a hyperplane {x ∈ R^n | a^T*x = b}
- e.g. a halfspace is half of a hyperplane
What is a polyhedron?
A polyhedron is the intersection of a finite number of half spaces.
- the points on and in the polyhedron is the set of solutions of the LP
What are the linear inequalities in LPs?
They are all half spaces
What is a polytope?
A polytope is a bounded polyhedron:
A set S ⊆ R^n is bounded if there’s a K such that for all (x1,x2,…xn) ∈ S, |xi|≤ K for all i=1…n
It’s a polytope if we take the set of points in the polyhedron and there’s an upper bound on the absolute value that any component of the vectors in the polyhedron can take
What two lemma’s prove that polyhedrons are convex sets?
1) that half spaces are convex sets
2) the intersection of convex sets is also convex
as a polyhedron is the intersection of a finite number of half spaces, polyhedrons are convex
What is the formal definition of an extreme point?
Let P be a polytope. A vector x ∈ P is an extreme point in our polyhedron, if there are no other distinct points y, z ∈ P from x and no λ ∈ [0,1], such that x = λy + (1 − λ)z
x is an extreme point if we can’t represent it as a convex combination of two other points in the polyhedron/polytope
What is the formal definition of a vertex?
A vector x ∈ P is a vertex if there’s a cost vector c such that c^Tx < c^Ty for all y ∈ P, where x y
A vertex is where the hyperplane aTx = b touches the polyhedron, and every other point on the polyhedron is larger than that point: cTy > cTx.
a point in the middle of the line is not a vertex because a hyperplane that touches it will also touch other points of the polyhedron hence cTu = cTy, meaning this constraint cTy > cTx won’t be satisfied.
What is an active constraint?
- if for point x* the inequality holds with equality, the corresponding constraint is active/binding at x*
- aiTx* = bi is true for an active constraint
How many constraints are active/binding for a vertex/extreme point?
Two constraints are active as at this point
- aiTx* = bi is true for two constraints
- if we know two constraints are active/binding and are not parallel, for a point x*, we’ve identified a corner
When are two constraints linearly independent?
The constraints {ai^Tx ≤ bi or ai^Tx = bi | i ∈ I} are linearly independent if their corresponding vectors {ai | i ∈ I} are linearly independent
- The vectors are LI if the only way of creating a linear combination of these vectors is by choosing zero coefficients everywhere, thus their linear combination is null values.
What are the requirements for a BS in a hyperplane/ n-dimensional real space?
1) all equality constrains are active at point x
2) of the active constraints at x, there are n that are linearly independent
So for a 2D space, there must be 2 active constraints at the point for it to be a BS
What is a polyhedron/polytope or LP also known as:
A system of linear equations
What are the requirements for a basic feasible solution?
1) all equality constraints are active at point x
2) of the active constraints at x, there must be n that are linearly independent
3) point x must be in the polyhedron/ feasible region
Which 3 statements are the same if:
Let x* ∈ ℝ^n and let I = {i | ai^Tx = bi} be the set of constraints that are active at x*
(a) There exist n vectors in the set {ai |i ∈ I} that are linearly independent.
(b) The span of the vectors in {ai |i ∈ I} is all of R^n
(c) The system of linear equations aiTx = bi, i ∈ I has a unique solution.
What 3 things are equivalent for a nonempty polyhedron P, where x* ∈ P.
(a) x* is a vertex
(b) x* is an extreme point
(c) x* is a basic feasible solution
What is true if there’s a finite number of constraints?
There’s a finite number of basic feasible solutions (as there’s a finite number of extreme points/vertices)
How can we calculate a unique BFS?
1( Look at all possible ways of choosing n linearly independent constraints out of the constraints that we have
2) solve the linear equations corresponding to these
3) take the point, plug it into the objective function.
4) Repeat for each BFS to find the optimal solution.
What does a BFS look like for a standard form LP:
Minimise: cTx
Subject to Ax = b and x >= 0
Matrix A has m (constraints) rows and n (decision variable) columns.
- At any basic feasible solution P, all m < n equality constraints are active. Additionally, m-n nonnegativity constraints are active.
- none of the decision variables can have negative values
What are the 4 steps for calculating a BS for a standard form polyhedron:
1) Choose m linearly independent columns from matrix A.
2) Set remaining variables to = 0. This gives us a system of equations Bx = b
4) Solve for the remaining (simultaneous) equations (that we haven’t set to 0)
What is the full row rank assumption?
That if we have feasible solutions at all, we assume we have m constraints and n variables: mxn matrix, we assume have fewer constraints than variables and that all the constraints/corresponding vectors are linearly independent
- if they weren’t we would get an inconsistent system of constraints:
L1: 2x1 + x2 + x3 = 2
L2: x1 + x2 = 1 - The linear combination of L1 and L2: L1 - L2 = x1 + x3 = 1, then we still have the constraint L3 = x1 + x3 = 2. Here we can see that this doesn’t have a solution.
What does full row rank assumption say we can do if we have a system of equations with a redundant constraint?
- We can remove it without that affecting the set of feasible solutions.
- If we remove the constraint we technically get a new polyhedra, but full row rank assumption says they’re the same polyhedra.
How do we construct a BFS?
1) choose m linearly independent columns from constraint matrix A to be in the basic
2) set the non-basic variables = 0
3) solves the system of equations for Ax = b
if all variables are non-negative, the BS is a BFS
If we have a non-empty polyhedron, what is equivalent:
a) the polyhedron has at least one extreme point
b) the polyhedron does not contain a line
c) there exist vectors in the constraint family that are linearly independent
What is the definition for a polyhedron containing a line:
A polyhedron contains a line if there exists a vector x ∈ P, and a nonzero vector d ∈ R^n, such that x + λd ∈ P for all scalars λ
e.g. the vector/line can go infinitely in either direction because it never hits a constraint.
When are two vectors linearly independent:
If neither vector is a scalar multiple of the other
What is true if a polyhedron doesn’t contain a line?
There exists vectors in the constraint family that are linearly independent
What is true if there exists vectors in the constraint family that are linearly independent?
The polyhedron contains at least one extreme point
When are two basic solutions adjacent?
Two basic solutions are adjacent if they differ by only one index/one basic variable in the basis.
How do we know that every standard form non-empty polytope/polyhedron has at least one BFS?
In Standard form, if we have n linearly independent active constraints, we always have an extreme point under these conditions, as we have a non negativity constraint, meaning it doesn’t contain a line
What are the two cases, if the polyhedron contains an extreme point ?
- If P has at least one extreme point and there’s an optimal solution, the optimal solution is at an extreme point
- If P has a least one extreme point, either the optimal cost is −∞ or the optimal solution is at an extreme point
