# Is it possible to show that this problem is convex?

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

• 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$. Commented Jan 11 at 13:11
• @MarkL.Stone thanks for the feedback. Will definitely look into grid search. Out of curiosity, are bilevel optimization problems always non-convex? Commented Jan 11 at 15:16
• Some trivial) bi-level problems can be expressed (formulated) as single level convex problems. Commented Jan 11 at 15:39
• 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.
– Max
Commented Jan 12 at 12:12
• @Max thank you for the feedback. Commented Jan 12 at 17:05

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