pounce_algorithm/tiny_step_stall.rs
1//! When the tiny-step stop may stop waiting for the multiplier step.
2//!
3//! Upstream stops at a tiny step only after the multiplier step is also
4//! below `tiny_step_y_tol` (`IpBacktrackingLineSearch.cpp`), so that a
5//! primal iterate which has stopped moving is not abandoned while its
6//! multipliers are still converging. At a point whose multipliers are not
7//! unique they need not converge: they run away, the multiplier step stays
8//! large, and the solve repeats the same iterate until `max_iter`.
9//!
10//! [`TinyStepDualStall`] bounds that wait by dual progress. Fed one
11//! observation per tiny primal step, it releases the stop once
12//! `max_iters` consecutive tiny steps have gone by without the scaled dual
13//! infeasibility falling below `0.99` times its best value in the run.
14//! Multipliers that are converging reduce the dual infeasibility and reset
15//! the count, so they are never cut short; a settled multiplier step or a
16//! non-tiny step ends the run.
17//!
18//! The case: the phase-change flash example
19//! (`pounce.examples.flash_mpcc.declare`) at 332 K, started from 331 K's
20//! all-vapor answer, sat for 3 000 iterations at a primal step of `5.6e-16`
21//! with the dual infeasibility constant at `1.3e29`, and the adaptive-mu
22//! re-solve then finished it in 14 (arm64 macOS). With the default bound the
23//! base attempt ends after 43 and the same re-solve takes it from there. On
24//! x86_64 Linux the re-solve stalls as well, under either rule, and the
25//! driver's l1 penalty answers: the same point, in 86 iterations against
26//! 6 012 (`python/tests/test_flash_mpcc.py`, which asserts only what both
27//! platforms share).
28
29use pounce_common::types::Number;
30
31/// Relative decrease of the dual infeasibility that counts as progress.
32const PROGRESS: Number = 0.99;
33
34#[derive(Debug, Clone)]
35pub struct TinyStepDualStall {
36 /// `tiny_step_dual_stall_iters`; `0` never releases (upstream's rule).
37 pub max_iters: usize,
38 count: usize,
39 best: Number,
40 released: bool,
41}
42
43impl TinyStepDualStall {
44 pub fn new(max_iters: usize) -> Self {
45 Self {
46 max_iters,
47 count: 0,
48 best: Number::INFINITY,
49 released: false,
50 }
51 }
52
53 /// A step that was not tiny ends the run of tiny steps.
54 pub fn not_tiny(&mut self) {
55 self.count = 0;
56 self.best = Number::INFINITY;
57 }
58
59 /// One tiny primal step. `y_settled`: the multiplier step is already
60 /// below `tiny_step_y_tol`, so upstream's own rule applies and this
61 /// one has nothing to add. `acceptable`: the iterate passes the
62 /// acceptable-level test, so it has an exit of its own
63 /// (`acceptable_iter`) and is left to it -- cutting it short would turn
64 /// `Solved_To_Acceptable_Level` into a tiny-step stop (gh#532's
65 /// `dual_inf_scale_kappa=0` case, where the dual sits on a round-off
66 /// floor at an acceptable point). `dual_inf`: the scaled dual
67 /// infeasibility at the iterate. Returns whether the stop may proceed
68 /// as if the multiplier step had settled.
69 pub fn observe(&mut self, y_settled: bool, acceptable: bool, dual_inf: Number) -> bool {
70 if y_settled || acceptable || self.max_iters == 0 {
71 self.not_tiny();
72 return false;
73 }
74 if dual_inf.is_finite() && dual_inf < PROGRESS * self.best {
75 self.best = dual_inf;
76 self.count = 0;
77 } else {
78 self.count += 1;
79 }
80 let stalled = self.count >= self.max_iters;
81 self.released |= stalled;
82 stalled
83 }
84
85 /// Whether the rule released the stop at least once.
86 pub fn released(&self) -> bool {
87 self.released
88 }
89}
90
91#[cfg(test)]
92mod tests {
93 use super::*;
94
95 /// Flat or growing dual infeasibility over tiny steps is released after
96 /// exactly `max_iters` steps without progress, the first observation
97 /// setting the baseline.
98 #[test]
99 fn a_dual_that_stops_improving_is_released_after_max_iters() {
100 for duals in [
101 vec![1.3e29; 20],
102 (0..20).map(|k| 1e21 * 10f64.powi(k)).collect(),
103 ] {
104 let mut s = TinyStepDualStall::new(10);
105 let fired: Vec<bool> = duals.iter().map(|&d| s.observe(false, false, d)).collect();
106 assert_eq!(fired.iter().position(|&f| f), Some(10), "{duals:?}");
107 assert!(s.released());
108 }
109 }
110
111 /// Multipliers that are converging improve the dual every step and are
112 /// never cut short, however long the run of tiny steps.
113 #[test]
114 fn converging_multipliers_are_never_released() {
115 let mut s = TinyStepDualStall::new(10);
116 for k in 0..200 {
117 assert!(!s.observe(false, false, 1e3 * 0.9f64.powi(k)), "step {k}");
118 }
119 assert!(!s.released());
120 }
121
122 /// Progress anywhere in the run restarts the count.
123 #[test]
124 fn progress_restarts_the_count() {
125 let mut s = TinyStepDualStall::new(10);
126 for _ in 0..9 {
127 assert!(!s.observe(false, false, 5.0));
128 }
129 assert!(!s.observe(false, false, 1.0)); // progress: count back to 0
130 for _ in 0..9 {
131 assert!(!s.observe(false, false, 1.0));
132 }
133 assert!(s.observe(false, false, 1.0));
134 }
135
136 /// A settled multiplier step is upstream's case, and a non-tiny step
137 /// ends the run; both reset.
138 #[test]
139 fn a_settled_multiplier_step_or_a_real_step_resets() {
140 let mut s = TinyStepDualStall::new(3);
141 s.observe(false, false, 1.0);
142 s.observe(false, false, 1.0);
143 assert!(!s.observe(true, false, 1.0));
144 assert!(!s.observe(false, false, 1.0)); // baseline again
145 assert!(!s.observe(false, false, 1.0));
146 s.not_tiny();
147 assert!(!s.observe(false, false, 1.0));
148 assert!(!s.observe(false, false, 1.0));
149 assert!(!s.observe(false, false, 1.0));
150 assert!(s.observe(false, false, 1.0));
151 }
152
153 /// An acceptable iterate is left to the acceptable-level exit, and
154 /// resets the run like a settled multiplier step.
155 #[test]
156 fn an_acceptable_iterate_is_left_to_its_own_exit() {
157 let mut s = TinyStepDualStall::new(3);
158 for _ in 0..100 {
159 assert!(!s.observe(false, true, 1.3e29));
160 }
161 assert!(!s.released());
162 assert!(!s.observe(false, false, 1.0));
163 assert!(!s.observe(false, false, 1.0));
164 assert!(!s.observe(false, true, 1.0));
165 assert!(!s.observe(false, false, 1.0));
166 }
167
168 /// `0` is upstream's rule: never released.
169 #[test]
170 fn zero_is_upstreams_rule() {
171 let mut s = TinyStepDualStall::new(0);
172 for _ in 0..5000 {
173 assert!(!s.observe(false, false, 1.3e29));
174 }
175 assert!(!s.released());
176 }
177
178 /// A non-finite dual is no progress, and sets no baseline: it counts
179 /// from the first observation.
180 #[test]
181 fn a_non_finite_dual_is_not_progress() {
182 let mut s = TinyStepDualStall::new(2);
183 assert!(!s.observe(false, false, Number::NAN));
184 assert!(s.observe(false, false, Number::INFINITY));
185 }
186}