KKT For LP Check

Problem

Verify KKT conditions for the LP min c dot x subject to A x <= b and x >= 0.

Check primal feasibility, dual feasibility c + A^T y >= 0 with y >= 0, and complementary slackness y dot (b - A x) = 0 and x dot (c + A^T y) = 0, all within tol. Return True when every condition holds.

Hint

Stationarity gives the reduced cost vector z = c + A^T y.

Test cases

case 1

in: [[0,0],[0],[1,1],[[1,1]],[1],1e-9]

expected: true

case 2

in: [[1,0],[1],[-1,1],[[1,1]],[1],1e-9]

expected: true

case 3

in: [[1,0],[0],[-1,1],[[1,1]],[1],1e-9]

expected: false

case 4

in: [[2,0],[0],[1,1],[[1,1]],[1],1e-9]

expected: false

Starter codePython

def kkt_lp_check(x, y, c, A, b, tol):
    # Your code here
    pass

4 test cases · run your code against them in the editor