Geometry and Linear Programming Basics

Question 1

What are the 3 components of optimisation problems:

Answer 1

Decisions: variables we can change to influence the outcome
Constraints: we have to abide by
Objective: typically want to maximise or minimise

Question 2

What is a deterministic model?

Answer 2

A model where we have all the information.

Question 3

How are decision variables typically labelled in optimisation problems?

Answer 3

x1, … xn E R (real numbers)

Question 4

How are objective functions typically labelled in optimisation problems?

Answer 4

f(x1, …xn): R^n –> R
function takes several real numbers and retruns a real number

Question 5

How are constraints typically labelled in optimisation problems?

Answer 5

typically labelled gi(x1, …, xn) <= ci
gi(x1, …, xn) : Rn → R where 1 <= i <= m

Question 6

If you choose two vertices that are non parallel what will you identify?

Answer 6

A corner in your feasible region, which may give the optimal solution depending on if your minimising or maximising in the objective

Question 7

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:

Answer 7

• 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.

Question 8

What are the definitions of decision variables, objective function and constraints for a Linear Optimisation Problem : LP?

Answer 8

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

Question 9

What is it called if we have an LP where the decision variables can only be integers:

Answer 9

ILP: Integer Linear Programming
- decision variables: x1,…, xn ∈ Z
- this is NP-complete

Question 10

What is a property of LPs?

Answer 10

They have local and global optimums

Question 11

What is a global optimum?

Answer 11

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

Question 12

What is a local optimum?

Answer 12

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’.

Question 13

What is the class of problems where every local minimum is a global minimum?

Answer 13

Convex optimisation problems

Question 14

What is the definition of a convex set?

Answer 14

• 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

Question 15

What is a convex function?

Answer 15

• 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.

Question 16

How can you tell if a function is convex or concave?

Answer 16

• 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

Question 17

How would we know if a function f is concave ?

Answer 17

If -f is convex (curves upwards)

Question 18

What is convex optimisation?

Answer 18

• 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

Question 19

What is the proof that in convex optimisation problems, every local optimum is a global optimum:

Answer 19

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

Question 20

If you have an LP where all the constraints are in the form Ax ≥ b, what can you write this as:

Answer 20

a matrix/vector multiplication of the constraints

Question 21

Why do we like to have LPs in normal form?

Answer 21

It’s restrictive and therefore easier to work with

Question 22

Describe the features of a general form LP:

Answer 22

• 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

Question 23

What are variables that are unrestricted called?

Answer 23

free variables

Question 24

Describe the features of a canonical form LP:

Answer 24

• 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

Question 25

How can we re-write a canonical form LP:

Answer 25

- 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

Question 26

Describe the features of a standard form LP:

Answer 26

- 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)

Question 27

How do remove inequality signs when transforming a general form LP into a standard form LP?

Answer 27

- We introduce slack and surplus variables - for a constraint x1 ≥ 4 then x1 - S = 4 - for a constraint x1 ≤ 4 then x1 + S = 4

Question 28

How can we re-write a standard form LP:

Answer 28

Ax = b, where x x ≥ 0 - as all left hand sides of constraints = right hand sides of

Question 29

What are piecewise linear convex functions?

Answer 29

- approximations of convex functions - formed of the maximum of a number of convex functions

Question 30

What are solution spaces?

Answer 30

They are the feasible regions where if a solution if found inside it, it is a feasible solution

Question 31

What is the formal definition of a hyperplane:

Answer 31

Where a is a vector of real numbers and b is a real number: the set {x ∈ R^n | a^T*x = b}

Question 32

What is the formal definition of a halfspace:

Answer 32

where a is a vector of real numbers and b is a real number: the sets {x ∈ R^n | a^T*x ≥ b} and {x ∈ R^n | a^T*x ≤ b} are half spaces of a hyperplane {x ∈ R^n | a^T*x = b} - e.g. a halfspace is half of a hyperplane

Question 33

What is a polyhedron?

Answer 33

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

Question 34

What are the linear inequalities in LPs?

Answer 34

They are all half spaces

Question 35

What is a polytope?

Answer 35

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

Question 36

What two lemma's prove that polyhedrons are convex sets?

Answer 36

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

Question 37

What is the formal definition of an extreme point?

Answer 37

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

Question 38

What is the formal definition of a vertex?

Answer 38

A vector x ∈ P is a vertex if there’s a cost vector c such that c^T*x < c^T*y 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.

Question 39

What is an active constraint?

Answer 39

- 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

Question 40

How many constraints are active/binding for a vertex/extreme point?

Answer 40

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

Question 41

When are two constraints linearly independent?

Answer 41

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.

Question 42

What are the requirements for a BS in a hyperplane/ n-dimensional real space?

Answer 42

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

Question 43

What is a polyhedron/polytope or LP also known as:

Answer 43

A system of linear equations

Question 44

What are the requirements for a basic feasible solution?

Answer 44

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

Question 45

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*

Answer 45

(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.

Question 46

What 3 things are equivalent for a nonempty polyhedron P, where x* ∈ P.

Answer 46

(a) x* is a vertex (b) x* is an extreme point (c) x* is a basic feasible solution

Question 47

What is true if there's a finite number of constraints?

Answer 47

There's a finite number of basic feasible solutions (as there's a finite number of extreme points/vertices)

Question 48

How can we calculate a unique BFS?

Answer 48

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.

Question 49

What does a BFS look like for a standard form LP: Minimise: cTx Subject to Ax = b and x >= 0

Answer 49

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

Question 50

What are the 4 steps for calculating a BS for a standard form polyhedron:

Answer 50

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)

Question 51

What is the full row rank assumption?

Answer 51

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.

Question 52

What does full row rank assumption say we can do if we have a system of equations with a redundant constraint?

Answer 52

- 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.

Question 53

How do we construct a BFS?

Answer 53

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

Question 54

If we have a non-empty polyhedron, what is equivalent:

Answer 54

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

Question 55

What is the definition for a polyhedron containing a line:

Answer 55

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.

Question 56

When are two vectors linearly independent:

Answer 56

If neither vector is a scalar multiple of the other

Question 57

What is true if a polyhedron doesn't contain a line?

Answer 57

There exists vectors in the constraint family that are linearly independent

Question 58

What is true if there exists vectors in the constraint family that are linearly independent?

Answer 58

The polyhedron contains at least one extreme point

Question 59

When are two basic solutions adjacent?

Answer 59

Two basic solutions are adjacent if they differ by only one index/one basic variable in the basis.

Question 60

How do we know that every standard form non-empty polytope/polyhedron has at least one BFS?

Answer 60

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

Question 61

What are the two cases, if the polyhedron contains an extreme point ?

Answer 61

- 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