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.

  • 1
    $\begingroup$ You've used $i$ for $x_{i}$ outside of the sum and $x_{i}$ inside of the sum- this is unclear and should be rewritten to use a different index for the sum. $\endgroup$ Commented Aug 17, 2019 at 18:12
  • 1
    $\begingroup$ What makes you believe that this is a convex optimization problem? $\endgroup$ Commented Aug 17, 2019 at 19:10
  • $\begingroup$ What kind of expression is $(T_ix_ix_i^T)$? If it is matrix-times-vector times vector-transposed, so something like $y_i x_i^T$, then it's a rank-one matrix, but a rank-one matrix does not have an inverse... $\endgroup$ Commented Aug 17, 2019 at 23:08
  • $\begingroup$ Or are you saying that the sum of the ten rank-one matrices has an inverse? $\endgroup$ Commented Aug 17, 2019 at 23:08
  • $\begingroup$ @WolfgangBangerth I believe the $T$’s are scalars. The ambient dimension is 5 in this case, so for almost all choices of the parameters the inverse will exist. $\endgroup$
    – cdipaolo
    Commented Aug 18, 2019 at 5:24

1 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()

  • $\begingroup$ Thank you so much! It works well. $\endgroup$
    – Botao Hao
    Commented Aug 18, 2019 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.