Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <panoc-alm/inner/decl/panoc-fwd.hpp>
       4             : #include <panoc-alm/util/problem.hpp>
       5             : #include <panoc-alm/util/solverstatus.hpp>
       6             : 
       7             : #include <chrono>
       8             : #include <string>
       9             : 
      10             : namespace pa {
      11             : 
      12             : /// Parameters for the Augmented Lagrangian solver.
      13           4 : struct ALMParams {
      14             :     /// Primal tolerance.
      15           4 :     real_t ε = 1e-5;
      16             :     /// Dual tolerance.
      17           4 :     real_t δ = 1e-5;
      18             :     /// Factor used in updating the penalty parameters.
      19           4 :     real_t Δ = 10;
      20             :     /// Factor to reduce @ref ALMParams::Δ when inner convergence fails.
      21           4 :     real_t Δ_lower = 0.8;
      22             :     /// Initial penalty parameter. When set to zero (which is the default),
      23             :     /// it is computed automatically, based on the constraint violation in the
      24             :     /// starting point and the parameter @ref ALMParams::σ₀.
      25             :     /// @todo Change default to 0.
      26           4 :     real_t Σ₀ = 1;
      27             :     /// Initial penalty parameter factor. Active if @ref ALMParams::Σ₀ is set
      28             :     /// to zero.
      29           4 :     real_t σ₀ = 20;
      30             :     /// Factor to reduce the initial penalty factor by if convergence fails in
      31             :     /// in the first iteration.
      32           4 :     real_t Σ₀_lower = 0.6;
      33             :     /// Initial primal tolerance.
      34           4 :     real_t ε₀ = 1;
      35             :     /// Factor to increase the initial primal tolerance if convergence fails in
      36             :     /// the first iteration.
      37           4 :     real_t ε₀_increase = 1.1;
      38             :     /// Update factor for primal tolerance.
      39           4 :     real_t ρ = 1e-1;
      40             :     /// Factor to increase the primal tolerance update factor by if convergence
      41             :     /// fails.
      42           4 :     real_t ρ_increase = 2;
      43             :     /// Error tolerance for penalty increase
      44           4 :     real_t θ = 0.1;
      45             :     /// Lagrange multiplier bound.
      46           4 :     real_t M = 1e9;
      47             :     /// Maximum penalty factor.
      48           4 :     real_t Σ_max = 1e9;
      49             :     /// Minimum penalty factor (used during initialization).
      50           4 :     real_t Σ_min = 1e-9;
      51             :     /// Maximum number of outer ALM iterations.
      52           4 :     unsigned int max_iter = 100;
      53             :     /// Maximum duration.
      54           4 :     std::chrono::microseconds max_time = std::chrono::minutes(5);
      55             : 
      56             :     /// How many times can the initial penalty @ref ALMParams::Σ₀ or
      57             :     /// @ref ALMParams::σ₀ and the initial primal tolerance @ref ALMParams::ε₀
      58             :     /// be reduced.
      59           4 :     unsigned max_num_initial_retries = 20;
      60             :     /// How many times can the penalty update factor @ref ALMParams::Δ and the
      61             :     /// primal tolerance factor @ref ALMParams::ρ be reduced.
      62           4 :     unsigned max_num_retries = 20;
      63             :     /// Combined limit for @ref ALMParams::max_num_initial_retries and
      64             :     /// @ref ALMParams::max_num_retries.
      65           4 :     unsigned max_total_num_retries = 40;
      66             : 
      67             :     /// When to print progress. If set to zero, nothing will be printed.
      68             :     /// If set to N != 0, progress is printed every N iterations.
      69           4 :     unsigned print_interval = 0;
      70             : 
      71             :     /// Apply preconditioning to the problem, based on the gradients in the
      72             :     /// starting point.
      73           4 :     bool preconditioning = false;
      74             :     /// Use one penalty factor for all m constraints.
      75           4 :     bool single_penalty_factor = false;
      76             : };
      77             : 
      78             : /// Augmented Lagrangian Method solver
      79             : ///
      80             : /// @ingroup    grp_ALMSolver
      81             : template <class InnerSolverT = PANOCSolver<>>
      82           4 : class ALMSolver {
      83             :   public:
      84             :     using Params      = ALMParams;
      85             :     using InnerSolver = InnerSolverT;
      86             : 
      87          10 :     struct Stats {
      88             :         /// Total number of outer ALM iterations (i.e. the number of times that
      89             :         /// the inner solver was invoked).
      90           5 :         unsigned outer_iterations = 0;
      91             :         /// Total elapsed time.
      92             :         std::chrono::microseconds elapsed_time;
      93             :         /// The number of times that the initial penalty factor was reduced by
      94             :         /// @ref ALMParams::Σ₀_lower and that the initial tolerance was 
      95             :         /// increased by @ref ALMParams::ε₀_increase because the inner solver 
      96             :         /// failed to converge in the first ALM iteration. If this number is 
      97             :         /// greater than zero, consider lowering the initial penalty factor 
      98             :         /// @ref ALMParams::Σ₀ or @ref ALMParams::σ₀ or increasing the initial 
      99             :         /// tolerance @ref ALMParams::ε₀ (or both).
     100           5 :         unsigned initial_penalty_reduced    = 0;
     101             :         /// The number of times that the penalty update factor @ref ALMParams::Δ
     102             :         /// was reduced, that the tolerance update factor @ref ALMParams::ρ was 
     103             :         /// increased, and that an ALM iteration had to be restarted with a 
     104             :         /// lower penalty factor and a higher tolerance because the inner solver
     105             :         /// failed to converge (not applicable in the first ALM iteration).
     106             :         /// If this number is greater than zero, consider lowerering the 
     107             :         /// penalty update factor @ref ALMParams::Δ or increasing the tolerance
     108             :         /// update factor (or both). Lowering the initial penalty factor could
     109             :         /// help as well.
     110           5 :         unsigned penalty_reduced            = 0;
     111             :         /// The total number of times that the inner solver failed to converge.
     112           5 :         unsigned inner_convergence_failures = 0;
     113             :         /// Final primal tolerance that was reached, depends on the stopping 
     114             :         /// criterion used by the inner solver, see for example 
     115             :         /// @ref PANOCStopCrit.
     116           5 :         real_t ε                            = inf;
     117             :         /// Final dual tolerance or constraint violation that was reached:
     118             :         /// @f[
     119             :         /// \delta = \| \Pi_D\left(g(x^k) + \Sigma^{-1}y\right) \|_\infty
     120             :         /// @f]
     121           5 :         real_t δ                            = inf;
     122             :         /// 2-norm of the final penalty factors @f$ \| \Sigma \|_2 @f$.
     123           5 :         real_t norm_penalty                 = 0;
     124             : 
     125             :         /// Whether the solver converged or not.
     126             :         /// @see @ref SolverStatus
     127           5 :         SolverStatus status = SolverStatus::Unknown;
     128             : 
     129             :         /// The statistics of the inner solver invocations, accumulated over all
     130             :         /// ALM iterations.
     131             :         InnerStatsAccumulator<typename InnerSolver::Stats> inner;
     132             :     };
     133             : 
     134           4 :     ALMSolver(Params params, InnerSolver &&inner_solver)
     135           4 :         : params(params),
     136           4 :           inner_solver(std::forward<InnerSolver>(inner_solver)) {}
     137           0 :     ALMSolver(Params params, const InnerSolver &inner_solver)
     138           0 :         : params(params), inner_solver(inner_solver) {}
     139             : 
     140             :     Stats operator()(const Problem &problem, rvec y, rvec x);
     141             : 
     142           0 :     std::string get_name() const {
     143           0 :         return "ALMSolver<" + inner_solver.get_name() + ">";
     144           0 :     }
     145             : 
     146             :     /// Abort the computation and return the result so far.
     147             :     /// Can be called from other threads or signal handlers.
     148           0 :     void stop() { inner_solver.stop(); }
     149             : 
     150           0 :     const Params &get_params() const { return params; }
     151             : 
     152             :   private:
     153             :     Params params;
     154             : 
     155             :   public:
     156             :     InnerSolver inner_solver;
     157             : };
     158             : 
     159             : } // namespace pa