OR-Tools  9.6
termination_test.cc
Go to the documentation of this file.
1 // Copyright 2010-2022 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #include "ortools/pdlp/termination.h"
15 
16 #include <atomic>
17 #include <cmath>
18 #include <limits>
19 #include <optional>
20 
21 #include "gmock/gmock.h"
22 #include "gtest/gtest.h"
23 #include "ortools/base/protobuf_util.h"
24 #include "ortools/pdlp/solve_log.pb.h"
25 #include "ortools/pdlp/solvers.pb.h"
26 
27 namespace operations_research::pdlp {
28 bool operator==(const TerminationCriteria::DetailedOptimalityCriteria& lhs,
29  const TerminationCriteria::DetailedOptimalityCriteria& rhs) {
30  if (lhs.eps_optimal_primal_residual_absolute() !=
31  rhs.eps_optimal_primal_residual_absolute()) {
32  return false;
33  }
34  if (lhs.eps_optimal_primal_residual_relative() !=
35  rhs.eps_optimal_primal_residual_relative()) {
36  return false;
37  }
38  if (lhs.eps_optimal_dual_residual_absolute() !=
39  rhs.eps_optimal_dual_residual_absolute()) {
40  return false;
41  }
42  if (lhs.eps_optimal_dual_residual_relative() !=
43  rhs.eps_optimal_dual_residual_relative()) {
44  return false;
45  }
46  if (lhs.eps_optimal_objective_gap_absolute() !=
47  rhs.eps_optimal_objective_gap_absolute()) {
48  return false;
49  }
50  if (lhs.eps_optimal_objective_gap_relative() !=
51  rhs.eps_optimal_objective_gap_relative()) {
52  return false;
53  }
54  return true;
55 }
56 
57 namespace {
58 
59 using ::google::protobuf::util::ParseTextOrDie;
60 using ::testing::Eq;
61 using ::testing::FieldsAre;
62 using ::testing::Optional;
63 
64 QuadraticProgramBoundNorms TestLpBoundNorms() {
65  return {.l2_norm_primal_linear_objective = std::sqrt(36.25),
66  .l2_norm_constraint_bounds = std::sqrt(210.0),
67  .l_inf_norm_primal_linear_objective = 5.5,
68  .l_inf_norm_constraint_bounds = 12.0};
69 }
70 
71 QuadraticProgramBoundNorms ZeroLpBoundNorms() {
72  return {.l2_norm_primal_linear_objective = 0.0,
73  .l2_norm_constraint_bounds = 0.0,
74  .l_inf_norm_primal_linear_objective = 0.0,
75  .l_inf_norm_constraint_bounds = 0.0};
76 }
77 
78 class SimpleTerminationTest : public testing::Test {
79  protected:
80  void SetUp() override {
81  test_criteria_ = ParseTextOrDie<TerminationCriteria>(R"pb(
82  time_sec_limit: 1.0
83  kkt_matrix_pass_limit: 2000
84  iteration_limit: 10)pb");
85  }
86 
87  TerminationCriteria test_criteria_;
88 };
89 
90 class IterateTerminationTest : public testing::TestWithParam<OptimalityNorm> {
91  protected:
92  void SetUp() override {
93  test_criteria_ = ParseTextOrDie<TerminationCriteria>(R"pb(
94  simple_optimality_criteria {
95  eps_optimal_absolute: 1.0e-4
96  eps_optimal_relative: 1.0e-4
97  }
98  eps_primal_infeasible: 1.0e-6
99  eps_dual_infeasible: 1.0e-6
100  time_sec_limit: 1.0
101  kkt_matrix_pass_limit: 2000
102  iteration_limit: 10)pb");
103  test_criteria_.set_optimality_norm(GetParam());
104  }
105 
106  TerminationCriteria test_criteria_;
107 };
108 
109 class DetailedRelativeTerminationTest
110  : public testing::TestWithParam<OptimalityNorm> {
111  protected:
112  void SetUp() override {
113  test_criteria_ = ParseTextOrDie<TerminationCriteria>(R"pb(
114  detailed_optimality_criteria {
115  eps_optimal_primal_residual_absolute: 0.0
116  eps_optimal_primal_residual_relative: 1.0e-4
117  eps_optimal_dual_residual_absolute: 0.0
118  eps_optimal_dual_residual_relative: 1.0e-4
119  eps_optimal_objective_gap_absolute: 0.0
120  eps_optimal_objective_gap_relative: 1.0e-4
121  }
122  )pb");
123  test_criteria_.set_optimality_norm(GetParam());
124  }
125 
126  TerminationCriteria test_criteria_;
127 };
128 
129 class DetailedAbsoluteTerminationTest
130  : public testing::TestWithParam<OptimalityNorm> {
131  protected:
132  void SetUp() override {
133  test_criteria_ = ParseTextOrDie<TerminationCriteria>(R"pb(
134  detailed_optimality_criteria {
135  eps_optimal_primal_residual_absolute: 1.0e-4
136  eps_optimal_primal_residual_relative: 0.0
137  eps_optimal_dual_residual_absolute: 1.0e-4
138  eps_optimal_dual_residual_relative: 0.0
139  eps_optimal_objective_gap_absolute: 1.0e-4
140  eps_optimal_objective_gap_relative: 0.0
141  }
142  )pb");
143  test_criteria_.set_optimality_norm(GetParam());
144  }
145 
146  TerminationCriteria test_criteria_;
147 };
148 
149 TEST(EffectiveOptimalityCriteriaTest, SimpleOptimalityCriteriaOverload) {
150  const auto criteria =
151  ParseTextOrDie<TerminationCriteria::SimpleOptimalityCriteria>(
152  R"pb(eps_optimal_absolute: 1.0e-4 eps_optimal_relative: 2.0e-4)pb");
153  EXPECT_THAT(
154  EffectiveOptimalityCriteria(criteria),
155  Eq(ParseTextOrDie<TerminationCriteria::DetailedOptimalityCriteria>(
156  R"pb(
157  eps_optimal_primal_residual_absolute: 1.0e-4
158  eps_optimal_primal_residual_relative: 2.0e-4
159  eps_optimal_dual_residual_absolute: 1.0e-4
160  eps_optimal_dual_residual_relative: 2.0e-4
161  eps_optimal_objective_gap_absolute: 1.0e-4
162  eps_optimal_objective_gap_relative: 2.0e-4
163  )pb")));
164 }
165 
166 TEST(EffectiveOptimalityCriteriaTest, SimpleOptimalityCriteriaInput) {
167  const auto criteria =
168  ParseTextOrDie<TerminationCriteria>(R"pb(simple_optimality_criteria {
169  eps_optimal_absolute: 1.0e-4
170  eps_optimal_relative: 2.0e-4
171  })pb");
172  EXPECT_THAT(
173  EffectiveOptimalityCriteria(criteria),
174  Eq(ParseTextOrDie<TerminationCriteria::DetailedOptimalityCriteria>(
175  R"pb(
176  eps_optimal_primal_residual_absolute: 1.0e-4
177  eps_optimal_primal_residual_relative: 2.0e-4
178  eps_optimal_dual_residual_absolute: 1.0e-4
179  eps_optimal_dual_residual_relative: 2.0e-4
180  eps_optimal_objective_gap_absolute: 1.0e-4
181  eps_optimal_objective_gap_relative: 2.0e-4
182  )pb")));
183 }
184 
185 TEST(EffectiveOptimalityCriteriaTest, DetailedOptimalityCriteriaInput) {
186  const auto criteria = ParseTextOrDie<TerminationCriteria>(
187  R"pb(detailed_optimality_criteria {
188  eps_optimal_primal_residual_absolute: 1.0e-4
189  eps_optimal_primal_residual_relative: 2.0e-4
190  eps_optimal_dual_residual_absolute: 3.0e-4
191  eps_optimal_dual_residual_relative: 4.0e-4
192  eps_optimal_objective_gap_absolute: 5.0e-4
193  eps_optimal_objective_gap_relative: 6.0e-4
194  })pb");
195  EXPECT_THAT(EffectiveOptimalityCriteria(criteria),
196  Eq(criteria.detailed_optimality_criteria()));
197 }
198 
199 TEST(EffectiveOptimalityCriteriaTest, DeprecatedInput) {
200  const auto criteria = ParseTextOrDie<TerminationCriteria>(
201  R"pb(eps_optimal_absolute: 1.0e-4 eps_optimal_relative: 2.0e-4)pb");
202  EXPECT_THAT(
203  EffectiveOptimalityCriteria(criteria),
204  Eq(ParseTextOrDie<TerminationCriteria::DetailedOptimalityCriteria>(
205  R"pb(
206  eps_optimal_primal_residual_absolute: 1.0e-4
207  eps_optimal_primal_residual_relative: 2.0e-4
208  eps_optimal_dual_residual_absolute: 1.0e-4
209  eps_optimal_dual_residual_relative: 2.0e-4
210  eps_optimal_objective_gap_absolute: 1.0e-4
211  eps_optimal_objective_gap_relative: 2.0e-4
212  )pb")));
213 }
214 
215 TEST_P(DetailedRelativeTerminationTest, TerminationWithNearOptimal) {
216  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
217  convergence_information {
218  primal_objective: 1.00019
219  dual_objective: 1.0
220  l_inf_primal_residual: 11.0e-4
221  l_inf_dual_residual: 5.4e-4
222  l2_primal_residual: 14.0e-4
223  l2_dual_residual: 6.0e-4
224  l_inf_componentwise_primal_residual: 9.0e-5
225  l_inf_componentwise_dual_residual: 9.0e-5
226  candidate_type: POINT_TYPE_CURRENT_ITERATE
227  })pb");
228  EXPECT_TRUE(ObjectiveGapMet(test_criteria_.detailed_optimality_criteria(),
229  stats.convergence_information(0)));
230  EXPECT_TRUE(OptimalityCriteriaMet(
231  test_criteria_.detailed_optimality_criteria(),
232  stats.convergence_information(0), test_criteria_.optimality_norm(),
233  TestLpBoundNorms()));
234  EXPECT_THAT(CheckIterateTerminationCriteria(test_criteria_, stats,
235  TestLpBoundNorms()),
236  Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
237  POINT_TYPE_CURRENT_ITERATE)));
238 }
239 
240 TEST_P(DetailedRelativeTerminationTest, NoTerminationWithExcessiveGap) {
241  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
242  convergence_information {
243  primal_objective: 1.00021
244  dual_objective: 1.0
245  l_inf_primal_residual: 11.0e-4
246  l_inf_dual_residual: 5.4e-4
247  l2_primal_residual: 14.0e-4
248  l2_dual_residual: 6.0e-4
249  l_inf_componentwise_primal_residual: 9.0e-5
250  l_inf_componentwise_dual_residual: 9.0e-5
251  candidate_type: POINT_TYPE_CURRENT_ITERATE
252  })pb");
253  EXPECT_FALSE(ObjectiveGapMet(test_criteria_.detailed_optimality_criteria(),
254  stats.convergence_information(0)));
255  EXPECT_FALSE(OptimalityCriteriaMet(
256  test_criteria_.detailed_optimality_criteria(),
257  stats.convergence_information(0), test_criteria_.optimality_norm(),
258  TestLpBoundNorms()));
259  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
260  TestLpBoundNorms()),
261  absl::nullopt);
262 }
263 
264 TEST_P(DetailedRelativeTerminationTest,
265  NoTerminationWithExcessivePrimalResidual) {
266  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
267  convergence_information {
268  primal_objective: 1.00019
269  dual_objective: 1.0
270  l_inf_primal_residual: 13.0e-4
271  l_inf_dual_residual: 5.4e-4
272  l2_primal_residual: 15.0e-4
273  l2_dual_residual: 6.0e-4
274  l_inf_componentwise_primal_residual: 1.1e-4
275  l_inf_componentwise_dual_residual: 9.0e-5
276  candidate_type: POINT_TYPE_CURRENT_ITERATE
277  })pb");
278  EXPECT_FALSE(OptimalityCriteriaMet(
279  test_criteria_.detailed_optimality_criteria(),
280  stats.convergence_information(0), test_criteria_.optimality_norm(),
281  TestLpBoundNorms()));
282  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
283  TestLpBoundNorms()),
284  absl::nullopt);
285 }
286 
287 TEST_P(DetailedRelativeTerminationTest,
288  NoTerminationWithExcessiveDualResidual) {
289  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
290  convergence_information {
291  primal_objective: 1.00019
292  dual_objective: 1.0
293  l_inf_primal_residual: 11.0e-4
294  l_inf_dual_residual: 5.6e-4
295  l2_primal_residual: 14.0e-4
296  l2_dual_residual: 7.0e-4
297  l_inf_componentwise_primal_residual: 9.0e-5
298  l_inf_componentwise_dual_residual: 1.1e-4
299  candidate_type: POINT_TYPE_CURRENT_ITERATE
300  })pb");
301  EXPECT_FALSE(OptimalityCriteriaMet(
302  test_criteria_.detailed_optimality_criteria(),
303  stats.convergence_information(0), test_criteria_.optimality_norm(),
304  TestLpBoundNorms()));
305  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
306  TestLpBoundNorms()),
307  absl::nullopt);
308 }
309 
310 TEST_P(DetailedAbsoluteTerminationTest, TerminationWithNearOptimal) {
311  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
312  convergence_information {
313  primal_objective: 1.00009
314  dual_objective: 1.0
315  l_inf_primal_residual: 9.0e-5
316  l_inf_dual_residual: 9.0e-5
317  l2_primal_residual: 9.0e-5
318  l2_dual_residual: 9.0e-5
319  l_inf_componentwise_primal_residual: 0.0
320  l_inf_componentwise_dual_residual: 0.0
321  candidate_type: POINT_TYPE_CURRENT_ITERATE
322  })pb");
323  EXPECT_TRUE(ObjectiveGapMet(test_criteria_.detailed_optimality_criteria(),
324  stats.convergence_information(0)));
325  EXPECT_TRUE(OptimalityCriteriaMet(
326  test_criteria_.detailed_optimality_criteria(),
327  stats.convergence_information(0), test_criteria_.optimality_norm(),
328  TestLpBoundNorms()));
329  EXPECT_THAT(CheckIterateTerminationCriteria(test_criteria_, stats,
330  TestLpBoundNorms()),
331  Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
332  POINT_TYPE_CURRENT_ITERATE)));
333 }
334 
335 TEST_P(DetailedAbsoluteTerminationTest, NoTerminationWithExcessiveGap) {
336  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
337  convergence_information {
338  primal_objective: 1.00011
339  dual_objective: 1.0
340  l_inf_primal_residual: 9.0e-5
341  l_inf_dual_residual: 9.0e-5
342  l2_primal_residual: 9.0e-5
343  l2_dual_residual: 9.0e-5
344  l_inf_componentwise_primal_residual: 0.0
345  l_inf_componentwise_dual_residual: 0.0
346  candidate_type: POINT_TYPE_CURRENT_ITERATE
347  })pb");
348  EXPECT_FALSE(ObjectiveGapMet(test_criteria_.detailed_optimality_criteria(),
349  stats.convergence_information(0)));
350  EXPECT_FALSE(OptimalityCriteriaMet(
351  test_criteria_.detailed_optimality_criteria(),
352  stats.convergence_information(0), test_criteria_.optimality_norm(),
353  TestLpBoundNorms()));
354  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
355  TestLpBoundNorms()),
356  absl::nullopt);
357 }
358 
359 TEST_P(DetailedAbsoluteTerminationTest,
360  NoTerminationWithExcessivePrimalResidual) {
361  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
362  convergence_information {
363  primal_objective: 1.00009
364  dual_objective: 1.0
365  l_inf_primal_residual: 11.0e-5
366  l_inf_dual_residual: 9.0e-5
367  l2_primal_residual: 11.0e-5
368  l2_dual_residual: 9.0e-5
369  l_inf_componentwise_primal_residual: 1.0e-6
370  l_inf_componentwise_dual_residual: 0.0
371  candidate_type: POINT_TYPE_CURRENT_ITERATE
372  })pb");
373  EXPECT_FALSE(OptimalityCriteriaMet(
374  test_criteria_.detailed_optimality_criteria(),
375  stats.convergence_information(0), test_criteria_.optimality_norm(),
376  TestLpBoundNorms()));
377  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
378  TestLpBoundNorms()),
379  absl::nullopt);
380 }
381 
382 TEST_P(DetailedAbsoluteTerminationTest,
383  NoTerminationWithExcessiveDualResidual) {
384  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
385  convergence_information {
386  primal_objective: 1.00009
387  dual_objective: 1.0
388  l_inf_primal_residual: 9.0e-5
389  l_inf_dual_residual: 11.0e-5
390  l2_primal_residual: 9.0e-5
391  l2_dual_residual: 11.0e-5
392  l_inf_componentwise_primal_residual: 0.0
393  l_inf_componentwise_dual_residual: 1.0e-6
394  candidate_type: POINT_TYPE_CURRENT_ITERATE
395  })pb");
396  EXPECT_FALSE(OptimalityCriteriaMet(
397  test_criteria_.detailed_optimality_criteria(),
398  stats.convergence_information(0), test_criteria_.optimality_norm(),
399  TestLpBoundNorms()));
400  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
401  TestLpBoundNorms()),
402  absl::nullopt);
403 }
404 
405 TEST_P(IterateTerminationTest, NoTerminationWithLargeGap) {
406  IterationStats stats = ParseTextOrDie<IterationStats>(R"pb(
407  convergence_information {
408  # Ensures that optimality conditions are not met.
409  primal_objective: 50.0
410  dual_objective: -50.0
411  })pb");
412  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
413  TestLpBoundNorms()),
414  std::nullopt);
415 }
416 
417 TEST_F(SimpleTerminationTest, NoTerminationWithEmptyIterationStats) {
418  IterationStats stats;
419  EXPECT_EQ(CheckSimpleTerminationCriteria(test_criteria_, stats),
420  std::nullopt);
421 }
422 
423 TEST_P(IterateTerminationTest, NoTerminationWithEmptyIterationStats) {
424  IterationStats stats;
425  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats,
426  TestLpBoundNorms()),
427  std::nullopt);
428 }
429 
430 TEST_F(SimpleTerminationTest, TerminationWithInterruptSolve) {
431  IterationStats stats;
432  std::atomic<bool> interrupt_solve = true;
433  std::optional<TerminationReasonAndPointType> maybe_result =
434  CheckSimpleTerminationCriteria(test_criteria_, stats, &interrupt_solve);
435  EXPECT_THAT(maybe_result,
436  Optional(FieldsAre(TERMINATION_REASON_INTERRUPTED_BY_USER,
437  POINT_TYPE_NONE)));
438 }
439 
440 TEST_P(IterateTerminationTest, TerminationWithNumericalError) {
441  IterationStats stats;
442  std::optional<TerminationReasonAndPointType> maybe_result =
443  CheckIterateTerminationCriteria(test_criteria_, stats, TestLpBoundNorms(),
444  /*force_numerical_termination=*/true);
445  EXPECT_THAT(
446  maybe_result,
447  Optional(FieldsAre(TERMINATION_REASON_NUMERICAL_ERROR, POINT_TYPE_NONE)));
448 }
449 
450 TEST_F(SimpleTerminationTest, TerminationWithTimeLimit) {
451  const auto stats =
452  ParseTextOrDie<IterationStats>(R"pb(cumulative_time_sec: 100.0)pb");
453  std::optional<TerminationReasonAndPointType> maybe_result =
454  CheckSimpleTerminationCriteria(test_criteria_, stats);
455  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_TIME_LIMIT,
456  POINT_TYPE_NONE)));
457 }
458 
459 TEST_F(SimpleTerminationTest, TerminationWithKktMatrixPassLimit) {
460  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
461  cumulative_kkt_matrix_passes: 2500)pb");
462  std::optional<TerminationReasonAndPointType> maybe_result =
463  CheckSimpleTerminationCriteria(test_criteria_, stats);
464  EXPECT_THAT(maybe_result,
465  Optional(FieldsAre(TERMINATION_REASON_KKT_MATRIX_PASS_LIMIT,
466  POINT_TYPE_NONE)));
467 }
468 
469 TEST_F(SimpleTerminationTest, TerminationWithIterationLimit) {
470  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
471  iteration_number: 20)pb");
472  std::optional<TerminationReasonAndPointType> maybe_result =
473  CheckSimpleTerminationCriteria(test_criteria_, stats);
474  EXPECT_THAT(
475  maybe_result,
476  Optional(FieldsAre(TERMINATION_REASON_ITERATION_LIMIT, POINT_TYPE_NONE)));
477 }
478 
479 TEST_P(IterateTerminationTest, PrimalInfeasibleFromIterateDifference) {
480  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
481  infeasibility_information: {
482  dual_ray_objective: 1.0
483  max_dual_ray_infeasibility: 1.0e-16
484  candidate_type: POINT_TYPE_ITERATE_DIFFERENCE
485  })pb");
486  std::optional<TerminationReasonAndPointType> maybe_result =
487  CheckIterateTerminationCriteria(test_criteria_, stats,
488  TestLpBoundNorms());
489  EXPECT_THAT(maybe_result,
490  Optional(FieldsAre(TERMINATION_REASON_PRIMAL_INFEASIBLE,
491  POINT_TYPE_ITERATE_DIFFERENCE)));
492 }
493 
494 TEST_P(IterateTerminationTest, NoTerminationWithInfeasibleDualRay) {
495  const auto stats_infeasible_ray = ParseTextOrDie<IterationStats>(R"pb(
496  infeasibility_information: {
497  dual_ray_objective: 1.0
498  max_dual_ray_infeasibility: 1.0e-5 # Too large
499  })pb");
500  EXPECT_EQ(CheckIterateTerminationCriteria(
501  test_criteria_, stats_infeasible_ray, TestLpBoundNorms()),
502  std::nullopt);
503 }
504 
505 TEST_P(IterateTerminationTest, NoTerminationWithNegativeDualRayObjective) {
506  const auto stats_wrong_sign = ParseTextOrDie<IterationStats>(R"pb(
507  infeasibility_information: {
508  dual_ray_objective: -1.0 # Wrong sign
509  max_dual_ray_infeasibility: 0.0
510  })pb");
511  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats_wrong_sign,
512  TestLpBoundNorms()),
513  std::nullopt);
514 }
515 
516 TEST_P(IterateTerminationTest, NoTerminationWithZeroDualRayObjective) {
517  const auto stats_objective_zero = ParseTextOrDie<IterationStats>(R"pb(
518  infeasibility_information: {
519  dual_ray_objective: 0.0
520  max_dual_ray_infeasibility: 0.0
521  })pb");
522  EXPECT_EQ(CheckIterateTerminationCriteria(
523  test_criteria_, stats_objective_zero, TestLpBoundNorms()),
524  std::nullopt);
525 }
526 
527 TEST_P(IterateTerminationTest, DualInfeasibleFromAverageIterate) {
528  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
529  infeasibility_information: {
530  primal_ray_linear_objective: -1.0
531  max_primal_ray_infeasibility: 1.0e-16
532  candidate_type: POINT_TYPE_AVERAGE_ITERATE
533  })pb");
534  std::optional<TerminationReasonAndPointType> maybe_result =
535  CheckIterateTerminationCriteria(test_criteria_, stats,
536  TestLpBoundNorms());
537  EXPECT_THAT(maybe_result,
538  Optional(FieldsAre(TERMINATION_REASON_DUAL_INFEASIBLE,
539  POINT_TYPE_AVERAGE_ITERATE)));
540 }
541 
542 TEST_P(IterateTerminationTest, NoTerminationWithInfeasiblePrimalRay) {
543  const auto stats_infeasible_ray = ParseTextOrDie<IterationStats>(R"pb(
544  infeasibility_information: {
545  primal_ray_linear_objective: -1.0
546  max_primal_ray_infeasibility: 1.0e-5 # Too large
547  })pb");
548  EXPECT_EQ(CheckIterateTerminationCriteria(
549  test_criteria_, stats_infeasible_ray, TestLpBoundNorms()),
550  std::nullopt);
551 }
552 
553 TEST_P(IterateTerminationTest, NoTerminationWithPositivePrimalRayObjective) {
554  const auto stats_wrong_sign = ParseTextOrDie<IterationStats>(R"pb(
555  infeasibility_information: {
556  primal_ray_linear_objective: 1.0 # Wrong sign
557  max_primal_ray_infeasibility: 0.0
558  })pb");
559  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats_wrong_sign,
560  TestLpBoundNorms()),
561  std::nullopt);
562 }
563 
564 TEST_P(IterateTerminationTest, NoTerminationWithZeroPrimalRayObjective) {
565  const auto stats_objective_zero = ParseTextOrDie<IterationStats>(R"pb(
566  infeasibility_information: {
567  primal_ray_linear_objective: 0.0
568  max_primal_ray_infeasibility: 0.0
569  })pb");
570  EXPECT_EQ(CheckIterateTerminationCriteria(
571  test_criteria_, stats_objective_zero, TestLpBoundNorms()),
572  std::nullopt);
573 }
574 
575 TEST_P(IterateTerminationTest, TerminationWithOptimal) {
576  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
577  convergence_information {
578  primal_objective: 1.0
579  dual_objective: 1.0
580  l_inf_primal_residual: 0.0
581  l_inf_dual_residual: 0.0
582  l2_primal_residual: 0.0
583  l2_dual_residual: 0.0
584  l_inf_componentwise_primal_residual: 0.0
585  l_inf_componentwise_dual_residual: 0.0
586  candidate_type: POINT_TYPE_CURRENT_ITERATE
587  })pb");
588 
589  std::optional<TerminationReasonAndPointType> maybe_result =
590  CheckIterateTerminationCriteria(test_criteria_, stats,
591  TestLpBoundNorms());
592  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
593  POINT_TYPE_CURRENT_ITERATE)));
594 }
595 
596 TEST_P(IterateTerminationTest, TerminationWithNearOptimal) {
597  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
598  convergence_information {
599  primal_objective: 1.00019
600  dual_objective: 1.0
601  l_inf_primal_residual: 11.0e-4
602  l_inf_dual_residual: 5.4e-4
603  l2_primal_residual: 14.0e-4
604  l2_dual_residual: 6.0e-4
605  l_inf_componentwise_primal_residual: 9.0e-5
606  l_inf_componentwise_dual_residual: 9.0e-5
607  candidate_type: POINT_TYPE_CURRENT_ITERATE
608  })pb");
609 
610  std::optional<TerminationReasonAndPointType> maybe_result =
611  CheckIterateTerminationCriteria(test_criteria_, stats,
612  TestLpBoundNorms());
613  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
614  POINT_TYPE_CURRENT_ITERATE)));
615 }
616 
617 TEST_P(IterateTerminationTest,
618  TerminationWithNonOptimalInfiniteAbsoluteTolerances) {
619  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
620  convergence_information {
621  primal_objective: 1.0
622  dual_objective: 1.0
623  l_inf_primal_residual: 1.0
624  l_inf_dual_residual: 1.0
625  l2_primal_residual: 1.0
626  l2_dual_residual: 1.0
627  l_inf_componentwise_primal_residual: 1.0
628  l_inf_componentwise_dual_residual: 1.0
629  candidate_type: POINT_TYPE_CURRENT_ITERATE
630  })pb");
631  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_absolute(
632  std::numeric_limits<double>::infinity());
633  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_relative(
634  0);
635  std::optional<TerminationReasonAndPointType> maybe_result =
636  CheckIterateTerminationCriteria(test_criteria_, stats,
637  ZeroLpBoundNorms());
638  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
639  POINT_TYPE_CURRENT_ITERATE)));
640 }
641 
642 TEST_P(IterateTerminationTest,
643  TerminationWithNonOptimalInfiniteRelativeTolerances) {
644  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
645  convergence_information {
646  primal_objective: 0.0
647  dual_objective: 0.0
648  l_inf_primal_residual: 1.0
649  l_inf_dual_residual: 1.0
650  l2_primal_residual: 1.0
651  l2_dual_residual: 1.0
652  l_inf_componentwise_primal_residual: 1.0
653  l_inf_componentwise_dual_residual: 1.0
654  candidate_type: POINT_TYPE_CURRENT_ITERATE
655  })pb");
656  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_absolute(
657  0);
658  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_relative(
659  std::numeric_limits<double>::infinity());
660  std::optional<TerminationReasonAndPointType> maybe_result =
661  CheckIterateTerminationCriteria(test_criteria_, stats,
662  ZeroLpBoundNorms());
663  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
664  POINT_TYPE_CURRENT_ITERATE)));
665 }
666 
667 TEST_P(IterateTerminationTest,
668  TerminationWithNonOptimalInfiniteAbsoluteAndRelativeTolerances) {
669  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
670  convergence_information {
671  primal_objective: 1.0
672  dual_objective: 1.0
673  l_inf_primal_residual: 1.0
674  l_inf_dual_residual: 1.0
675  l2_primal_residual: 1.0
676  l2_dual_residual: 1.0
677  l_inf_componentwise_primal_residual: 1.0
678  l_inf_componentwise_dual_residual: 1.0
679  candidate_type: POINT_TYPE_CURRENT_ITERATE
680  })pb");
681  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_absolute(
682  std::numeric_limits<double>::infinity());
683  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_relative(
684  std::numeric_limits<double>::infinity());
685  std::optional<TerminationReasonAndPointType> maybe_result =
686  CheckIterateTerminationCriteria(test_criteria_, stats,
687  ZeroLpBoundNorms());
688  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
689  POINT_TYPE_CURRENT_ITERATE)));
690 }
691 
692 TEST_P(IterateTerminationTest, OptimalEvenWithNumericalError) {
693  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
694  convergence_information {
695  primal_objective: 1.0
696  dual_objective: 1.0
697  l_inf_primal_residual: 0.0
698  l_inf_dual_residual: 0.0
699  l2_primal_residual: 0.0
700  l2_dual_residual: 0.0
701  l_inf_componentwise_primal_residual: 0.0
702  l_inf_componentwise_dual_residual: 0.0
703  candidate_type: POINT_TYPE_CURRENT_ITERATE
704  })pb");
705  // Tests that `TERMINATION_REASON_OPTIMAL` overrides
706  // `TERMINATION_REASON_NUMERICAL_ERROR` when
707  // `force_numerical_termination == true`.
708  std::optional<TerminationReasonAndPointType> maybe_result =
709  CheckIterateTerminationCriteria(test_criteria_, stats, TestLpBoundNorms(),
710  /*force_numerical_termination=*/true);
711  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
712  POINT_TYPE_CURRENT_ITERATE)));
713 }
714 
715 TEST_P(IterateTerminationTest, NoTerminationWithBadGap) {
716  const auto stats_bad_gap = ParseTextOrDie<IterationStats>(R"pb(
717  convergence_information {
718  primal_objective: 10.0
719  dual_objective: 1.0
720  l_inf_primal_residual: 0.0
721  l_inf_dual_residual: 0.0
722  l2_primal_residual: 0.0
723  l2_dual_residual: 0.0
724  l_inf_componentwise_primal_residual: 0.0
725  l_inf_componentwise_dual_residual: 0.0
726  })pb");
727  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats_bad_gap,
728  TestLpBoundNorms()),
729  std::nullopt);
730 }
731 
732 TEST_P(IterateTerminationTest, NoTerminationWithInfiniteGap) {
733  const auto stats_infinite_gap = ParseTextOrDie<IterationStats>(R"pb(
734  convergence_information {
735  primal_objective: 0
736  dual_objective: -Inf
737  l_inf_primal_residual: 0.0
738  l_inf_dual_residual: 0.0
739  l2_primal_residual: 0.0
740  l2_dual_residual: 0.0
741  l_inf_componentwise_primal_residual: 0.0
742  l_inf_componentwise_dual_residual: 0.0
743  })pb");
744  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats_infinite_gap,
745  TestLpBoundNorms()),
746  std::nullopt);
747 }
748 
749 TEST_P(IterateTerminationTest, NoTerminationWithBadPrimalResidual) {
750  const auto stats_bad_primal = ParseTextOrDie<IterationStats>(R"pb(
751  convergence_information {
752  primal_objective: 1.0
753  dual_objective: 1.0
754  l_inf_primal_residual: 1.0
755  l_inf_dual_residual: 0.0
756  l2_primal_residual: 1.0
757  l2_dual_residual: 0.0
758  l_inf_componentwise_primal_residual: 1.0
759  l_inf_componentwise_dual_residual: 0.0
760  })pb");
761  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats_bad_primal,
762  TestLpBoundNorms()),
763  std::nullopt);
764 }
765 
766 TEST_P(IterateTerminationTest, NoTerminationWithBadDualResidual) {
767  const auto stats_bad_dual = ParseTextOrDie<IterationStats>(R"pb(
768  convergence_information {
769  primal_objective: 1.0
770  dual_objective: 1.0
771  l_inf_primal_residual: 0.0
772  l_inf_dual_residual: 1.0
773  l2_primal_residual: 0.0
774  l2_dual_residual: 1.0
775  l_inf_componentwise_primal_residual: 0.0
776  l_inf_componentwise_dual_residual: 1.0
777  })pb");
778  EXPECT_EQ(CheckIterateTerminationCriteria(test_criteria_, stats_bad_dual,
779  TestLpBoundNorms()),
780  std::nullopt);
781 }
782 
783 // Tests that optimality is checked with non-strict inequalities, as per the
784 // definitions in solvers.proto.
785 TEST_P(IterateTerminationTest, ZeroToleranceZeroError) {
786  const auto stats = ParseTextOrDie<IterationStats>(R"pb(
787  convergence_information {
788  primal_objective: 1.0
789  dual_objective: 1.0
790  l_inf_primal_residual: 0.0
791  l_inf_dual_residual: 0.0
792  l2_primal_residual: 0.0
793  l2_dual_residual: 0.0
794  l_inf_componentwise_primal_residual: 0.0
795  l_inf_componentwise_dual_residual: 0.0
796  candidate_type: POINT_TYPE_CURRENT_ITERATE
797  })pb");
798 
799  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_absolute(
800  0.0);
801  test_criteria_.mutable_simple_optimality_criteria()->set_eps_optimal_relative(
802  0.0);
803 
804  std::optional<TerminationReasonAndPointType> maybe_result =
805  CheckIterateTerminationCriteria(test_criteria_, stats,
806  TestLpBoundNorms());
807  EXPECT_THAT(maybe_result, Optional(FieldsAre(TERMINATION_REASON_OPTIMAL,
808  POINT_TYPE_CURRENT_ITERATE)));
809 }
810 
811 INSTANTIATE_TEST_SUITE_P(OptNorm, IterateTerminationTest,
812  testing::Values(OPTIMALITY_NORM_L_INF,
813  OPTIMALITY_NORM_L2,
814  OPTIMALITY_NORM_L_INF_COMPONENTWISE));
815 
816 INSTANTIATE_TEST_SUITE_P(DetailedRelativeOptNorm,
817  DetailedRelativeTerminationTest,
818  testing::Values(OPTIMALITY_NORM_L_INF,
819  OPTIMALITY_NORM_L2,
820  OPTIMALITY_NORM_L_INF_COMPONENTWISE));
821 INSTANTIATE_TEST_SUITE_P(DetailedAbsoluteOptNorm,
822  DetailedAbsoluteTerminationTest,
823  testing::Values(OPTIMALITY_NORM_L_INF,
824  OPTIMALITY_NORM_L2,
825  OPTIMALITY_NORM_L_INF_COMPONENTWISE));
826 
827 TEST(IterateTerminationTest, OptimalityNormsDiffer) {
828  auto test_criteria = ParseTextOrDie<TerminationCriteria>(R"pb(
829  simple_optimality_criteria { eps_optimal_relative: 1.0 })pb");
830 
831  // For L2, optimality requires norm(`primal_residual`, 2) <= 14.49
832  // For L_inf, optimality requires norm(`primal_residual`, Inf) <= 12.0
833  // For L_inf_componentwise, optimality requires norm(`primal_residual`) <= 1.0
834 
835  struct {
836  double primal_residual;
837  std::optional<TerminationReasonAndPointType> expected_l2;
838  std::optional<TerminationReasonAndPointType> expected_l_inf;
839  std::optional<TerminationReasonAndPointType> expected_l_inf_relative;
840  } test_configs[] = {
841  {0.5,
842  TerminationReasonAndPointType{.reason = TERMINATION_REASON_OPTIMAL,
843  .type = POINT_TYPE_CURRENT_ITERATE},
844  TerminationReasonAndPointType{.reason = TERMINATION_REASON_OPTIMAL,
845  .type = POINT_TYPE_CURRENT_ITERATE},
846  TerminationReasonAndPointType{.reason = TERMINATION_REASON_OPTIMAL,
847  .type = POINT_TYPE_CURRENT_ITERATE}},
848  {10.0,
849  TerminationReasonAndPointType{.reason = TERMINATION_REASON_OPTIMAL,
850  .type = POINT_TYPE_CURRENT_ITERATE},
851  TerminationReasonAndPointType{.reason = TERMINATION_REASON_OPTIMAL,
852  .type = POINT_TYPE_CURRENT_ITERATE},
853  std::nullopt},
854  {13.0,
855  TerminationReasonAndPointType{.reason = TERMINATION_REASON_OPTIMAL,
856  .type = POINT_TYPE_CURRENT_ITERATE},
857  std::nullopt, std::nullopt},
858  {15.0, std::nullopt, std::nullopt, std::nullopt}};
859 
860  for (const auto& config : test_configs) {
861  IterationStats stats;
862  auto* convergence_info = stats.add_convergence_information();
863  convergence_info->set_primal_objective(1.0);
864  convergence_info->set_dual_objective(1.0);
865  convergence_info->set_l_inf_primal_residual(config.primal_residual);
866  convergence_info->set_l2_primal_residual(config.primal_residual);
867  convergence_info->set_l_inf_componentwise_primal_residual(
868  config.primal_residual);
869  convergence_info->set_candidate_type(POINT_TYPE_CURRENT_ITERATE);
870 
871  test_criteria.set_optimality_norm(OPTIMALITY_NORM_L_INF);
872  std::optional<TerminationReasonAndPointType> maybe_result =
873  CheckIterateTerminationCriteria(test_criteria, stats,
874  TestLpBoundNorms());
875  ASSERT_TRUE(maybe_result.has_value() == config.expected_l_inf.has_value())
876  << "primal_residual: " << config.primal_residual;
877  if (config.expected_l_inf.has_value()) {
878  EXPECT_EQ(maybe_result->reason, config.expected_l_inf->reason);
879  EXPECT_EQ(maybe_result->type, config.expected_l_inf->type);
880  }
881 
882  test_criteria.set_optimality_norm(OPTIMALITY_NORM_L2);
883 
884  maybe_result = CheckIterateTerminationCriteria(test_criteria, stats,
885  TestLpBoundNorms());
886  ASSERT_TRUE(maybe_result.has_value() == config.expected_l2.has_value())
887  << "primal_residual: " << config.primal_residual;
888  if (config.expected_l2.has_value()) {
889  EXPECT_EQ(maybe_result->reason, config.expected_l2->reason);
890  EXPECT_EQ(maybe_result->type, config.expected_l2->type);
891  }
892 
893  test_criteria.set_optimality_norm(OPTIMALITY_NORM_L_INF_COMPONENTWISE);
894  maybe_result = CheckIterateTerminationCriteria(test_criteria, stats,
895  TestLpBoundNorms());
896  ASSERT_TRUE(maybe_result.has_value() ==
897  config.expected_l_inf_relative.has_value())
898  << "primal_residual: " << config.primal_residual;
899  if (config.expected_l_inf_relative.has_value()) {
900  EXPECT_EQ(maybe_result->reason, config.expected_l_inf_relative->reason);
901  EXPECT_EQ(maybe_result->type, config.expected_l_inf_relative->type);
902  }
903  }
904 }
905 
906 TEST(BoundNormsFromProblemStats, ExtractsBoundNorms) {
907  const auto qp_stats = ParseTextOrDie<QuadraticProgramStats>(R"pb(
908  objective_vector_l2_norm: 4.0
909  combined_bounds_l2_norm: 3.0
910  objective_vector_abs_max: 1.0
911  combined_bounds_max: 2.0
912  )pb");
913  const QuadraticProgramBoundNorms norms = BoundNormsFromProblemStats(qp_stats);
914  EXPECT_EQ(norms.l2_norm_primal_linear_objective, 4.0);
915  EXPECT_EQ(norms.l2_norm_constraint_bounds, 3.0);
916  EXPECT_EQ(norms.l_inf_norm_primal_linear_objective, 1.0);
917  EXPECT_EQ(norms.l_inf_norm_constraint_bounds, 2.0);
918 }
919 
920 TEST(EpsilonRatio, SimpleChecks) {
921  EXPECT_EQ(EpsilonRatio(0.0, 0.0), 1.0);
922  EXPECT_EQ(EpsilonRatio(1.0, 1.0), 1.0);
923  EXPECT_EQ(EpsilonRatio(std::numeric_limits<double>::infinity(),
924  std::numeric_limits<double>::infinity()),
925  1.0);
926  EXPECT_EQ(EpsilonRatio(1.0, 2.0), 0.5);
927  EXPECT_EQ(EpsilonRatio(2.0, 1.0), 2.0);
928  EXPECT_EQ(EpsilonRatio(0.0, std::numeric_limits<double>::infinity()), 0.0);
929  EXPECT_EQ(EpsilonRatio(std::numeric_limits<double>::infinity(), 0.0),
930  std::numeric_limits<double>::infinity());
931 }
932 
933 TEST(ComputeRelativeResiduals,
934  ComputesRelativeResidualsForZeroAbsoluteTolerance) {
935  ConvergenceInformation stats;
936  // If the absolute error tolerance is 0.0 and the relative error tolerance is
937  // nonzero, the relative residuals are just the absolute residuals divided by
938  // the corresponding norms (the actual nonzero value of the relative error
939  // tolerance doesn't matter).
940  stats.set_primal_objective(10.0);
941  stats.set_dual_objective(5.0);
942  stats.set_l_inf_primal_residual(1.0);
943  stats.set_l2_primal_residual(1.0);
944  stats.set_l_inf_dual_residual(1.0);
945  stats.set_l2_dual_residual(1.0);
946  TerminationCriteria termination_criteria;
947  termination_criteria.mutable_simple_optimality_criteria()
948  ->set_eps_optimal_absolute(0.0);
949  termination_criteria.mutable_simple_optimality_criteria()
950  ->set_eps_optimal_relative(1.0e-6);
951  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
952  EffectiveOptimalityCriteria(termination_criteria), stats,
953  TestLpBoundNorms());
954 
955  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 1.0 / 12.0);
956  EXPECT_EQ(relative_info.relative_l2_primal_residual, 1.0 / std::sqrt(210.0));
957 
958  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 1.0 / 5.5);
959  EXPECT_EQ(relative_info.relative_l2_dual_residual, 1.0 / sqrt(36.25));
960 
961  // The relative optimality gap should just be the objective difference divided
962  // by the sum of absolute values (the actual nonzero value of the relative
963  // error tolerance doesn't matter).
964  EXPECT_EQ(relative_info.relative_optimality_gap, 5.0 / 15.0);
965 }
966 
967 TEST(ComputeRelativeResiduals,
968  ComputesRelativeResidualsForZeroRelativeTolerance) {
969  ConvergenceInformation stats;
970  // If the relative error tolerance is 0.0 and the absolute error tolerance
971  // is nonzero, all of the relative residuals and the relative optimality gap
972  // should be 0.0, no matter what the absolute error tolerance is.
973  stats.set_primal_objective(10.0);
974  stats.set_dual_objective(5.0);
975  stats.set_l_inf_primal_residual(1.0);
976  stats.set_l2_primal_residual(1.0);
977  stats.set_l_inf_dual_residual(1.0);
978  stats.set_l2_dual_residual(1.0);
979  TerminationCriteria::SimpleOptimalityCriteria opt_criteria;
980  opt_criteria.set_eps_optimal_absolute(1.0e-6);
981  opt_criteria.set_eps_optimal_relative(0.0);
982  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
983  EffectiveOptimalityCriteria(opt_criteria), stats, TestLpBoundNorms());
984 
985  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 0.0);
986  EXPECT_EQ(relative_info.relative_l2_primal_residual, 0.0);
987  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 0.0);
988  EXPECT_EQ(relative_info.relative_l2_dual_residual, 0.0);
989  EXPECT_EQ(relative_info.relative_optimality_gap, 0.0);
990 }
991 
992 TEST(ComputeRelativeResiduals,
993  ComputesCorrectRelativeResidualsForEqualTolerances) {
994  ConvergenceInformation stats;
995  // If the absolute error tolerance and relative error tolerance are equal (and
996  // nonzero), the relative residuals are the absolute residuals divided by 1.0
997  // plus the corresponding norms.
998  stats.set_primal_objective(10.0);
999  stats.set_dual_objective(5.0);
1000  stats.set_l_inf_primal_residual(1.0);
1001  stats.set_l2_primal_residual(1.0);
1002  stats.set_l_inf_dual_residual(1.0);
1003  stats.set_l2_dual_residual(1.0);
1004  TerminationCriteria::SimpleOptimalityCriteria opt_criteria;
1005  opt_criteria.set_eps_optimal_absolute(1.0e-6);
1006  opt_criteria.set_eps_optimal_relative(1.0e-6);
1007  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
1008  EffectiveOptimalityCriteria(opt_criteria), stats, TestLpBoundNorms());
1009 
1010  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 1.0 / (1.0 + 12.0));
1011  EXPECT_EQ(relative_info.relative_l2_primal_residual,
1012  1.0 / (1.0 + std::sqrt(210.0)));
1013 
1014  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 1.0 / (1.0 + 5.5));
1015  EXPECT_EQ(relative_info.relative_l2_dual_residual, 1.0 / (1.0 + sqrt(36.25)));
1016 
1017  // The relative optimality gap should just be the objective difference divided
1018  // by 1.0 + the sum of absolute values.
1019  EXPECT_EQ(relative_info.relative_optimality_gap, 5.0 / (1.0 + 15.0));
1020 }
1021 
1022 TEST(ComputeRelativeResiduals,
1023  ComputesCorrectRelativeResidualsForBothTolerancesZero) {
1024  ConvergenceInformation stats;
1025  // If the absolute error tolerance and relative error tolerance are both zero,
1026  // the relative residuals are the same as when the tolerances are equal and
1027  // nonzero.
1028  stats.set_primal_objective(10.0);
1029  stats.set_dual_objective(5.0);
1030  stats.set_l_inf_primal_residual(1.0);
1031  stats.set_l2_primal_residual(1.0);
1032  stats.set_l_inf_dual_residual(1.0);
1033  stats.set_l2_dual_residual(1.0);
1034  TerminationCriteria::SimpleOptimalityCriteria opt_criteria;
1035  opt_criteria.set_eps_optimal_absolute(0.0);
1036  opt_criteria.set_eps_optimal_relative(0.0);
1037  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
1038  EffectiveOptimalityCriteria(opt_criteria), stats, TestLpBoundNorms());
1039 
1040  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 1.0 / (1.0 + 12.0));
1041  EXPECT_EQ(relative_info.relative_l2_primal_residual,
1042  1.0 / (1.0 + std::sqrt(210.0)));
1043 
1044  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 1.0 / (1.0 + 5.5));
1045  EXPECT_EQ(relative_info.relative_l2_dual_residual, 1.0 / (1.0 + sqrt(36.25)));
1046 
1047  // The relative optimality gap should just be the objective difference divided
1048  // by 1.0 + the sum of absolute values.
1049  EXPECT_EQ(relative_info.relative_optimality_gap, 5.0 / (1.0 + 15.0));
1050 }
1051 
1052 TEST(ComputeRelativeResiduals,
1053  ComputesCorrectRelativeResidualsForDetailedTerminationCriteria) {
1054  ConvergenceInformation stats;
1055  // If the absolute error tolerance and relative error tolerance are equal (and
1056  // nonzero), the relative residuals are the absolute residuals divided by 1.0
1057  // plus the corresponding norms.
1058  stats.set_primal_objective(10.0);
1059  stats.set_dual_objective(5.0);
1060  stats.set_l_inf_primal_residual(1.0);
1061  stats.set_l2_primal_residual(1.0);
1062  stats.set_l_inf_dual_residual(1.0);
1063  stats.set_l2_dual_residual(1.0);
1064  TerminationCriteria::DetailedOptimalityCriteria opt_criteria;
1065  opt_criteria.set_eps_optimal_primal_residual_absolute(2.0e-6);
1066  opt_criteria.set_eps_optimal_primal_residual_relative(2.0e-4);
1067  opt_criteria.set_eps_optimal_dual_residual_absolute(1.0e-3);
1068  opt_criteria.set_eps_optimal_dual_residual_relative(1.0e-4);
1069  opt_criteria.set_eps_optimal_objective_gap_absolute(3.0e-8);
1070  opt_criteria.set_eps_optimal_objective_gap_relative(3.0e-7);
1071  const RelativeConvergenceInformation relative_info =
1072  ComputeRelativeResiduals(opt_criteria, stats, TestLpBoundNorms());
1073 
1074  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 1.0 / (0.01 + 12.0));
1075  EXPECT_EQ(relative_info.relative_l2_primal_residual,
1076  1.0 / (0.01 + std::sqrt(210.0)));
1077 
1078  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 1.0 / (10.0 + 5.5));
1079  EXPECT_EQ(relative_info.relative_l2_dual_residual,
1080  1.0 / (10.0 + sqrt(36.25)));
1081 
1082  // The relative optimality gap should just be the objective difference divided
1083  // by 0.1 + the sum of absolute values.
1084  EXPECT_EQ(relative_info.relative_optimality_gap, 5.0 / (0.1 + 15.0));
1085 }
1086 
1087 TEST(ComputeRelativeResiduals,
1088  ComputesCorrectRelativeResidualsForInfiniteAbsoluteTolerances) {
1089  ConvergenceInformation stats;
1090  stats.set_primal_objective(10.0);
1091  stats.set_dual_objective(5.0);
1092  stats.set_l_inf_primal_residual(1.0);
1093  stats.set_l2_primal_residual(1.0);
1094  stats.set_l_inf_dual_residual(1.0);
1095  stats.set_l2_dual_residual(1.0);
1096  TerminationCriteria::SimpleOptimalityCriteria opt_criteria;
1097  opt_criteria.set_eps_optimal_absolute(
1098  std::numeric_limits<double>::infinity());
1099  opt_criteria.set_eps_optimal_relative(1.0e-6);
1100  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
1101  EffectiveOptimalityCriteria(opt_criteria), stats, TestLpBoundNorms());
1102 
1103  // If absolute tolerance is infinite the relative residuals are zero.
1104  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 0.0);
1105  EXPECT_EQ(relative_info.relative_l2_primal_residual, 0.0);
1106  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 0.0);
1107  EXPECT_EQ(relative_info.relative_l2_dual_residual, 0.0);
1108  EXPECT_EQ(relative_info.relative_optimality_gap, 0.0);
1109 }
1110 
1111 TEST(ComputeRelativeResiduals,
1112  ComputesCorrectRelativeResidualsForInfiniteRelativeTolerances) {
1113  ConvergenceInformation stats;
1114  stats.set_primal_objective(10.0);
1115  stats.set_dual_objective(5.0);
1116  stats.set_l_inf_primal_residual(1.0);
1117  stats.set_l2_primal_residual(1.0);
1118  stats.set_l_inf_dual_residual(1.0);
1119  stats.set_l2_dual_residual(1.0);
1120  TerminationCriteria::SimpleOptimalityCriteria opt_criteria;
1121  opt_criteria.set_eps_optimal_absolute(1.0e-6);
1122  opt_criteria.set_eps_optimal_relative(
1123  std::numeric_limits<double>::infinity());
1124  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
1125  EffectiveOptimalityCriteria(opt_criteria), stats, TestLpBoundNorms());
1126 
1127  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 1.0 / 12.0);
1128  EXPECT_EQ(relative_info.relative_l2_primal_residual, 1.0 / std::sqrt(210.0));
1129 
1130  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 1.0 / 5.5);
1131  EXPECT_EQ(relative_info.relative_l2_dual_residual, 1.0 / sqrt(36.25));
1132 
1133  // The relative optimality gap should just be the objective difference divided
1134  // by the sum of absolute values.
1135  EXPECT_EQ(relative_info.relative_optimality_gap, 5.0 / 15.0);
1136 }
1137 
1138 TEST(ComputeRelativeResiduals,
1139  ComputesCorrectRelativeResidualsForInfiniteAbsoluteAndRelativeTolerances) {
1140  ConvergenceInformation stats;
1141  // If the absolute error tolerance and relative error tolerance are both
1142  // infinity (and nonzero), the relative residuals are the absolute residuals
1143  // divided by 1.0 plus the corresponding norms.
1144  stats.set_primal_objective(10.0);
1145  stats.set_dual_objective(5.0);
1146  stats.set_l_inf_primal_residual(1.0);
1147  stats.set_l2_primal_residual(1.0);
1148  stats.set_l_inf_dual_residual(1.0);
1149  stats.set_l2_dual_residual(1.0);
1150  TerminationCriteria::SimpleOptimalityCriteria opt_criteria;
1151  opt_criteria.set_eps_optimal_absolute(
1152  std::numeric_limits<double>::infinity());
1153  opt_criteria.set_eps_optimal_relative(
1154  std::numeric_limits<double>::infinity());
1155  const RelativeConvergenceInformation relative_info = ComputeRelativeResiduals(
1156  EffectiveOptimalityCriteria(opt_criteria), stats, TestLpBoundNorms());
1157 
1158  EXPECT_EQ(relative_info.relative_l_inf_primal_residual, 1.0 / (1.0 + 12.0));
1159  EXPECT_EQ(relative_info.relative_l2_primal_residual,
1160  1.0 / (1.0 + std::sqrt(210.0)));
1161 
1162  EXPECT_EQ(relative_info.relative_l_inf_dual_residual, 1.0 / (1.0 + 5.5));
1163  EXPECT_EQ(relative_info.relative_l2_dual_residual, 1.0 / (1.0 + sqrt(36.25)));
1164 
1165  // The relative optimality gap should just be the objective difference divided
1166  // by 1.0 + the sum of absolute values.
1167  EXPECT_EQ(relative_info.relative_optimality_gap, 5.0 / (1.0 + 15.0));
1168 }
1169 
1170 } // namespace
1171 } // namespace operations_research::pdlp
google::protobuf::util::ParseTextOrDie
T ParseTextOrDie(const std::string &input)
Definition: protobuf_util.h:77
operations_research::pdlp
Definition: iteration_stats.cc:35
operations_research::pdlp::EpsilonRatio
double EpsilonRatio(const double epsilon_absolute, const double epsilon_relative)
Definition: termination.cc:231
operations_research::pdlp::OptimalityCriteriaMet
bool OptimalityCriteriaMet(const TerminationCriteria::DetailedOptimalityCriteria &optimality_criteria, const ConvergenceInformation &stats, const OptimalityNorm optimality_norm, const QuadraticProgramBoundNorms &bound_norms)
Definition: termination.cc:44
operations_research::pdlp::ObjectiveGapMet
bool ObjectiveGapMet(const TerminationCriteria::DetailedOptimalityCriteria &optimality_criteria, const ConvergenceInformation &stats)
Definition: termination.cc:27
operations_research::pdlp::EffectiveOptimalityCriteria
TerminationCriteria::DetailedOptimalityCriteria EffectiveOptimalityCriteria(const TerminationCriteria &termination_criteria)
Definition: termination.cc:127
operations_research::pdlp::CheckIterateTerminationCriteria
std::optional< TerminationReasonAndPointType > CheckIterateTerminationCriteria(const TerminationCriteria &criteria, const IterationStats &stats, const QuadraticProgramBoundNorms &bound_norms, const bool force_numerical_termination)
Definition: termination.cc:187
operations_research::pdlp::ComputeRelativeResiduals
RelativeConvergenceInformation ComputeRelativeResiduals(const TerminationCriteria::DetailedOptimalityCriteria &optimality_criteria, const ConvergenceInformation &stats, const QuadraticProgramBoundNorms &bound_norms)
Definition: termination.cc:240
operations_research::pdlp::CheckSimpleTerminationCriteria
std::optional< TerminationReasonAndPointType > CheckSimpleTerminationCriteria(const TerminationCriteria &criteria, const IterationStats &stats, const std::atomic< bool > *interrupt_solve)
Definition: termination.cc:162
operations_research::pdlp::BoundNormsFromProblemStats
QuadraticProgramBoundNorms BoundNormsFromProblemStats(const QuadraticProgramStats &stats)
Definition: termination.cc:222
operations_research::pdlp::operator==
bool operator==(const TerminationCriteria::DetailedOptimalityCriteria &lhs, const TerminationCriteria::DetailedOptimalityCriteria &rhs)
Definition: termination_test.cc:28
operations_research::TEST
TEST(LinearAssignmentTest, NullMatrix)
Definition: hungarian_test.cc:78
protobuf_util.h
test_criteria_
TerminationCriteria test_criteria_
Definition: termination_test.cc:87