0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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 >=.

$\endgroup$
6
  • $\begingroup$ Dr. Grant, thanks a lot! $\endgroup$
    – user2987
    May 26, 2015 at 18:05
  • $\begingroup$ What would be the objective function if I would like to solve that using cvx in MATLAB. Would it work if I write it explicitly: (z(1)-ax(1)^2 -bx(1)*y(1)-c*y(1)^2)^2+(....)^2+(...)^2. $\endgroup$
    – user2987
    May 26, 2015 at 18:18
  • $\begingroup$ I've edited the answer with a model. $\endgroup$ May 26, 2015 at 18:26
  • $\begingroup$ Dr. Grant is there a way to control the curvature of the concave surface in order to have $f(x,y)\geq0$ . Do we have to add a bias term $d$. In this case should I use a fourth point to estimate $d$? $\endgroup$
    – user2987
    May 27, 2015 at 3:38
  • $\begingroup$ I think the bias term should be $\eta^T\theta$ where $\eta=(d~ e)^T$ then we will have two extra terms $dx_i+ey_i$ in the objective function. Does that mean I need 5 points to have a unique solution. And what should be the choice of $d$ and $e$ to control the curvature $LB\leq\max (f(x,y)\leq UB)$ $\endgroup$
    – user2987
    May 27, 2015 at 4:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .