Exam

Question 1

What is convex set? [1-INTRO]

Answer 1

A set C is convex if for any x1, x2 ∈ C, for any lambda [0, 1], it holds that lambda * x1 + (1 - lambda) * x2 ∈ C

Question 2

What is convex function? [1-INTRO]

Answer 2

A function f is convex if dom f is convex and for any x, y ∈ dom f and lambda [0,1] it holds that
f(lambda * x + (1 - lambda) * y) <= lambda * f(x) + (1 - lambda) * f(y)

Question 3

What are steps to standardise LP? [2-GEOMETRY]

Answer 3

1 Maximization → Minimization
2 ≤ inequalities → equalities (slack variables)
3 ≥ inequalities → equalities (surplus variables)
4 Negative right hand sides → multiply by −1
5 Eliminate free variables

Question 4

What is a polyhedra? [2-GEOMETRY]

Answer 4

Convex set that is the intersection of a finite number of hyperplanes and halfspaces

Question 5

What is an extreme point of polyhedron P? [2-GEOMETRY]

Answer 5

We can not find x,y ∈ P s.t. lambda * x + (1 - lambda) * y ∈ P

[Theorem: Suppose P has at least one extreme point. Then, either the optimal cost is −∞ or there exists an extreme point that is optimal.]

Question 6

What is basic solution and BFS? [2-GEOMETRY]

Answer 6

Let P be a polyhedron. The vector x ∈ Rn is is a basic solution if
1) All equality constraints are active at x, and
2) Out of the constraints that are active, n of them are linearly independent

BFS - A basic feasible solution(BFS) is a basic solution that satisfies all of the constraints

Question 7

What is a vertex of polyhedron P? [2-GEOMETRY]

Answer 7

Point x is the vertex of P if there exists c ∈ Rn such that x is the unique optimal solution of problem
min c^T*x subject to x ∈ P

Question 8

What is the connection between Extreme Pt, Vertex and BFS? [2-GEOMETRY]

Answer 8

If we let P be a non-empty polyhedron and let x ∈ P. Then, these are equivalent

[Property of being a BFS is representation independent] [P has a BFS <=> P does not contain a line (Th)]

Question 9

When polyhedron P = {x : Ax = b, x ≥ 0} does have a BFS? Let A = [A1, A2, …, An] (Ai: ith column of A) [2-GEOMETRY]

Answer 9

Theorem: Assume that rank(A) = m. A vector x ∈ Rn is a basic solution if and only if Ax = b, and there exist indices B(1), . . . , B(m) such that:
(a) The columns AB(1), . . . , AB(m) are linearly independent
(b) xi = 0 ∀ i != B(1),…,B(m)

Question 10

When a basic solution is called degenerate? [2-GEOMETRY]

Answer 10

A basic solution x is degenerate if the cardinality of the set {i : a_i^T * x = b_i } is greater than n (more than n constraints are active)

[ Degeneracy may depend on the particular representation of a polyhedron!]

In case of simplex method - θ* can equal 0 → new BFS = current BFS -> Finite termination is not guaranteed: cycling is possible.

Question 11

What is the standard view of a LP? [3 - Simplex 1]

Answer 11

minimize c^T*x
subject to Ax = b, x≥0
with data A ∈ Rm×n, c∈Rn, b∈Rm (b≥0)

We assume:
*rows of A are linearly independent (otherwise, the constraints are
redundant or inconsistent).
* Requires that # of variables = n ≥ m = # of equations
=> rank(A) = m

Question 12

What are basic variables in terms of A matrix? [3 - Simplex 1]

Answer 12

The set of columns that makes the matrix A invertible. The rest columns of A are called non-basic variables.

Note - By construction, the non-basic variables are always zero, but the basic variables can be zero or non-zero.

Question 13

Write the Basic Representation [3 - Simplex 1]

Answer 13

it is on the list == revise it!!!

Question 14

How do we define the reduced costs vector? [3 - Simplex 1]

Answer 14

Definition: Let x be a basic solution, let B be an associated basis matrix, and let c_B be the vector of costs of the basic variables.
For each j, we define the reduced cost rj of the variable xj according to
r_j = c_j − (c_B)^TB^(− 1)A_j.
when r ≥ 0 - we found the optimal solution! If not - we increase the variables with the negative reduced costs!

note - for basic variables they equal 0
r_B = c_B − (B)^TB^(− 1)^Tc_B
for NBVs:
r_N = c_B − (N)^TB^(− 1)^Tc_B

Question 15

Theorem: Consider a basic feasible solution x associated with a basis matrix B, and let r be the corresponding vector of reduced costs. [3 - Simplex 1]

Answer 15

1.If r ≥0, then x is optimal.
2 If x is optimal and non-degenerate, then r ≥ 0.

Question 16

What is the expression for the basic direction? [3 - Simplex 1]

Answer 16

So basically it is the direction in which we reduce the costs (we move as fas as possible)
A(x + θd) = b
Since θ>0 ,we require Ad =0,i.e.,
0=Ad =Bd_B +A_j.

The unique solution is d_B = −B^(−1)*A_j.
The vector d = (d_B,d_N) is called j-th basic direction.

Question 17

What are key steps of Simplex Method? [3 - Simplex 1]

Answer 17

Identify Basis, BFS
Calculate Reduced Costs
Determine Direction, Feasibility
Adjust Basis, Recalculate

for adjusting the basis - Smallest subscript pivoting rule + for the direction - we select the smallest x_old/x_new fraction

Question 18

How does the full tableau look like? [4 - Simplex 2]

Answer 18

it is on the list == revise it!!!

Question 19

How to work with tableau? [4 - Simplex 2]

Answer 19

Initialize Tableau: Begin with the tableau for the current basis and BFS.
Evaluate Optimality: If all reduced costs are non-negative, the solution is optimal; stop.
Select Pivot: Choose a column with a negative reduced cost for improvement. If no positive pivot direction, the cost is unbounded.
Determine Pivot Row: Use the minimum ratio test to find which variable leaves the basis.
Update Tableau: Perform row operations to pivot, making the new basis element canonical.

Question 20

How to find an initial BFS? Also share the observations [4 - Simplex 2]

Answer 20

Introduce a vector of artificial variables y ∈ Rm and use simplex algorithm to solve the auxiliary problem

minimize e^Ty
subject to Ax+y=b (AP)
x,y ≥ 0

[Note: Initialization is easy for (AP) - take (x, y) = (0, b).]

Observations from the auxiliary problem:
* If x is feasible for (LP), then (x,0) is feasible for (AP) with objective value 0.
* Thus, if optimal objective of (AP) is > 0, we can conclude that (LP) is infeasible.

Suppose optimal objective is zero (must have y = 0):
- if no artificial variables are on the basis - we have found an initial BFS for (LP).
- if some are still in the basis - we must drive them out of it

Question 21

What is the motivation of the duality? [5 - Duality]

Answer 21

Relax the constraints Ax = b by introducing a penalty
so, we get
g(p) = minimize c^Tx + p^T(b − A*x) subject to x ≥ 0

minimal bound property - g(p) = x* (optimal solution of LP)

Question 22

How does dual problem look like? [5 - Duality]

Answer 22

maximize b^Tp
subject to A^⊤p ≤ c

Optimal cost in dual problem is equal to optimal cost in primal problem c^T (x)

Question 23

What is weak duality theorem? [5 - Duality]

Answer 23

Theorem: If x is primal feasible and p is dual feasible then b^Tp ≤ c^Tx.

Corollary: If x is primal feasible, p is dual feasible, and b⊤p = c⊤x, then x is optimal in the primal and p is optimal in the dual.

Question 24

What is strong duality theorem? [5 - Duality]

Answer 24

If a linear programming problem has an optimal solution, so does the dual, and the respective optimal costs are equal.

Question 25

What is economic interpretation of dual? [5 - Duality]

Answer 25

Each component pi of the optimal dual vector can be interpreted as the marginal cost (or shadow price) per unit increase of the ith requirement bi.

Question 26

Complementary Slackness theorem [5 - Duality]

Answer 26

Let x primal feasible and p dual feasible. Then, x and p are optimal for the respective problems if and only if
p_i((a_i)^T x−b_i)=0, ∀i
x_j(c_j −p^TA_j)=0, ∀j

Question 27

How does Problem Reformulation look for large-scale optimisation? [6 - Large Scale]

Answer 27

it is on the list == revise it!!!

Question 28

Which algorithm helps to solve large scale problems and what are key steps? [6 - Large Scale]

Answer 28

Answer - Benders Decomposition

Initialize Master Problem: Solve relaxed master problem.
Solve Dual Subproblems: For each scenario, solve the dual.
Check Optimality: Assess feasibility and optimality of solutions.
Add Cuts: Introduce optimality and feasibility cuts as needed.
Iterate: Refine master problem, iterate until convergence.

Question 29

What is LSA and General Framework for it? [7 - Sensitivity]

Answer 29

We are given an optimal basis B and optimal solution x*
- Assume some entry of A, b or c changes, or that a new variable or constraint is added.
* Under what conditions is the current basis still optimal?
* If these conditions are violated, how to find a new optimal solution without solving the problem from scratch?

Since B is optimal in original problem (P), we have:
Feasibility: B^(-1)b >= 0
Optimality: c^T - c_B^(T)B^(-1)*A >= 0^T

Question 30

LSA - Local Changes in b [7 - Sensitivity]

Answer 30

change is here: Ax=b+δ*e_i
Changes in b affect feasibility

(OPTIMAL RANGE FOR delta is on the list)

If δ is outside allowed range:
* Current solution is primal infeasible, but satisfies optimality conditions.
* Can apply dual simplex method starting from the current basis.

Question 31

LSA - Local Changes in c [7 - Sensitivity]

Answer 31

Suppose cj changes to cj + δ
-> examine condition c ̃⊤ ≥ c ̃^(T)B^(-1)A

Changes in c affect optimality conditions

Case 1: xj nonbasic
c_B: unaffected
Only inequality affected is the one for the reduced cost of xj ; we need:
cj +δ≥c_B^(T)B^(-1)A_j i.e.,δ≥−rj

• If this condition holds, current basis remains optimal.
• Otherwise, can apply primal simplex algorithm, starting at current BFS.

Case 2: xj basic - SEE THE LIST

Question 32

LSA - A New Variable is Added [7 - Sensitivity]

Answer 32

new LP
min c^Tx + c_(n+1)x(n+1)
Ax + A_(n+1)x_(n+1) = b
x >= 0

Need only examine optimality conditions:
B is optimal <=> r_(n+1) = c_(n+1) -c^(T)B^(-1)A_(n+1) >= 0

if r_(n+1) < 0 - add column to simplex tableau and use primal simplex algorithm, starting from current basis B.

Question 33

LSA - A New Constraint is Added [7 - Sensitivity]

Answer 33

LP stays the same, just 1 line added

(a_(m+1))^⊤*x = b_(m+1)

If current solution feasible, it is optimal

• Otherwise, apply dual simplex (obtaining a dual BFS may be difficult).

Question 34

LSA -Local Changes in A [7 - Sensitivity]

Answer 34

aij ← aij + δ

Assume Aj does not belong in the basis

Feasibility conditions - unaffected
Optimality conditions:
c_i -c_B^(T)B^(-1)A_i >= 0 when i != j
c_j - p^⊤*(Aj +δei)≥0 => rj −δpi ≥0
If condition is violated, continue with primal simplex

Question 35

How to model the requirement that event E2 can only occur if event E1 occurs [8 - Discrete]

Answer 35

yj = 1 if event Ej occurs , else yj = 0

E2 occurs only if E1 - using the constraint y2 ≤ y1

Question 36

The capacity of a facility can only be expanded if the facility has been built, how to express it? [8 - Discrete]

Answer 36

x ≤ My, where y is a binary, M is the capacity

Question 37

What is the key idea of Cutting Plane Algorithm? [9 - BB and Cutting Planes]

Answer 37

1) Solve the LP relaxation. Let * be an optimal solution.
2) If x* is integer, STOP; x* is an optimal solution to IP.
3) If not, add a linear inequality constraint to LP relaxation that all integer solutions satisfy, but x* does not; go to Step 1.

Note: Assumes that original LP relaxation is not unbounded

Question 38

Describe Gomory Cuts shortly [9 - BB and Cutting Planes]

Answer 38

SEE THE LIST!

Question 39

Describe BB algorithm shortly [9 - BB and Cutting Planes]

Answer 39

Set U = +∞ (the current best upper bound)

1 Branching. Select an active subproblem Fi
2 Pruning. If the subproblem is infeasible, delete it and go to 1.
3 Bounding. Otherwise, compute a lower bound b(Fi ) for the subproblem.
4 Pruning. If b(Fi) ≥ U, delete the subproblem and go to 1.
5 Partitioning. If b(Fi) < U, either obtain an optimal solution to the subproblem (update U if optimal value < U), or break the corresponding problem into further subproblems, which are added to the list of active subproblems (we can split by taking x_ and x^ here). Go back to step 1.

The algorithm stops (with optimal value U) when there are no active subproblems left.

Question 40

What is the connection between convexity and minima? [10 - Nonlinear optimisation]

Answer 40

Suppose that F is a convex set, f : F → R is a convex function, and x* is a local minimum of P. Then x⋆ is a global minimum of f over F. So - In convex optimization, any local minimum is a global minimum

Question 41

Gradient & Hessian [10 - Nonlinear optimisation]

Answer 41

Proposition. Suppose that f is twice differentiable on the open convex set S. Then, f is convex on S if and only if H(x) is sym- metric positive semi-definite (PSD) for all x ∈ S

Question 42

Key propositions about the convex functions [10 - Nonlinear optimisation]

Answer 42

1) If f1 (x ) and f2 (x ) are convex functions, and a,b ≥ 0, then f(x) := af1(x) + bf2(x) is a convex function
2) if f(x) is a convex function and x = Ay + b, then
g(y) := f(Ay + b) is a convex function

Question 43

What are necessary conditions for a local minimum? [11 -Optimality Conditions]

Answer 43

Theorem. Let f : Rn → R be twice continuously differentiable and let x⋆ ∈ Rn be a local minimum of f. Then
1 1st order necessary condition: ∇f(x⋆) = 0, and
2 2nd order necessary condition: ∇2f(x⋆) is PSD

Question 44

What are sufficient conditions for a local minimum?
[11 -Optimality Conditions]

Answer 44

Theorem. Let f : Rn → R be twice continuously differentiable. Suppose that x⋆ satisfies
1 1st order condition: ∇f(x⋆) = 0, and
2 2st order condition: ∇2f(x⋆) is PD
Then x⋆ is a local minimum.