<jupyter_start><jupyter_text>**1** Хотим минимизировать $c^T x$ при условии $Ax = b, x \ge 0$.$L(x, \lambda, \mu) = c^T x - \lambda^T x + \mu^T (Ax - b)$$q(\lambda, \mu) = \begin{cases} -\mu^T b,\ c^T - \lambda^T + \mu^T A = 0\\ -\infty,\ c^T - \lambda^T + \mu^T A \neq 0 \end{cases} $Двойственная задача: хотим максимизировать $-\mu^T b$ при условии $c^T - \lambda^T + \mu^T A = 0, \lambda \ge 0$.<jupyter_code>def solve_dual_task(A, b, c):
    mu, lambda_ = cp.Variable(A.shape[0]), cp.Variable(A.shape[1])
    cp.Problem(
        cp.Minimize(mu.T @ b),
        [c.T - lambda_.T + mu.T @ A == 0, lambda_ >= 0]
    ).solve()
    return mu.value, lambda_.value
A = np.array([[3, 2], [3, 4]]) 
b = np.array([4, 6])
c = np.array([41, 13])
solve_dual_task(A, b, c)<jupyter_output><empty_output><jupyter_text>Заметим, что для ненулевых $\lambda_i$ соответствующий $x_i = 0$, значит, достаточно решить систему $Ax = b$ для остальных.<jupyter_code>def solve(A, b, c):
    _, lambda_ = solve_dual_task(A, b, c)
    x = np.zeros(A.shape[1])
    zero_lambda = np.isclose(lambda_, 0)
    A_ = A[:, zero_lambda].T
    x[zero_lambda] = np.linalg.inv(A_ @ A_.T) @ A_ @ b
    return x
solve(A, b, c)<jupyter_output><empty_output><jupyter_text>**2** Хотим минимизировть максимальное из расстояний от центра до точек.<jupyter_code>def min_ball(X):
    c = cp.Variable((1, X.shape[1]))
    r = cp.Problem(
        cp.Minimize(
            cp.max(cp.sum((c - X) ** 2, 1))
        )
    )
    r.solve()
    return c.value, np.sqrt(r.value)
min_ball(np.array([
    [0, 3, 4],
    [5, 0, 0],
    [-5, 0, 0],
    [-1, 0, -2],
    [1, 0, 2]
]))<jupyter_output><empty_output><jupyter_text>**3** Хотим максимизироваать $\min \limits_{y_i = 1} a^T x_i - \max \limits_{y_i = 0} a^T x_i$, что то же самое что минимизировать $p - q$ при условии $p \ge \max \limits_{y_i = 0} a^T x_i, q \le \min \limits_{y_i = 1} a^T x_i$. Будем считать что вектор $a$ лежит в единичном шаре.<jupyter_code>def SVM(X, Y):
    a = cp.Variable((1, X.shape[1]))
    p, q = cp.Variable(2)
    cp.Problem(cp.Minimize(p - q),
               [p >= a @ x for x in X[Y == 0]] + \
               [q <= a @ x for x in X[Y == 1]] + \
               [cp.norm(a) <= 1]).solve()
    return a.value
SVM(np.array([[1, 2, 4], [3, 5, 6], [7, 8, -3]]), np.array([0, 1, 1]))<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup