 Solution

ID: past-exam-of-the-probability-statistics-and-options-ii-course-of-the-university-of-oxford/2009/t/t2/a/ii/solution

Feasibility makes both sums

x^{T} (A^{T} y - c)

and

y^{T} (b - A x)

nonnegative. Their sum is the gap

b^{T} y - c^{T} x

. At optimal points the assumed equal optimal values make that gap zero, forcing each nonnegative sum to vanish. Hence

(y^{T} A - c^{T}) x = 0, y^{T} (A x - b) = 0.

In fact every individual nonnegative product in the two sums vanishes, giving the componentwise complementary slackness conditions too.

 New to topics? Read the docs here!