где $\mathcal{K}$ - некоторый конус (обычно $\mathbb{R}^n_{+}$, $\mathbb{S}^n_{+}$ или конус второго порядка) или декартово произведение конусов
где $P_K$ - задача, которую можно решать IPM
Визуализацию и результат разбора можно посмотреть на сайте
Pro:
Contra:
In [3]:
import cvxpy as cvx
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
print(cvx.installed_solvers())
USE_COLAB = False
if USE_COLAB == False:
plt.rc("text", usetex=True)
Модельная задача - compressed sensing
\begin{align*} & \min_x \|x\|_1\\ \text{s.t. } & Ax = b, \end{align*}где $A \in \mathbb{R}^{m \times n}$ и $n \gg m$
In [4]:
n = 1000
m = 10
x_true = np.random.randn(n)
x_true[np.abs(x_true) > 0.05] = 0
print("Num of nnz in x = {}".format(np.sum(x_true != 0)))
A = np.random.randn(m, n)
b = A.dot(x_true)
In [5]:
x = cvx.Variable(n)
objective = cvx.norm1(x)
constr = [A*x == b]
problem = cvx.Problem(cvx.Minimize(objective), constr)
problem.solve(verbose=True, max_iter=3000)
Out[5]:
In [6]:
tol= 1e-4
print(np.linalg.norm(A.dot(x.value) - b))
print(np.linalg.norm(A[:, np.abs(x.value) > tol].dot(x.value[np.abs(x.value) > tol]) - b))
print(np.linalg.norm(x_true - x.value))
print("Num nnz = {}".format(np.sum(np.abs(x.value) > tol)))
In [7]:
plt.figure(figsize=(10, 8))
plt.plot(x.value, label=r"$x^*$")
plt.plot(x_true, label=r"True $x$")
plt.legend(fontsize=26)
plt.yticks(fontsize=26)
Out[7]:
In [8]:
plt.figure(figsize=(9, 7))
plt.semilogy(np.sort(np.abs(x.value))[::-1])
plt.ylabel("$|x_i|$", fontsize=24)
plt.yticks(fontsize=24)
plt.xlabel(r"Sorted index of $x^*$", fontsize=24)
plt.xticks(fontsize=24)
Out[8]:
In [9]:
# Non-affine equality constraint
y = cvx.Variable(1)
obj = cvx.Minimize(cvx.power(y, 3))
problem = cvx.Problem(obj, [cvx.power(y - 3, 2) == 0])
problem.solve(verbose=True)
In [10]:
# Non-convex objective function
y = cvx.Variable(2)
obj = cvx.Minimize(y[0]**2 - y[1]**2)
problem = cvx.Problem(obj)
problem.solve(verbose=True)
Картинка отсюда
In [1]:
import torch
n = 5
A = torch.randn((n, n), requires_grad=True)
b = torch.randn((n,))
x = torch.randn((n,), requires_grad=True)
f = 0.5 * x @ A @ x - b @ x
f.backward()
print(f)
print(f.item())
In [2]:
manual_grad_x = 0.5 * (A + A.t()) @ x - b
print(manual_grad_x.data)
print(x.grad.data)
In [3]:
manual_grad_A = 0.5 * torch.ger(x, x)
print(manual_grad_A.data)
print(A.grad.data)
print(torch.norm(manual_grad_A.data - A.grad.data).item())