Estimation of Quadratic form parameters and convexity/concavity surface

Question

I have 3 points in the 3-d space with their coordinates $(x~y~z)^T$. I would like to find the expression of the $\textbf{concave}$ quadratic surface that form those 3 points, i.e., $z=f(x,y)=ax^2 + bxy +cy^2 = \theta^TQ\theta$ where $\theta=(x~y)^T$ and $Q=\Big[\begin{array}{cc} a & b/2 \\ b/2 & c \\ \end{array}\Big]$. It is obvious to see that using those 3 points we can find the parameters $(a~ b~ c)^T$ hence the entries of the matrix $Q$. However, by doing that we cannot guarantee that we will get a concave surface since it depends on the eigenvalues of the matrix $Q$ which could be positive or negative or with totally different sign. So my question is what is the expression that I should use in order to guarantee that I get a concave surface and what is the expression of the convex one. I know that we can use $-f(x,y)$ to switch between convex and concave but what we should do if we get to the case of saddle surface and is there a general rule to impose the needed shape.

Answer 1

Your values of $(a,b,c)$ must satisfy $$a,c\leq 0, \quad b/2 \leq \sqrt{ac}$$ if you wish to ensure that $f(x,y)$ is concave; that is, that $Q$ is negative semidefinite. Since you already have three equations for your three unknowns, your problem is overdetermined. You'll want to minimize some sort of fitting error subject to these constraints, which happen to describe a convex set (one sheet of a hyperboloid, to be specific). For instance, you could solve something like this: \begin{array}{ll} \text{minimize}_{a,b,c} & \sum_i ( z_i - a x_i^2 - b x_i y_i - c y_i^2 )^2 \\ \text{subject to} & b/2 \leq \sqrt{ac} \\ & a,c \leq 0 \end{array} This is a convex optimization problem. Feel free to substitute any other fitting function for the objective, as long as it is convex in $a,b,c$.

For the convex case one must simply constrain $a$ and $c$ to be nonnegative instead of nonpositive; everything else remains the same.

EDIT: For CVX the model would look like this, assuming x, y, and z are 3-vectors:

cvx_begin sdp
    variables a b c
    minimize(norm(z-a*x.^2-b*x.*y-c*y.^2))
    [ a, b/2 ; b/2, c ] <= 0
cvx_end

This uses CVX's SDP mode to directly constrain the $Q$ matrix to be negative semidefinite. And I'm using a Euclidean norm here, the square root of the objective I proposed above. You could use any other convex measure you wish of course. To handle the convex case, just switch the <= to >=.