Recipe

Compute a constrained trust-region step

Use when: you have an iterate x_k, a local quadratic model m_k(p), a trust-region radius r_k, and one linearized inequality constraint, and need the next trial point

Goal: a candidate step p -- the Cauchy point when the ball binds -- together with a check of whether the linearized constraint stayed satisfied

Taught in Trust-region methods for constrained problems

1. 1

   At x_k, form m_k(p)=f(x_k)+\nabla f(x_k)^\top p+\frac12p^\top B_kp. Compute \nabla f(x_k) and its norm; the model's own unconstrained minimizer is p=-\nabla f(x_k) when B_k=I.

   Example

   x_k=(2.4,2.4), B_k=I: \nabla f(x_k)=(4.8,4.8), \lVert\nabla f(x_k)\rVert=4.8\sqrt2\approx6.788.

   Why: the trust-region step is a constrained version of this same minimizer -- you need to know how far the unconstrained choice would want to go before deciding what caps it.

2. 2

   Compare the unconstrained minimizer's length against the radius r_k, and check how close x_k already sits to the constraint boundary.

   • the unconstrained minimizer's length is far past r_k, and x_k isn't already hugging the boundary — the trust-region ball binds first; go to Step 3 for the Cauchy point.
   • x_k already sits close to the boundary relative to r_k (a large radius, or an iterate near the fence) — the linearized constraint binds first instead; solving that harder subproblem by hand is beyond what this section covers, but recognizing this case is the real skill being tested.

   Why: two different things can cap this step, and which one binds changes which formula applies next -- guessing wrong means computing the wrong point entirely.

3. 3

   Truncate the steepest-descent direction to the radius: p=-r_k\,\dfrac{\nabla f(x_k)}{\lVert\nabla f(x_k)\rVert}.

   Example

   p=-0.1\cdot(4.8,4.8)/6.788\approx(-0.0707,-0.0707); new point x_k+p\approx(2.329,2.329), and f drops from 11.52 to about 10.85.

   Why: this is the farthest step the trust region allows in the steepest-descent direction -- the best the model can do once the ball, not the model's own unconstrained taste, is what actually limits the step.

4. 4

   Evaluate g(x_k)+\nabla g(x_k)^\top p at the step just computed and check it's \le0.

   Example

   g(x_k)=-0.8, \nabla g(x_k)=(-1,-1): -0.8-\big((-1)(-0.0707)+(-1)(-0.0707)\big)=-0.9414\le0 -- satisfied with room to spare.

   Why: Step 2's case only guessed which bound would win before computing anything -- this step is the actual check that the ball-binds guess held up, not just an assumption.