# How is this problem quasi-convex?

I'm currently reading the following paper

B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. I. Jordan, and S. S. Sastry, “Kalman filtering with intermittent observations,” IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1453–1464, Sep. 2004, doi: 10.1109/TAC.2004.834121.

In Corollary 1 of Theorem 5 on page 1456 (right column), the authors consider the following optimization problem: \begin{aligned} \min_{\lambda,Y,Z} \quad & \lambda \\ \textrm{s.t.} \quad & 0 \leq \lambda \leq 1 \\ \quad & \Psi(\lambda,A,C,Y,Z) \succ 0 \\ \quad & 0 \preceq Y \preceq I \end{aligned} where $$\Psi(\lambda,A,C,Y,Z) = \begin{bmatrix}Y & \sqrt{\lambda}(YA + ZC) & \sqrt{1-\lambda}YA \\ \sqrt{\lambda}(A^T Y + C^T Z^T) & Y & 0 \\ \sqrt{1-\lambda}A^T Y & 0 & Y\end{bmatrix}$$ The matrices $$A$$ and $$C$$ are given as constant inputs and the matrices $$Y$$ and $$Z$$ are variables. The authors then write that this is a quasi-convex optimization problem in the variables $$(\lambda,Y,Z)$$ and that the solution can be obtained by iterating linear matrix inequality (LMI) feasibility problems and using bisection for the variable $$\lambda$$, as shown in the book "Linear Matrix Inequalities in System and Control Theory" by Boyd et al.

Unfortunately, the authors do not mention where in Boyd's book they are referring to. I'm also not sure why this is a quasi-convex problem, since the matrix variable $$Z$$ isn't necessarily positive semi-definite (so the feasible set does not consist only of the set of positive semi-definite matrices). I initially thought that this can be re-written as a generalized eigenvalue problem, but I'm not sure.

Any suggestions on why this is a quasi-convex problem and how it can be solved?

• Perhaps you can provide a reference to the paper you refer to. Dec 23, 2023 at 12:45
• @MarkL.Stone I've edited my question to include this reference, but I'm not sure how useful it is since it's mostly control theory. Dec 23, 2023 at 12:52

I won't prove the paper's claim that the optimization problem is quasiconvex. However, the problem is clearly a convex Linear SDP (LMI) for any fixed value of $$\lambda$$. That does not require $$Z$$ to be positive semidefinite, or even symmetric or square (note the the transpose on the "transposed" occurrence of $$Z$$).
• Thank you for this answer and for pointing me to Algorithm 4.1 in Boyd's book. Could you elaborate in your answer a bit more about how $Z$ can be non-square and still be a decision variable in an LMI feasibility problem? I'm reading over Boyd's LMI book mentioned in my question, but I could not find a case where some of the decision variables are not restricted to be positive semi-definite. If there is another example of an LMI feasibility problem that you know of where some of the decision variables are not square, could you please point me to it too? Dec 24, 2023 at 7:59
• The paper's $\Psi(Y,Z)$ is constrained to be PSD. It is symmetric (note the appearance of $Z^T$ in the entry which is the transpose of the entry involving $Z$). The matrix $Z$, which need not even be square, let alone symmetric, is not constrained to be PSD. For easch feasibility problem, $\lambda$ is treated as an input, hence $\Psi(Y,Z)$ is linear (affine) in the decision variables; hence constraining $\Psi(Y,Z)$ to be PSD is an LMI (Linear Matrix Inequality), a.l.a. Linear SDP.. Separately constraining $Y$ to be PSD iis redundant, because it's implied by constraining $\Psi(Y,Z)$ to be PSD. Dec 24, 2023 at 12:34
• So if I input this problem into cvxpy with a chosen $\lambda$, it will tell me if there exists a $Y$ and a $Z$ such that $\Psi(Y,Z) \succ 0$ (and it will also return a valid $Y$ and $Z$)? Dec 24, 2023 at 14:09
• I have no reason to think you are correct in your assertion that $Y \succeq I$ I did point out that although, $0 \preceq Y$, it is redundant to include that as an explicit constraint. Dec 27, 2023 at 12:10