padmm.h

Go to the documentation of this file.

#ifndef SOPT_PROXIMAL_ADMM_H
#define SOPT_PROXIMAL_ADMM_H
 
#include "sopt/config.h"
#include <functional>
#include <limits>
#include <tuple> // for std::tuple<>
#include <utility> // for std::move<>
#include "sopt/exception.h"
#include "sopt/linear_transform.h"
#include "sopt/logging.h"
#include "sopt/types.h"
 
namespace sopt::algorithm {
 
template <typename SCALAR>
class ProximalADMM {
 public:
  using value_type = SCALAR;
  using Scalar = value_type;
  using Real = typename real_type<Scalar>::type;
  using t_Vector = Vector<Scalar>;
  using t_LinearTransform = LinearTransform<t_Vector>;
  using t_IsConverged = std::function<bool (const t_Vector &, const t_Vector &)>;
  using t_Proximal = ProximalFunction<Scalar>;
 
  struct Diagnostic {
    t_uint niters;
    bool good;
    t_Vector residual;
 
    Diagnostic(t_uint niters = 0u, bool good = false)
        : niters(niters), good(good), residual(t_Vector::Zero(0)) {}
    Diagnostic(t_uint niters, bool good, t_Vector &&residual)
        : niters(niters), good(good), residual(std::move(residual)) {}
  };
  struct DiagnosticAndResult : public Diagnostic {
    t_Vector x;
  };
 
  template <typename DERIVED>
  ProximalADMM(t_Proximal const &f_proximal, t_Proximal const &g_proximal,
               Eigen::MatrixBase<DERIVED> const &target)
      : itermax_(std::numeric_limits<t_uint>::max()),
        regulariser_strength_(1e-8),
        lagrange_update_scale_(0.9),
        is_converged_(),
        Phi_(linear_transform_identity<Scalar>()),
        f_proximal_(f_proximal),
        g_proximal_(g_proximal),
        target_(target) {}
  virtual ~ProximalADMM() {}
 
// Macro helps define properties that can be initialized as in
// auto sdmm  = ProximalADMM<float>().prop0(value).prop1(value);
#define SOPT_MACRO(NAME, TYPE)                   \
  TYPE const &NAME() const { return NAME##_; }   \
  ProximalADMM<SCALAR> &NAME(TYPE const &(NAME)) { \
    NAME##_ = NAME;                              \
    return *this;                                \
  }                                              \
                                                 \
 protected:                                      \
  TYPE NAME##_;                                  \
                                                 \
 public:
 
  SOPT_MACRO(itermax, t_uint);
  SOPT_MACRO(regulariser_strength, Real);
  SOPT_MACRO(lagrange_update_scale, Real);
  SOPT_MACRO(is_converged, t_IsConverged);
  SOPT_MACRO(Phi, t_LinearTransform);
  SOPT_MACRO(f_proximal, t_Proximal);
  SOPT_MACRO(g_proximal, t_Proximal);
#undef SOPT_MACRO
  void f_proximal(t_Vector &out, Real regulariser_strength, t_Vector const &x) const {
    f_proximal()(out, regulariser_strength, x);
  }
  void g_proximal(t_Vector &out, Real regulariser_strength, t_Vector const &x) const {
    g_proximal()(out, regulariser_strength, x);
  }
 
  ProximalADMM<Scalar> &is_converged(std::function<bool(t_Vector const &x)> const &func) {
    return is_converged([func](t_Vector const &x, t_Vector const &) { return func(x); });
  }
 
  t_Vector const &target() const { return target_; }
  template <typename DERIVED>
  ProximalADMM<Scalar> &target(Eigen::MatrixBase<DERIVED> const &target) {
    target_ = target;
    return *this;
  }
 
  bool is_converged(t_Vector const &x, t_Vector const &residual) const {
    return static_cast<bool>(is_converged()) and is_converged()(x, residual);
  }
 
  Diagnostic operator()(t_Vector &out) const { return operator()(out, initial_guess()); }
  Diagnostic operator()(t_Vector &out, std::tuple<t_Vector, t_Vector> const &guess) const {
    return operator()(out, std::get<0>(guess), std::get<1>(guess));
  }
  Diagnostic operator()(t_Vector &out,
                        std::tuple<t_Vector const &, t_Vector const &> const &guess) const {
    return operator()(out, std::get<0>(guess), std::get<1>(guess));
  }
  DiagnosticAndResult operator()(std::tuple<t_Vector, t_Vector> const &guess) const {
    return operator()(std::tie(std::get<0>(guess), std::get<1>(guess)));
  }
  DiagnosticAndResult operator()(
      std::tuple<t_Vector const &, t_Vector const &> const &guess) const {
    DiagnosticAndResult result;
    static_cast<Diagnostic &>(result) = operator()(result.x, guess);
    return result;
  }
  DiagnosticAndResult operator()() const {
    DiagnosticAndResult result;
    static_cast<Diagnostic &>(result) = operator()(result.x, initial_guess());
    return result;
  }
  DiagnosticAndResult operator()(DiagnosticAndResult const &warmstart) const {
    DiagnosticAndResult result = warmstart;
    static_cast<Diagnostic &>(result) = operator()(result.x, warmstart.x, warmstart.residual);
    return result;
  }
  template <typename... ARGS>
  typename std::enable_if<sizeof...(ARGS) >= 1, ProximalADMM &>::type Phi(ARGS &&... args) {
    Phi_ = linear_transform(std::forward<ARGS>(args)...);
    return *this;
  }
 
  std::tuple<t_Vector, t_Vector> initial_guess() const {
    return ProximalADMM<SCALAR>::initial_guess(target(), Phi());
  }
 
  static std::tuple<t_Vector, t_Vector> initial_guess(t_Vector const &target,
                                                      t_LinearTransform const &phi) {
    std::tuple<t_Vector, t_Vector> guess;
    std::get<0>(guess) = static_cast<t_Vector>(phi.adjoint() * target) / phi.sq_norm();
    std::get<1>(guess) = phi * std::get<0>(guess) - target;
    return guess;
  }
 
 protected:
  void iteration_step(t_Vector &out, t_Vector &residual, t_Vector &lambda, t_Vector &z) const;
 
  void sanity_check(t_Vector const &x_guess, t_Vector const &res_guess) const {
    if ((Phi().adjoint() * target()).size() != x_guess.size())
      SOPT_THROW("target, adjoint measurement operator and input vector have inconsistent sizes");
    if (target().size() != res_guess.size())
      SOPT_THROW("target and residual vector have inconsistent sizes");
    if ((Phi() * x_guess).size() != target().size())
      SOPT_THROW("target, measurement operator and input vector have inconsistent sizes");
    if (not static_cast<bool>(is_converged()))
      SOPT_WARN("No convergence function was provided: algorithm will run for {} steps", itermax());
  }
 
  Diagnostic operator()(t_Vector &out, t_Vector const &guess, t_Vector const &res) const;
 
  t_Vector target_;
};
 
template <typename SCALAR>
void ProximalADMM<SCALAR>::iteration_step(t_Vector &out, t_Vector &residual, t_Vector &lambda,
                                          t_Vector &z) const {
  g_proximal(z, regulariser_strength(), -lambda - residual);
  f_proximal(out, regulariser_strength() / Phi().sq_norm(),
             out - static_cast<t_Vector>(Phi().adjoint() * (residual + lambda + z)) / Phi().sq_norm());
  residual = static_cast<t_Vector>(Phi() * out - target());
  lambda += lagrange_update_scale() * (residual + z);
}
 
template <typename SCALAR>
typename ProximalADMM<SCALAR>::Diagnostic ProximalADMM<SCALAR>::operator()(
    t_Vector &out, t_Vector const &x_guess, t_Vector const &res_guess) const {
  SOPT_HIGH_LOG("Performing Proximal ADMM");
  sanity_check(x_guess, res_guess);
 
  t_Vector lambda = t_Vector::Zero(target().size());
  t_Vector z = t_Vector::Zero(target().size());
  t_Vector residual = res_guess;
  out = x_guess;
 
  t_uint niters(0);
  bool converged = false;
  for (; (not converged) && (niters < itermax()); ++niters) {
    SOPT_LOW_LOG("    - [PADMM] Iteration {}/{}", niters, itermax());
    iteration_step(out, residual, lambda, z);
    SOPT_LOW_LOG("      - [PADMM] Sum of residuals: {}", residual.array().abs().sum());
    converged = is_converged(out, residual);
  }
 
  if (converged) {
    SOPT_MEDIUM_LOG("    - [PADMM] converged in {} of {} iterations", niters, itermax());
  } else if (static_cast<bool>(is_converged())) {
    // not meaningful if not convergence function
    SOPT_ERROR("    - [PADMM] did not converge within {} iterations", itermax());
  }
  return {niters, converged, std::move(residual)};
}
} // namespace sopt::algorithm
#endif