2
$\begingroup$

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following problem $$ \begin{aligned} \min_x \quad & \Tr(WF(x)) \\ \textrm{s.t.} \quad & 0 < x \leq 1 \end{aligned} \tag{1} $$ where $\Tr(\cdot)$ is the trace operator, $W$ is positive semi-definite and $$ \begin{aligned} F(x) = \argmax_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & \begin{bmatrix} AVA^T + Q - V & \sqrt{x}(AVA^T + Q)C^T \\ \sqrt{x} C(AVA^T + Q) & C(AVA^T + Q)C^T + R \end{bmatrix} \succeq 0 \\ \quad & V \succeq 0 \end{aligned} \tag{2} $$ where $A \in \mathbb R^{n \times n}, C \in \mathbb R^{m \times n},Q \succeq 0,$ and $R \succ 0$. Suppose that there exists a $V \succeq 0$ such that $AVA^T + Q - V \succeq 0$. Note that the positive semi-definiteness constraint in $(2)$ is equivalent to (via the Schur complement lemma) the following "modified" algebraic Riccati inequality: $$ AVA^T + Q - V - x(AVA^T + Q)C^T(C(AVA^T + Q)C^T + R)^{-1}C(AVA^T + Q) \succeq 0 $$ Question: Assuming that $(2)$ has a unique solution for every value of $x \in (0,1]$ (such that $F$ in $(2)$ is well-defined on $(0,1]$), is it possible to show that the problem in $(1)$ is convex? I'm trying to prove this by showing that $F(x)$ is convex in $x$. However, given that $x$ appears in the constraint in $(2)$, I'm not sure how to go about this.

$\endgroup$
5
  • 1
    $\begingroup$ This is a bi-level optimization problem, so I believe non-convex. But you could grid in $x$, and solve the convex optimization problem (2) for each fixed grid value of $x$. Then pick the best value of $x$, with its corresponding optimal value of $V$. $\endgroup$ Jan 11 at 13:11
  • $\begingroup$ @MarkL.Stone thanks for the feedback. Will definitely look into grid search. Out of curiosity, are bilevel optimization problems always non-convex? $\endgroup$
    – mhdadk
    Jan 11 at 15:16
  • $\begingroup$ Some trivial) bi-level problems can be expressed (formulated) as single level convex problems. $\endgroup$ Jan 11 at 15:39
  • $\begingroup$ Since $x$ is a scalar on $(0, 1]$, this is really just "line search" in the outer level, and since the inner problem is convex, this approach is likely to work well. $\endgroup$
    – Max
    Jan 12 at 12:12
  • $\begingroup$ @Max thank you for the feedback. $\endgroup$
    – mhdadk
    Jan 12 at 17:05

1 Answer 1

0
$\begingroup$

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$It seems that $x = 1$ should solve $(1)$. My reasoning for this is as follows.

Because $x \neq 0$, then $\frac{1}{x}$ always exists, and so the constraint $$ \begin{bmatrix} AVA^T + Q - V & \sqrt{x}(AVA^T + Q)C^T \\ \sqrt{x} C(AVA^T + Q) & C(AVA^T + Q)C^T + R \end{bmatrix} \succeq 0 $$ in $(2)$ can be transformed as follows $$ \begin{align} &\begin{bmatrix} AVA^T + Q - V & \sqrt{x}(AVA^T + Q)C^T \\ \sqrt{x} C(AVA^T + Q) & C(AVA^T + Q)C^T + R \end{bmatrix} \succeq 0 \\ &\iff AVA^T + Q - V - x(AVA^T + Q)C^T(C(AVA^T + Q)C^T + R)^{-1}C(AVA^T + Q) \succeq 0 \\ &\iff AVA^T + Q - V - (AVA^T + Q)C^T\left(\frac{1}{x}[C(AVA^T + Q)C^T + R]\right)^{-1}C(AVA^T + Q) \succeq 0 \\ &\iff \begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & \frac{1}{x}[C(AVA^T + Q)C^T + R] \end{bmatrix} \succeq 0 \\ &\iff \begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & 0 \end{bmatrix} + \frac{1}{x}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} \succeq 0 \\ &\iff \begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & 0 \end{bmatrix} \succeq -\frac{1}{x}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} \end{align} $$ Because $\frac{1}{x} \in [1,\infty)$ and the matrix $$ \begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} $$ is positive semi-definite (since $R$ is positive definite and $AVA^T + Q$ is positive semi-definite), then the matrix $$ -\frac{1}{x}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} $$ is negative semi-definite for every $x \in (0,1]$.

Moreover, as $x$ decreases from $1$ towards $0$, the feasible set in $(2)$ gets larger in the following sense. Fix any $x_1$ and $x_2$ in $(0,1]$ such that $x_1 < x_2$. Then, $$ -\frac{1}{x_1}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} \prec -\frac{1}{x_2}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} $$ and so $$ \begin{align} &\begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & 0 \end{bmatrix} \succeq -\frac{1}{x_2}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} \\ &\implies \begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & 0 \end{bmatrix} \succeq -\frac{1}{x_1}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix} \end{align} $$ Therefore, the set $$ \mathcal G(x_2) = \left\{V \succeq 0 \ \Bigg| \begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & 0 \end{bmatrix} \succeq -\frac{1}{x_2}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix}\right\} $$ is a subset of $$ \mathcal G(x_1) = \left\{V \succeq 0 \ \Bigg| \begin{bmatrix} AVA^T + Q - V & (AVA^T + Q)C^T \\ C(AVA^T + Q) & 0 \end{bmatrix} \succeq -\frac{1}{x_1}\begin{bmatrix} 0 & 0 \\ 0 & C(AVA^T + Q)C^T + R \end{bmatrix}\right\} $$ for every $x_1 < x_2$ and $x_1,x_2 \in (0,1]$.

Furthermore, because the objective function in $(2)$ is $\Tr(V)$, a linear and monotonically increasing function of $V$, then $\argmax_V \Tr(V)$ should either increase or stay the same as the size of the feasible set increases, which occurs when $x$ decreases.

The rate of increase of the size of the feasible set, however, cannot be constant, as the map $x \mapsto -\frac{1}{x}$ has a nonlinearly decreasing rate of increase. Therefore, $F(x)$ cannot be a linear function of $x$.

To conclude, although some additional precision can be added to the preceding argument, one would expect $F(x)$ to be a monotonically decreasing function of $x$, such that $x = 1$ solves the problem in $(1)$.

$\endgroup$

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.