I'm interested in the problem of minimizing a convex function $f(x)$ for $x$ living in some Banach space $X$, subject to the linear constraint $Kx = g$ where $K : X \to Y^*$ for some other space $Y$. The Lagrangian is then $$L(x, y) = f(x) + \langle Kx - g, y\rangle.$$ A trust region method for an unconstrained problem would seek an update vector $p$ that minimizes a quadratic model of $f$ around $x$ subject to the constraint that $\|p\| \le \Delta$. Then there's some adaptation strategy for $\Delta$.

When you try to apply this approach naively to constrained problems, you run into the issue that, if the current candidate solution $x$ has $Kx - g \neq 0$, the trust region radius might be smaller than the distance to the subspace of feasible vectors. Consequently there are lots of strategies that break up the update into two parts: $p_g$ reduces the infeasibility while staying within the trust region, and $p_f$ which reduces $f$ and has $Kp_f = 0$ so that it doesn't increase the infeasibility.

These strategies work, but I've always found them a little unsatisfactory. They seem to forget about computing the multipliers $y$, which I care about, and which is often not mentioned at all. In the papers that do mention it, they sort of offhandedly say that you can compute them after the fact.

Is there a trust-region-like strategy that simultaneously computes estimates for the Lagrange multipliers $y$? For example, you might imagine instead posing the problem of finding a critical point $p$, $q$ of the quadratic functional $$\hat L(p, q) = \langle df(x), p\rangle + \frac{1}{2}\langle d^2f(x)p, p\rangle + \langle Kx - g, q\rangle + \langle Kp, y\rangle + \langle Kp, q\rangle$$ subject to the constraints that $\|p\| \le \Delta_p$, $\|q\| \le \Delta_q$. This gives at each step the linear system $$\left[\begin{matrix}d^2f(x) + \lambda M & K^* \\ K & -\mu N\end{matrix}\right]\left[\begin{matrix}p \\ q\end{matrix}\right] = -\left[\begin{matrix}df(x) + K^*y \\ Kx - g\end{matrix}\right]$$ where $M$ and $N$ are the Riesz representers for the dual pairings in $X$ and $Y$ respectively and $\lambda$, $\mu$ are positive scalar Lagrange multipliers to enforce the trust region constraints. I've looked through the relevant chapter in the book by Conn, Gould, and Toint and couldn't find anything like this. Does it exist or is there a reason I'm missing why it wouldn't work?

  • 2
    $\begingroup$ Have you seen optimization-online.org/wp-content/uploads/2002/11/562.pdf and other papers involving, primal-dual trust region? $\endgroup$ Commented Jun 8 at 19:35
  • $\begingroup$ Thanks @MarkL.Stone! Yes I've seen that and a few other papers I could find by searching for primal-dual trust region. I get mixed up easily with all the moving parts -- inequality + equality constraints, barrier functions, they usually care about non-convex problems also. What I have in mind is most similar to eqn 1.7 in that paper but they bring up several issues of ill-conditioning that I don't think are relevant in the equality-constrained case? It's also kind of reminiscent of eqn 17.62 in Nocedal and Wright. $\endgroup$ Commented Jun 8 at 23:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.