MISDP/MISOCP in cvxpy

Question 1

Sto cercando di risolvere il seguente problema in CVXPY.

Il problema è un mixed-integer SDP a causa del PSD matrice stiamo risolvendo. Tuttavia, secondo questa lista sembra come se nessuno dei solutori in grado di gestire un tale problema.

Si può usare il fatto che A è una matrice 2x2 per convertire in qualche modo questo per un mixed-integer SOCP problema?

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

Diciamo A=[[x,z], [z,y]]quindi, è possibile massimizzare sqrt(det(A)) (che è l'equivalente per il tuo obiettivo). Nota che

det(A) = xy-z^2

modo da massimizzare sqrt(det(A)) è lo stesso come massimizzare u soggetto a

xy - z^2 >= u^2

equivalentemente

xy >= z^2 + u^2

Questo è (quasi) una ruotata di secondo ordine cono nel senso di https://docs.mosek.com/modeling-cookbook/cqo.html#rotated-quadratic-cones

Penso che qualcosa di simile

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

(non ho testato la sintassi) può essere il modo più conveniente per esprimere in cvxpy.

Si noti che la definizione del cono e di quad_over_lin impone anche x,y>=0 quindi non c'è bisogno che separatamente, e conica vincoli automaticamente garantisce PSDness di A.

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

Diciamo A=[[x,z], [z,y]]quindi, è possibile massimizzare sqrt(det(A)) (che è l'equivalente per il tuo obiettivo). Nota che

det(A) = xy-z^2

modo da massimizzare sqrt(det(A)) è lo stesso come massimizzare u soggetto a

xy - z^2 >= u^2

equivalentemente

xy >= z^2 + u^2

Questo è (quasi) una ruotata di secondo ordine cono nel senso di https://docs.mosek.com/modeling-cookbook/cqo.html#rotated-quadratic-cones

Penso che qualcosa di simile

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

(non ho testato la sintassi) può essere il modo più conveniente per esprimere in cvxpy.

Si noti che la definizione del cono e di quad_over_lin impone anche x,y>=0 quindi non c'è bisogno che separatamente, e conica vincoli automaticamente garantisce PSDness di A.

E qui è un po ' di luce di intrattenimento legati al tuo problema: twitter.com/mosektw/status/1190259248250445824

MISDP/MISOCP in cvxpy

Domanda

Migliore risposta

In altre lingue

Questa pagina è in altre lingue

Popolare in questa categoria

Domande popolari in questa categoria