I don't fully understand the subsection 3.2 Constrained minimization of this paper. In particular, I don't understand the first step "Register active set" and the definition of projection $P(x)$.

Simplified algorithm (stripped-down version of the paper's one):

  1. Select initial guess and project it: $x^{(0)} = P(x'^{(0)})$
  2. Loop until precise enough
    1. Register active set
    2. Solve $\nabla^2E \cdot \Delta v = \nabla E$ via Conjugate Gradient to obtain $\Delta v$
    3. Use line search to find step $\alpha$
    4. Take step: $v^{(n+1)} = v^{(n)} + \alpha\Delta v$
    5. Project $v^{(n+1)}$

Projections. Let $P(x)$ be the projection that applies $P_{bp}$ to $x_p$ for all body-particle pairs $(b, p)$ that are labeled as active or are violated ($\phi_b(x_p) < 0$). Note that pairs such that $\phi_b(x_p) = 0$ (as would be the case once projected) are considered to be touching but not violated. The iterates $x^{(i)}$ obtained at the end of each Newton step, as well as the initial guess, are projected with $P$.

... We begin by representing our collision objects (indexed with $b$) by a level set, which we denote $\phi_b$ to avoid confusion with potential energy. By convention, $\phi_b(x) < 0$ for points $x$ in the interior of the collision object $b$. Our collision constraint is simply that $\phi_b\left(x_p^{(n+1)}\right) \gt 0$ for each simulation particle $p$ and every constraint collision object $b$. With such a formulation, we can project a particle at $x_p$ to the closest point $x'_p$ on the constraint manifold using $x'_p = P_{bp}(x_p) = x_p - \phi_b(x_p)\cdot\nabla\phi_b(x_p)$. ...

Register active set. Let $E'$ be the objective that would be computed in the unconstrained case. The objective function for constrained optimization is $E(x) = E'(P(x))$.
Compute the gradient $\nabla E'$. Constraints that are touching ($\phi(x_p) = 0$) and for which $\nabla E'\cdot\nabla\phi \ge 0$ are labeled as active for the remainder of the Newton step. All others are labeled as inactive. No constraint should be violated at this stage. Note that $E'(x^{(i)}) = E(x^{(i)})$ is true before and after every Newton step, since constraints are never violated there.

The emphasized sections are the ones I don't understand.

From the above I assume that the projection function $P(x)$ is defined as $$\begin{align} \phi_b \left( x_i \right) &= \text{the shortest distance from point $x_i$ to the surface/boundary of $b$ } \\ P \left(x_i\right) &= \begin{cases} x_i - \phi_b \left( x_i \right) \cdot \nabla\phi_b \left( x_i \right) & \,\,\, \text{if $\phi_b \left( x_i \right) < 0$ or when particle $i$ is active} \\ x_i & \,\,\, \text{otherwise}\\ \end{cases} \end{align} $$ As can be seen from the algorithm, and from the fact $E(x) = E'(P(x))$, the projection function has tangible effect only on such particles that are "active" (since no constraint is violated inside of the loop).

What is the purpose of labeling a pair $(b, p)$ as "active"? And why are labeled only those pairs for which $\nabla E'\cdot\nabla\phi \ge 0$?

I do currently understand this as selecting those particles $p$ that violated the constraints and were thus projected on the level-set manifold (or just happened to be at the precise boundary of the manifold) and at the same time the direction of force (represented by $-\nabla E'$) is trying to push the particle outside the manifold ($\nabla\phi$ is the surface normal of the level-set pointing inside the manifold at the position of particle $p$).

Do I understand it correctly that the projection function has effect only on the derivatives of the objective function $E'(x^{(i)}) = E(x^{(i)})$ (because otherwise it degrades to identity)?

Why exactly is $P = x_i - \phi_b \left( x_i \right) \cdot \nabla\phi_b \left( x_i \right)$ for the "active" particles? By definition, for the "active" particles $\phi_b \left( x_i \right) = 0$, so the value of $P$ is $x_i$ – the same as for the inactive particles.


Your Answer

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

Browse other questions tagged or ask your own question.