It seems that ConvexOptimization does not attain the optimal value

Question

I am trying to implement the concrete example of formula (11.20) Boyd & Vandenberghe, page 580.

Therefore, we have computed a point that satisfies many (m − r) of the inequalities, i.e., we have identified a large subset of inequalities that is feasible.

I set five inequalities that is five interior of five ellipses. I made four ellipses at most share with one area as the following picture, the red spots are centers of ellipses ,respectively.

So I guess the optimal point would fall into the blue area.

Clear["Global`*"]
Hf = (RotationMatrix[#2] . 
     Transpose[#1 // DiagonalMatrix // 
       Inverse] . (#1 // DiagonalMatrix // Inverse) . 
     Transpose[RotationMatrix[#2]]) &; 
Jf =  (-(Hf @@ {#1, #2} . #3) - ((Hf @@ {#1, #2} // 
         Transpose) . #3)) &;
Cf = ( #3 . (Hf @@ {#1, #2}) . #3 - 1) &;

(* epllise parameters as scaling, rotating and moving from a unit \
circle*)
ellipse1 = {{0.5, 0.2}, Pi/12, {1.5, 1}};
ellipse2 = {{1, 0.5}, Pi/2, {0, 0}};
ellipse3 = {{1.5, 1.0}, Pi/6, {1., -0.2}};
ellipse4 = {{1.5, 1.0}, Pi/3, {1.2, 0.5}};
ellipse5 = {{1.0, 0.6}, Pi/6, {0, 0.5}};
ellipse = {ellipse1, ellipse2, ellipse3, ellipse4, ellipse5};

H = Hf @@@ ellipse;
J = Jf @@@ ellipse;
Const = Cf @@@ ellipse;
exprs = Table[{x, y} . H[[i]] . {x, y} + Transpose[J[[i]]] . {x, y} + 
    Const[[i]], {i, 1, Length[ellipse]}];
Show[ContourPlot[exprs, {x, -2, 3}, {y, -2, 2}, Axes -> True, 
  AxesOrigin -> {0，0}, 
  Epilog -> {Red, AbsolutePointSize[5], 
    Point@(Take[ellipse, All, {3}]~Flatten~1)}]]

Use ConvexOptimization to solve the optimal problem.

dimx = 2 ;(*domain is xy plane *)
dims = Length[
  epllise]; (* dimension of slack 's' variable for every inequality *)
\

numIneq =  
 Length[epllise] + 
  dims;(*number of  inequalities of 'fi' and inequalities for slack \
variables *)
numEq = 0; (*no equality constraint*)

(*fi[s_List,x_List,i_Integer/;(i>0 && i<= \
numIneq/2)]:=x.H[[i]].x+Transpose[J[[i]]].x+Const[[i]]-s[[i]]*)

var[1] = Array[ss, 5];
var[2] = Array[xx, 2];
ConvexOptimization[
 Sum[var[1][[i]], {i, 1, 5}], {Table[
   var[2] . H[[i]] . var[2] + Transpose[J[[i]]] . var[2] + 
     Const[[i]] - var[1][[i]] \[VectorLess] 0, {i, 1, 5}], 
  var[1] \[VectorGreaterEqual] -0.0001}, Flatten[{var[1], var[2]}]]

It is noticeable if set $s\succcurlyeq0$ would allow the point on the boudary of ellipse to be optimal, so I set $s\succcurlyeq -0.0001 $ or anyone negative close to zero.

Then I get the optimal result.

{ss[1] -> 1.39408, ss[2] -> 1.90769, ss[3] -> -0.000100014, 
 ss[4] -> -0.0000999987, ss[5] -> -0.000099999, xx[1] -> 0.754975, 
 xx[2] -> 0.792299}

Then I plot the optimal point $xx$

Show[ContourPlot[exprs, {x, -2, 3}, {y, -2, 2}, Axes -> True, 
  AxesOrigin -> {0，0}, 
  Epilog -> {Red, AbsolutePointSize[5], 
    Point@( (Take[ellipse, All, {3}]~Flatten~1))}], 
 Graphics[{PointSize[Large], Blue, Point@{0.754975, 0.792299}}]]

So the problem is obvious - the point is not optimal.

There are two small problems. How to get the value of $xx$? The other is if I use self-defined function $fi$ and put it into ConvexOptimization, it fails to solve.

fi[s_List, x_List, i_Integer] := 
 x . H[[i]] . x + Transpose[J[[i]]] . x + Const[[i]] - s[[i]]
var[1] = Array[ss, 5];
var[2] = Array[xx, 2];
ConvexOptimization[
 Sum[var[1][[i]], {i, 1, 5}], {Table[
   fi[var[1], var[2]] \[VectorLess] 0, {i, 1, 5}], 
  var[1] \[VectorGreaterEqual] -0.0001}, Flatten[{var[1], var[2]}]]

Report

ConvexOptimization::ctuf: The function fi[{ss1,ss2,ss3,ss[4],ss[5]},{xx1,xx2}] is neither convex or concave so the curvature of the constraint fi[{ss1,ss2,ss3,ss[4],ss[5]},{xx1,xx2}][VectorLess]0 cannot be determined.

Thank you for any and all suggestions.

Answer 1

There seems to be two problems here.

The second one is easy to solve: you defined fi to take 3 arguments but forgot to put the index i in the call to fi[var[1], var[2]] \[VectorLess] 0 inside ConvexOptimization. The functions remain unevaluated and that triggers the error message.

The first problem is not really a problem. You seem to expect that the solution to the problem will give you a point satisfying the maximum possible number of feasible inequalities. That is not the case. The statement you quote is misleading. There is no guarantee that the subset of feasible inequalities that will be captured by solving this problem is "large." Only that the optimal solution is such that the inequalities for which the corresponding $s_i$ are zero are feasible. There will always be one such inequality if at least one of the inequalities is feasible.

What is true however is that there will be a positive linear combination of the $s$'s that produces the subset with the maximum cardinality. The one you are looking for in this case can be obtained by minimizing $s_1 + 10 s_2 + 10 s_3 + s_4 + s_5$ instead of $s_1 + s_2 + s_3 + s_4 + s_5$, as in

var[1] = {s1,s2,s3,s4,s5};
var[2] = {x1,x2};
c = {1, 10, 10, 1, 1};
sol = ConvexOptimization[
        Sum[c[[i]]*var[1][[i]], {i, 1, 5}], 
        Append[Table[fi[var[1], var[2], i] <= 0, {i, 1, 5}],
               var[1] \[VectorGreaterEqual] 0],
        Flatten[{var[1], var[2]}]]

which results in

{s1 -> 4.68061, s2 -> -9.4105610^-8, s3 -> -7.5911210^-8, s4 -> -6.397910^-9, s5 -> -7.4448310^-9, x1 -> 0.398559, x2 -> 0.603822}

in which only the first inequality is not feasible. The optimal solution $(x1,x2)$ is now in the region you expected it to be.