# Find best convex approximation of an “almost convex” function

I've got values of a function of two variables at integer points inside a rectangle, that is, a rectangular table $f(i,j)$, $1\leqslant i\leqslant m$, $1\leqslant j\leqslant n$. The function is very nearly convex, there are just a few points $(i,j)$ (less than 1%) where convexity fails just slightly. There is (afaik) more or less unique way to change these values (or maybe very few neighboring ones too) to obtain a convex function $\tilde f\leqslant f$ which would agree with $f$ almost everywhere.

The only way to do it that I found is to invoke ConvexHullMesh on the array of 3D points $(i,j,f(i,j))$ (that is, on the graph of $f$) and then extract relevant part from its FullForm. Is there a less hacky way to do what I want?

• Pending answers, your approach seems not hacky, but very much clever. – LLlAMnYP Apr 21 '16 at 11:07
• it doesnt seem your approach satisfies your <= constraint. – george2079 Apr 21 '16 at 12:10
• It seems, I've completely overlooked what @george2079 remarked on. That changes a lot. – LLlAMnYP Apr 21 '16 at 12:17
• Table[{i, j, Sqrt[50- i^2 - j^2] - 2 KroneckerDelta[i, 0] KroneckerDelta[j, 0]}, {i, -4, 4}, {j, -4, 4}] // Flatten[#, 1] & // ConvexHullMesh. The point at {0,0} has a height of 5.07, but ConvexHullMesh leaves it out, so the boundary of the mesh at {0,0} has the height of the neighboring points, which is 7. – LLlAMnYP Apr 21 '16 at 13:14
• Does this question have a 2D equivalent? It might help you formulate your criterea and solution if you could come up with a simple 2d example. – george2079 Apr 21 '16 at 14:06