0
$\begingroup$

Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem: $$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$ where objective function $f_0: \mathbb{R}^n \rightarrow \mathbb{R}$ is linear and $G(x,p)\leq 0$ is a matrix inequality. The matrix inequality has the following bilinear form in decision variable $x$ and parameter $p$: $$G(x,p) = G_0 + G_1(x) + p\cdot G_2(x), $$ where $G_0 \in \mathbb{S}^{n}, G_1,G_2:\mathbb{R}^n\rightarrow\mathbb{S}^n$ being linear mapping, and $\mathbb{S}^n$ is the space of $n\times n$ symmetric matrices. For any given value of $p$, the constrained optimization problem is a semidefinite problem. Hence, $f(p)$ can be solved via a standard SDP solver.

Given the function $f(p)$, I would like to minimize $f(p)$ over $p$. I knew I could either form a nonlinear optimization problem that jointly solves $x,p$ at the same time. But I prefer to use either zero-order optimization over $p$ and convex optimization to solve $f(p)$ for some algorithm design choose to preserve physical meaning and computational cost. If the function $f(p)$ is convex in $p$, we can justify the use of a zero-order optimization algorithm.

I've done some literature review and found some results on Lipschitz continuity of the optimal value function for parametric nonlinear programming. However, I couldn't find any results specifically for convexity of the optimal value function for parametric (convex) programming. Appreciate if you can share some approaches and resources regarding this issue.

$\endgroup$
4
  • $\begingroup$ You seem to be looking for a magic convexifier of non-convex bilinear optimization. For fixed p, you claim to have a (presumably) linear SDP; so that makes your overall problem a BMI (Bilnear Matrix Inequality), which is non-convex. $\endgroup$ Aug 9, 2022 at 15:50
  • $\begingroup$ Thank you for your comment, @MarkL.Stone. For fixed p, my problem is a linear SDP as $G_1,G_2$ are linear mappings. I've edited my question to clarify this. Also, my overall problem is indeed BMI, which is non-convex in general. However, we preferred to go with the approach mentioned in my questions for design consideration. Hence, my question are actually asking about the approaches of proving or disproving the convexity (in p) of the optimal value function of the parametric linear SDP, instead of a BMI. $\endgroup$ Aug 9, 2022 at 18:48
  • $\begingroup$ Actually, you didn't tell us enough about $f_0(x)$ to conclude that the original problem with fixed p is Linear SDP-representable. And that is even if $f_0(x)$ is convex. $\endgroup$ Aug 9, 2022 at 19:09
  • $\begingroup$ Thanks for the reminder! The function $f_0(x)$ is actually a linear function. I'll edit it accordingly. $\endgroup$ Aug 9, 2022 at 19:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.