Convex optimization with constraints involving matrix inverse

Question

I have the following convex optimization problem. I would like to ask is there any efficient way to solve it in Python? Can I use CVXOPT package? If so, any detailed instruction? Thanks a lot.

$$ \min_{T\in[0, \infty]^{10}}\sum_{i=1}^{10}T_ia_i $$ subject to $$ x^{\top}_j(\sum_{i=1}^{10}T_i x_ix_i^{\top})^{-1}x_j\leq b_j, \text{for all} \ j\in[10]. $$ Here, $\{a_1,\ldots, a_{10}\}\subset \mathbb R$ and $\{x_1, \ldots, x_{10}\}\subset\mathbb R^5$. 10 and 5 are just generic constants. If the inverse does not exist, we could replace it by pseudo inverse.

Answer 1

Yes this can be done, see the code block below. I'm using the CVXPY library, which is maintained by Boyd's group at Stanford and wraps the CVXOPT solvers (among other things.)

Assuming we've already constructed the input data from the Problem data section, the Construct the problem and Report solution parts take around 550ms in a simple benchmark I just ran. If we increase the problem size by a factor of 2, the solution takes around 3.6s, and 11.5s if we increase by a factor of 3.

import cvxpy as cp
import numpy as np

# Problem data.
# m is matrix dimension, n is number of terms
m, n = 5, 10
X = np.random.randn(m, n)
b = np.abs(np.random.randn(n)) # constraint upper bounds
a = np.abs(np.random.randn(n)) # objective coefficients

# Construct the problem.
T = cp.Variable(n)
A = cp.Variable((m,m))
objective = cp.Minimize(a @ T)
constraints = [A == X @ cp.diag(T) @ X.T] + \
              [T >= 0] + \
              [cp.matrix_frac(x, A) <= bi for x, bi in zip(X.T, b)]
problem = cp.Problem(objective, constraints)

# Report solution.
result = problem.solve()
print(result)