linear indepedence constraint qualification

licq.py

# Copyright [2024] Taylor Howell
# Linear independence constraint qualification (LICQ)

import numpy as np

# problem setup:
# minimize   0.5 x' P x + q' x
# subject to     A x = b

# Lagrangian
# 0.5 x' P x + q' x + y' (A x - b)

# KKT system
# [[P A'][A 0]] [[dx][dy]] = -[[P x + q + A' y][A x - b]]

## example
print("EXAMPLE:\n")
print("minimize   0.5 x' P x + q' x\n")
print("subject to     A x = b\n")

# dimensions
n = 2
m = 1

# data
P = np.eye(2)
q = np.array([[1.0], [1.0]])
A = np.array([[1.0, 1.0]])
b = np.array([1.0])
print("data:\n")
print(f"P:\n {P}\n")
print(f"q:\n {q}\n")
print(f"A:\n {A}\n")
print(f"b:\n {b}\n")

# KKT system
K = np.vstack([np.hstack([P, A.T]), np.hstack([A, np.zeros((m, m))])])
print(f"KKT matrix:\n {K}\n")

# rank
Krank = np.linalg.matrix_rank(K)
print(f"rank(KKT) = {Krank} / {n + m}\n")

## example: repeated constraints
# repeated constraints will violated LICQ
# KKT matrix will be rank deficient
print("EXAMPLE (repeated constraints):\n")
print("minimize   0.5 x' P x + q' x\n")
print("subject to     A x = b\n")
print("               A x = b\n")

AA = np.vstack([A, A])
print(f"A (repeated):\n {AA}\n")

# KKT system
KK = np.vstack(
    [np.hstack([P, AA.T]), np.hstack([AA, np.zeros((2 * m, 2 * m))])]
)
print(f"KKT matrix:\n {KK}\n")

# rank
KKrank = np.linalg.matrix_rank(KK)
print(f"rank(KKT (repeated)) == {KKrank} / {n + 2 * m}\n")

## fix with small regularization
reg = 1.0e-8

# KKT system (repeated + regularized)
KKr = np.vstack([np.hstack([P, AA.T]), np.hstack([AA, -reg * np.eye(2 * m)])])
print(f"KKT matrix (regularized):\n {KKr}\n")

# rank
KKrrank = np.linalg.matrix_rank(KKr)
print(f"rank(KKT (repeated + regularized)) == {KKrrank} / {n + 2 * m}\n")