Deal with bounds constrained problems in the Solver.
1. Detect if the problem is bounds constrained.
2. Detect if the problem is infeasible due to
constant infeasible parameter blocks.
3. Simplify the interface to TrustRegionMinimize and
LineSearchMinimize. In the process fix a bug related
to early return and the way user state pointers
were being dealt with in parameter blocks.
Change-Id: Ie7e70862029d3e0734636882c21ea594516119d1
diff --git a/internal/ceres/solver_impl.cc b/internal/ceres/solver_impl.cc
index 0d55c05..070ed80 100644
--- a/internal/ceres/solver_impl.cc
+++ b/internal/ceres/solver_impl.cc
@@ -323,6 +323,61 @@
return true;
}
+// Returns true if the program has any non-constant parameter blocks
+// which have non-trivial bounds constraints.
+bool IsBoundsConstrained(const Program& program) {
+ const vector<ParameterBlock*>& parameter_blocks = program.parameter_blocks();
+ for (int i = 0; i < parameter_blocks.size(); ++i) {
+ if (parameter_blocks[i]->IsConstant()) {
+ continue;
+ }
+
+ const double* lower_bounds = parameter_blocks[i]->lower_bounds();
+ const double* upper_bounds = parameter_blocks[i]->upper_bounds();
+ const int size = parameter_blocks[i]->Size();
+ for (int j = 0; j < size; ++j) {
+ if (lower_bounds[j] > -std::numeric_limits<double>::max() ||
+ upper_bounds[j] < std::numeric_limits<double>::max()) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+// Returns true, if the problem has any constant parameter blocks
+// which are not feasible. This means that Ceres cannot produce a
+// feasible solution to the problem.
+bool HasInfeasibleConstantParameterBlock(const ProblemImpl* problem,
+ string* message) {
+ CHECK_NOTNULL(message);
+ const Program& program = problem->program();
+ const vector<ParameterBlock*>& parameter_blocks = program.parameter_blocks();
+ for (int i = 0; i < parameter_blocks.size(); ++i) {
+ if (!parameter_blocks[i]->IsConstant()) {
+ continue;
+ }
+
+ const double* array = parameter_blocks[i]->user_state();
+ const double* lower_bounds = parameter_blocks[i]->lower_bounds();
+ const double* upper_bounds = parameter_blocks[i]->upper_bounds();
+ const int size = parameter_blocks[i]->Size();
+ for (int j = 0; j < size; ++j) {
+ if (array[j] < lower_bounds[j] || array[j] > upper_bounds[j]) {
+ *message = StringPrintf(
+ "ParameterBlock: %p with size %d has at least one infeasible value."
+ "\nFirst infeasible value is at index: %d."
+ "\nLower bound: %e, value: %e, upper bound: %e"
+ "\nParameter block values: ",
+ array, size, j, lower_bounds[j], array[j], upper_bounds[j]);
+ AppendArrayToString(size, array, message);
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
} // namespace
void SolverImpl::TrustRegionMinimize(
@@ -331,12 +386,18 @@
CoordinateDescentMinimizer* inner_iteration_minimizer,
Evaluator* evaluator,
LinearSolver* linear_solver,
- double* parameters,
Solver::Summary* summary) {
Minimizer::Options minimizer_options(options);
+ minimizer_options.is_constrained = IsBoundsConstrained(*program);
- // TODO(sameeragarwal): Add support for logging the configuration
- // and more detailed stats.
+ // The optimizer works on contiguous parameter vectors; allocate
+ // some.
+ Vector parameters(program->NumParameters());
+
+ // Collect the discontiguous parameters into a contiguous state
+ // vector.
+ program->ParameterBlocksToStateVector(parameters.data());
+
scoped_ptr<IterationCallback> file_logging_callback;
if (!options.solver_log.empty()) {
file_logging_callback.reset(new FileLoggingCallback(options.solver_log));
@@ -351,7 +412,7 @@
&logging_callback);
}
- StateUpdatingCallback updating_callback(program, parameters);
+ StateUpdatingCallback updating_callback(program, parameters.data());
if (options.update_state_every_iteration) {
// This must get pushed to the front of the callbacks so that it is run
// before any of the user callbacks.
@@ -381,7 +442,17 @@
TrustRegionMinimizer minimizer;
double minimizer_start_time = WallTimeInSeconds();
- minimizer.Minimize(minimizer_options, parameters, summary);
+ minimizer.Minimize(minimizer_options, parameters.data(), summary);
+
+ // If the user aborted mid-optimization or the optimization
+ // terminated because of a numerical failure, then do not update
+ // user state.
+ if (summary->termination_type != USER_FAILURE &&
+ summary->termination_type != FAILURE) {
+ program->StateVectorToParameterBlocks(parameters.data());
+ program->CopyParameterBlockStateToUserState();
+ }
+
summary->minimizer_time_in_seconds =
WallTimeInSeconds() - minimizer_start_time;
}
@@ -391,10 +462,15 @@
const Solver::Options& options,
Program* program,
Evaluator* evaluator,
- double* parameters,
Solver::Summary* summary) {
Minimizer::Options minimizer_options(options);
+ // The optimizer works on contiguous parameter vectors; allocate some.
+ Vector parameters(program->NumParameters());
+
+ // Collect the discontiguous parameters into a contiguous state vector.
+ program->ParameterBlocksToStateVector(parameters.data());
+
// TODO(sameeragarwal): Add support for logging the configuration
// and more detailed stats.
scoped_ptr<IterationCallback> file_logging_callback;
@@ -411,7 +487,7 @@
&logging_callback);
}
- StateUpdatingCallback updating_callback(program, parameters);
+ StateUpdatingCallback updating_callback(program, parameters.data());
if (options.update_state_every_iteration) {
// This must get pushed to the front of the callbacks so that it is run
// before any of the user callbacks.
@@ -423,7 +499,17 @@
LineSearchMinimizer minimizer;
double minimizer_start_time = WallTimeInSeconds();
- minimizer.Minimize(minimizer_options, parameters, summary);
+ minimizer.Minimize(minimizer_options, parameters.data(), summary);
+
+ // If the user aborted mid-optimization or the optimization
+ // terminated because of a numerical failure, then do not update
+ // user state.
+ if (summary->termination_type != USER_FAILURE &&
+ summary->termination_type != FAILURE) {
+ program->StateVectorToParameterBlocks(parameters.data());
+ program->CopyParameterBlockStateToUserState();
+ }
+
summary->minimizer_time_in_seconds =
WallTimeInSeconds() - minimizer_start_time;
}
@@ -508,6 +594,11 @@
return;
}
+ if (HasInfeasibleConstantParameterBlock(problem_impl, &summary->message)) {
+ LOG(ERROR) << "Terminating: " << summary->message;
+ return;
+ }
+
event_logger.AddEvent("Init");
original_program->SetParameterBlockStatePtrsToUserStatePtrs();
@@ -654,14 +745,6 @@
}
event_logger.AddEvent("CreateInnerIterationMinimizer");
- // The optimizer works on contiguous parameter vectors; allocate some.
- Vector parameters(reduced_program->NumParameters());
-
- // Collect the discontiguous parameters into a contiguous state vector.
- reduced_program->ParameterBlocksToStateVector(parameters.data());
-
- Vector original_parameters = parameters;
-
double minimizer_start_time = WallTimeInSeconds();
summary->preprocessor_time_in_seconds =
minimizer_start_time - solver_start_time;
@@ -672,26 +755,12 @@
inner_iteration_minimizer.get(),
evaluator.get(),
linear_solver.get(),
- parameters.data(),
summary);
event_logger.AddEvent("Minimize");
- SetSummaryFinalCost(summary);
-
- // If the user aborted mid-optimization or the optimization
- // terminated because of a numerical failure, then return without
- // updating user state.
- if (summary->termination_type == USER_FAILURE ||
- summary->termination_type == FAILURE) {
- return;
- }
-
double post_process_start_time = WallTimeInSeconds();
- // Push the contiguous optimized parameters back to the user's
- // parameters.
- reduced_program->StateVectorToParameterBlocks(parameters.data());
- reduced_program->CopyParameterBlockStateToUserState();
+ SetSummaryFinalCost(summary);
// Ensure the program state is set to the user parameters on the way
// out.
@@ -744,6 +813,12 @@
return;
}
+ if (IsBoundsConstrained(problem_impl->program())) {
+ summary->message = "LINE_SEARCH Minimizer does not support bounds.";
+ LOG(ERROR) << "Terminating: " << summary->message;
+ return;
+ }
+
Solver::Options options(original_options);
// This ensures that we get a Block Jacobian Evaluator along with
@@ -851,39 +926,15 @@
return;
}
- // The optimizer works on contiguous parameter vectors; allocate some.
- Vector parameters(reduced_program->NumParameters());
-
- // Collect the discontiguous parameters into a contiguous state vector.
- reduced_program->ParameterBlocksToStateVector(parameters.data());
-
- Vector original_parameters = parameters;
-
const double minimizer_start_time = WallTimeInSeconds();
summary->preprocessor_time_in_seconds =
minimizer_start_time - solver_start_time;
// Run the optimization.
- LineSearchMinimize(options,
- reduced_program.get(),
- evaluator.get(),
- parameters.data(),
- summary);
-
- // If the user aborted mid-optimization or the optimization
- // terminated because of a numerical failure, then return without
- // updating user state.
- if (summary->termination_type == USER_FAILURE ||
- summary->termination_type == FAILURE) {
- return;
- }
+ LineSearchMinimize(options, reduced_program.get(), evaluator.get(), summary);
const double post_process_start_time = WallTimeInSeconds();
- // Push the contiguous optimized parameters back to the user's parameters.
- reduced_program->StateVectorToParameterBlocks(parameters.data());
- reduced_program->CopyParameterBlockStateToUserState();
-
SetSummaryFinalCost(summary);
// Ensure the program state is set to the user parameters on the way out.
