5
$\begingroup$

Let us suppose $I_1, \ldots, I_n$ are symmetric and positive definite matrices. Let $\mathbf{u}$ be the vector with $n$ 1s. I'm interested in the following optimization problem:

$$\min \; u^T (x_1I_1+x_2I_2+\ldots + x_nI_n)^{-1}u$$

such that $0 \leq x_i\leq 1$ and $\sum x_i \leq 1$.

Question: Is the above optimization problem convex over the domain of $x_i$s?

$\endgroup$
2
  • $\begingroup$ Which variables are you optimizing over? $\endgroup$
    – batwing
    Nov 19, 2021 at 21:44
  • $\begingroup$ We are optimizing over $x_i$s. $\endgroup$
    – Jagadish
    Nov 20, 2021 at 2:51

1 Answer 1

9
$\begingroup$

This is a convex optimization problem, which can easily be formed (and solved), in CVX, among other convex optimization tools.

Let $A = x_1I_1 + x_2I_2 + ... + x_nI_n$, where the $I_i$ are m by m matrices (this does not require $m = n)$.

$A$ is symmetric positive definite, because each $x_iI_i$ is symmetric positive definite, and hence the sum of these terms also is (unless all $x_i = 0$ (in which case it would still be symmetric positive semidefinite), but the optimizer would never choose that solution because it is non-optimal).

The objective function is a matrix fractional form, as is shown in example 3.4 of Convex Optimization, by Boyd and Vandenberghe. This is done by use of epigraph formulation, which utilizes a semidefinite constraint, which is shown in the YALMIP code at the end of this post.

CVX (under MATLAB) conveniently has a function, matrix_frac, which under the hood, converts this to the epigraph formulation shown in example 3.4 (and below in the YALMIP (under MATLAB) code). That formulation can be used if using a convex optimization tool, such as YALMIP, which doesn't have a built-in matrix_frac function. The popular tool, CVXPY (under Python), also has a matrix_frac, which is used the same way as CVX's.

The CVX code below (as well as the YALMIP code at the end of this post) assumes that I is an m by m by n array, for which $I(:,:,i) = I_i$.

cvx_begin
variable x(n)
A=0;
for i=1:n
  A=A+x(i)*I(:,:,i);
end
minimize(matrix_frac(ones(m,1),A))
0 <= x <= 1
sum(x) <= 1
cvx_end

After successful execution, x will be populated with the optimal solution.

Note: the formulation could be changed, with no effect on optimal solution, to change the constraints to 0 <= x , sum(x) == 1.

Here is the explicit epigraph formulation, which I'll show in YALMIP.

x = sdpvar(n,1);
t = sdpvar;
A=0;
for j=1:n
  A=A+x(j)*I(:,:,j);
end
Constraints = [[A ones(m,1);ones(1,m) t] >= 0,0 <= x <= 1,sum(x) <= 1];
optimize(Constraints,t) % minimizes t, subject to Constraints

at the successful conclusion of which, value(x) is the optimal value of x. Note that the constraint [A ones(m,1);ones(1,m) t] >= 0 denotes in YALMIP that the matrix [A ones(m,1);ones(1,m) t] is constrained to be symmetric positive semidefinite. Minimizing t, subject to that semidefinite constraint is the epigraph formulation previously mentioned.

$\endgroup$
4
  • 1
    $\begingroup$ The matrix A isn't positive definite for $x_1 = \ldots = x_n = 0$. $\endgroup$
    – joni
    Nov 19, 2021 at 21:49
  • 1
    $\begingroup$ @jon, you are correct. I originally misread the sum constraint as =, not $\le$. But actually, the sum will be driven to 1 at optimality, even if an inequality. $\endgroup$ Nov 19, 2021 at 21:56
  • $\begingroup$ @MarkL.Stone The matrix fractional form xY^{-1}x' in Example 3.4 has n^2+n variables but my problem has only n variables. So the correspondence is not so direct, isn't. it? To prove convexity I'd have to restrict the values of the n^2 variables by writing linear constraints. Is that correct? $\endgroup$
    – Jagadish
    Nov 21, 2021 at 6:34
  • $\begingroup$ The Schur Complement epigraph semidefinite constraint formulation applies. The CVX and YALMIP code shown solves the problem, without any additional constraints needed.. If you wanted to, you could have an extra m*(m+1)/2 variables for each of the $I_i$, then constrain them to their numerical values, and it would still be a valid formulation, but with a lot of extra variables and constraints accomplishing nothing. Your what is "x" in example 3.4 also a constant - no matter, just a special case of being a variable. $\endgroup$ Nov 21, 2021 at 13:07

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.