APM261: Quiz 3. Convex Analysis and Polyhedral Sets

Quiz 3. Convex Analysis and Polyhedral Sets

Enter your name:

Each question has only one correct answer. The results of the quiz do not affect the final marks.

1: A face of a feasible region is given by the convex combination of four extreme points:

x = a₁ x₁ + a₂ x₂ + a₃ x₃ + a₄ x₄

where vectors x₁, x₂, x₃, x₄ are linearly independent, while numbers a₁, a₂, a₃, a₄ >= 0, and

a₁ + a₂ + a₃ + a₄ = 1

What is the dimension of the face?

The face has zero dimension
The face is one-dimensional
The face is two-dimensional
The face is three-dimensional

2: Consider two extreme points of a convex set: A(0,1,2) and B(3,4,8). Identify the point C which belongs to a line segment joining A and B.

C(3/2,5/2,7/2)
C(1,2,4)
C(0,1,3)
C(0,4,8)

3: An unbounded feasible region is given by the set of constraints:

- 3 x + 7 y <= 13
6 x + y >= 4

where both x and y are non-negative. Find two extreme directions d1 and d2 in the feasible region.


 d1(-3,7)

and d2(6,1)


 d1(1,0)

and d2(1,6)


 d1(1,0)

and d2(7,3)


 d1(0,1)

and d2(1,-6)

4: The feasible region of a linear programming problem has four extreme points: A(0,0), B(1,1), C(0,1), and D(1,0). Identify an optimal solution for minimization problem with the objective function

z = 2 x - 2 y

A unique solution at C
A unique solutions at D
An alternative solution at a line segment between A and B
An unbounded solution

5: Degeneracy occurs when

Basic variables are positive but some of non-basic variables have negative values
The basic matrix is singular, it has no inverse
Some of basic variables have zero values
Some of non-basic variables have zero values

Your Results: