5
$\begingroup$

I have a question related to optimization.

Given natural numbers $n$ and $\ell$, matrices ${\bf K}_1, \dots, {\bf K}_\ell \in \Bbb R^{n \times n}$ and a vector ${\bf y} \in \Bbb R^n$, define $${\bf K} := s_1 {\bf K}_1 + \dots + s_\ell {\bf K}_\ell + \lambda {\bf I}_n$$ where $s_1, \dots, s_\ell, \lambda \in \Bbb R$, $\lambda > 0$ and ${\bf I}_n$ is the identity matrix. It is also given that the ${\bf K}_1, \dots, {\bf K}_\ell$ are all symmetric and semidefinite so ${\bf K}$ is invertible. The problem is to minimize ${\bf y}^\top {\bf K}^{-1} {\bf y}$ under the constraints $s_1, \dots s_\ell \ge 0$ and $s_1 + \dots + s_\ell = 1$.


I have searched that this problem is related to semidefinite programming (SDP) but since I have no background on optimization theory, I cannot proceed any further. How can I solve this problem?

$\endgroup$
5
  • $\begingroup$ Are there any conditions on the matrices $K_i$? It is not even clear that clear that $K^{-1}$ exists for general chocies of $K_i$ and $s_i$. If there is a feasible set of $s_i$'s such that $K^{-1}$ does not exist, then one can potentially perturb these values to make the objective arbitrarily large $\endgroup$
    – whpowell96
    Commented May 16, 2023 at 3:29
  • 2
    $\begingroup$ If you have an additional constraint that $K$ is positive definite, then your problem can be reformulated as $\min_{s_1, \dots, s_l, t} t$ subject to $y^T K^{-1} y \leq t$, $K = s_1 K_1 + \dotsb + s_n K_n \succ 0$, $s_1, \dots, s_l \geq 0$, $s_1 + \dotsb + s_l = 1$. The constraint $y^T K^{-1} y \leq t$ can be converted into $\begin{pmatrix} t & y^T \\ y & K\end{pmatrix} \succeq 0$. This is semidefinite programming. $\endgroup$
    – nowhere
    Commented May 16, 2023 at 5:24
  • $\begingroup$ Your comments are definitely right so I editted the problem. Could you recommend any references to solve this problem? $\endgroup$
    – 박희인
    Commented May 16, 2023 at 9:08
  • 1
    $\begingroup$ Take a look at this $\endgroup$ Commented May 16, 2023 at 9:24
  • $\begingroup$ Since the matrices are constant, and the $s_i$ are the only variables, it looks like a tweak of the constraint in @RodrigodeAzevedo 's comment should work; however, since the author is new to the field, should probably be written out. $\endgroup$
    – Zim
    Commented May 16, 2023 at 9:28

1 Answer 1

3
$\begingroup$

Let me expand on my earlier comment and @RodrigodeAzevedo 's reference.

Your original problem is \begin{align*} \min_{s_1, \dots, s_\ell, \lambda, \mathbf{K}} & \quad \mathbf{y}^T \mathbf{K}^{-1} \mathbf{y}\\ \text{subject to} & \quad \mathbf{K} = s_1 \mathbf{K}_1 + \dotsb + s_\ell \mathbf{K}_\ell + \lambda \mathbf{I}_n\\ & \quad s_1, \dots, s_\ell \geq 0\\ & \quad s_1 + \dotsb + s_\ell = 1\\ & \quad \lambda > 0\\ & \quad \mathbf{K} \succ 0\\ \end{align*}

If you just want to find a numerical solution to the problem, then CVX or CVXPY can do the job. Use the matrix_frac function (reference here) as your objective, write out all of the above constraints, and that should solve the problem. For guidance on using CVX or CVXPY, first check their documentation. They provide plenty of examples to get you started. In case you need additional help with coding, post your question on StackOverflow.

If you want to understand how matrix_frac works and how it relates to semidefinite programming, then here are the details.

First, write your problem in equivalent form \begin{align*} \min_{s_1, \dots, s_\ell, \lambda, \mathbf{K}, t} & \quad t\\ \text{subject to} & \quad \mathbf{y}^T \mathbf{K}^{-1} \mathbf{y} \leq t\\ & \quad \mathbf{K} = s_1 \mathbf{K}_1 + \dotsb + s_\ell \mathbf{K}_\ell + \lambda \mathbf{I}_n\\ & \quad s_1, \dots, s_\ell \geq 0\\ & \quad s_1 + \dotsb + s_\ell = 1\\ & \quad \lambda > 0\\ & \quad \mathbf{K} \succ 0\\ \end{align*}

We want to turn the constraints $\mathbf{y}^T \mathbf{K}^{-1} \mathbf{y} \leq t$, $\mathbf{K} \succ 0$ into a condition involving some matrix being positive semidefinite. The key is Schur complement: If you have a symmetric block matrix $X = \begin{pmatrix} A & B^T\\ B & C \end{pmatrix}$ and $C \succ 0$, then $X \succeq 0$ if and only if $A - B^T C^{-1} B \succeq 0$.

Using Schur complement, we find that the constraints are equivalent to $\begin{pmatrix} t & \mathbf{y}^T\\ \mathbf{y} & \mathbf{K} \end{pmatrix} \succeq 0$, $\mathbf{K} \succ 0$.

Now your problem can be expressed as \begin{align*} \min_{s_1, \dots, s_\ell, \lambda, \mathbf{K}, t} & \quad t\\ \text{subject to} & \quad \begin{pmatrix} t & \mathbf{y}^T\\ \mathbf{y} & \mathbf{K} \end{pmatrix} \succeq 0\\ & \quad \mathbf{K} = s_1 \mathbf{K}_1 + \dotsb + s_\ell \mathbf{K}_\ell + \lambda \mathbf{I}_n\\ & \quad s_1, \dots, s_\ell \geq 0\\ & \quad s_1 + \dotsb + s_\ell = 1\\ & \quad \lambda > 0\\ & \quad \mathbf{K} \succ 0\\ \end{align*} This is a bona fide semidefinite program: You just have a linear objective, linear equality and inequality constraints, and semidefinite matrix constraints.

Note that for implementation purposes, you don't need to manually express your problem in this last form. matrix_frac automatically does this reduction for you behind the scene.

$\endgroup$
1
  • $\begingroup$ Wow, great thanks! $\endgroup$
    – 박희인
    Commented May 17, 2023 at 23:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .