1
SQP with Trust Region (Byrd–Omojokun)
At iterate \(x_k\) we solve a quadratic model with linearized constraints and a trust-region:
$$
\begin{aligned}
\min_{p}\;& \tfrac12\,p^\top H_k\,p + \nabla f(x_k)^\top p \\
\text{s.t. }& c_E(x_k) + J_E(x_k)\,p = 0,\quad
c_I(x_k) + J_I(x_k)\,p \le 0, \\
& \|p\|_{\mathrm{TR}} \le \Delta_k,\quad \ell \le x_k + p \le u.
\end{aligned}
$$
We use a Byrd–Omojokun composite step \(p = p_n + p_t\): a normal step reduces
feasibility in the equality space, then a tangential step optimizes the Lagrangian in the
nullspace, both within the trust region (Euclidean or ellipsoidal).
Trust-Region Geometry
- Ellipsoidal norm (optional): \(\|p\|_{\mathrm{TR}}=\|L^\top p\|_2\)
with \(M=L L^\top \approx \operatorname{sym}(H_k)+\tau I\).
- PCG (Steihaug–Toint): preconditioned CG on the TR subproblem; dense/CSR path with Jacobi.
- Active-set inequalities: augment equalities when
\(J_I p + c_I(x_k)\) violates feasibility.
- Box-safe scaling: fraction-to-boundary cap \(\alpha_{\max}\) keeps
\(x_k+\alpha p \in [\ell,u]\).
Stabilization & Feasibility
- dOPT stabilization: small residual shifts on \(c_E,c_I\) near active sets.
- Criticality safeguard: when \(\|P_T\nabla f\|\) is small, shrink
\(\Delta_k\) to regain model accuracy.
- Adaptive split: \(\Delta_n=\zeta\Delta_k\) with
\(\zeta\) adapted from feasibility history.
- SOC (least-squares) correction: solve
\(\min_{\Delta x}\|J_E\Delta x + c_E\|^2 + \|J_I\Delta x + (c_I+s)\|^2\),
set \(\Delta s = -(c_I + s + J_I\Delta x)\); fraction-to-boundary on \(\Delta s\).
- Restoration: feasibility-first step if acceptance fails.
Acceptance & Updates
- ared/pred ratio: feasibility-aware \(\rho_k\) integrates with filter/funnel.
- Curvature-aware radius: expand/shrink \(\Delta_k\) based on model agreement.
- Line search bridge: merit/filter line search before SOC, clipped by \(\alpha_{\max}\).
- Multipliers: recover \((\lambda,\nu)\) from a safeguarded LS system.
What’s inside the subproblem solve?
Normal step: solve \(J_E p_n \approx -c_E(x_k)\), clipped to
\(\Delta_n\) (and box).
Tangential step: minimize the reduced quadratic in the nullspace \(
\mathcal N(J_E)\) with Steihaug–Toint PCG; ellipsoidal metric handled by change of variables.
Active-set loop: add violated \(J_I\) rows as temporary equalities until feasible.
2
Interior-Point (Slack + Shifted Log-Barrier)
We solve a slack-augmented, optionally shifted barrier problem with variable bounds:
$$
\begin{aligned}
\min_{x,s}&\;\; f(x)\;-\;\mu\!\sum_{j}\log\big(s_j+\tau\big) \\
\text{s.t. }&\; c_E(x)=0,\;\; c_I(x)+s=0, \\
&\; \ell \le x \le u \quad (\text{optional}).
\end{aligned}
$$
Bounds use shifted slacks \(s_L=x-\ell,\; s_U=u-x\) with duals \(z_L,z_U\) (and optional bound shift
\(\beta\)). The perturbed complementarity conditions are:
$$
(s+\tau)\odot\lambda=\mu,\qquad
(s_L+\beta)\odot z_L=\mu,\qquad
(s_U+\beta)\odot z_U=\mu.
$$
We form a regularized augmented system (HYKKT by default; LDLᵀ fallback) with diagonal barriers and solve predictor/corrector steps efficiently.
$$
W \;=\; \nabla_{xx}^2 \mathcal{L}(x,\lambda,\nu)\;+\;\Sigma_x\;+\;J_I^\top \Sigma_s J_I,
\quad
\begin{bmatrix} W & J_E^\top \\ J_E & 0 \end{bmatrix}
\begin{bmatrix} \Delta x \\ \Delta \nu \end{bmatrix}
= \begin{bmatrix} -r_d \\ -r_{p,E} \end{bmatrix},
\ \ \Delta s = -\big(c_I + J_I\,\Delta x\big).
$$
Algorithmic Highlights
- Mehrotra Predictor–Corrector: affine predictor, adaptive centering, corrector.
- Fraction-to-Boundary: separate caps for \(s,\lambda,z_L,z_U\) to keep positivity.
- Shifted Barrier: automatic \(\tau,\beta\) adaptation to avoid tiny slacks.
- Gondzio Multi-Corrector (opt): extra RHS sweeps when affine step is short.
- Higher-Order Correction (opt): capped quadratic correction on \(J_I\).
- Tiny TR on \(\Delta x\): prevent aggressive steps with marginal conditioning.
- KKT Solves: HYKKT with reuse & CG refinement; LDLᵀ fallback; Ruiz equilibration.
Stopping & μ-update
Stop when \(\|r_d\|_\infty,\|c_E\|_\infty,\|c_I\|_\infty\) and complementarity residuals are below tolerance and \(\mu\) is small.
\(\mu\) decreases via a safeguarded schedule based on predictor quality, feasibility, complementarity, and Hessian conditioning.
