MISDP/MISOCP в cvxpy

Question 1

Я пытаюсь решить следующую проблему в CVXPY.

Проблема заключается в смешанном целочисленном SDP из-за матрицы PSD, которую мы решаем. Однако, согласно этому списку, похоже, что ни один из решателей не может справиться с такой проблемой.

Можем ли мы использовать тот факт, что A может ли матрица 2x2 каким-то образом преобразовать это в задачу SOC со смешанным целым числом?

import cvxpy as cp
import matplotlib.pyplot as plt
import numpy as np

np.random.seed(271828) 
m = 2; n = 50
x = np.random.randn(m,n)

off = cp.Variable(boolean=True)

A = cp.Variable((2,2), PSD=True)
b = cp.Variable(2)
obj = cp.Maximize(cp.log_det(A))
constraints = [ cp.norm(A@x[:,i] + b) <= 1 + 20*off for i in range(n) ]
constraints += [cp.sum(off) <= 20]

prob = cp.Problem(obj, constraints)
optval = prob.solve(solver='XPRESS', verbose=False) # seems to work, although it's not super accurate

print(f"Optimum value: {optval}")

# plot the ellipse and data
angles = np.linspace(0, 2*np.pi, 200)
rhs = np.row_stack((np.cos(angles) - b.value[0], np.sin(angles) - b.value[1]))
ellipse = np.linalg.solve(A.value, rhs)

plt.scatter(x[0,:], x[1,:])
plt.plot(ellipse[0,:].T, ellipse[1,:].T)
plt.xlabel('Dimension 1'); plt.ylabel('Dimension 2')
plt.title('Minimum Volume Ellipsoid')
plt.show()

Question 2

Допустим, A=[[x,z], [z,y]], тогда вы сможете максимально sqrt(det(A)) (что эквивалентно вашей цели). Обратите внимание, что

det(A) = xy-z^2

так что максимизация sqrt(det(A)) это то же самое, что максимизировать u подлежит

xy - z^2 >= u^2

эквивалентно

xy >= z^2 + u^2

Это (почти) вращающийся конус второго порядка в смысле https://docs.mosek.com/modeling-cookbook/cqo.html#rotated-quadratic-cones

Я думаю, что-то вроде

x >= quad_over_lin([z,u], y)

(не проверял синтаксис) может быть наиболее удобным способом выразить это в cvxpy.

Обратите внимание, что определение конуса и quad_over_lin также накладывает x,y>=0 таким образом, вам это не нужно отдельно, и ограничения на конические связи автоматически гарантируют A.

Michal Adamaszek · Answer 1 · 2021-11-24T09:08:37

Допустим, A=[[x,z], [z,y]], тогда вы сможете максимально sqrt(det(A)) (что эквивалентно вашей цели). Обратите внимание, что

det(A) = xy-z^2

так что максимизация sqrt(det(A)) это то же самое, что максимизировать u подлежит

xy - z^2 >= u^2

эквивалентно

xy >= z^2 + u^2

Это (почти) вращающийся конус второго порядка в смысле https://docs.mosek.com/modeling-cookbook/cqo.html#rotated-quadratic-cones

Я думаю, что-то вроде

x >= quad_over_lin([z,u], y)

(не проверял синтаксис) может быть наиболее удобным способом выразить это в cvxpy.

Обратите внимание, что определение конуса и quad_over_lin также накладывает x,y>=0 таким образом, вам это не нужно отдельно, и ограничения на конические связи автоматически гарантируют A.

И вот несколько легких развлечений, связанных с вашей проблемой: twitter.com/mosektw/status/1190259248250445824

MISDP/MISOCP в cvxpy

Вопрос

Лучший ответ

На других языках

Эта страница на других языках

Популярное в этой категории

Популярные вопросы в этой категории