# How to use ConvexOptimization on a function constructed from data?

Given the following data points sampled from a convex function, how could I construct a convex function that can be minimized using ConvexOptimization?

mypts = {{0, 0, 2}, {0, 1, 1}, {0, 2, 2.01}, {1, 0, 1}, {1, 1, 0}, {1, 2, 1}, {2, 0, 2}, {2, 1, 1}, {2, 2, 2}};
g = Interpolation[ mypts, InterpolationOrder -> 2 ];
Plot3D[ g[x, y], {x, 0, 2}, {y, 0, 2} ]
ConvexOptimization[ g[x, y] + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}, {x, y} ]


The error message is:

ConvexOptimization: The function InterpolatingFunction[...] is neither convex or concave so the curvature of the objective function ... cannot be determined.

I tried option InterpolationOrder -> 1, but got the same error message.

I could use NMinimize, but I hope to use ConvexOptimization, which should be considerably faster for larger problems.

I am considering generating a convex hull using the data points:

R = ConvexHullRegion[mypts]
Show[ListPlot3D[mypts], HighlightMesh[R, Style[2, Opacity[0.5]]]]


Can anyone help on how to convert a subset of the surfaces of a convex hull into a convex function that can then serve as an input for ConvexOptimization? Perhaps this is a long shot. I hope there is a shortcut to construct a convex function from data points and then apply ConvexOptimization. The function doesn't need to be smooth, just need to be acceptable by ConvexOptimization. Thank you for your read and help.

• Use: NMinimize[{g[x, y] + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}}, {x, y}] Jan 15, 2022 at 8:50

To create convex function we can use InterpolatingPolynomial as follows

mypts = {{0, 0, 2}, {0, 1, 1}, {0, 2, 2}, {1, 0, 1}, {1, 1, 0}, {1, 2,
1}, {2, 0, 2}, {2, 1, 1}, {2, 2, 2}}; g =
Interpolation[mypts, InterpolationOrder -> 2]; {zc =
Table[g[x, y], {x, 0, 2, .4}, {y, 0, 2, .4}],
xc = Table[x, {x, 0, 2, .4}], yc = Table[y, {y, 0, 2, .4}]};

yinterp =
Map[InterpolatingPolynomial[Transpose[{yc, #}], y] &, zc] // Chop;

g1 = InterpolatingPolynomial[Transpose[{xc, yinterp}], x] // Chop

Plot3D[g1, {x, 0, 2}, {y, 0, 2}]


Optimization

ConvexOptimization[
g1 + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}, {x, y}]

Out[]= {x -> 0.5, y -> 0.5}


Update 1. We also can construct convex function using FindFit as follows

model = a + b1 x + b2 y + c1 x^2 + c2 y^2 + d x y; ff =
FindFit[mypts, model, {a, b1, b2, c1, c2, d}, {x, y}]

(*Out[]= {a -> 1.99972, b1 -> -2.0025, b2 -> -1.99917, c1 -> 1.00167,
c2 -> 1.00167, d -> -0.0025}*)

g2 = model /. ff

(*Out[]= 1.99972 - 2.0025 x + 1.00167 x^2 - 1.99917 y - 0.0025 x y +
1.00167 y^2*)

ConvexOptimization[
g2 + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}, {x, y}]

Out[]= {x -> 0.501039, y -> 0.499377}

• Thank you Alex for your suggestion! However, if the data points are slightly perturbed while maintaining the existence of a convex interpolation, your suggestion does not work anymore. Here is the perturbed data: mypts = {{0, 0, 2}, {0, 1, 1}, {0, 2, 2.01}, {1, 0, 1}, {1, 1, 0}, {1,2, 1}, {2, 0, 2}, {2, 1, 1}, {2, 2, 2}}; Mathematica can verify the convexity: FunctionConvexity[{g1, {x >= 0, x <= 2, y >= 0, y <= 2}}, {x, y}] returns 1, but ConvexOptimization returns an error. Jan 15, 2022 at 15:17
• We can use ConvexOptimization[ Rationalize[g1 // Expand // Simplify, 10^-2] + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}, {x, y}] Jan 15, 2022 at 16:12
• I appreciate your help, Alex! Your method works for some special cases, but not in general. Suppose the data is: mypts={{0, 0, 2}, {0, 1, 1.05}, {0, 2, 2}, {1, 0, 1}, {1, 1, 0}, {1, 2, 1}, {2, 0, 2}, {2, 1, 1}, {2, 2, 2}}; Then I will need to rationalize the result using a coarser approximation. My original problem has many iterative minimizations, so I wanted to avoid introducing approximation errors. I am hoping to make the Convex Hull method work. Although Convex Hull doesn't give me a smooth surface, I can ensure convexity when using ConvexOptimization Jan 15, 2022 at 16:50
• @newOwen We have 9 points in 2D. In theory we can't make very precise approximation with 9 points only. Anyway, please, see Update 1 to my answer with second algorithm to construct convex function from your data. Jan 16, 2022 at 4:51
• This is a clever solution. Thanks, Alex! I like your solution when a parametric model is a good approximation. For general applications, basis functions may be hard to determine and I wish to use non-parametric models, such as Interpolation function in convex optimization. But I guess ConvexOptimization is pretty strict on the function to be optimized. Jan 16, 2022 at 15:35