Consider the following Matrix constraint: $$ \begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0 $$ where $\Sigma_b$ is a known positive definite matrix (shape matrix of saturation bound). $U \geq 0 \in \mathbb{S}_{+}^{ n \times n} $ and $V \in \mathbb{R}^n$ and $\tau_2,\psi >0 \in \mathbb{R}$ are the decision variables. I can propose the following linearization technique for the problem. $$ \begin{bmatrix} 0 & 0 \\ 0 & -V^TU^{-1}V \end{bmatrix} \leq \begin{bmatrix} U-\psi\Sigma_b^{-1} & -V \\ -V^T & -\tau_2 +\psi \end{bmatrix} $$ as the left hand side is surely negative semi definite we can replace the original nonlinear constraint with the following linear constraint. $$ \begin{bmatrix} U-\psi\Sigma_b^{-1} & -V \\ -V^T & -\tau_2 +\psi \end{bmatrix} \geq 0 $$ But this linearization has conservatism which is generated from ignoring the features of term $V^TU^{-1}V$ and its impacts on the problem. So I wanted to ask do you guys have any suggestion for improving this linearization process?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ What are we approximating? $\endgroup$– Ben McKayCommented Jul 30, 2021 at 16:15
-
$\begingroup$ My first aim is to find a linear equivallent to this constraint, but if that is impossible, I am interested in a linear constraint which is a good approximation of this nonlinear constraint. $\endgroup$– Navid HashemiCommented Jul 30, 2021 at 16:21
-
$\begingroup$ I don't think there is an y (exact) linearization given that Y and y are both variables. That is a (non-convex) nonlinear semidefinite constraint. Any linear approximation would be at best locally "valid". $\endgroup$– Mark L. StoneCommented Jul 30, 2021 at 19:49
-
$\begingroup$ I am pretty sure it is convex even if it is not linear. because I replaced $y^T Y^{-1}y$ with a new variable $s$ and solved the optimization. and then updated $s$ with the solution of $Y$ and $y$. I witnessed the solution of this itereative approach always converges to a unique solution no matter what I selected as the initial condition for $s$. $\endgroup$– Navid HashemiCommented Aug 1, 2021 at 21:41
-
$\begingroup$ That's not as proof of comvexity. An alternating variable scheme, as you seem to be describing, is a possible solution technique. I don't think it will generally come with a guarantee of converging to anything, let alone a global, or even local minimum. Nevertheless, if your computational experience with that approach is favorable, it may be that it works well in your case $\endgroup$– Mark L. StoneCommented Aug 1, 2021 at 23:23
|
Show 2 more comments