pounce_sensitivity/solver.rs
1//! `Solver` — value-typed session API that holds an `IpoptApplication`,
2//! its TNLP, and the converged KKT factor between calls.
3//!
4//! This is Phase 3a of the factor-reuse work tracked in
5//! [pounce#16](https://github.com/jkitchin/pounce/issues/16). It is
6//! the public surface for callers who want to:
7//!
8//! 1. Run a normal IPM solve, then
9//! 2. Issue many cheap operations against the converged factor
10//! (`kkt_solve`, `parametric_step`) without going through the
11//! [`set_on_converged`] callback shape that [`crate::SensSolve`]
12//! requires.
13//!
14//! [`set_on_converged`]: pounce_algorithm::IpoptApplication::set_on_converged
15//!
16//! # Usage
17//!
18//! ```ignore
19//! use pounce_sensitivity::Solver;
20//! use std::cell::RefCell;
21//! use std::rc::Rc;
22//!
23//! let app = make_configured_app();
24//! let tnlp: Rc<RefCell<dyn TNLP>> = Rc::new(RefCell::new(MyTnlp));
25//! let mut solver = Solver::new(app, tnlp);
26//!
27//! let status = solver.solve();
28//! assert!(solver.converged().is_some());
29//!
30//! // Issue any number of back-solves against the same factor:
31//! let dim = solver.kkt_dim().unwrap();
32//! let mut lhs = vec![0.0; dim];
33//! let rhs = vec![1.0; dim];
34//! solver.kkt_solve(&rhs, &mut lhs).unwrap();
35//!
36//! // Parametric step with respect to a set of pinned equality
37//! // constraints (same interpretation as [`crate::SensSolve`]):
38//! let dx = solver.parametric_step(&[2, 3], &[-0.5, 0.0]).unwrap();
39//! ```
40//!
41//! # Scope of Phase 3a
42//!
43//! - **In**: `solve()`, `converged()`, `kkt_solve()`, `parametric_step()`,
44//! `block_dims()` / `kkt_dim()`.
45//! - **Deferred to Phase 3b**: `resolve()` (warm-start that reuses the
46//! linear backend pool) and the `parametric_mpc` /
47//! `sensitivity_session` example binaries.
48//! ([`Solver::compute_reduced_hessian`] has since landed on the Solver
49//! and is no longer `SensSolve`-only.)
50
51use std::cell::{Ref, RefCell};
52use std::rc::Rc;
53
54use pounce_algorithm::application::IpoptApplication;
55use pounce_common::types::{Index, Number};
56use pounce_nlp::TNLP;
57use pounce_nlp::return_codes::ApplicationReturnStatus;
58
59use crate::PdSensBacksolver;
60use crate::activity::{ActivityReport, ReducedActivityReport, ReducedRowActivityReport};
61use crate::backsolver::SensBacksolver;
62use crate::boundcheck::PathOperator;
63use crate::index::{FullXSlice, VarToFull, VarX};
64use crate::schur_data::IndexSchurData;
65use crate::sens_app::{SensApplication, SensOptions};
66use crate::vec_util::dense_to_vec;
67
68/// Sign of the barrier correction term, set from a comparison
69/// against sIPOPT rather than derived.
70pub const BARRIER_SIGN: Number = -1.0;
71
72/// The bound geometry the bound-aware parametric steps share. See
73/// [`Solver::bound_context`].
74struct BoundContext {
75 /// Length of the `x` block: how much of the box below is
76 /// variables, and how much of a step is the caller's answer.
77 n_x: usize,
78 /// Lower bounds over the `(x, s)` prefix of the compound KKT
79 /// vector, in the model's own units.
80 ///
81 /// The `s` half is the limits of the inequality rows, `d_l`. A
82 /// limit written as a constraint — `g(x) <= cap` — is a bound like
83 /// any other, on the row's slack instead of on a variable, and
84 /// leaving it out of the box is what let a step walk straight
85 /// through a cap with no breakpoint and no warning (gh#928). The
86 /// two blocks are adjacent in the compound vector, so the box is
87 /// one contiguous slice and a consumer needs no second index
88 /// space; `n_x` is where it changes meaning.
89 lo: Vec<Number>,
90 /// Upper bounds, likewise: variable `x_u` then row `d_u`.
91 hi: Vec<Number>,
92 /// The converged point over that same `(x, s)` prefix.
93 x_curr: Vec<Number>,
94 /// How far outside a bound still counts as on it.
95 eps: Number,
96 /// How far negative a bound multiplier has to go before its bound
97 /// is released. Always the solve's own margin, whatever `eps` is.
98 release_eps: Number,
99 /// Bound multipliers at the base point, in the solve's own
100 /// coordinates, with the compound row each occupies: `z_l`, `z_u`,
101 /// then `v_l`, `v_u`. The `v` half is what lets an active
102 /// constraint limit be *released* when a step drives its
103 /// multiplier through zero, the mirror of the `s` half of the box.
104 mults: Vec<crate::boundcheck::BoundMultiplier>,
105}
106
107impl BoundContext {
108 /// Distance from the base point to each bound, for one var-x row.
109 ///
110 /// Typed because the callers read a full-x `ActivityReport` in the
111 /// same scope: indexing `lo` / `hi` / `x_curr` with a full-x value
112 /// is the swap `crate::index` exists to prevent. Those three now
113 /// run past the `x` block into `s`, so the type is doing more work
114 /// than it was: a var-x row is in range for the whole box and a
115 /// full-x row that overshoots `n_x` no longer runs off the end,
116 /// it silently reads a slack.
117 fn slacks_at(&self, row: VarX) -> (Number, Number) {
118 let i = row.get();
119 (self.x_curr[i] - self.lo[i], self.hi[i] - self.x_curr[i])
120 }
121}
122
123/// Errors returned by post-convergence operations on [`Solver`].
124#[derive(Debug, Clone)]
125#[non_exhaustive]
126pub enum SolverError {
127 /// The solver has not yet converged, or the last solve failed
128 /// before producing a usable KKT factor.
129 NotConverged,
130 /// An input slice's length did not match the KKT dimension or the
131 /// parameter count.
132 BadShape {
133 /// Human description of the mismatched buffer.
134 what: &'static str,
135 /// Length the caller passed.
136 got: usize,
137 /// Length expected.
138 expected: usize,
139 },
140 /// The underlying back-solve failed (singular factor, numerical
141 /// breakdown).
142 BacksolveFailed,
143 /// The underlying [`SensApplication`] step failed (e.g. row mapping
144 /// invalid for the current problem).
145 SensComputationFailed(String),
146 /// An option the requested computation depends on holds an
147 /// incompatible value; the message names the option and the value
148 /// required.
149 BadOptions(String),
150}
151
152/// State captured at convergence: the user-visible iterate plus the
153/// `PdSensBacksolver` that wraps the converged KKT factor.
154///
155/// Read this via [`Solver::converged`].
156pub struct ConvergedState {
157 /// IPM return status of the most recent solve.
158 pub status: ApplicationReturnStatus,
159 /// Final primal iterate `x*` (length `n_x`), in the user's own
160 /// units: a `user-scaling` change of variables is undone here, so
161 /// this is `x`, never the algorithm's `x̃ = d ⊙ x` (gh#486).
162 pub x: Vec<Number>,
163 /// Final objective value `f(x*)`.
164 pub obj_val: Number,
165 /// `bound_relax_factor` **as the solve that produced this state
166 /// ran with it**, not as the application's options read today.
167 /// The bounds were relaxed (or not) once, during this solve; a
168 /// later `set_numeric_value` cannot change what the held slacks
169 /// were measured against, so post-solve calls whose validity
170 /// depends on unrelaxed bounds must guard on this value. See
171 /// [`Solver::classify_activity`].
172 pub bound_relax_factor: Number,
173 /// Whether the solve computed exact Hessians, **as it ran**. A
174 /// `limited-memory` solve's `IpoptData::w` is the quasi-Newton
175 /// matrix, and there is no exact Hessian to evaluate at another
176 /// point, so the corrector keeps that matrix instead of
177 /// refreshing it at the predicted iterate.
178 pub exact_hessian: bool,
179 /// Converged KKT-factor wrapper. Owns `Rc` handles to the
180 /// `PdFullSpaceSolver`, the IpoptData / Cq, and the NLP, so it
181 /// outlives the IPM call frame.
182 backsolver: PdSensBacksolver,
183}
184
185impl ConvergedState {
186 /// Block dimensions of the compound KKT vector in
187 /// `(x, s, y_c, y_d, z_l, z_u, v_l, v_u)` order.
188 pub fn block_dims(&self) -> [usize; 8] {
189 self.backsolver.block_dims()
190 }
191
192 /// Total dimension of the compound KKT vector (sum of `block_dims`).
193 pub fn kkt_dim(&self) -> usize {
194 self.backsolver.dim()
195 }
196}
197
198/// Session-style solver: holds an [`IpoptApplication`], its TNLP, and
199/// the converged factor between calls.
200pub struct Solver {
201 app: IpoptApplication,
202 tnlp: Rc<RefCell<dyn TNLP>>,
203 /// Side channel populated by the `on_converged` callback installed
204 /// in [`Self::solve`]. The `RefCell<Option<…>>` shape mirrors the
205 /// pattern in [`crate::convenience`] (the callback closure needs
206 /// shared mutable access; the `Option` is `None` before the first
207 /// solve and gets overwritten on each call).
208 state: Rc<RefCell<Option<ConvergedState>>>,
209}
210
211impl Solver {
212 /// Build a new session. The `app` should already have its options
213 /// configured and `initialize()` called.
214 pub fn new(app: IpoptApplication, tnlp: Rc<RefCell<dyn TNLP>>) -> Self {
215 Self {
216 app,
217 tnlp,
218 state: Rc::new(RefCell::new(None)),
219 }
220 }
221
222 /// Borrow the underlying `IpoptApplication` (e.g. to read its
223 /// options table after a solve). Mutation between `solve` calls is
224 /// supported via [`Self::app_mut`].
225 pub fn app(&self) -> &IpoptApplication {
226 &self.app
227 }
228
229 /// Mutable borrow of the underlying `IpoptApplication`. Useful for
230 /// reconfiguring options before a follow-up `solve()`. Note that
231 /// changing options that affect the KKT linear system between
232 /// calls will invalidate the cached factor; the next `solve()`
233 /// rebuilds it.
234 pub fn app_mut(&mut self) -> &mut IpoptApplication {
235 &mut self.app
236 }
237
238 /// Run the IPM to convergence. On a successful solve the
239 /// [`ConvergedState`] (including the KKT backsolver) is stashed
240 /// inside the `Solver` and accessible via [`Self::converged`].
241 ///
242 /// Each call to `solve()` overwrites the previous converged
243 /// state; the previously held factor is dropped.
244 pub fn solve(&mut self) -> ApplicationReturnStatus {
245 // Clear any previous state so a failed re-solve doesn't leave
246 // a stale factor visible.
247 self.state.borrow_mut().take();
248
249 // Snapshot the options this solve will run under, before it
250 // runs. `bound_relax_factor` is consumed once, when the NLP
251 // relaxes its bounds; reading it back at query time would
252 // describe the application's options rather than the state
253 // being queried. The registry supplies its own default when
254 // the option is unset, so no second copy of the default lives
255 // here.
256 let brf = self
257 .app
258 .options()
259 .get_numeric_value("bound_relax_factor", "")
260 .map(|(v, _)| v)
261 .expect("bound_relax_factor is a registered core option");
262 let exact_hessian = self
263 .app
264 .options()
265 .get_string_value("hessian_approximation", "")
266 .map(|(v, _)| v == "exact")
267 .expect("hessian_approximation is a registered core option");
268
269 let state_cb = Rc::clone(&self.state);
270 // NOTE (gh#884 follow-up): `set_on_converged` fires once per
271 // *attempt*. When a later attempt loses and an earlier one's answer
272 // is replayed through the three-sink floor -- the mu fallback
273 // (pounce#870, on by DEFAULT) or the gh#884 dual-divergence retry --
274 // the converged KKT state this closure reads belongs to the
275 // DISCARDED attempt, while the status, objective and statistics
276 // reported alongside it are the winner's.
277 // `IpoptApplication::answer_restored_from_floor()` reports that this
278 // happened; the CLI's main path consults it and re-reads the point
279 // from the `finalize_solution` payload. This site does not, because
280 // what it needs is the factorization and the KKT state, which the
281 // payload does not carry and which cannot be rewound. Pre-existing
282 // and unfixed: a sensitivity result taken across a floored solve
283 // describes the attempt that lost.
284 self.app
285 .set_on_converged(Box::new(move |data, cq, nlp, pd| {
286 let curr = match data.borrow().curr.clone() {
287 Some(c) => c,
288 None => return,
289 };
290 let backsolver = match PdSensBacksolver::new(data, cq, nlp, Rc::clone(&pd)) {
291 Ok(b) => b,
292 Err(e) => {
293 // No session state is stored, so post-solve
294 // calls will report NotConverged; at least say
295 // why on stderr rather than failing silently.
296 eprintln!("pounce: Solver could not capture the KKT factor: {e}");
297 return;
298 }
299 };
300 // The algorithm's iterate is `x̃ = d ⊙ x` when the
301 // solve ran under a change of variables (gh#486): this
302 // capture reads the iterate, not the
303 // `finalize_solution` payload, so it undoes the
304 // substitution itself. The backsolver already read the
305 // factors off the NLP, in this same var-x space.
306 let mut x = dense_to_vec(&*curr.x);
307 if let Some(d) = backsolver.variable_scaling() {
308 debug_assert_eq!(x.len(), d.len());
309 for (xi, &di) in x.iter_mut().zip(d.iter()) {
310 *xi /= di;
311 }
312 }
313 let obj_val = cq.borrow_mut().curr_f();
314 // Status is overwritten with the real value after
315 // optimize_tnlp returns.
316 *state_cb.borrow_mut() = Some(ConvergedState {
317 status: ApplicationReturnStatus::InternalError,
318 x,
319 obj_val,
320 bound_relax_factor: brf,
321 exact_hessian,
322 backsolver,
323 });
324 }));
325
326 let status = crate::optimize_tnlp_for_sensitivity(&mut self.app, Rc::clone(&self.tnlp));
327 if let Some(s) = self.state.borrow_mut().as_mut() {
328 s.status = status;
329 }
330 status
331 }
332
333 /// Borrow the converged state, if a successful solve has been
334 /// run. Returns `None` if no solve has run or if the most recent
335 /// solve failed before reaching convergence.
336 pub fn converged(&self) -> Option<Ref<'_, ConvergedState>> {
337 let r = self.state.borrow();
338 r.as_ref()?;
339 Some(Ref::map(r, |o| {
340 o.as_ref()
341 .unwrap_or_else(|| unreachable!("checked is_some above"))
342 }))
343 }
344
345 /// Total dimension of the compound KKT vector (sum of
346 /// `block_dims`). Returns `None` if no converged factor is held.
347 pub fn kkt_dim(&self) -> Option<usize> {
348 self.converged().map(|c| c.kkt_dim())
349 }
350
351 /// Block dimensions of the compound KKT vector in
352 /// `(x, s, y_c, y_d, z_l, z_u, v_l, v_u)` order. Returns `None` if
353 /// no converged factor is held.
354 pub fn block_dims(&self) -> Option<[usize; 8]> {
355 self.converged().map(|c| c.block_dims())
356 }
357
358 /// Classify every bounded variable and every finite-bounded
359 /// inequality row of the converged solve by activity: see
360 /// [`crate::activity`] and
361 /// `dev-notes/covariance-information-roadmap.md` item 0 (gh #362).
362 ///
363 /// Requires the held solve to have run with `bound_relax_factor=0`
364 /// (the Ipopt default is `1e-8`): with relaxed bounds the solver's
365 /// slacks are measured against perturbed bounds, and the
366 /// complementarity products the classifier reads no longer track
367 /// `μ`.
368 ///
369 /// The guard reads
370 /// [`ConvergedState::bound_relax_factor`] — the value that solve
371 /// ran under — not the application's current options. Setting the
372 /// option after the fact neither unlocks a state whose bounds were
373 /// relaxed nor invalidates one whose bounds were not; re-solve to
374 /// change the answer.
375 ///
376 /// # Neither classes' `q` is a reduced curvature
377 ///
378 /// A variable's ratio is `Σ_i/|H_ii|`, and at a kink the
379 /// multiplier is generated by the curvature **reduced** along that
380 /// coordinate, not by the diagonal. The two agree only where the
381 /// coordinate is decoupled, so a genuine kink coupled to a
382 /// neighbour reads [`AMBIGUOUS`](crate::activity::AMBIGUOUS) here
383 /// at any tolerance (gh#763). Do not read that class as "probably
384 /// not a kink": use [`Self::reduced_activity`], which normalizes
385 /// by the reduced curvature at one back-solve per coordinate.
386 ///
387 /// A row's ratio divides by the curvature along the row's own
388 /// gradient instead, which is a genuine directional curvature but
389 /// still not a reduced one, so the same warning and the same
390 /// remedy apply there: its ratio is `reduced/directional` and
391 /// [`Self::reduced_row_activity`] answers the kink question
392 /// (gh#804).
393 pub fn classify_activity(&self) -> Result<ActivityReport, SolverError> {
394 let state = self.state.borrow();
395 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
396 let brf = state.bound_relax_factor;
397 if brf != 0.0 {
398 return Err(SolverError::BadOptions(format!(
399 "classify_activity requires bound_relax_factor=0, but the \
400 held solve ran with {brf:e}: relaxed bounds shift the \
401 slacks the classifier reads. Set the option and solve() \
402 again — changing it now does not re-measure the slacks."
403 )));
404 }
405 Ok(crate::activity::compute(&state.backsolver))
406 }
407
408 /// [`Self::classify_activity`]'s per-variable verdict for
409 /// `user_vars`, re-measured against the **reduced** curvature
410 /// along each coordinate instead of the Hessian diagonal — one
411 /// back-solve against the held factor per variable (gh#763).
412 ///
413 /// `classify_activity` normalizes a variable's `Σ` by `H_ii`, but
414 /// the multiplier at a kink is generated by the curvature left
415 /// after the other free variables re-optimize. The two agree only
416 /// where the coordinate is decoupled, so a genuine kink coupled to
417 /// a neighbour reads [`AMBIGUOUS`](crate::activity::AMBIGUOUS)
418 /// there at any tolerance — the ratio is `μ`-independent. Ask here
419 /// and the same kink reads
420 /// [`WEAKLY_ACTIVE`](crate::activity::WEAKLY_ACTIVE).
421 ///
422 /// Indices are **user space** (full-x), as the report's are. The
423 /// intended call is over a report's ambiguous entries:
424 ///
425 /// ```ignore
426 /// let report = solver.classify_activity()?;
427 /// let ask: Vec<usize> = (0..report.var_status.len())
428 /// .filter(|&i| report.var_status[i] == AMBIGUOUS)
429 /// .collect();
430 /// let refined = solver.reduced_activity(&ask)?;
431 /// ```
432 ///
433 /// The cost is one back-solve per index, so it is a refinement to
434 /// call over the entries in question, not over every bounded
435 /// variable of a large model. See
436 /// [`crate::activity::reduced_activity`] for the algebra and the
437 /// edge cases.
438 ///
439 /// Requires the held solve to have run with `bound_relax_factor=0`
440 /// for the same reason [`Self::classify_activity`] does: both read
441 /// the slacks relaxed bounds shift.
442 pub fn reduced_activity(
443 &self,
444 user_vars: &[usize],
445 ) -> Result<ReducedActivityReport, SolverError> {
446 let state = self.state.borrow();
447 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
448 let brf = state.bound_relax_factor;
449 if brf != 0.0 {
450 return Err(SolverError::BadOptions(format!(
451 "reduced_activity requires bound_relax_factor=0, but the \
452 held solve ran with {brf:e}: relaxed bounds shift the \
453 slacks the classifier reads. Set the option and solve() \
454 again — changing it now does not re-measure the slacks."
455 )));
456 }
457 crate::activity::reduced_activity(&state.backsolver, user_vars).map_err(|e| match e {
458 crate::activity::ReducedActivityError::OutOfRange { got, n_full_x } => {
459 SolverError::BadShape {
460 what: "reduced_activity variable index",
461 got,
462 expected: n_full_x,
463 }
464 }
465 crate::activity::ReducedActivityError::Backsolve => SolverError::BacksolveFailed,
466 })
467 }
468
469 /// [`Self::classify_activity`]'s per-ROW verdict for `user_rows`,
470 /// re-measured against the **reduced** curvature along each row's
471 /// gradient instead of the directional curvature `∇dᵀH∇d/‖∇d‖²` —
472 /// one back-solve against the held factor per row (gh#804).
473 ///
474 /// The row counterpart of [`Self::reduced_activity`], and the same
475 /// defect one block over. A row's directional denominator is a
476 /// genuine curvature along the row's own gradient — strictly
477 /// better than the variable path's bare `H_ii`, which is why
478 /// gh#763 fixed the variables first — but it is still not
479 /// *reduced*: it does not account for the other free coordinates
480 /// re-optimizing, and the multiplier is generated by what is left
481 /// after they do. So a row's ratio there is
482 /// `reduced/directional`, equal to `1` only where the row's
483 /// direction is decoupled from the remaining free space, and a
484 /// genuine row kink that is coupled reads
485 /// [`AMBIGUOUS`](crate::activity::AMBIGUOUS) at any tolerance —
486 /// the ratio is `μ`-independent. Ask here and the same kink reads
487 /// [`WEAKLY_ACTIVE`](crate::activity::WEAKLY_ACTIVE).
488 ///
489 /// Indices are **user space** (full-g), as the report's are —
490 /// equality rows included, which report
491 /// [`EQUALITY`](crate::activity::EQUALITY) rather than being an
492 /// error. The intended call is over a report's ambiguous rows:
493 ///
494 /// ```ignore
495 /// let report = solver.classify_activity()?;
496 /// let ask: Vec<usize> = (0..report.row_status.len())
497 /// .filter(|&j| report.row_status[j] == AMBIGUOUS)
498 /// .collect();
499 /// let refined = solver.reduced_row_activity(&ask)?;
500 /// ```
501 ///
502 /// The cost is one back-solve per index, so it is a refinement to
503 /// call over the rows in question, not over every bounded row of a
504 /// large model. See [`crate::activity::reduced_row_activity`] for
505 /// the algebra and the edge cases.
506 ///
507 /// Requires the held solve to have run with `bound_relax_factor=0`
508 /// for the same reason [`Self::classify_activity`] does: both read
509 /// the slacks relaxed bounds shift.
510 pub fn reduced_row_activity(
511 &self,
512 user_rows: &[usize],
513 ) -> Result<ReducedRowActivityReport, SolverError> {
514 let state = self.state.borrow();
515 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
516 let brf = state.bound_relax_factor;
517 if brf != 0.0 {
518 return Err(SolverError::BadOptions(format!(
519 "reduced_row_activity requires bound_relax_factor=0, but the \
520 held solve ran with {brf:e}: relaxed bounds shift the \
521 slacks the classifier reads. Set the option and solve() \
522 again — changing it now does not re-measure the slacks."
523 )));
524 }
525 crate::activity::reduced_row_activity(&state.backsolver, user_rows).map_err(|e| match e {
526 crate::activity::ReducedRowActivityError::OutOfRange { got, n_full_g } => {
527 SolverError::BadShape {
528 what: "reduced_row_activity constraint index",
529 got,
530 expected: n_full_g,
531 }
532 }
533 crate::activity::ReducedRowActivityError::Backsolve => SolverError::BacksolveFailed,
534 })
535 }
536
537 /// The gradient of user constraint row `user_row` at the converged
538 /// iterate, in user variable order (length `n_full_x`) and in
539 /// **natural (unscaled) units**: the internal Jacobian row carries
540 /// the solver's per-row `c_scale`/`d_scale`, which is divided out
541 /// here, so this is the gradient of the row as the user wrote it.
542 /// Equality and inequality rows alike; entries for fixed
543 /// (`make_parameter`-removed) variables are 0 because the solve
544 /// dropped their columns. Errors on an out-of-range row.
545 ///
546 /// Serves the covariance roadmap's item 1: a binding row's normal
547 /// restricted to the fitted block is the projection direction.
548 pub fn row_normal(&self, user_row: usize) -> Result<Vec<Number>, SolverError> {
549 let state = self.state.borrow();
550 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
551 crate::activity::row_normal(&state.backsolver, user_row).map_err(|m| {
552 SolverError::BadShape {
553 what: "row_normal constraint index",
554 got: user_row,
555 expected: m,
556 }
557 })
558 }
559
560 /// The exact Lagrangian Hessian times a user-space vector, in
561 /// user variable order and natural units (see
562 /// [`crate::activity::hessian_vec`]). Errors on a length mismatch.
563 pub fn hessian_vec(&self, v: &[Number]) -> Result<Vec<Number>, SolverError> {
564 let state = self.state.borrow();
565 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
566 crate::activity::hessian_vec(&state.backsolver, v).map_err(|n| SolverError::BadShape {
567 what: "hessian_vec vector length",
568 got: v.len(),
569 expected: n,
570 })
571 }
572
573 /// Solve `K · lhs = rhs` against the converged KKT factor. Both
574 /// slices must have length `kkt_dim()`; the layout is the flat
575 /// `x || s || y_c || y_d || z_l || z_u || v_l || v_u` packing.
576 ///
577 /// `K` here is the **natural-units** (unscaled) KKT matrix: when
578 /// the IPM solved with active NLP scaling, the backsolver scales
579 /// the RHS/solution (all eight blocks, including the z/v
580 /// bound-multiplier rows) so callers pass and receive data in the
581 /// user's own units (pounce#128) — see
582 /// [`crate::PdSensBacksolver::solve`]. For the raw scaled-space
583 /// back-solve use [`Self::kkt_solve_scaled`].
584 pub fn kkt_solve(&self, rhs: &[Number], lhs: &mut [Number]) -> Result<(), SolverError> {
585 self.kkt_solve_impl(rhs, lhs, false)
586 }
587
588 /// [`Self::kkt_solve`] without the natural-units conjugation: the
589 /// back-solve runs against the factor exactly as the IPM holds it
590 /// (the solver's internal scaled space). Identical to `kkt_solve`
591 /// when no NLP scaling is active. "Scaled space" includes a
592 /// `user-scaling` change of variables (gh#486), so on such a solve
593 /// the `x` and `z` blocks here are in the substituted coordinates
594 /// `x̃ = d ⊙ x`, not the model's.
595 pub fn kkt_solve_scaled(&self, rhs: &[Number], lhs: &mut [Number]) -> Result<(), SolverError> {
596 self.kkt_solve_impl(rhs, lhs, true)
597 }
598
599 fn kkt_solve_impl(
600 &self,
601 rhs: &[Number],
602 lhs: &mut [Number],
603 scaled: bool,
604 ) -> Result<(), SolverError> {
605 let state = self.state.borrow();
606 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
607 let total = state.backsolver.dim();
608 if rhs.len() != total {
609 return Err(SolverError::BadShape {
610 what: "rhs",
611 got: rhs.len(),
612 expected: total,
613 });
614 }
615 if lhs.len() != total {
616 return Err(SolverError::BadShape {
617 what: "lhs",
618 got: lhs.len(),
619 expected: total,
620 });
621 }
622 let ok = if scaled {
623 state.backsolver.solve_scaled_space(rhs, lhs)
624 } else {
625 state.backsolver.solve(rhs, lhs)
626 };
627 if ok {
628 Ok(())
629 } else {
630 Err(SolverError::BacksolveFailed)
631 }
632 }
633
634 /// Batched-RHS back-solve. `rhs_flat` and `lhs_flat` are row-major
635 /// `(n_rhs, kkt_dim)` buffers; each row is solved against the
636 /// same converged factor. Equivalent in result to looping
637 /// [`Self::kkt_solve`] but reuses one `IteratesVector` for the
638 /// RHS and one for the result across all `n_rhs` calls — see
639 /// [`crate::algorithm_backsolver::PdSensBacksolver::solve_many`].
640 pub fn kkt_solve_many(
641 &self,
642 rhs_flat: &[Number],
643 lhs_flat: &mut [Number],
644 n_rhs: usize,
645 ) -> Result<(), SolverError> {
646 self.kkt_solve_many_impl(rhs_flat, lhs_flat, n_rhs, false)
647 }
648
649 /// [`Self::kkt_solve_many`] without the natural-units
650 /// conjugation (the batched sibling of [`Self::kkt_solve_scaled`]).
651 pub fn kkt_solve_many_scaled(
652 &self,
653 rhs_flat: &[Number],
654 lhs_flat: &mut [Number],
655 n_rhs: usize,
656 ) -> Result<(), SolverError> {
657 self.kkt_solve_many_impl(rhs_flat, lhs_flat, n_rhs, true)
658 }
659
660 fn kkt_solve_many_impl(
661 &self,
662 rhs_flat: &[Number],
663 lhs_flat: &mut [Number],
664 n_rhs: usize,
665 scaled: bool,
666 ) -> Result<(), SolverError> {
667 let state = self.state.borrow();
668 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
669 let total = state.backsolver.dim();
670 let expected = n_rhs * total;
671 if rhs_flat.len() != expected {
672 return Err(SolverError::BadShape {
673 what: "rhs",
674 got: rhs_flat.len(),
675 expected,
676 });
677 }
678 if lhs_flat.len() != expected {
679 return Err(SolverError::BadShape {
680 what: "lhs",
681 got: lhs_flat.len(),
682 expected,
683 });
684 }
685 let ok = if scaled {
686 state
687 .backsolver
688 .solve_many_scaled_space(rhs_flat, lhs_flat, n_rhs)
689 } else {
690 state.backsolver.solve_many(rhs_flat, lhs_flat, n_rhs)
691 };
692 if ok {
693 Ok(())
694 } else {
695 Err(SolverError::BacksolveFailed)
696 }
697 }
698
699 /// First-order parametric step `Δx ≈ ∂x*/∂p · Δp` for a set of
700 /// pinned equality constraints. `pin_constraint_indices` are
701 /// 0-based indices into the user's `g(x)`; `deltas` is the
702 /// perturbation `Δp` (same length).
703 ///
704 /// Returns the `n_x`-long primal step. For the full KKT-space
705 /// step, use [`Self::kkt_solve`] directly.
706 pub fn parametric_step(
707 &self,
708 pin_constraint_indices: &[Index],
709 deltas: &[Number],
710 ) -> Result<Vec<Number>, SolverError> {
711 if pin_constraint_indices.len() != deltas.len() {
712 return Err(SolverError::BadShape {
713 what: "deltas",
714 got: deltas.len(),
715 expected: pin_constraint_indices.len(),
716 });
717 }
718 let state = self.state.borrow();
719 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
720
721 // Map user g-indices to y_c rows through the NLP's c/d-split
722 // permutation (pounce#128; matches `convenience.rs`).
723 let dims = state.backsolver.block_dims();
724 let n_x = dims[0];
725 let param_rows = state
726 .backsolver
727 .map_pin_g_to_kkt_rows(pin_constraint_indices)
728 .map_err(SolverError::SensComputationFailed)?;
729 let signs = vec![1; pin_constraint_indices.len()];
730 let a_data = IndexSchurData::from_parts(param_rows, signs)
731 .map_err(|e| SolverError::SensComputationFailed(format!("{e:?}")))?;
732
733 let opts = SensOptions {
734 run_sens: true,
735 ..SensOptions::default()
736 };
737 let sens_app = SensApplication::new(a_data, state.backsolver.clone(), opts);
738 let n_full = state.backsolver.dim();
739 let mut dx_full = vec![0.0; n_full];
740 if !sens_app.parametric_step(deltas, &mut dx_full) {
741 return Err(SolverError::SensComputationFailed(
742 "SensApplication::parametric_step failed".into(),
743 ));
744 }
745 // carry the step from the barrier problem's solution toward the
746 // original problem's (the paper's equation 11)
747 let corr = self.barrier_correction(state)?;
748 for (d, c) in dx_full.iter_mut().zip(corr.iter()) {
749 *d += *c * BARRIER_SIGN;
750 }
751 dx_full.truncate(n_x);
752 Ok(dx_full)
753 // NOTE: parametric_step_full below applies the same correction,
754 // so the two agree on their shared block.
755 }
756
757 /// The right-hand side [`Self::parametric_step_full`] answers,
758 /// barrier term included. That method adds the term as a correction
759 /// to the solution rather than to the right-hand side, which is the
760 /// same thing by linearity.
761 ///
762 /// The parameter rows go through `map_pin_g_to_kkt_rows` exactly as
763 /// they do there. Passing the constraint indices raw instead puts
764 /// the perturbation on the x rows, where it contributes nothing --
765 /// a release then sees only its own multiplier shift and lands on
766 /// the wrong answer without failing.
767 fn parametric_rhs_full(
768 &self,
769 pin_constraint_indices: &[Index],
770 deltas: &[Number],
771 ) -> Result<Vec<Number>, SolverError> {
772 let state = self.converged().ok_or(SolverError::NotConverged)?;
773 let state = &*state;
774 let dims = state.backsolver.block_dims();
775 let n_full = state.backsolver.dim();
776 let param_rows = state
777 .backsolver
778 .map_pin_g_to_kkt_rows(pin_constraint_indices)
779 .map_err(SolverError::SensComputationFailed)?;
780 let signs = vec![1; pin_constraint_indices.len()];
781 let a_data = IndexSchurData::from_parts(param_rows, signs)
782 .map_err(|e| SolverError::SensComputationFailed(format!("{e:?}")))?;
783 let opts = SensOptions {
784 run_sens: true,
785 ..SensOptions::default()
786 };
787 let sens_app = SensApplication::new(a_data, state.backsolver.clone(), opts);
788 let mut rhs = vec![0.0; n_full];
789 if !sens_app.parametric_rhs(deltas, &mut rhs) {
790 return Err(SolverError::SensComputationFailed(
791 "SensApplication::parametric_rhs failed".into(),
792 ));
793 }
794 let mu = state.backsolver.barrier_mu();
795 let start = dims[0] + dims[1] + dims[2] + dims[3];
796 let end = start + dims[4] + dims[5] + dims[6] + dims[7];
797 for r in rhs.iter_mut().take(end).skip(start) {
798 *r += mu * BARRIER_SIGN;
799 }
800 Ok(rhs)
801 }
802
803 /// The barrier correction of the parametric step: the paper's
804 /// equation 11 term, which carries the step from the solution of
805 /// the barrier problem at `mu > 0` toward the one at `mu = 0`.
806 ///
807 /// [`Self::parametric_step`] is taken against a factorization held
808 /// at the final `mu`, so it estimates where the BARRIER problem's
809 /// solution moves, not where the original problem's does. The two
810 /// differ by `O(mu)`, which is negligible at a tight tolerance and
811 /// is not at a loose one. Measured against sIPOPT on a nonlinear
812 /// model, the uncorrected step agrees to 2e-9 at `tol = 1e-8` and
813 /// differs by 9e-6 at `tol = 1e-3`.
814 ///
815 /// The term is one more backsolve against the same factor, with
816 /// `mu` in the complementarity rows, which are the bound multiplier
817 /// blocks of the compound vector.
818 ///
819 /// Returns the correction over the whole compound vector, to be
820 /// added to the step.
821 fn barrier_correction(&self, state: &ConvergedState) -> Result<Vec<Number>, SolverError> {
822 let dims = state.backsolver.block_dims();
823 let n_full = state.backsolver.dim();
824 let mu = state.backsolver.barrier_mu();
825 // z_l, z_u, v_l, v_u: the rows carrying the complementarity
826 // conditions, which are the ones the barrier perturbs
827 let start = dims[0] + dims[1] + dims[2] + dims[3];
828 let end = start + dims[4] + dims[5] + dims[6] + dims[7];
829 let mut rhs = vec![0.0; n_full];
830 for r in rhs.iter_mut().take(end).skip(start) {
831 *r = mu;
832 }
833 let mut corr = vec![0.0; n_full];
834 if !state.backsolver.solve(&rhs, &mut corr) {
835 return Err(SolverError::BacksolveFailed);
836 }
837 Ok(corr)
838 }
839
840 /// Parametric step with the bounds respected by pinning, not by
841 /// clamping. Returns the `n_x`-long primal step, the rows it
842 /// constrained to reach it, and why the refinement stopped.
843 ///
844 /// [`Self::parametric_step`] answers where the linear predictor
845 /// points, which can be outside the box. Clamping a coordinate
846 /// back to its bound leaves every other coordinate at its
847 /// predictor value, so the answer is feasible but no longer
848 /// consistent with the KKT relations. This instead adds a row
849 /// pinning each offending coordinate at its bound and re-solves, so
850 /// the others move to stay consistent under the pins, which is the
851 /// refinement upstream runs under `sens_boundcheck`.
852 ///
853 /// A pass takes every crossing it can see, pins them together, and
854 /// re-solves, so the loop ends when nothing is left outside rather
855 /// than when the passes run out. Each pass rebuilds the Schur
856 /// complement over the pins so far, so a pass carrying `k` of them
857 /// costs one dense `k × k` solve and `k + 1` back-solves; the
858 /// factorization itself is never rebuilt for a pin.
859 ///
860 /// What counts as outside a bound is the `eps` argument when the
861 /// caller passes one, and the solve's own margin when it passes
862 /// `None`: the solve was willing to leave a converged point
863 /// `bound_relax_factor` outside its bound, so anything within that
864 /// is on the bound. An unrelaxed solve gets a roundoff floor.
865 ///
866 /// Passes stop when nothing is outside its bound by that much, when
867 /// a pin cannot be achieved because the pins have exhausted the
868 /// problem's degrees of freedom, or at `max_iter`, which is a
869 /// safety limit rather than a budget: it took one pin per pass
870 /// until gh#732, where a model with more crossings than passes had
871 /// its answer picked by the limit. None of those is an error, and
872 /// the returned [`crate::boundcheck::RefineStop`] says which
873 /// happened.
874 pub fn parametric_step_bounded(
875 &self,
876 pin_constraint_indices: &[Index],
877 deltas: &[Number],
878 max_iter: usize,
879 bound_eps: Option<Number>,
880 ) -> Result<(Vec<Number>, Vec<Index>, crate::boundcheck::RefineStop), SolverError> {
881 let dx_full = self.parametric_step_full(pin_constraint_indices, deltas)?;
882 let rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
883 let ctx = self.bound_context(bound_eps)?;
884 let state = self.state.borrow();
885 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
886 let (dx, pinned, stop) = crate::boundcheck::refine_step_onto_bounds(
887 &state.backsolver,
888 &dx_full,
889 &ctx.x_curr,
890 &ctx.lo,
891 &ctx.hi,
892 &ctx.mults,
893 &rhs_plain,
894 ctx.eps,
895 ctx.release_eps,
896 max_iter,
897 )
898 .map_err(SolverError::SensComputationFailed)?;
899 Ok((
900 dx[..ctx.n_x].to_vec(),
901 pinned.into_iter().map(|p| p as Index).collect(),
902 stop,
903 ))
904 }
905
906 /// Parametric step applied a little at a time instead of taken
907 /// whole, stopping wherever the active set changes and continuing
908 /// from there under the new one. Returns the primal step and the
909 /// breakpoints crossed.
910 ///
911 /// [`Self::parametric_step_bounded`] decides every condition at the
912 /// base point, which is upstream's fix-relax. This is past it: the
913 /// result is piecewise linear in the parameter, exact for a QP
914 /// because a QP's solution is piecewise affine in the parameter,
915 /// and still a predictor for an NLP because nothing is
916 /// re-linearized between breakpoints.
917 ///
918 /// `max_iter` caps the breakpoints crossed. It is in practice a
919 /// budget on factorizations, since a pin is a back-solve against
920 /// the held factor while a release re-factors.
921 pub fn parametric_step_path(
922 &self,
923 pin_constraint_indices: &[Index],
924 deltas: &[Number],
925 max_iter: usize,
926 ) -> Result<(Vec<Number>, Vec<crate::boundcheck::PathSegment>), SolverError> {
927 let rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
928 // Nothing here decides the weak rows -- that is what the
929 // "decided" variant below is for -- but the walk still has to
930 // be told which they are, or it reads their order-one sigma as
931 // a bound the factorization enforces and lets the variable
932 // walk out of its box (gh#852). A relaxed solve shifts the
933 // slacks the classifier reads, so this comes back empty there
934 // and the walk behaves as it did before -- the same silence
935 // `weakly_active_bounds` hands every other caller.
936 let weak_rows: Vec<usize> = self.weakly_active_bounds()?.iter().map(|w| w.row).collect();
937 let ctx = self.bound_context(None)?;
938 let state = self.state.borrow();
939 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
940 let (dx, segments) = crate::boundcheck::step_along_path(
941 &state.backsolver,
942 &rhs_plain,
943 &ctx.x_curr,
944 &ctx.lo,
945 &ctx.hi,
946 &ctx.mults,
947 max_iter,
948 &[],
949 &[],
950 &weak_rows,
951 ctx.eps,
952 )
953 .map_err(SolverError::SensComputationFailed)?;
954 Ok((dx[..ctx.n_x].to_vec(), segments))
955 }
956
957 /// [`Self::parametric_step_path`] with the weak-row
958 /// decision supplied by the caller instead of searched for.
959 /// `held_var_rows` names the var-x rows of the weakly active
960 /// bounds the direction holds; every other weakly active bound is
961 /// forced into the walk's base-activity table as a leaving row.
962 /// A row left there is still reachable, so a caller that hands in
963 /// an empty held list — every weak row declared a leaver, which is
964 /// what an undecided study of the all-released step does — gets
965 /// the bound back at the fraction the walk finds the direction
966 /// pressing into it, rather than an answer outside the box
967 /// (gh#852). Study surface for an externally solved eq. 14 QP.
968 pub fn parametric_step_path_decided(
969 &self,
970 pin_constraint_indices: &[Index],
971 deltas: &[Number],
972 max_iter: usize,
973 held_var_rows: &[Index],
974 ) -> Result<(Vec<Number>, Vec<crate::boundcheck::PathSegment>), SolverError> {
975 let weak = self.weakly_active_bounds()?;
976 if weak.is_empty() {
977 return self.parametric_step_path(pin_constraint_indices, deltas, max_iter);
978 }
979 let mut rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
980 for w in &weak {
981 rhs_plain[w.row] = 0.0;
982 }
983 let held: std::collections::HashSet<usize> =
984 held_var_rows.iter().map(|&r| r as usize).collect();
985 let ctx = self.bound_context(None)?;
986 let state = self.state.borrow();
987 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
988 let holds: Vec<(usize, bool)> = weak
989 .iter()
990 .filter(|w| held.contains(&w.var_row))
991 .map(|w| (w.var_row, w.lower))
992 .collect();
993 let forced_active: Vec<usize> = weak
994 .iter()
995 .filter(|w| !held.contains(&w.var_row))
996 .map(|w| w.row)
997 .collect();
998 // Every weak row, held or leaving. For a held one the flag is
999 // inert -- it arrives released and pinned already -- and for a
1000 // leaving one it is what lets the walk take the bound back
1001 // when the direction turns out to press into it, which is the
1002 // whole of an empty held list on a holding perturbation
1003 // (gh#852).
1004 let weak_rows: Vec<usize> = weak.iter().map(|w| w.row).collect();
1005 let (dx, segments) = crate::boundcheck::step_along_path(
1006 &state.backsolver,
1007 &rhs_plain,
1008 &ctx.x_curr,
1009 &ctx.lo,
1010 &ctx.hi,
1011 &ctx.mults,
1012 max_iter,
1013 &forced_active,
1014 &holds,
1015 &weak_rows,
1016 ctx.eps,
1017 )
1018 .map_err(SolverError::SensComputationFailed)?;
1019 Ok((dx[..ctx.n_x].to_vec(), segments))
1020 }
1021
1022 /// Newton iterations on the barrier system, refining a step that
1023 /// some mode already produced.
1024 ///
1025 /// `step` is a full compound step, the shape
1026 /// [`Self::parametric_step_full`] returns, so any mode's result
1027 /// can be handed in. Every correction pays one derivative
1028 /// evaluation and one factorization at the predicted point, and
1029 /// each iteration after that costs one back-solve. Returns the
1030 /// refined step and a [`CorrectorReport`] saying what the
1031 /// iterations bought.
1032 ///
1033 /// The corrector aims at the barrier solution at the μ the solve
1034 /// finished on, not at a re-solve, so the accuracy it can reach is
1035 /// bounded by that offset. Its operator is assembled at the
1036 /// PREDICTED point, every block: the Hessian, the constraint
1037 /// Jacobians, and the barrier diagonal all evaluated at the
1038 /// stepped iterate with the step's own multipliers, and the
1039 /// predictor's active set applied to the diagonal in that frame.
1040 /// A base solve the sigma ceiling (gh#737) touched, or one that
1041 /// crossed over into the declared frame (gh#654), is no
1042 /// exception: both rules are re-derived at the predicted point
1043 /// rather than read from the base-point diagonals stored for the
1044 /// held factor's own back-solves.
1045 /// A chord iteration contracts at the rate the distance between
1046 /// its operator and the true Jacobian sets, and the predicted
1047 /// point is where the truth is. Under a `limited-memory` solve
1048 /// the quasi-Newton matrix is kept as is, since no exact Hessian
1049 /// exists to evaluate elsewhere. Where the perturbation needs a
1050 /// bound to leave the active set that the step's endpoint does
1051 /// not show, no released row is applied: the step's clamped
1052 /// multiplier leaves a weak diagonal entry there, the iterations
1053 /// can move the coordinate partway off the bound, and the answer
1054 /// is not the re-solve. The release-deciding modes are the ones
1055 /// that cross exactly. `CorrectorReport::improved` reports
1056 /// whether the residual fell; when it did not, the step handed
1057 /// back is the caller's own.
1058 ///
1059 /// The returned point always satisfies the variable bounds, since
1060 /// the barrier residual is undefined outside them and the
1061 /// fraction-to-boundary rule keeps every iterate inside. A step
1062 /// that arrives pointing out of the box is therefore put back in
1063 /// before the first iteration, which means `max_iter = 0` is not a
1064 /// no-op: it costs the derivative evaluation and the residual
1065 /// evaluation, no back-solve, and reports the residual the
1066 /// caller's step leaves.
1067 ///
1068 /// Errors with [`SolverError::SensComputationFailed`] when the
1069 /// barrier residual at that starting point is not finite, which is
1070 /// what a predicted point outside the domain of one of the model's
1071 /// functions gives (gh#845). A *declared bound* is protection here,
1072 /// since the clamp above puts the coordinate back inside it; a
1073 /// variable held in a function's domain by a **constraint** has no
1074 /// bound to be put back inside, and an ordinary `log`, `sqrt` or
1075 /// reciprocal is then reachable by a large enough perturbation.
1076 /// There is no correction to make from such a point, so it is an
1077 /// error rather than a report -- and never a step full of NaN
1078 /// carrying `residual = 0.0` and `converged = true`.
1079 pub fn correct_step(
1080 &self,
1081 pin_constraint_indices: &[Index],
1082 deltas: &[Number],
1083 step: &[Number],
1084 max_iter: usize,
1085 ) -> Result<(Vec<Number>, crate::corrector::CorrectorReport), SolverError> {
1086 let ctx = self.bound_context(None)?;
1087 let state = self.state.borrow();
1088 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1089 let bs = &state.backsolver;
1090 let dim = bs.dim();
1091 if step.len() != dim {
1092 return Err(SolverError::BadShape {
1093 what: "step",
1094 got: step.len(),
1095 expected: dim,
1096 });
1097 }
1098 // `>= 0`, not `> 0`: `barrier_mu` reports exactly zero for a
1099 // point whose bound multipliers were zeroed on the way out (see
1100 // its doc comment), and that is a barrier level, not a missing
1101 // one. The complementarity rows are then already satisfied
1102 // where they stand, which is what the corrector should measure.
1103 let mu = {
1104 let m = bs.barrier_mu();
1105 if m >= 0.0 && m.is_finite() {
1106 m
1107 } else {
1108 return Err(SolverError::SensComputationFailed(
1109 "corrector: the solve reported no barrier parameter".into(),
1110 ));
1111 }
1112 };
1113 let base = {
1114 let mut flat = vec![0.0; dim];
1115 bs.curr_flat(&mut flat).map_err(|_| {
1116 SolverError::SensComputationFailed(
1117 "corrector: converged iterate unavailable".into(),
1118 )
1119 })?;
1120 flat
1121 };
1122 // The pinned equalities' KKT rows and the row scales the
1123 // algorithm applied to them. A user `g` index is not the KKT
1124 // row: the two differ once an inequality precedes the pin in
1125 // `g(x)` (pounce#128), and the residual the corrector measures
1126 // sits in the algorithm's scaled equality block, so the deltas
1127 // have to carry the same factors.
1128 let (pin_rows, pin_scales) = bs
1129 .pin_rows_and_c_scales(pin_constraint_indices)
1130 .map_err(SolverError::SensComputationFailed)?;
1131 let pin_rows: Vec<usize> = pin_rows.iter().map(|&r| r as usize).collect();
1132 let scaled_deltas: Vec<Number> = deltas
1133 .iter()
1134 .zip(&pin_scales)
1135 .map(|(&d, &c)| d * c)
1136 .collect();
1137 crate::corrector::run(
1138 bs,
1139 &base,
1140 step,
1141 &pin_rows,
1142 &scaled_deltas,
1143 &ctx.lo,
1144 &ctx.hi,
1145 mu,
1146 max_iter,
1147 state.exact_hessian,
1148 )
1149 }
1150
1151 /// [`Self::parametric_step_bounded`] with the weak-row
1152 /// decision supplied by the caller instead of searched for. The
1153 /// direction is computed for the given working set (all weak rows
1154 /// released, the held variables pinned through Schur rows), then
1155 /// refined onto the bounds exactly as the searched variant does.
1156 /// Study surface for an externally solved eq. 14 QP.
1157 pub fn parametric_step_bounded_decided(
1158 &self,
1159 pin_constraint_indices: &[Index],
1160 deltas: &[Number],
1161 max_iter: usize,
1162 held_var_rows: &[Index],
1163 bound_eps: Option<Number>,
1164 ) -> Result<(Vec<Number>, Vec<Index>, crate::boundcheck::RefineStop), SolverError> {
1165 let weak = self.weakly_active_bounds()?;
1166 if weak.is_empty() {
1167 return self.parametric_step_bounded(
1168 pin_constraint_indices,
1169 deltas,
1170 max_iter,
1171 bound_eps,
1172 );
1173 }
1174 let rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
1175 let ctx = self.bound_context(bound_eps)?;
1176 let state = self.state.borrow();
1177 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1178 let released: Vec<usize> = weak.iter().map(|w| w.row).collect();
1179 let pinned_rows: Vec<usize> = held_var_rows.iter().map(|&r| r as usize).collect();
1180 let (d, _) = crate::boundcheck::path_direction(
1181 &state.backsolver,
1182 &rhs_plain,
1183 &released,
1184 &pinned_rows,
1185 )
1186 .map_err(SolverError::SensComputationFailed)?;
1187 let (dx, pinned, stop) = crate::boundcheck::refine_step_onto_bounds(
1188 &state.backsolver,
1189 &d,
1190 &ctx.x_curr,
1191 &ctx.lo,
1192 &ctx.hi,
1193 &ctx.mults,
1194 &rhs_plain,
1195 ctx.eps,
1196 ctx.release_eps,
1197 max_iter,
1198 )
1199 .map_err(SolverError::SensComputationFailed)?;
1200 Ok((
1201 dx[..ctx.n_x].to_vec(),
1202 pinned.into_iter().map(|p| p as Index).collect(),
1203 stop,
1204 ))
1205 }
1206
1207 /// [`crate::boundcheck::path_direction`] for a working set the
1208 /// caller names, and the force each held row carries under it.
1209 /// Study surface, and the seam the two pins are measured against
1210 /// each other through.
1211 ///
1212 /// `released_bound_rows` are compound bound-multiplier rows, as
1213 /// [`Self::weakly_active_bounds`] reports them;
1214 /// `held_primal_rows` are primal rows -- `x` block for a
1215 /// variable, `s` block for a constraint's own limit (gh#928).
1216 ///
1217 /// `operator` picks which *operator* the walk's (single, exact)
1218 /// Schur pin is applied to.
1219 /// [`Plain`](PathOperator::Plain) is the released system as the
1220 /// factorization already holds it -- one factorization for the
1221 /// whole segment, and no inverse at all when releasing two
1222 /// curvature-free variables that share a row leaves the
1223 /// stationarity rows dependent (gh#930).
1224 /// [`Regularized`](PathOperator::Regularized) raises the pinned
1225 /// diagonals until it is invertible, at the cost of rebuilding
1226 /// the diagonal per solve, so the factorization cache misses.
1227 /// [`Preferred`](PathOperator::Preferred) is what the walk itself
1228 /// runs: the plain one, falling back when it fails *or when its
1229 /// pins do not take*, which is not the same test -- see
1230 /// [`crate::boundcheck::path_direction`].
1231 ///
1232 /// Both operators give the same answer: the Schur row enforces
1233 /// `Eᵀ w = 0`, which annihilates the added diagonal, so the
1234 /// system solved is the released one either way and both return
1235 /// values agree in value, frame and units.
1236 /// `issue_930_two_curvature_free_releases.rs` measures that.
1237 pub fn path_direction_decided(
1238 &self,
1239 pin_constraint_indices: &[Index],
1240 deltas: &[Number],
1241 released_bound_rows: &[Index],
1242 held_primal_rows: &[Index],
1243 operator: PathOperator,
1244 ) -> Result<(Vec<Number>, Vec<Number>), SolverError> {
1245 let rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
1246 let state = self.state.borrow();
1247 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1248 let released: Vec<usize> = released_bound_rows.iter().map(|&r| r as usize).collect();
1249 let held: Vec<usize> = held_primal_rows.iter().map(|&r| r as usize).collect();
1250 crate::boundcheck::path_direction_with(
1251 &state.backsolver,
1252 &rhs_plain,
1253 &released,
1254 &held,
1255 operator,
1256 )
1257 .map_err(SolverError::SensComputationFailed)
1258 }
1259
1260 /// The all-released step: the plain parametric step solved with
1261 /// every weakly active bound's row released, and nothing decided.
1262 ///
1263 /// This is [`Self::parametric_step_directional`]'s first
1264 /// back-solve returned as the answer instead of refined. The
1265 /// caller trades the engagement's budget for whatever violations
1266 /// the released direction carries at weak bounds the perturbation
1267 /// actually holds, which come back as crossings for the mode's
1268 /// clamp, pins, or path segments, or for a correction, to handle.
1269 /// A clean base point takes the plain step. Returns the direction
1270 /// over the model's variables and the number of rows released.
1271 pub fn parametric_step_release_all(
1272 &self,
1273 pin_constraint_indices: &[Index],
1274 deltas: &[Number],
1275 ) -> Result<(Vec<Number>, usize), SolverError> {
1276 let rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
1277 let weak = self.weakly_active_bounds()?;
1278 let ctx = self.bound_context(None)?;
1279 let state = self.state.borrow();
1280 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1281 let released: Vec<usize> = weak.iter().map(|w| w.row).collect();
1282 let mut d = vec![0.0; state.backsolver.dim()];
1283 // solve_released is the whole mechanism: an empty released set
1284 // is the plain solve, and shift = false matches the
1285 // directional path's all-released solve, whose rationale lives
1286 // on `solve_released_inner`.
1287 if !state
1288 .backsolver
1289 .solve_released(&released, &rhs_plain, &mut d)
1290 {
1291 return Err(SolverError::BacksolveFailed);
1292 }
1293 Ok((d[..ctx.n_x].to_vec(), released.len()))
1294 }
1295
1296 /// The eq. 14 directional derivative, decided by pounce-qp over
1297 /// the weak rows the direction engages.
1298 ///
1299 /// One released factorization serves the whole decision: the
1300 /// released `Σ` is built once and every solve passes the same
1301 /// object, so the factorization cache reuses the factor across the
1302 /// all-released direction and the basis columns. The decision
1303 /// itself is the dual of eq. 14 restricted to the weak rows the
1304 /// direction engages: with `a_k` the signed unit vector of weak
1305 /// row `k` (positive for a lower bound), `X_k = K_rel^{-1} a_k`,
1306 /// `S = aᵀX` and `m = aᵀd0`, the pin forces `λ` solve
1307 ///
1308 /// ```text
1309 /// min ½ λᵀ S λ + mᵀ λ s.t. λ ≥ 0
1310 /// ```
1311 ///
1312 /// whose KKT conditions are eq. 14's complementarity: a released
1313 /// row moves to its feasible side (the QP gradient `Sλ + m ≥ 0`)
1314 /// and a held row's pin force is nonnegative. Rows outside the
1315 /// engaged set are verified against the decided direction and the
1316 /// set expands until no new row violates. Nothing reads the
1317 /// perturbation's size, so the decision is linear in the step.
1318 ///
1319 /// An engaged row is decided only when its bound is at a kink,
1320 /// read off `kappa = sigma * S_kk`, the barrier weight times the
1321 /// row's own diagonal of the reduced matrix. `sigma` equals the
1322 /// curvature reduced along the coordinate at an exact kink, and
1323 /// `S_kk` is that reduced curvature's inverse, so `kappa` is 1
1324 /// there at any curvature, coupling, or scaling, and it falls as
1325 /// the squared ratio of kink width to slack away from one. A row
1326 /// below `KAPPA_MIN` is dropped from the engaged set and its
1327 /// plain movement stands: its bound is too far from a kink for a
1328 /// pin force to decide, and the error of leaving it undecided is
1329 /// bounded by its own slack, order `sqrt(mu)` at the threshold.
1330 /// A coordinate an equality pins is the limiting case, `S_kk`
1331 /// exactly zero, dropped by the same test.
1332 ///
1333 /// `max_iter` is the total back-solve budget: the all-released
1334 /// solve, every basis column, and the combined solve that recovers
1335 /// the direction all count against it. A budget of zero errs
1336 /// before any work. Any budget above that pays the all-released
1337 /// factorization first, because which rows engage is only known
1338 /// once that solve has run, and the shortfall is reported when the
1339 /// basis columns cannot fit. Either way the caller falls back to
1340 /// the one-sided step. Returns the direction, the var-x rows held,
1341 /// and the back-solves spent.
1342 pub fn parametric_step_directional(
1343 &self,
1344 pin_constraint_indices: &[Index],
1345 deltas: &[Number],
1346 max_iter: usize,
1347 ) -> Result<(Vec<Number>, Vec<usize>, usize), SolverError> {
1348 use pounce_common::types::NLP_UPPER_BOUND_INF;
1349 use pounce_linalg::triplet::{GenTMatrix, GenTMatrixSpace, SymTMatrix, SymTMatrixSpace};
1350 use pounce_qp::QpStatus;
1351 use pounce_qp::options::QpOptions;
1352 use pounce_qp::problem::{HessianInertia, QpProblem};
1353 use pounce_qp::solver::{ParametricActiveSetSolver, QpSolver};
1354
1355 const EPS_REL: Number = 1e-9;
1356 /// A row whose `kappa = sigma * S_kk` is below this is not at
1357 /// a kink and is dropped from the QP. `kappa` is 1 at an
1358 /// exact kink and equals the squared ratio of kink width to
1359 /// slack, so a row at the threshold sits about 30 widths from
1360 /// its bound and the cost of deciding it either way is
1361 /// bounded by that slack. Measured populations: exact fixture
1362 /// kinks 1.0, held solves near a release 4e-2 and 6e-3,
1363 /// genuinely interior rows 3e-8 and below, pin-owned rows at
1364 /// or below zero.
1365 const KAPPA_MIN: Number = 1e-3;
1366
1367 let rhs_plain = self.parametric_rhs_full(pin_constraint_indices, deltas)?;
1368 let weak = self.weakly_active_bounds()?;
1369 let ctx = self.bound_context(None)?;
1370 let state = self.state.borrow();
1371 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1372 let bs = &state.backsolver;
1373 let dim = bs.dim();
1374 let n_x = ctx.n_x;
1375 let nw = weak.len();
1376 let mut work = 0usize;
1377 // A weak bound's slack and multiplier are both of order
1378 // sqrt(mu) and their uncertainty equals their magnitude, so a
1379 // movement below sqrt(mu) of the direction's scale cannot be
1380 // resolved against the bound and does not warrant an exact
1381 // complementarity decision. The engagement and expansion
1382 // tests use this band; acceptance-level roundoff tests keep
1383 // EPS_REL.
1384 let band = bs.barrier_mu().max(0.0).sqrt().max(EPS_REL);
1385
1386 if weak.is_empty() {
1387 // a clean base point takes the plain step and no decision
1388 // happens, so the reported decision work is zero
1389 let mut d = vec![0.0; dim];
1390 if !bs.solve(&rhs_plain, &mut d) {
1391 return Err(SolverError::BacksolveFailed);
1392 }
1393 return Ok((d[..n_x].to_vec(), Vec::new(), 0));
1394 }
1395
1396 // What the caller needs is the number to raise
1397 // `degeneracy_iter` to, so the message reports the engaged
1398 // count rather than the weak-set size: engagement is the retry
1399 // price, and on a model with hundreds of weak bounds the two
1400 // differ by enough that raising one at a time is dozens of
1401 // retries. The engaged set can still grow on a later pass, so
1402 // the figure is a floor and says so.
1403 //
1404 // `engaged_now + 2` prices a decision that finishes on one
1405 // pass. Each expansion round pays another combined solve, so
1406 // on a multi-pass decision that total is short, and once the
1407 // engaged set stops growing it stops moving at all: the
1408 // combined solve of the last round would otherwise be told to
1409 // raise the budget to the number already spent, which is a
1410 // retry that buys nothing and reads as self-contradictory.
1411 // Flooring at `spent + 1` keeps the advice strictly larger
1412 // than what is gone, so every retry makes progress.
1413 let budget = |engaged_now: usize, spent: usize| {
1414 let need = (engaged_now + 2).max(spent + 1);
1415 SolverError::SensComputationFailed(format!(
1416 "directional derivative: {spent} of {max_iter} back-solve(s) \
1417 spent, and {engaged_now} of {nw} weakly active bound(s) are \
1418 engaged so far. Raise degeneracy_iter to at least {need}; \
1419 the engaged set can still grow, so that is a floor."
1420 ))
1421 };
1422 let fail = |what: &str| {
1423 SolverError::SensComputationFailed(format!("directional derivative: {what}"))
1424 };
1425
1426 let released: Vec<usize> = weak.iter().map(|w| w.row).collect();
1427 // `weak` comes from `weakly_active_bounds`, which is keyed by
1428 // a var-x row and so can only ever name a bound in the `x`
1429 // block. Constraint-row limits (gh#928) live in the `s` block
1430 // and would need the second diagonal below; releasing one here
1431 // with the `s` diagonal left at its base value would solve a
1432 // system that still enforces the bound it claims to have
1433 // released, silently. Asked for rather than assumed: the
1434 // second slot is `None` exactly when nothing in `released`
1435 // touched the `s` block, so a non-`None` here means the
1436 // premise this arm rests on has stopped holding.
1437 let (sigma, sigma_s) = bs
1438 .released_sigmas(&released)
1439 .ok_or_else(|| fail("released sigma unavailable"))?;
1440 if sigma_s.is_some() {
1441 return Err(fail(
1442 "a released bound reached the `s` block. The directional \
1443 decision is built on `weakly_active_bounds`, whose rows are \
1444 var-x, so this cannot happen without that contract having \
1445 changed -- and releasing an `s`-block bound needs the slack \
1446 diagonal this arm does not carry.",
1447 ));
1448 }
1449 if work + 1 > max_iter {
1450 // Nothing is engaged before the all-released solve, so
1451 // this fires only at a budget of zero, and the floor is
1452 // the one solve the decision cannot start without.
1453 return Err(SolverError::SensComputationFailed(format!(
1454 "directional derivative: degeneracy_iter is {max_iter}, and the \
1455 decision cannot start without one back-solve over the {nw} \
1456 weakly active bound(s). Raise degeneracy_iter to at least 2."
1457 )));
1458 }
1459 let mut d0 = vec![0.0; dim];
1460 // shift = false, matching `path_direction`'s all-released
1461 // solve: a weak bound's multiplier is order sqrt(mu) and the
1462 // released convention holds it at exactly zero, so the step
1463 // shift's multiplier injection is deliberately omitted.
1464 if !bs.solve_released_prebuilt(
1465 &released,
1466 Rc::clone(&sigma),
1467 None,
1468 None,
1469 &rhs_plain,
1470 &mut d0,
1471 false,
1472 ) {
1473 return Err(SolverError::BacksolveFailed);
1474 }
1475 work += 1;
1476
1477 // movement of weak row k under a direction: positive is the
1478 // feasible side for that row's bound
1479 let sign = |k: usize| if weak[k].lower { 1.0 } else { -1.0 };
1480 let movement = |k: usize, d: &[Number]| -> Number { sign(k) * d[weak[k].var_row] };
1481 // The barrier weight of each weak row's variable, in natural
1482 // units to match the natural-units response the back-solves
1483 // return, so `kappa` below is frame-invariant. The classifier
1484 // succeeded inside `weakly_active_bounds`, so a nonempty weak
1485 // set implies this call succeeds too.
1486 // `var_sigma` is a FULL-x array read from a VAR-x row, and the
1487 // `unwrap_or(0.0)` below turns a miss into a zero that silently
1488 // drops the row from the engaged set rather than raising. That
1489 // is the shape gh#672 finding 1 shipped, so the index is typed:
1490 // `sigma.at` takes a `FullX` and a bare `w.var_row` will not
1491 // compile. See `crate::index`.
1492 let nat_sigma: Vec<Number> = {
1493 let report = self.classify_activity()?;
1494 let (_, _, nlp) = state.backsolver.activity_handles();
1495 let nl = nlp.borrow();
1496 let sigma = FullXSlice::new(&report.var_sigma);
1497 let map = VarToFull::build(ctx.n_x, |r| nl.var_x_to_full_x(r.as_index()) as usize);
1498 weak.iter()
1499 .map(|w| {
1500 map.full_of(VarX::new(w.var_row))
1501 .and_then(|full| sigma.at(full))
1502 .unwrap_or(0.0)
1503 })
1504 .collect()
1505 };
1506 let scale_of = |d: &[Number]| -> Number {
1507 d[..n_x]
1508 .iter()
1509 .fold(0.0_f64, |a, &b| a.max(b.abs()))
1510 .max(1e-300)
1511 };
1512
1513 let tol0 = band * scale_of(&d0);
1514 let mut engaged: Vec<usize> = (0..nw).filter(|&k| movement(k, &d0) < -tol0).collect();
1515 if engaged.is_empty() {
1516 return Ok((d0[..n_x].to_vec(), Vec::new(), work));
1517 }
1518
1519 // Each basis column is only ever read at the weak rows' own
1520 // variables, once to build `S` and never again: the direction
1521 // it contributes is recovered below in a single solve. So the
1522 // column is projected onto those `nw` entries and the
1523 // full-length vector dropped, which bounds this by the weak
1524 // set rather than by `dim` times the budget. Holding the full
1525 // columns costs about 114 MB on a 62k model at 230 engaged
1526 // rows, and grows with `degeneracy_iter`.
1527 let mut proj: Vec<Option<Vec<Number>>> = vec![None; nw];
1528 let mut d = d0.clone();
1529 let held: Vec<usize>;
1530 // A weak row is decided only when its bound is at a kink,
1531 // and `kappa = sigma * S_kk` measures exactly that: 1 at an
1532 // exact kink, falling as the squared ratio of kink width to
1533 // slack away from one. A row below the threshold is dropped
1534 // and its plain movement stands, since a pin force there
1535 // holds the coordinate a full slack from where the bound
1536 // actually is, and the error of not deciding is bounded by
1537 // that same slack. The limiting cases fall out of the one
1538 // test: a coordinate an equality owns has `S_kk` exactly
1539 // zero (its pin absorbs any bound force, and admitting it
1540 // puts a zero diagonal beside a nonzero gradient, an
1541 // unbounded QP), and a negative diagonal, which the QP could
1542 // not bound either, is likewise below the threshold.
1543 let mut inert: Vec<usize> = Vec::new();
1544 loop {
1545 for &k in &engaged {
1546 if proj[k].is_some() {
1547 continue;
1548 }
1549 if work + 1 > max_iter {
1550 return Err(budget(engaged.len(), work));
1551 }
1552 let mut unit = vec![0.0; dim];
1553 unit[weak[k].var_row] = sign(k);
1554 let mut xk = vec![0.0; dim];
1555 if !bs.solve_released_prebuilt(
1556 &released,
1557 Rc::clone(&sigma),
1558 None,
1559 None,
1560 &unit,
1561 &mut xk,
1562 false,
1563 ) {
1564 return Err(SolverError::BacksolveFailed);
1565 }
1566 work += 1;
1567 let col: Vec<Number> = weak.iter().map(|w| xk[w.var_row]).collect();
1568 let own = sign(k) * col[k];
1569 if nat_sigma[k] * own < KAPPA_MIN {
1570 inert.push(k);
1571 }
1572 proj[k] = Some(col);
1573 }
1574 engaged.retain(|k| !inert.contains(k));
1575 if engaged.is_empty() {
1576 return Ok((d[..n_x].to_vec(), Vec::new(), work));
1577 }
1578
1579 // dense reduced data over the engaged rows, upper triangle
1580 let ke = engaged.len();
1581 let mut irows = Vec::new();
1582 let mut jcols = Vec::new();
1583 let mut vals = Vec::new();
1584 for i in 0..ke {
1585 for j in i..ke {
1586 let col_j = proj[engaged[j]].as_ref().expect("column built");
1587 let col_i = proj[engaged[i]].as_ref().expect("column built");
1588 // S_ij = a_i^T X_j; symmetrize, since S is
1589 // symmetric in exact arithmetic. The projection
1590 // holds one entry per weak row, so a weak row's
1591 // own index is where its `a` picks the column out.
1592 let s_ij = 0.5
1593 * (sign(engaged[i]) * col_j[engaged[i]]
1594 + sign(engaged[j]) * col_i[engaged[j]]);
1595 // pounce-linalg triplets are one-based
1596 irows.push((i + 1) as Index);
1597 jcols.push((j + 1) as Index);
1598 vals.push(s_ij);
1599 }
1600 }
1601 // The engine's feasibility and optimality tolerances are
1602 // absolute and act on the QP's variables, which are the
1603 // pin forces, so both sides of the problem are scaled to
1604 // order one: the gradient against the direction's scale
1605 // (a 1e-10 perturbation must decide the same way a 1e-2
1606 // one does) and S against its largest entry, which is a
1607 // compliance in the model's units. The joint scaling maps
1608 // the solution by g_scale / s_scale exactly, so the
1609 // scaled solve loses nothing.
1610 let g_raw: Vec<Number> = engaged.iter().map(|&k| movement(k, &d0)).collect();
1611 let g_scale = g_raw
1612 .iter()
1613 .fold(0.0_f64, |a, &b| a.max(b.abs()))
1614 .max(1e-300);
1615 let g: Vec<Number> = g_raw.iter().map(|&v| v / g_scale).collect();
1616 let s_scale = vals
1617 .iter()
1618 .fold(0.0_f64, |a, &b| a.max(b.abs()))
1619 .max(1e-300);
1620 let vals_scaled: Vec<Number> = vals.iter().map(|&v| v / s_scale).collect();
1621 let space = SymTMatrixSpace::new(ke as Index, irows, jcols);
1622 let mut h = SymTMatrix::new(space);
1623 h.set_values(&vals_scaled);
1624 let a_space = GenTMatrixSpace::new(0, ke as Index, Vec::new(), Vec::new());
1625 let a = GenTMatrix::new(a_space);
1626 let xl = vec![0.0; ke];
1627 let xu = vec![NLP_UPPER_BOUND_INF; ke];
1628 let qp = QpProblem {
1629 n: ke,
1630 m: 0,
1631 h: &h,
1632 g: &g,
1633 a: &a,
1634 bl: &[],
1635 bu: &[],
1636 xl: &xl,
1637 xu: &xu,
1638 hessian_inertia: HessianInertia::Unknown,
1639 };
1640 let opts = QpOptions {
1641 max_iter: (10 * ke as u32).max(200),
1642 // the engine's Schur-update path (use_schur_updates)
1643 // hits MaxIter on a dense reduced problem of hundreds
1644 // of rows where the refactorizing path terminates
1645 // Optimal, so the default stays; the heavy-direction
1646 // exact decision pays engine refactorizations and is
1647 // priced accordingly in the docs
1648 ..QpOptions::default()
1649 };
1650 let mut engine =
1651 ParametricActiveSetSolver::new(Box::new(pounce_feral::FeralSolverInterface::new()));
1652 let sol = engine
1653 .solve(&qp, None, &opts)
1654 .map_err(|e| fail(&format!("reduced QP failed: {e:?}")))?;
1655 if sol.status != QpStatus::Optimal {
1656 return Err(fail(&format!(
1657 "reduced QP terminated {:?} over {ke} engaged row(s)",
1658 sol.status
1659 )));
1660 }
1661 let lambda: Vec<Number> = sol.x.iter().map(|&v| v * (g_scale / s_scale)).collect();
1662
1663 // plus, not minus: the QP's optimality gradient is
1664 // S lambda + m, so the direction's movement must be
1665 // m + lambda S, which is d0 + Σ λ_k X_k here.
1666 //
1667 // Each `X_k` is `K_rel⁻¹ a_k`, so that sum is
1668 // `K_rel⁻¹ (Σ λ_k a_k)` and one solve on the combined
1669 // right-hand side gives it. That is why the columns above
1670 // need not be kept: the only thing they were held for is
1671 // recovered here, in a single back-solve, at the price of
1672 // one more against the budget per expansion round.
1673 d.copy_from_slice(&d0);
1674 if lambda.iter().any(|&l| l != 0.0) {
1675 if work + 1 > max_iter {
1676 return Err(budget(engaged.len(), work));
1677 }
1678 let mut comb = vec![0.0; dim];
1679 for (i, &k) in engaged.iter().enumerate() {
1680 comb[weak[k].var_row] += lambda[i] * sign(k);
1681 }
1682 let mut corr = vec![0.0; dim];
1683 if !bs.solve_released_prebuilt(
1684 &released,
1685 Rc::clone(&sigma),
1686 None,
1687 None,
1688 &comb,
1689 &mut corr,
1690 false,
1691 ) {
1692 return Err(SolverError::BacksolveFailed);
1693 }
1694 work += 1;
1695 for (dv, &cv) in d.iter_mut().zip(corr.iter()) {
1696 *dv += cv;
1697 }
1698 }
1699
1700 let tol = band * scale_of(&d);
1701 let mut grew = false;
1702 for k in 0..nw {
1703 if engaged.contains(&k) || inert.contains(&k) {
1704 continue;
1705 }
1706 if movement(k, &d) < -tol {
1707 engaged.push(k);
1708 grew = true;
1709 }
1710 }
1711 if !grew {
1712 // relative to the largest pin force, with no absolute
1713 // floor: a 1e-10-scale perturbation's pins are as real
1714 // as a 1e-2 one's, and a floor here silently unlabels
1715 // them while the direction still carries the pin
1716 let lam_scale = lambda
1717 .iter()
1718 .fold(0.0_f64, |a, &b| a.max(b.abs()))
1719 .max(1e-300);
1720 held = engaged
1721 .iter()
1722 .enumerate()
1723 .filter(|(i, _)| lambda[*i] > EPS_REL * lam_scale)
1724 .map(|(_, &k)| weak[k].var_row)
1725 .collect();
1726 break;
1727 }
1728 }
1729
1730 Ok((d[..n_x].to_vec(), held, work))
1731 }
1732
1733 /// The bounds the activity classifier could not call at the base
1734 /// point: on the bound with a multiplier of the same order as the
1735 /// slack. Each entry is a bound row present in the held
1736 /// factorization, with the side taken from the smaller slack,
1737 /// which is the only side an ambiguous label can come from.
1738 ///
1739 /// Both [`WEAKLY_ACTIVE`](crate::activity::WEAKLY_ACTIVE) and
1740 /// [`AMBIGUOUS`](crate::activity::AMBIGUOUS) count as weak here,
1741 /// deliberately: the ambiguous class contains genuine kinks whose
1742 /// coordinate is coupled to a neighbour (gh#763), so treating it
1743 /// as "not a kink" would drop real weak rows. That is why the
1744 /// mislabeling is not a wrong answer in the step path — see
1745 /// [`Self::reduced_activity`] for the class itself.
1746 ///
1747 /// The classifier reports per user variable, in full-x, while the
1748 /// bound context and the factor's rows are var-x, and the two
1749 /// index spaces diverge from the first fixed variable on. Each
1750 /// var-x row's status is read through the same map the classifier
1751 /// scattered through, so a fixed variable shifts nothing. Using
1752 /// the full-x index as a factor row instead returns a NEIGHBORING
1753 /// variable's answer, plausible and wrong, which is the gh#450
1754 /// hazard the `primal_row` discipline exists to prevent.
1755 pub fn weakly_active_bounds(&self) -> Result<Vec<crate::boundcheck::WeakBound>, SolverError> {
1756 use crate::activity::{AMBIGUOUS, WEAKLY_ACTIVE};
1757
1758 // A relaxed solve shifts the slacks the classifier reads, so
1759 // degeneracy is undetectable there: the callers take the plain
1760 // step, the same choice `estimate_report` makes when it fills
1761 // `bounds_relaxed` instead of raising.
1762 let report = match self.classify_activity() {
1763 Ok(r) => r,
1764 Err(SolverError::BadOptions(_)) => return Ok(Vec::new()),
1765 Err(e) => return Err(e),
1766 };
1767 let ctx = self.bound_context(None)?;
1768 let state = self.state.borrow();
1769 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1770 let Some(rows) = state.backsolver.bound_rows() else {
1771 return Ok(Vec::new());
1772 };
1773 // Three index spaces are live in the loop below: `report` is
1774 // FULL-x, `ctx` is VAR-x, and `br.row` is a bound row. The
1775 // first two coincide until the first `make_parameter`-removed
1776 // variable and diverge after it, so a swap reads a NEIGHBOURING
1777 // variable's status -- in range, plausible, wrong (gh#450, then
1778 // gh#672 finding 1). The typed indices make that a compile
1779 // error; `sens_invariance_legs.rs` leg 3 is what covers the
1780 // site already written. See `crate::index`.
1781 let map = {
1782 let (_, _, nlp) = state.backsolver.activity_handles();
1783 let nl = nlp.borrow();
1784 VarToFull::build(ctx.n_x, |r| nl.var_x_to_full_x(r.as_index()) as usize)
1785 };
1786 let status = FullXSlice::new(&report.var_status);
1787 let mut out = Vec::new();
1788 for row in map.rows() {
1789 let Some(full) = map.full_of(row) else {
1790 continue;
1791 };
1792 let Some(st) = status.at(full) else {
1793 continue;
1794 };
1795 if st != WEAKLY_ACTIVE && st != AMBIGUOUS {
1796 continue;
1797 }
1798 let (s_lo, s_hi) = ctx.slacks_at(row);
1799 let lower = s_lo <= s_hi;
1800 // a table lookup, so a space-swap here would fail loudly
1801 let var_row = row.get();
1802 // `rows` now carries constraint-row limits too, whose
1803 // `var_row` is an `s`-block row (gh#928). They can never
1804 // match here -- `map.rows()` runs over the `x` block, so
1805 // `var_row < ctx.n_x`, and every `s` row is at or above it
1806 // -- but that is a property of two index ranges not
1807 // overlapping, which is exactly the kind of thing that
1808 // silently stops being true. Said out loud so it is a
1809 // filter rather than a coincidence.
1810 debug_assert!(var_row < ctx.n_x);
1811 if let Some(br) = rows
1812 .iter()
1813 .filter(|b| b.var_row < ctx.n_x)
1814 .find(|b| b.var_row == var_row && b.lower == lower)
1815 {
1816 out.push(crate::boundcheck::WeakBound {
1817 row: br.row,
1818 var_row,
1819 lower,
1820 });
1821 }
1822 }
1823 Ok(out)
1824 }
1825
1826 /// The bound geometry both bound-aware steps read: the primal
1827 /// block's size and base point, its bounds in the model's own
1828 /// units, the tolerance that decides what counts as on a bound, and
1829 /// the bound multipliers at the base point.
1830 ///
1831 /// Shared rather than assembled twice. The two callers have to
1832 /// agree on all of it, and the unit and index-space conversions
1833 /// below are exactly what went wrong when a second caller wrote its
1834 /// own.
1835 ///
1836 /// `bound_eps` overrides the margin. `None` keeps how far outside
1837 /// the solve itself was willing to settle, floored so an unrelaxed
1838 /// solve does not pin on roundoff.
1839 fn bound_context(&self, bound_eps: Option<Number>) -> Result<BoundContext, SolverError> {
1840 let state = self.state.borrow();
1841 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
1842 let dims = state.backsolver.block_dims();
1843 let n_x = dims[0];
1844 let n_s = dims[1];
1845
1846 // Expanded once, before any re-solve: reading the compressed
1847 // form means borrowing the NLP, and the solves below re-borrow
1848 // it.
1849 //
1850 // Both primal blocks, in one pass over the same borrow: `x`
1851 // against `x_l` / `x_u` through `px_l` / `px_u`, and `s`
1852 // against `d_l` / `d_u` through `pd_l` / `pd_u`. The second
1853 // half is gh#928's subject — an inequality row's limit is a
1854 // bound on its slack, and a box that stopped at `n_x` left
1855 // every such limit unwatched.
1856 let (mut lo, mut hi, s_lo, s_hi) = {
1857 let (_, _, nlp) = state.backsolver.activity_handles();
1858 let nl = nlp.borrow();
1859 let (lo, hi) =
1860 crate::boundcheck::expand_bounds(n_x, &nl.px_l(), &nl.px_u(), nl.x_l(), nl.x_u());
1861 let (s_lo, s_hi) =
1862 crate::boundcheck::expand_bounds(n_s, &nl.pd_l(), &nl.pd_u(), nl.d_l(), nl.d_u());
1863 (lo, hi, s_lo, s_hi)
1864 };
1865 // Those bounds bound the algorithm's `x̃ = d ⊙ x`, while
1866 // `state.x` and the step are both in the model's own units
1867 // (gh#486 stage 3). Undo the change of variables on the bounds
1868 // so all three agree, rather than projecting onto the wrong box.
1869 // A negative factor reflects the interval, so the sides swap.
1870 // `variable_scaling`, not `variable_scaling_full`: `lo` / `hi`
1871 // are var-x length, and the two index spaces diverge from the
1872 // first fixed variable on.
1873 if let Some(d) = state.backsolver.variable_scaling() {
1874 for i in 0..n_x {
1875 let di = d[i];
1876 if di == 0.0 || di == 1.0 {
1877 continue;
1878 }
1879 let (a, b) = (lo[i] / di, hi[i] / di);
1880 lo[i] = a.min(b);
1881 hi[i] = a.max(b);
1882 }
1883 }
1884
1885 // The `s` block gets the same treatment for the row scaling it
1886 // was solved under. `F` — the vector every back-solve
1887 // post-multiplies its answer by — is `1/dd_r` on the `s` rows,
1888 // so a scaled quantity times `F` is the natural one, which is
1889 // exactly the conversion the `x` block just made by dividing
1890 // by `d`. Using `F` rather than re-reading `d_scale` keeps
1891 // this pinned to the same numbers the step arrives in: the
1892 // point of the conversion is that `x_curr`, the box and the
1893 // step agree, not that the arithmetic matches a formula.
1894 //
1895 // The base slack `s* - d_l` is scale-invariant in sign but not
1896 // in size, and it is compared against a multiplier that gets
1897 // the same treatment inside the walk, so both sides move
1898 // together. `variable_scaling_sensitivity.rs` is the general
1899 // statement of why that has to be checked rather than assumed.
1900 let mut s_curr: Vec<Number> = {
1901 let (data, _, _) = state.backsolver.activity_handles();
1902 let d = data.borrow();
1903 let curr = d.curr.as_ref().ok_or(SolverError::NotConverged)?;
1904 crate::vec_util::dense_to_vec(&*curr.s)
1905 };
1906 let mut s_lo = s_lo;
1907 let mut s_hi = s_hi;
1908 if s_curr.len() != n_s {
1909 return Err(SolverError::BadShape {
1910 what: "slack block of the converged iterate",
1911 got: s_curr.len(),
1912 expected: n_s,
1913 });
1914 }
1915 if let Some(f) = state.backsolver.natural_units_factor() {
1916 for i in 0..n_s {
1917 let fi = f[n_x + i];
1918 if fi == 1.0 {
1919 continue;
1920 }
1921 s_curr[i] *= fi;
1922 let (a, b) = (s_lo[i] * fi, s_hi[i] * fi);
1923 s_lo[i] = a.min(b);
1924 s_hi[i] = a.max(b);
1925 }
1926 }
1927
1928 // What counts as outside a bound is the solve's own answer: it
1929 // was willing to leave a converged point `bound_relax_factor`
1930 // outside, so anything within that is on the bound, not past
1931 // it. A floor keeps an unrelaxed solve from pinning on
1932 // roundoff.
1933 let floor = crate::boundcheck::release_floor(state.bound_relax_factor);
1934 // Rejected here rather than at each entry point, so the pyo3
1935 // binding and every Rust caller get the check the CLI's
1936 // `sens_bound_eps` gets from its strict lower bound. Zero
1937 // reinstates the roundoff pinning the floor prevents, and NaN
1938 // makes `over > eps` false everywhere, so the refinement pins
1939 // nothing and still reports settled — both return a plausible
1940 // vector rather than failing, which is the worse outcome.
1941 // `> 0.0` is false for NaN, as `pyomo_pounce`'s own check is.
1942 let eps = match bound_eps {
1943 None => floor,
1944 Some(e) if e > 0.0 => e,
1945 Some(e) => {
1946 return Err(SolverError::BadOptions(format!(
1947 "bound_eps must be a positive number, got {e}"
1948 )));
1949 }
1950 };
1951 // A caller's `bound_eps` is a primal margin and says nothing
1952 // about when a multiplier has changed sign, so the release test
1953 // keeps the solve's own margin.
1954 let release_eps = floor;
1955 // The bound multipliers at the base point, with the compound
1956 // row each one occupies, so a step that drives one negative can
1957 // release that bound.
1958 let mults = {
1959 let (z_l_off, z_u_off) = (
1960 dims[0] + dims[1] + dims[2] + dims[3],
1961 dims[0] + dims[1] + dims[2] + dims[3] + dims[4],
1962 );
1963 let (data, _, _) = state.backsolver.activity_handles();
1964 let d = data.borrow();
1965 let curr = d.curr.as_ref().ok_or(SolverError::NotConverged)?;
1966 let (v_l_off, v_u_off) = (z_u_off + dims[5], z_u_off + dims[5] + dims[6]);
1967 let mut out = Vec::new();
1968 for (off, v) in [
1969 (z_l_off, &curr.z_l),
1970 (z_u_off, &curr.z_u),
1971 (v_l_off, &curr.v_l),
1972 (v_u_off, &curr.v_u),
1973 ] {
1974 for (k, &base) in crate::vec_util::dense_to_vec(&**v).iter().enumerate() {
1975 out.push(crate::boundcheck::BoundMultiplier { row: off + k, base });
1976 }
1977 }
1978 out
1979 };
1980 lo.extend_from_slice(&s_lo);
1981 hi.extend_from_slice(&s_hi);
1982 let mut x_curr = state.x[..n_x].to_vec();
1983 x_curr.extend_from_slice(&s_curr);
1984 Ok(BoundContext {
1985 n_x,
1986 lo,
1987 hi,
1988 x_curr,
1989 eps,
1990 release_eps,
1991 mults,
1992 })
1993 }
1994
1995 /// Full KKT-space parametric step for a set of pinned equality
1996 /// constraints: the same computation as [`Self::parametric_step`],
1997 /// returned WITHOUT truncating to the primal block. The layout is
1998 /// the compound KKT vector `(x, s, y_c, y_d, z_l, z_u, v_l, v_u)`;
1999 /// use [`Self::block_dims`] for the block sizes and
2000 /// [`Self::g_multiplier_rows`] to locate a constraint's multiplier
2001 /// row. This exposes the multiplier sensitivities `∂λ*/∂p`
2002 /// alongside the primal step.
2003 pub fn parametric_step_full(
2004 &self,
2005 pin_constraint_indices: &[Index],
2006 deltas: &[Number],
2007 ) -> Result<Vec<Number>, SolverError> {
2008 if pin_constraint_indices.len() != deltas.len() {
2009 return Err(SolverError::BadShape {
2010 what: "deltas",
2011 got: deltas.len(),
2012 expected: pin_constraint_indices.len(),
2013 });
2014 }
2015 let state = self.state.borrow();
2016 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2017
2018 let param_rows = state
2019 .backsolver
2020 .map_pin_g_to_kkt_rows(pin_constraint_indices)
2021 .map_err(SolverError::SensComputationFailed)?;
2022 let signs = vec![1; pin_constraint_indices.len()];
2023 let a_data = IndexSchurData::from_parts(param_rows, signs)
2024 .map_err(|e| SolverError::SensComputationFailed(format!("{e:?}")))?;
2025
2026 let opts = SensOptions {
2027 run_sens: true,
2028 ..SensOptions::default()
2029 };
2030 let sens_app = SensApplication::new(a_data, state.backsolver.clone(), opts);
2031 let n_full = state.backsolver.dim();
2032 let mut dx_full = vec![0.0; n_full];
2033 if !sens_app.parametric_step(deltas, &mut dx_full) {
2034 return Err(SolverError::SensComputationFailed(
2035 "SensApplication::parametric_step failed".into(),
2036 ));
2037 }
2038 let corr = self.barrier_correction(state)?;
2039 for (d, c) in dx_full.iter_mut().zip(corr.iter()) {
2040 *d += *c * BARRIER_SIGN;
2041 }
2042 Ok(dx_full)
2043 }
2044
2045 /// Flat rows of the compound KKT vector holding the equality
2046 /// multipliers `y_c` for the given 0-based **full-g** constraint
2047 /// indices. `None` for inequalities — their multipliers live in
2048 /// the `y_d` block, which [`Self::d_multiplier_rows`] addresses.
2049 /// Row `r` of a [`Self::parametric_step_full`] result is then
2050 /// `∂λ_g/∂p · Δp`.
2051 pub fn g_multiplier_rows(
2052 &self,
2053 g_indices: &[Index],
2054 ) -> Result<Vec<Option<Index>>, SolverError> {
2055 let state = self.state.borrow();
2056 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2057 let dims = state.backsolver.block_dims();
2058 let y_c_offset = (dims[0] + dims[1]) as Index;
2059 Ok(g_indices
2060 .iter()
2061 .map(|&g| {
2062 state
2063 .backsolver
2064 .full_g_to_c_block(g)
2065 .map(|pos| y_c_offset + pos)
2066 })
2067 .collect())
2068 }
2069
2070 /// Flat rows of the compound KKT vector holding the **inequality**
2071 /// multipliers `y_d` for the given 0-based **full-g** constraint
2072 /// indices. `None` for equalities (those are
2073 /// [`Self::g_multiplier_rows`]'s). The `y_d` counterpart of that
2074 /// accessor, added by gh#910: `parametric_step_full` already
2075 /// returned the `y_d` block, and this is the map that says which
2076 /// row of it belongs to which user constraint.
2077 ///
2078 /// **Reading the row is not the same as the row being a
2079 /// derivative.** `y_d` holds a number for every inequality, in all
2080 /// three activity regimes, and only one of them has a two-sided
2081 /// `∂λ/∂p` at all:
2082 ///
2083 /// * **strictly active** (`s ≈ 0`, `λ > 0`): the row behaves as an
2084 /// equality over a neighbourhood of the solved point, and this
2085 /// row is the same back-solve an equality gets. Well defined.
2086 /// * **inactive** (`s > 0`, `λ ≈ 0`): the derivative is a
2087 /// structural zero over a neighbourhood; the KKT row carries the
2088 /// barrier's residue rather than a derivative of anything.
2089 /// * **weakly active** (a kink: `s ≈ 0` *and* `λ ≈ 0`): the two
2090 /// one-sided derivatives differ and no two-sided value exists.
2091 /// The entry holds whichever side the factorization landed on —
2092 /// the silently-wrong-while-reporting-success class.
2093 /// [`Self::parametric_step_directional`] is what answers a kink,
2094 /// and it needs a direction.
2095 ///
2096 /// So a caller reading these rows as `∂λ/∂p` must gate on the
2097 /// regime first, and the classifier that answers it is
2098 /// [`Self::reduced_row_activity`], **not**
2099 /// [`Self::classify_activity`]: a genuine kink whose row couples
2100 /// to the remaining free space reports `INACTIVE` on the
2101 /// directional normalizer at strong enough coupling (gh#804), and
2102 /// `INACTIVE` is the one class whose derivative a caller may
2103 /// legitimately read as a structural zero. Gating on the cheap
2104 /// classifier would therefore answer "it does not move" about a
2105 /// kink — a wrong answer wearing a refusal's clothes. That
2106 /// inference, reading an activity class as a proxy for kink-ness,
2107 /// is what shipped gh#756.
2108 pub fn d_multiplier_rows(
2109 &self,
2110 g_indices: &[Index],
2111 ) -> Result<Vec<Option<Index>>, SolverError> {
2112 let state = self.state.borrow();
2113 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2114 let dims = state.backsolver.block_dims();
2115 let y_d_offset = (dims[0] + dims[1] + dims[2]) as Index;
2116 Ok(g_indices
2117 .iter()
2118 .map(|&g| {
2119 state
2120 .backsolver
2121 .full_g_to_d_block(g)
2122 .map(|pos| y_d_offset + pos)
2123 })
2124 .collect())
2125 }
2126
2127 /// Flat rows of the compound KKT vector holding an inequality's
2128 /// **slack** `s`, for the given 0-based full-g row indices; `None`
2129 /// for a row that is not an inequality.
2130 ///
2131 /// The primal counterpart of [`Self::d_multiplier_rows`], and the
2132 /// discriminator a consumer of [`Self::parametric_step_path`]
2133 /// needs. A limit written as `g(x) <= cap` bounds this slack
2134 /// rather than any variable, so a breakpoint on it carries a
2135 /// primal KKT row in the `s` block (gh#928). Reading such a row as
2136 /// a var-x index returns a neighbouring variable's answer, the
2137 /// gh#450 hazard, so a caller that maps rows back to model objects
2138 /// resolves them here.
2139 ///
2140 /// The `s` block sits immediately after `x`, and is indexed by
2141 /// d-block position exactly as `y_d` is, so this row and
2142 /// [`Self::d_multiplier_rows`]'s row name the same inequality from
2143 /// the two sides of its complementarity pair.
2144 pub fn d_slack_rows(&self, g_indices: &[Index]) -> Result<Vec<Option<Index>>, SolverError> {
2145 let state = self.state.borrow();
2146 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2147 let s_offset = state.backsolver.block_dims()[0] as Index;
2148 Ok(g_indices
2149 .iter()
2150 .map(|&g| {
2151 state
2152 .backsolver
2153 .full_g_to_d_block(g)
2154 .map(|pos| s_offset + pos)
2155 })
2156 .collect())
2157 }
2158
2159 /// Flat rows of the compound KKT vector holding the primal values
2160 /// `x` for the given 0-based **full-x** variable indices. `None`
2161 /// where the solve removed the column (`x_l == x_u` under
2162 /// `fixed_variable_treatment = make_parameter`), which has no row
2163 /// in the factor at all.
2164 ///
2165 /// The `x` counterpart of [`Self::g_multiplier_rows`], and needed
2166 /// for the same reason: a caller holding user-space indices — from
2167 /// the `.col` file, from [`Self::classify_activity`], from
2168 /// [`Self::row_normal`] — cannot index the factor with them
2169 /// directly. Row `r` of a [`Self::parametric_step_full`] result is
2170 /// then `∂x/∂p · Δp` for that variable, and `e_r` is the unit
2171 /// vector selecting its column in a [`Self::kkt_solve`].
2172 pub fn x_primal_rows(&self, x_indices: &[Index]) -> Result<Vec<Option<Index>>, SolverError> {
2173 let state = self.state.borrow();
2174 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2175 let n_full = state.backsolver.n_full_x();
2176 // out of range must not masquerade as "removed as fixed": the
2177 // NLP map returns None for both, and the caller's whole reason
2178 // for asking is that it cannot tell the spaces apart itself
2179 if let Some(&bad) = x_indices.iter().find(|&&i| i < 0 || i >= n_full) {
2180 return Err(SolverError::BadShape {
2181 what: "x_primal_rows variable index",
2182 got: bad as usize,
2183 expected: n_full as usize,
2184 });
2185 }
2186 // the x block starts at flat index 0, so the var-x position IS
2187 // the KKT row; the offset stays explicit for the day it is not
2188 Ok(x_indices
2189 .iter()
2190 .map(|&i| state.backsolver.full_x_to_var_x(i))
2191 .collect())
2192 }
2193
2194 /// The user TNLP's variable count: the length of a full-x report
2195 /// and the domain of [`Self::x_primal_rows`].
2196 pub fn n_full_x(&self) -> Result<usize, SolverError> {
2197 let state = self.state.borrow();
2198 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2199 Ok(state.backsolver.n_full_x() as usize)
2200 }
2201
2202 /// The user TNLP's constraint count: the length of a full-g
2203 /// report and the domain of [`Self::reduced_row_activity`].
2204 pub fn n_full_g(&self) -> Result<usize, SolverError> {
2205 let state = self.state.borrow();
2206 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2207 Ok(state.backsolver.n_full_g() as usize)
2208 }
2209
2210 /// Reduced Hessian over the pinned equality-constraint rows:
2211 /// `obj_scal · B K⁻¹ Bᵀ`, where `B` selects the
2212 /// `pin_constraint_indices` rows of the y_c block and `K` is the
2213 /// **natural-units** (unscaled) KKT matrix — active NLP scaling
2214 /// is undone by the backsolver, so `−inv` of the returned matrix
2215 /// is directly the parameter covariance regardless of
2216 /// `nlp_scaling_method` (pounce#128). `obj_scal` survives as a
2217 /// plain extra multiplier (default 1.0); it is no longer needed to
2218 /// recover natural units. Returns the `n²`-long column-major dense
2219 /// matrix (`n = pin_constraint_indices.len()`).
2220 ///
2221 /// # Sign convention: this returns `−H_R`, not `H_R` (gh#937)
2222 ///
2223 /// The matrix is the **negated** reduced Hessian. On a model whose
2224 /// objective Hessian is `[[2, 1], [1, 2]]` with both variables
2225 /// pinned, this returns `[[−2, −1], [−1, −2]]`. So a well-posed
2226 /// minimum reports an all-*negative* spectrum; that is the
2227 /// convention, not an indefiniteness or convergence bug.
2228 ///
2229 /// The minus is the augmented system's, and it is why the
2230 /// covariance recipe above negates: pin indices map to the `y_c`
2231 /// multiplier block, and for `K = [[H, Aᵀ], [A, 0]]` the
2232 /// `(y_c, y_c)` block of `K⁻¹` is `−(A H⁻¹ Aᵀ)⁻¹` — so over pin
2233 /// rows `B K⁻¹ Bᵀ` is the multiplier sensitivity
2234 /// `∂λ/∂p = −∂²f*/∂p²`, i.e. `±H_R` itself and not a submatrix of
2235 /// an inverse. (The `x` block of `K⁻¹` *is* an inverse. The two
2236 /// blocks sit on opposite sides of one inversion, which is what
2237 /// makes the CLI's `red_hessian` suffix path — upstream sIPOPT's,
2238 /// selecting x rows — a different quantity rather than the same
2239 /// one with a different sign.)
2240 ///
2241 /// Negate to read curvature: `−hr` is `H_R`, and `−inv(hr)` is the
2242 /// covariance. Pinned by
2243 /// `tests/issue_937_reduced_hessian_sign.rs`; demonstrated by
2244 /// `examples/rh_orientation_check.rs`.
2245 ///
2246 /// Equivalent to [`crate::SensSolve::with_reduced_hessian`] but
2247 /// usable post-hoc on a held `Solver`. For the solver-space
2248 /// (pre-#128) value use [`Self::compute_reduced_hessian_scaled`];
2249 /// the factors themselves are exposed via [`Self::nlp_scaling`] /
2250 /// [`Self::pin_g_scaling`].
2251 pub fn compute_reduced_hessian(
2252 &self,
2253 pin_constraint_indices: &[Index],
2254 obj_scal: Number,
2255 ) -> Result<Vec<Number>, SolverError> {
2256 let state = self.state.borrow();
2257 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2258 let n = pin_constraint_indices.len();
2259 let param_rows = state
2260 .backsolver
2261 .map_pin_g_to_kkt_rows(pin_constraint_indices)
2262 .map_err(SolverError::SensComputationFailed)?;
2263 let signs = vec![1; n];
2264 let a_data = IndexSchurData::from_parts(param_rows, signs)
2265 .map_err(|e| SolverError::SensComputationFailed(format!("{e:?}")))?;
2266 let opts = SensOptions {
2267 compute_red_hessian: true,
2268 obj_scal,
2269 ..SensOptions::default()
2270 };
2271 let mut sens_app = SensApplication::new(a_data, state.backsolver.clone(), opts);
2272 let mut hr = vec![0.0; n * n];
2273 if !sens_app.compute_reduced_hessian(&mut hr) {
2274 return Err(SolverError::SensComputationFailed(
2275 "SensApplication::compute_reduced_hessian failed".into(),
2276 ));
2277 }
2278 Ok(hr)
2279 }
2280
2281 /// [`Self::compute_reduced_hessian`] plus its eigendecomposition —
2282 /// `(H_R, eigenvalues, eigenvectors)`.
2283 ///
2284 /// The curvature on the null space of the active constraints is the
2285 /// question; its **spectrum** is what answers "is this parameter
2286 /// identifiable, and along which direction". `SensSolve` has offered that
2287 /// since gh#561 ([`crate::SensSolve::with_reduced_hessian_eigen`]), and
2288 /// the session API did not — so a caller holding a `Solver` had to
2289 /// re-solve the whole NLP through the one-shot builder to get a
2290 /// decomposition of a matrix it already had. That is the gap this closes;
2291 /// the numbers are the one-shot path's, from the same
2292 /// [`pounce_linalg::symmetric_eigen`].
2293 ///
2294 /// Eigenvectors are column-major, length `n²`, column `j` belonging to
2295 /// eigenvalue `j`, and sign-pinned by `symmetric_eigen` so a column read
2296 /// as a direction reproduces across builds.
2297 ///
2298 /// # This is the spectrum of `−H_R`, so ascending runs stiffest first
2299 ///
2300 /// [`Self::compute_reduced_hessian`] returns the **negated** reduced
2301 /// Hessian (gh#937, and see its docs for why). The eigenvalues here are
2302 /// that matrix's, in ascending order — which on `−H_R` runs from most
2303 /// negative to least, i.e. **stiffest mode first and softest last**, the
2304 /// reverse of what the identifiability reading wants. On `H = [[2, 1],
2305 /// [1, 2]]` fully pinned they come back `[−3, −1]`: the leading column is
2306 /// the curvature-3 stiff direction, the trailing one the curvature-1 soft
2307 /// direction.
2308 ///
2309 /// So a caller taking the leading columns as the least-identifiable
2310 /// directions gets the best-identified ones, and nothing looks wrong —
2311 /// the vectors are unit-norm, sign-pinned and entirely plausible. Either
2312 /// negate the eigenvalues and reverse the order, or read the *trailing*
2313 /// columns as the soft modes. Pinned by
2314 /// `tests/issue_937_reduced_hessian_sign.rs`.
2315 pub fn compute_reduced_hessian_eigen(
2316 &self,
2317 pin_constraint_indices: &[Index],
2318 obj_scal: Number,
2319 ) -> Result<(Vec<Number>, Vec<Number>, Vec<Number>), SolverError> {
2320 let hr = self.compute_reduced_hessian(pin_constraint_indices, obj_scal)?;
2321 let n = pin_constraint_indices.len();
2322 let mut vals = vec![0.0; n];
2323 let mut vecs = vec![0.0; n * n];
2324 if !pounce_linalg::symmetric_eigen(&hr, n, &mut vals, &mut vecs) {
2325 return Err(SolverError::SensComputationFailed(
2326 "the reduced Hessian's eigendecomposition did not converge".into(),
2327 ));
2328 }
2329 Ok((hr, vals, vecs))
2330 }
2331
2332 /// The reduced Hessian as the solver's internal **scaled** space
2333 /// sees it — the value [`Self::compute_reduced_hessian`] returned
2334 /// before pounce#128: `H̃_ij = (df / (dc_i·dc_j)) · H_ij`.
2335 /// Identical to `compute_reduced_hessian` when no NLP scaling is
2336 /// active.
2337 ///
2338 /// Sign: this is [`Self::compute_reduced_hessian`]'s `−H_R`
2339 /// multiplied through by `df / (dc_i·dc_j)` (gh#937), so unlike the
2340 /// natural-units value its orientation is **not** fixed. Measured on
2341 /// a fully pinned `[[2, 1], [1, 2]]`: `[[−2, −1], [−1, −2]]` by
2342 /// default, but `[[2, 1], [1, 2]]` under `obj_scaling_factor = −1`,
2343 /// where `df` carries the minus that makes a maximization a
2344 /// minimization. Read the sign off the reported factors
2345 /// ([`Self::nlp_scaling`], [`Self::pin_g_scaling`]) rather than
2346 /// assuming it, or use the natural-units value, whose `−H_R` holds
2347 /// whatever the scaling.
2348 pub fn compute_reduced_hessian_scaled(
2349 &self,
2350 pin_constraint_indices: &[Index],
2351 obj_scal: Number,
2352 ) -> Result<Vec<Number>, SolverError> {
2353 let mut hr = self.compute_reduced_hessian(pin_constraint_indices, obj_scal)?;
2354 let state = self.state.borrow();
2355 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2356 let df = state.backsolver.obj_scaling_factor();
2357 let dc = state
2358 .backsolver
2359 .pin_c_scales(pin_constraint_indices)
2360 .map_err(SolverError::SensComputationFailed)?;
2361 crate::reduced_hessian::scale_to_solver_space(&mut hr, df, &dc);
2362 Ok(hr)
2363 }
2364
2365 /// Effective NLP scaling the IPM applied on the most recent
2366 /// converged solve: `(obj_scaling_factor, c_scale, d_scale)`.
2367 /// `(1.0, None, None)` ⇔ no scaling was active. The vectors are
2368 /// per-row factors over the algorithm's equality (`c`) and
2369 /// inequality (`d`) blocks.
2370 pub fn nlp_scaling(
2371 &self,
2372 ) -> Result<(Number, Option<Vec<Number>>, Option<Vec<Number>>), SolverError> {
2373 let state = self.state.borrow();
2374 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2375 Ok(state.backsolver.nlp_scaling())
2376 }
2377
2378 /// The per-variable `user-scaling` factors `d` the held solve ran
2379 /// under (gh#486), in the user TNLP's **full-x** space, or `None`
2380 /// when the solve applied no change of variables.
2381 ///
2382 /// Every accessor on this type already reports natural units, so
2383 /// this is diagnostic rather than a correction a caller has to
2384 /// apply — it answers "was this solve conditioned, and by how
2385 /// much", the x-axis counterpart of [`Self::nlp_scaling`].
2386 pub fn variable_scaling(&self) -> Result<Option<Vec<Number>>, SolverError> {
2387 let state = self.state.borrow();
2388 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2389 Ok(state.backsolver.variable_scaling_full().map(|d| d.to_vec()))
2390 }
2391
2392 /// Inertia-correction perturbations `(δ_x, δ_s, δ_c, δ_d)` baked
2393 /// into the held KKT factor. All zero ⇔ the final factorization
2394 /// was unregularized and the natural-units back-solves invert the
2395 /// exact KKT matrix — see
2396 /// [`crate::PdSensBacksolver::kkt_perturbations`].
2397 pub fn kkt_perturbations(&self) -> Result<[Number; 4], SolverError> {
2398 let state = self.state.borrow();
2399 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2400 Ok(state.backsolver.kkt_perturbations())
2401 }
2402
2403 /// Per-pin equality-row scaling factors `dc_i` (1.0 entries when
2404 /// no constraint scaling is active), ordered like
2405 /// `pin_constraint_indices`.
2406 pub fn pin_g_scaling(
2407 &self,
2408 pin_constraint_indices: &[Index],
2409 ) -> Result<Vec<Number>, SolverError> {
2410 let state = self.state.borrow();
2411 let state = state.as_ref().ok_or(SolverError::NotConverged)?;
2412 state
2413 .backsolver
2414 .pin_c_scales(pin_constraint_indices)
2415 .map_err(SolverError::SensComputationFailed)
2416 }
2417}