python-3.xcvxpyconvex-optimization

How to optimize trace of inverse in CVXPY?


How can I formulate an objective function that minimizes the trace of an inverse matrix using cvxpy?

Concretely the following problem:

enter image description here

enter image description here

subject to:

enter image description here

I have seen the trace_inv objective function in cvx but so far was not able to figure out how to translate this to cvxpy.


Solution


  • Edit:
    They just released CVXPY 1.3 with the objective function tr_inv().

    https://www.cvxpy.org/updates/index.html#cvxpy-1-3

    https://www.cvxpy.org/api_reference/cvxpy.atoms.other_atoms.html#tr-inv


    I figured it out by looking at the source code on github, https://github.com/cvxpy/cvxpy/tree/master/cvxpy/atoms.

    The function matrix_frac() fits the problem.

    Here is a minimal example:

    import cvxpy as cp
    
    n = 20
    k = 5
    
    A_list = []
    for i in range(n):
        A = np.random.uniform(0,10,(6,6))
        A_list.append(A.T@A)
    
    # Create two scalar optimization variables.
    z = cp.Variable(n)
    
    # Create two constraints.
    constraints = [z >= 0,
                   z <= 1,
                  np.ones((n,))@z == k]
    
    cost = sum([z[i] * A_list[i] for i in range(n)])
    
    # Form objective.
    obj = cp.Minimize(cp.matrix_frac(np.eye(6), cost))
    
    # Form and solve problem.
    prob = cp.Problem(obj, constraints)
    
    prob.solve()  # Returns the optimal value.
    
    print("status:", prob.status)
    print("optimal value", prob.value)
    
    # compute trace of inverse using z
    S = np.zeros(A_list[0].shape)
    for i in range(len(z.value)):
        S += z.value[i] * A_list[i]
    value = np.trace(np.linalg.inv(S))
    
    print("value", value)
    print(prob.value == value)
    

    Output:

    status: optimal
    optimal value 0.02061809722699777
    value 0.02061809722699777
    True