[mlpack-svn] r16388 - mlpack/trunk/src/mlpack/core/optimizers/lrsdp

fastlab-svn at coffeetalk-1.cc.gatech.edu fastlab-svn at coffeetalk-1.cc.gatech.edu
Fri Mar 28 11:38:27 EDT 2014


Author: rcurtin
Date: Fri Mar 28 11:38:26 2014
New Revision: 16388

Log:
Refactor LRSDP into the main class and a separate function (LRSDPFunction).
This is a patch from Abhishek Laddha for #318.


Added:
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp
Removed:
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp
Modified:
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp

Modified: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
==============================================================================
--- mlpack/trunk/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt	(original)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt	Fri Mar 28 11:38:26 2014
@@ -1,6 +1,8 @@
 set(SOURCES
   lrsdp.hpp
   lrsdp.cpp
+  lrsdp_function.hpp
+  lrsdp_function.cpp
 )
 
 set(DIR_SRCS)
@@ -8,4 +10,4 @@
   set(DIR_SRCS ${DIR_SRCS} ${CMAKE_CURRENT_SOURCE_DIR}/${file})
 endforeach()
 
-set(MLPACK_SRCS ${MLPACK_SRCS} ${DIR_SRCS} PARENT_SCOPE)
+set(MLPACK_SRCS ${MLPACK_SRCS} ${DIR_SRCS} PARENT_SCOPE)
\ No newline at end of file

Modified: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp	(original)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp	Fri Mar 28 11:38:26 2014
@@ -13,23 +13,8 @@
 
 LRSDP::LRSDP(const size_t numConstraints,
              const arma::mat& initialPoint) :
-    a(numConstraints),
-    b(numConstraints),
-    aModes(numConstraints),
-    initialPoint(initialPoint),
-    augLagInternal(*this),
-    augLag(augLagInternal)
-{ }
-
-LRSDP::LRSDP(const size_t numConstraints,
-             const arma::mat& initialPoint,
-             AugLagrangian<LRSDP>& augLag) :
-    a(numConstraints),
-    b(numConstraints),
-    aModes(numConstraints),
-    initialPoint(initialPoint),
-    augLagInternal(*this),
-    augLag(augLag)
+    function(numConstraints, initialPoint),
+    augLag(function)
 { }
 
 double LRSDP::Optimize(arma::mat& coordinates)
@@ -37,46 +22,7 @@
   augLag.Sigma() = 20;
   augLag.Optimize(coordinates, 1000);
 
-  return Evaluate(coordinates);
-}
-
-double LRSDP::Evaluate(const arma::mat& coordinates) const
-{
-  return -accu(coordinates * trans(coordinates));
-}
-
-void LRSDP::Gradient(const arma::mat& /*coordinates*/,
-                     arma::mat& /*gradient*/) const
-{
-  Log::Fatal << "LRSDP::Gradient() called!  Not implemented!  Uh-oh..." << std::endl;
-}
-
-double LRSDP::EvaluateConstraint(const size_t index,
-                                 const arma::mat& coordinates) const
-{
-  arma::mat rrt = coordinates * trans(coordinates);
-  if (aModes[index] == 0)
-    return trace(a[index] * rrt) - b[index];
-  else
-  {
-    double value = -b[index];
-    for (size_t i = 0; i < a[index].n_cols; ++i)
-      value += a[index](2, i) * rrt(a[index](0, i), a[index](1, i));
-
-    return value;
-  }
-}
-
-void LRSDP::GradientConstraint(const size_t /* index */,
-                               const arma::mat& /* coordinates */,
-                               arma::mat& /* gradient */) const
-{
-  Log::Fatal << "LRSDP::GradientConstraint() called!  Not implemented!  Uh-oh..." << std::endl;
-}
-
-const arma::mat& LRSDP::GetInitialPoint()
-{
-  return initialPoint;
+  return augLag.Function().Evaluate(coordinates);
 }
 
 // Convert the object to a string.
@@ -84,104 +30,9 @@
 {
   std::ostringstream convert;
   convert << "LRSDP [" << this << "]" << std::endl;
-  convert << "  Matrix Size: " << c.n_rows << "x" << c.n_cols << std::endl;
-  convert << "  Initial point Size : " << initialPoint.n_rows << "x"
-      << initialPoint.n_cols << std::endl;
+  convert << "  Matrix Size: " << function.C().n_rows << "x"
+      << function.C().n_cols << std::endl;
+  convert << "  Initial point Size : " << function.GetInitialPoint().n_rows
+      << "x" << function.GetInitialPoint().n_cols << std::endl;
   return convert.str();
 }
-
-namespace mlpack {
-namespace optimization {
-
-// Custom specializations of the AugmentedLagrangianFunction for the LRSDP case.
-template<>
-double AugLagrangianFunction<LRSDP>::Evaluate(
-    const arma::mat& coordinates) const
-{
-  // We can calculate the entire objective in a smart way.
-  // L(R, y, s) = Tr(C * (R R^T)) -
-  //     sum_{i = 1}^{m} (y_i (Tr(A_i * (R R^T)) - b_i)) +
-  //     (sigma / 2) * sum_{i = 1}^{m} (Tr(A_i * (R R^T)) - b_i)^2
-
-  // Let's start with the objective: Tr(C * (R R^T)).
-  // Simple, possibly slow solution.
-  arma::mat rrt = coordinates * trans(coordinates);
-  double objective = trace(function.C() * rrt);
-
-  // Now each constraint.
-  for (size_t i = 0; i < function.B().n_elem; ++i)
-  {
-    // Take the trace subtracted by the b_i.
-    double constraint = -function.B()[i];
-
-    if (function.AModes()[i] == 0)
-    {
-      constraint += trace(function.A()[i] * rrt);
-    }
-    else
-    {
-      for (size_t j = 0; j < function.A()[i].n_cols; ++j)
-      {
-        constraint += function.A()[i](2, j) *
-            rrt(function.A()[i](0, j), function.A()[i](1, j));
-      }
-    }
-
-    objective -= (lambda[i] * constraint);
-    objective += (sigma / 2) * std::pow(constraint, 2.0);
-  }
-
-  return objective;
-}
-
-template<>
-void AugLagrangianFunction<LRSDP>::Gradient(
-    const arma::mat& coordinates,
-    arma::mat& gradient) const
-{
-  // We can calculate the gradient in a smart way.
-  // L'(R, y, s) = 2 * S' * R
-  //   with
-  // S' = C - sum_{i = 1}^{m} y'_i A_i
-  // y'_i = y_i - sigma * (Trace(A_i * (R R^T)) - b_i)
-  arma::mat rrt = coordinates * trans(coordinates);
-  arma::mat s = function.C();
-
-  for (size_t i = 0; i < function.B().n_elem; ++i)
-  {
-    double constraint = -function.B()[i];
-
-    if (function.AModes()[i] == 0)
-    {
-      constraint += trace(function.A()[i] * rrt);
-    }
-    else
-    {
-      for (size_t j = 0; j < function.A()[i].n_cols; ++j)
-      {
-        constraint += function.A()[i](2, j) *
-            rrt(function.A()[i](0, j), function.A()[i](1, j));
-      }
-    }
-
-    double y = lambda[i] - sigma * constraint;
-
-    if (function.AModes()[i] == 0)
-    {
-      s -= (y * function.A()[i]);
-    }
-    else
-    {
-      // We only need to subtract the entries which could be modified.
-      for (size_t j = 0; j < function.A()[i].n_cols; ++j)
-      {
-        s(function.A()[i](0, j), function.A()[i](1, j)) -= y;
-      }
-    }
-  }
-
-  gradient = 2 * s * coordinates;
-}
-
-}; // namespace optimization
-}; // namespace mlpack

Modified: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp	Fri Mar 28 11:38:26 2014
@@ -11,17 +11,15 @@
 #include <mlpack/core.hpp>
 #include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian.hpp>
 
+#include "lrsdp_function.hpp"
+
 namespace mlpack {
 namespace optimization {
 
 /**
- * An implementation of a low-rank semidefinite program solver, based on
- * Monteiro and Burer's formulation.  The optimizer is the augmented Lagrangian
- * algorithm, and thus this class has Evaluate(), Gradient(),
- * EvaluateConstraint(), and GradientConstraint() functions for that purpose.
- * However, you should not call the Gradient() or GradientConstraint() functions
- * by hand, because they are only implemented as part of the augmented
- * Lagrangian optimizer.
+ * LRSDP is the implementation of Monteiro and Burer's formulation of low-rank
+ * semidefinite programs (LR-SDP).  This solver uses the augmented Lagrangian
+ * optimizer to solve low-rank semidefinite programs.
  */
 class LRSDP
 {
@@ -49,7 +47,7 @@
    */
   LRSDP(const size_t numConstraints,
         const arma::mat& initialPoint,
-        AugLagrangian<LRSDP>& augLagrangian);
+        AugLagrangian<LRSDPFunction>& augLagrangian);
 
   /**
    * Optimize the LRSDP and return the final objective value.  The given
@@ -59,87 +57,45 @@
    */
   double Optimize(arma::mat& coordinates);
 
-  /**
-   * Evaluate the objective function of the LRSDP (no constraints) at the given
-   * coordinates.  This is used by AugLagrangian<LRSDP>.
-   */
-  double Evaluate(const arma::mat& coordinates) const;
-
-  /**
-   * Evaluate the gradient of the LRSDP (no constraints) at the given
-   * coordinates.  This is used by AugLagrangian<LRSDP>.
-   */
-  void Gradient(const arma::mat& coordinates, arma::mat& gradient) const;
-
-  /**
-   * Evaluate a particular constraint of the LRSDP at the given coordinates.
-   */
-  double EvaluateConstraint(const size_t index,
-                            const arma::mat& coordinates) const;
-
-  /**
-   * Evaluate the gradient of a particular constraint of the LRSDP at the given
-   * coordinates.
-   */
-  void GradientConstraint(const size_t index,
-                          const arma::mat& coordinates,
-                          arma::mat& gradient) const;
-
-  //! Get the number of constraints in the LRSDP.
-  size_t NumConstraints() const { return b.n_elem; }
-
-  //! Get the initial point of the LRSDP.
-  const arma::mat& GetInitialPoint();
-
   //! Return the objective function matrix (C).
-  const arma::mat& C() const { return c; }
+  const arma::mat& C() const { return function.C(); }
   //! Modify the objective function matrix (C).
-  arma::mat& C() { return c; }
+  arma::mat& C() { return function.C(); }
 
   //! Return the vector of A matrices (which correspond to the constraints).
-  const std::vector<arma::mat>& A() const { return a; }
+  const std::vector<arma::mat>& A() const { return function.A(); }
   //! Modify the veector of A matrices (which correspond to the constraints).
-  std::vector<arma::mat>& A() { return a; }
+  std::vector<arma::mat>& A() { return function.A(); }
 
   //! Return the vector of modes for the A matrices.
-  const arma::uvec& AModes() const { return aModes; }
+  const arma::uvec& AModes() const { return function.AModes(); }
   //! Modify the vector of modes for the A matrices.
-  arma::uvec& AModes() { return aModes; }
+  arma::uvec& AModes() { return function.AModes(); }
 
   //! Return the vector of B values.
-  const arma::vec& B() const { return b; }
+  const arma::vec& B() const { return function.B(); }
   //! Modify the vector of B values.
-  arma::vec& B() { return b; }
+  arma::vec& B() { return function.B(); }
+
+  //! Return the function to be optimized.
+  const LRSDPFunction& Function() const { return function; }
+  //! Modify the function to be optimized.
+  LRSDPFunction& Function() { return function; }
 
   //! Return the augmented Lagrangian object.
-  const AugLagrangian<LRSDP>& AugLag() const { return augLag; }
+  const AugLagrangian<LRSDPFunction>& AugLag() const { return augLag; }
   //! Modify the augmented Lagrangian object.
-  AugLagrangian<LRSDP>& AugLag() { return augLag; }
+  AugLagrangian<LRSDPFunction>& AugLag() { return augLag; }
 
-  // convert the obkect into a string
+  //! Return a string representation of the object.
   std::string ToString() const;
 
  private:
-  // Should probably use sparse matrices for some of these.
-
-  //! For objective function.
-  arma::mat c;
-  //! A_i for each constraint.
-  std::vector<arma::mat> a;
-  //! b_i for each constraint.
-  arma::vec b;
-
-  //! 1 if entries in matrix, 0 for normal.
-  arma::uvec aModes;
-
-  //! Initial point.
-  arma::mat initialPoint;
-
-  //! Internal AugLagrangian object, if one was not passed at construction time.
-  AugLagrangian<LRSDP> augLagInternal;
+  //! Function to optimize, which the AugLagrangian object holds.
+  LRSDPFunction function;
 
   //! The AugLagrangian object which will be used for optimization.
-  AugLagrangian<LRSDP>& augLag;
+  AugLagrangian<LRSDPFunction> augLag;
 };
 
 }; // namespace optimization

Added: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
==============================================================================
--- (empty file)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp	Fri Mar 28 11:38:26 2014
@@ -0,0 +1,154 @@
+/**
+ * @file lrsdp_function.cpp
+ * @author Ryan Curtin
+ * @author Abhishek Laddha
+ *
+ * Implementation of the LRSDPFunction class, and also template specializations
+ * for faster execution with the AugLagrangian optimizer.
+ */
+#include "lrsdp_function.hpp"
+
+using namespace mlpack;
+using namespace mlpack::optimization;
+
+LRSDPFunction::LRSDPFunction(const size_t numConstraints,
+                             const arma::mat& initialPoint):
+    a(numConstraints),
+    b(numConstraints),
+    initialPoint(initialPoint),
+    aModes(numConstraints)
+{ }
+
+double LRSDPFunction::Evaluate(const arma::mat& coordinates) const
+{
+  return -accu(coordinates * trans(coordinates));
+}
+
+void LRSDPFunction::Gradient(const arma::mat& /* coordinates */,
+                     arma::mat& /* gradient */) const
+{
+  Log::Fatal << "LRSDP::Gradient() not implemented for arbitrary optimizers!"
+      << std::endl;
+}
+
+double LRSDPFunction::EvaluateConstraint(const size_t index,
+                                 const arma::mat& coordinates) const
+{
+  arma::mat rrt = coordinates * trans(coordinates);
+  if (aModes[index] == 0)
+    return trace(a[index] * rrt) - b[index];
+  else
+  {
+    double value = -b[index];
+    for (size_t i = 0; i < a[index].n_cols; ++i)
+      value += a[index](2, i) * rrt(a[index](0, i), a[index](1, i));
+
+    return value;
+  }
+}
+
+void LRSDPFunction::GradientConstraint(const size_t /* index */,
+                               const arma::mat& /* coordinates */,
+                               arma::mat& /* gradient */) const
+{
+  Log::Fatal << "LRSDP::GradientConstraint() not implemented for arbitrary "
+      << "optimizers!" << std::endl;
+}
+
+namespace mlpack {
+namespace optimization {
+
+// Template specializations for function and gradient evaluation.
+template<>
+double AugLagrangianFunction<LRSDPFunction>::Evaluate(
+    const arma::mat& coordinates) const
+{
+  // We can calculate the entire objective in a smart way.
+  // L(R, y, s) = Tr(C * (R R^T)) -
+  //     sum_{i = 1}^{m} (y_i (Tr(A_i * (R R^T)) - b_i)) +
+  //     (sigma / 2) * sum_{i = 1}^{m} (Tr(A_i * (R R^T)) - b_i)^2
+
+  // Let's start with the objective: Tr(C * (R R^T)).
+  // Simple, possibly slow solution.
+  arma::mat rrt = coordinates * trans(coordinates);
+  double objective = trace(function.C() * rrt);
+
+  // Now each constraint.
+  for (size_t i = 0; i < function.B().n_elem; ++i)
+  {
+    // Take the trace subtracted by the b_i.
+    double constraint = -function.B()[i];
+
+    if (function.AModes()[i] == 0)
+    {
+      constraint += trace(function.A()[i] * rrt);
+    }
+    else
+    {
+      for (size_t j = 0; j < function.A()[i].n_cols; ++j)
+      {
+        constraint += function.A()[i](2, j) *
+            rrt(function.A()[i](0, j), function.A()[i](1, j));
+      }
+    }
+
+    objective -= (lambda[i] * constraint);
+    objective += (sigma / 2) * std::pow(constraint, 2.0);
+  }
+
+  return objective;
+}
+
+
+template<>
+void AugLagrangianFunction<LRSDPFunction>::Gradient(
+    const arma::mat& coordinates,
+    arma::mat& gradient) const
+{
+  // We can calculate the gradient in a smart way.
+  // L'(R, y, s) = 2 * S' * R
+  //   with
+  // S' = C - sum_{i = 1}^{m} y'_i A_i
+  // y'_i = y_i - sigma * (Trace(A_i * (R R^T)) - b_i)
+  arma::mat rrt = coordinates * trans(coordinates);
+  arma::mat s = function.C();
+
+  for (size_t i = 0; i < function.B().n_elem; ++i)
+  {
+    double constraint = -function.B()[i];
+
+    if (function.AModes()[i] == 0)
+    {
+      constraint += trace(function.A()[i] * rrt);
+    }
+    else
+    {
+      for (size_t j = 0; j < function.A()[i].n_cols; ++j)
+      {
+        constraint += function.A()[i](2, j) *
+            rrt(function.A()[i](0, j), function.A()[i](1, j));
+      }
+    }
+
+    double y = lambda[i] - sigma * constraint;
+
+    if (function.AModes()[i] == 0)
+    {
+      s -= (y * function.A()[i]);
+    }
+    else
+    {
+      // We only need to subtract the entries which could be modified.
+      for (size_t j = 0; j < function.A()[i].n_cols; ++j)
+      {
+        s(function.A()[i](0, j), function.A()[i](1, j)) -= y;
+      }
+    }
+  }
+
+  gradient = 2 * s * coordinates;
+}
+
+}; // namespace optimization
+}; // namespace mlpack
+

Added: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp
==============================================================================
--- (empty file)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp	Fri Mar 28 11:38:26 2014
@@ -0,0 +1,99 @@
+/**
+ * @file lrsdp_function.hpp
+ * @author Ryan Curtin
+ * @author Abhishek Laddha
+ *
+ * A class that represents the objective function which LRSDP optimizes.
+ */
+#ifndef __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_FUNCTION_HPP
+#define __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_FUNCTION_HPP
+
+#include <mlpack/core.hpp>
+#include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian.hpp>
+
+namespace mlpack {
+namespace optimization {
+
+/**
+ * The objective function that LRSDP is trying to optimize.
+ */
+class LRSDPFunction
+{
+ public:
+  /**
+   * Construct the LRSDPFunction with the given initial point and number of
+   * constraints.  Set the A, B, and C matrices for each constraint using the
+   * A(), B(), and C() functions.
+   */
+  LRSDPFunction(const size_t numConstraints,
+                const arma::mat& initialPoint);
+
+  /**
+   * Evaluate the objective function of the LRSDP (no constraints) at the given
+   * coordinates.
+   */
+  double Evaluate(const arma::mat& coordinates) const;
+
+  /**
+   * Evaluate the gradient of the LRSDP (no constraints) at the given
+   * coordinates.
+   */
+  void Gradient(const arma::mat& coordinates, arma::mat& gradient) const;
+
+  /**
+   * Evaluate a particular constraint of the LRSDP at the given coordinates.
+   */
+  double EvaluateConstraint(const size_t index,
+                            const arma::mat& coordinates) const;
+  /**
+   * Evaluate the gradient of a particular constraint of the LRSDP at the given
+   * coordinates.
+   */
+  void GradientConstraint(const size_t index,
+                          const arma::mat& coordinates,
+                          arma::mat& gradient) const;
+
+  //! Get the number of constraints in the LRSDP.
+  size_t NumConstraints() const { return b.n_elem; }
+
+  //! Get the initial point of the LRSDP.
+  const arma::mat& GetInitialPoint() const {return initialPoint; }
+
+  //! Return the objective function matrix (C).
+  const arma::mat& C() const { return c; }
+  //! Modify the objective function matrix (C).
+  arma::mat& C() { return c; }
+
+  //! Return the vector of A matrices (which correspond to the constraints).
+  const std::vector<arma::mat>& A() const { return a; }
+  //! Modify the veector of A matrices (which correspond to the constraints).
+  std::vector<arma::mat>& A() { return a; }
+
+  //! Return the vector of modes for the A matrices.
+  const arma::uvec& AModes() const { return aModes; }
+  //! Modify the vector of modes for the A matrices.
+  arma::uvec& AModes() { return aModes; }
+
+  //! Return the vector of B values.
+  const arma::vec& B() const { return b; }
+  //! Modify the vector of B values.
+  arma::vec& B() { return b; }
+
+ private:
+  //! Objective function matrix c.
+  arma::mat c;
+  //! A_i for each constraint.
+  std::vector<arma::mat> a;
+  //! b_i for each constraint.
+  arma::vec b;
+
+  //! Initial point.
+  arma::mat initialPoint;
+  //! 1 if entries in matrix, 0 for normal.
+  arma::uvec aModes;
+};
+
+};
+};
+
+#endif // __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_FUNCTION_HPP



More information about the mlpack-svn mailing list