# Utilizing CVX for a max-min problem with semidefinite constraints

The objective is to find the greatest lower bound of the variable \mu. The lower bound is resulting from the positive-semidefinite (PSD) constraint $\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} 16 \mu -x(2)-4 x(10) & \frac{x(8)}{2}+2 x(11)+x(12) & 8 \mu -x(2)-2 x(10)+x(12) \ \frac{x(8)}{2}+2 x(11)+x(12) & 4 \mu -x(2)-2 x(5)-x(8)-2 x(10) & -x(2)+2 x(11)+x(12) \ 8 \mu -x(2)-2 x(10)+x(12) & -x(2)+2 x(11)+x(12) & 2 (8 \mu -x(2)-2 x(10)+x(12)) \ \end{array} \right)\succeq0,where \mathbf{x} is a 12-dimensional vector. Now, I optimize over \mathbf{x}, when subjected to PSD conditions on 4 matrices \mathbf{T}_i$ which depend linearly in the components of \mathbf{x}, and a set of given constants \mathit{c}_j. Symbolically, I write \mathbf{T}_i(c_j,\mathbf{x})\succeq0. I’m struggling with utilizing CVX. Any help would be gratefully acknowledged.

Note: if \tilde{\mathbf{T}} was a scalar of the value \tilde{\mathbf{T}}_{11}, then the lower bound could have been obtained analytically, yielding \mu_{min}=x(2)/16+x(10)/4, and the problem becomes a standard maximization problem over x(2)/16+x(10)/4.

What have you tried so far? Can you please copy/paste the code in that you have used to build this matrix?

I tried to convert the internal optimization to a constraint. Thus, when the lowest eigenvalue of \tilde{\mathbf{T}} equals zero, I get the lower bound for \mu. Consequently, I tried implementing it as an additional constraint for a maximize \mu command. However, this is an ill-posed formulation, as a concave function cannot be constrained to a constant. I also thought about treating external maximization problem as a loop over given values of $\mu$for a feasibility problem of the internal minimization. That didn’t work. Which code are you referring to? the CVX, or the one that yielded \tilde{\mathbf{T}}?

If you’re not going to offer any code, as I requested, I just can’t help you. I can’t offer model building help. That’s what the documentation and example library is for. But given your description, there is a good chance that your problem is not convex, and if so I refer you to the FAQ.

I will gladly upload any code, I just didn’t understand which one are you referring to, the one CVX, or the one that give me the matrix?

I’m talking about a CVX model you have written that comes closest to what you are trying to do, and shows the problems you are having.

Here is a link to the file

please let me know if there is anything not clear, I really appreciate the help.

I didn’t really look at your code - I just copied and pasted it into MATLAB. CVX accepted it, and both sedumi and sdpt3 reported the problem is infeasible. Do you have reason to believe that your problem should be feasible?

Agreed, I see no problem with it either.

The code, as it stands, provides \infty as the optimal value for \mu. The reason is that the first condition for \tilde{\mathbf{T}} (in the code it is called DMT) is not satisfied as an equality, but as an inequality, and hence does not provide the greatest lower bound, just the greatest value. This is the essence of my problem. As I mentioned, the greatest lower bound will be attained when the lowest eigenvalue of \tilde{\mathbf{T}} equals zero. To impose this provides an error, as expected, as a concave function cannot be constrained to a constant: https://www.dropbox.com/s/h2yyhx67yg6nzsb/lower_bound_3field_reduced_form_v4.m?dl=0

So it sounds like the problem you want to solve is not convex, and the relaxed problem that is convex fails to give you useful results. I wish I could say this is unusual, alas, it is not.

I see. Anyways, I thank you for your time.

Yes, now that I see a fuller statement of your problem on Math.SE I am confident CVX cannot solve it as is.

Too bad for me, CVX is a fantastic tool.

Thank you! I’m going to give your Math.SE question some thought and if I can think of a solution I will let you know.