1
$\begingroup$

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.

$\endgroup$

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.