0
$\begingroup$

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{equation} \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} \end{equation} 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?

$\endgroup$
2
  • 1
    $\begingroup$ Perhaps you can provide a reference to the paper you refer to. $\endgroup$ Commented Dec 23, 2023 at 12:45
  • $\begingroup$ @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. $\endgroup$
    – mhdadk
    Commented Dec 23, 2023 at 12:52

1 Answer 1

2
$\begingroup$

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$).

Algorithm 4.1 "Bisection method for quasiconvex optimization" in "Convex Optimization" by Boyd and Vandenberghe shows the bisection algorithm for solving quasiconvex optimization problems. It should be easy to implement the bisection algorithm for this problem in any DCP (Disciplined Convex Programming) convex optimization tool, such as CVX, CVXPY, CVXR, and YALMIP. It can be handled even more easily using CVXPY's Disciplined Quasiconvex Programming capability (DQCP), which implements the bisection algorithm for you under the hood.

This reference may slightly post-date the finalization of the paper; hence why it was not provided in the paper.

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – mhdadk
    Commented Dec 24, 2023 at 7:59
  • $\begingroup$ 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. $\endgroup$ Commented Dec 24, 2023 at 12:34
  • $\begingroup$ 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$)? $\endgroup$
    – mhdadk
    Commented Dec 24, 2023 at 14:09
  • 1
    $\begingroup$ All submatrices on the (block) diagonal of a positive semidefinite matrix must be positive semidefinite. If 1 by 1 submatrices are considered, that says that all diagonal elements of a positive semidefinite matrix must be positive semiodefinite, i.e., nonnegative (for 1 by 1 matrix). But this applies for j by j matrices on the diagonal, for any value of j from 1 to n , where the overall matrix is n by n,. $\endgroup$ Commented Dec 26, 2023 at 16:20
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 27, 2023 at 12:10

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.