Is these two problems equivalent?


#1

Hi everyone. For some reasons, I need to eliminate the inequality contraints and replace them by equality constraints. I’m not very sure if two of the following optimization problems are equivalent. If so, how should I explain it ? Because the original problem belongs to linear programming and the solutions fall on the edge of the constraints? Thank you very much !

  1. The original one

\begin{split} \mathop {\min }\limits_{\mathbf{e}} \;&{\left\| {\mathbf{e}} \right\|_1} \hfill \\ {\text{s}}{\text{.t}}\;&\operatorname{tr} \left( {\mathbf{A}} \right) \leq \lambda \hfill \\ &\left[ {\begin{array}{*{20}{c}} {\mathbf{A}}&{\mathbf{I}} \\ {\mathbf{I}}&{{{ {\sum\limits_{n \in \mathcal{V}} {\sum\limits_{w \in \mathcal{W}} {{e_{n,w}}} {{\mathbf{B}}_{n,w}}} } }}} \end{array}} \right] \succeq {\mathbf{0}} \hfill \\ &\sum\limits_{w \in \mathcal{W}} {{e_{n,w}}} \leq 1,n \in \mathcal{V} \hfill \\ &{e_{n,w}} \in \left[ {0,1} \right],w \in \mathcal{W},n \in \mathcal{V} \hfill \\ \end{split}

  1. The modified one

\begin{split} \mathop {\min }\limits_{\mathbf{e}} \;&{\left\| {\mathbf{e}} \right\|_1} \hfill \\ {\text{s}}{\text{.t}}\;&\operatorname{tr} \left( {\mathbf{A}} \right) = \lambda \hfill \\ &\left[ {\begin{array}{*{20}{c}} {\mathbf{A}}&{\mathbf{I}} \\ {\mathbf{I}}&{{{ {\sum\limits_{n \in \mathcal{V}} {\sum\limits_{w \in \mathcal{W}} {{e_{n,w}}} {{\mathbf{B}}_{n,w}}} } }}} \end{array}} \right] = {\mathbf{0}} \hfill \\ &\sum\limits_{w \in \mathcal{W}} {{e_{n,w}}} \leq 1,n \in \mathcal{V} \hfill \\ &{e_{n,w}} \in \left[ {0,1} \right],w \in \mathcal{W},n \in \mathcal{V} \hfill \\ \end{split}

where {\mathbf{e}} is a vector which contains {e_{n,w}},w \in \mathcal{W},n \in \mathcal{V}.


(Mark L. Stone) #2

Is that an LMI in formulation 1? How is that a linear program?

What does that matrix = 0 in formulation 2 mean? Clearly it can’t be element-wise because of the I 's. Are you trying to say it is psd and non-full rank (at least one eigenvalue = 0)? If so, that would be non-convex.

Presumably formulation 1 is easy to enter in CVX. I don’t know for formulation 2 because I don’t know what that constraint is.

This is not a forum for modeling assistance. Rather for help in implementing a convex optimization problem in CVX. And as applicable, it is not a forum for doing people’s school assignments for them. This is kind of a strange statement " For some reasons, I need to eliminate the inequality contraints and replace them by equality constraints.".


(Michael C. Grant) #3

Mark is being very generous here (thanks Mark!) but this is not a CVX-specific question. Please direct your question to a more general math or optimization forum, like Math StackExchange or OR-Exchange.


(Michael C. Grant) #4