def A_contains_xstar()

in figs/fig_4.py [0:0]

• 27 lines of code
• 3 McCabe index (conditional complexity)

def A_contains_xstar(xstar, A, perm):
    d = len(xstar)
    D = A.shape[0]
    Acon = np.zeros((d, D))
    Acon[:d, :d] = np.diag(np.ones(d))
    # Shuffle columns, to place true embedding on columns perm
    Acon = Acon[:, perm]
    Q = A @ np.linalg.pinv(A) - np.eye(D)
    A_eq = np.vstack((Acon, Q))
    b_eq = np.hstack((xstar, np.zeros(D)))
    
    c = np.zeros(D)
    
    x = cp.Variable(D)
    prob = cp.Problem(
        cp.Minimize(c.T * x),
        [
            A_eq @ x == b_eq,
            x >= -1,
            x <= 1,
        ],
    )
    prob.solve(solver=cp.ECOS)
    
    if prob.status == cp.OPTIMAL:
        has_opt = True
    elif prob.status == cp.INFEASIBLE:
        has_opt = False
    else:
        raise ValueError(prob.status)
    return has_opt, prob