# Questions about Laplacian Surface Editing

I read the paper called Laplacian Surface Editing, but I'm confused about how does the author solve the formula (4). The paper says that 'Solving this quadratic minimization problem results in a sparse linear system of equations', so I have tried to use the quadprog function in matlab, but when the size of the nodes is growing up, my result is becoming messy. And I read the 'MATLAB 2D demo' code of this paper (http://igl.ethz.ch/projects/Laplacian-mesh-processing/Laplacian-mesh-editing/), it seems that they solve the question just by solving a linear system instead of using method such like 'interior-point' or 'active-set'. If someone has read this paper, Could you please tell me how on earth they solve the formula(4) ? Thanks a lot!

• Welcome to SciComp! In the future, please type in full the formula you refer to in your question. Forcing users to visit an external link to get essential information to answer your question is discouraged. – Geoff Oxberry Jan 27 '14 at 19:39

I'll state this in terms of an analogous problem in a domain where you are looking for a function $u(x)$ (namely the Laplace equation): If you are looking to minimize the problem $$\min_{u \in H^1} \frac 12 \|\nabla u\|^2_{L_2(\Omega)} - \int f\; u \; dx$$ then this is equivalent to solving the partial differential equation $$-\Delta u = f.$$ This is because the PDE are the optimality conditions for the optimization problem and, because they are linear, allows for the direct solution.

In the same way, the minimization problem given by equation (4) of the paper leads to a partial differential equation -- here posed on the surface of a body -- as the optimality conditions, and this is what the authors solve.

• Thank you very much! I understand the principle with your help, by the way, if you have seen the code for this paper, could you please tell me what the meaning of 'Tdelta' and why can they calculate the pseudo inverse of 'C' to get 'Tdelta'? It seems that they want to get 's' and 'a' subject to that s1*x1 + s2*x2+ s3*x3 + s4*y1 + s5*y2 + s6*y3 = 1 and s1*y1 + s2*y2 + s3*y3 - s4*x1 - s5*x2 - s6*x3 = 0 and s1 + s2 + s3 = 0 and s3 + s4 + s5 = 0 and the condition for 'a' is similar, where s = [s1, s2, s3, s4, s5, s6], and C = [x1, y1, 1, 0; x2, y2, 1, 0; x3, y3, 1, 0; y1, -x1, 0, 1; ...]; – Monkey D Bear Jan 27 '14 at 3:34
• I haven't looked at the code, so can't help -- sorry. – Wolfgang Bangerth Jan 27 '14 at 3:48

To add to Wolfgang's answer, the PDE that they come up with in the paper arises as the optimality condition for an unconstrained optimization problem. You mention using the quadprog function in MATLAB and methods like interior point and active set; these are more appropriate for optimization problems with inequality constraints. This would be a problem like

$\min\frac{1}{2}\int_\Omega |\nabla u|^2 dx - \int_\Omega u\cdot f dx$, over all $u$: $u \ge 0$.

The addition of the constraint $u \ge 0$ is what makes quadratic programming problems with inequality constraints so much harder than unconstrained QP, which boils down to just solving a linear system. By using the interior point method, you would be applying a method normally used for problems with inequality constraints to an unconstrained problem. Hope this clarifies matters!

• Box constraints like $u(x)\ge 0$ are actually not all that difficult to treat with quadratic objective functions such as the one you mention here. They are efficiently solved with active set methods. It becomes much more complicated if you have constraints of the kind $|\nabla u(x)|\le \gamma$ as you have in plasticity, for example. – Wolfgang Bangerth Jan 28 '14 at 4:01
• Cool, I thought inequality constraints make everything a total nightmare. By efficient, do you mean that the run-time of the solver scales as the number of non-zeros, like for AMG? – Daniel Shapero Jan 28 '14 at 4:14
• I don't know enough about the theory of optimization, but typically box constraints are not overly expensive to deal with because they concern only individual variables. – Wolfgang Bangerth Jan 29 '14 at 2:01