3
$\begingroup$

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} ]

enter image description here

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]]]]

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ Use: NMinimize[{g[x, y] + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}}, {x, y}] $\endgroup$ Jan 15 at 8:50
3
$\begingroup$

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}]

Figure 1

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}
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – newOwen
    Jan 15 at 15:17
  • 1
    $\begingroup$ We can use ConvexOptimization[ Rationalize[g1 // Expand // Simplify, 10^-2] + x + y, {x >= 0, x <= 2, y >= 0, y <= 2}, {x, y}] $\endgroup$ Jan 15 at 16:12
  • $\begingroup$ 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 $\endgroup$
    – newOwen
    Jan 15 at 16:50
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 16 at 4:51
  • $\begingroup$ 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. $\endgroup$
    – newOwen
    Jan 16 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.