= Solution
The linearized constraints may be inconsistent, for example when $-c(x_k)$ is not in the <image of a linear map> defined by $A(x_k)$. Even if feasible, the quadratic objective may have negative curvature along its feasible tangent space, making it unbounded below and leaving no local minimizer.
Fletcher's <Sℓ1QP> replaces the hard linearized constraints by an <L1 exact penalty> and bounds the step inside a <trust region>. One usual form is
$$
\boxed{\min_{\|s\|_\infty\leq\Delta_k}\ g_k^Ts+\frac12s^TH_ks+\rho_k\|c_k+A_ks\|_1,\qquad\rho_k>0.}
$$
The zero step is always admissible. The trust region is compact, so a minimum exists even when the model <Hessian matrix> is indefinite; the constraint penalty measures infeasibility rather than making the subproblem impossible to solve. Adjusting its weight promotes feasibility, while the radius keeps the local model within a controlled neighbourhood. Introducing nonnegative positive- and negative-part slack variables converts the absolute values to an equivalent smooth <quadratic program> with box constraints.<Sequential Quadratic Programming Methods by Philip E. Gill and Elizabeth Wong>[§3.3, equations (3.25)–(3.26): Fletcher's Sℓ1-QP model and its elastic quadratic-program formulation]{ref}
Back to article page
