[mlpack-git] master, mlpack-1.0.x: Refactor LRSDP into the main class and a separate function (LRSDPFunction). This is a patch from Abhishek Laddha for #318. (cc8bfb9)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:45:40 EST 2015
Repository : https://github.com/mlpack/mlpack
On branches: master,mlpack-1.0.x
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit cc8bfb95ddc906f3e4525a2010d8cc499e796f79
Author: Ryan Curtin <ryan at ratml.org>
Date: Fri Mar 28 15:38:26 2014 +0000
Refactor LRSDP into the main class and a separate function (LRSDPFunction).
This is a patch from Abhishek Laddha for #318.
>---------------------------------------------------------------
cc8bfb95ddc906f3e4525a2010d8cc499e796f79
src/mlpack/core/optimizers/lrsdp/CMakeLists.txt | 2 +
src/mlpack/core/optimizers/lrsdp/lrsdp.cpp | 163 +--------------------
src/mlpack/core/optimizers/lrsdp/lrsdp.hpp | 94 ++++--------
.../lrsdp/{lrsdp_impl.hpp => lrsdp_function.cpp} | 73 +++++++--
.../core/optimizers/lrsdp/lrsdp_function.hpp | 99 +++++++++++++
5 files changed, 191 insertions(+), 240 deletions(-)
diff --git a/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt b/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
index f981ed9..7f21124 100644
--- a/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
+++ b/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
@@ -1,6 +1,8 @@
set(SOURCES
lrsdp.hpp
lrsdp.cpp
+ lrsdp_function.hpp
+ lrsdp_function.cpp
)
set(DIR_SRCS)
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp b/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
index b945caa..b593889 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
+++ b/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
@@ -13,23 +13,8 @@ using namespace std;
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 @@ double LRSDP::Optimize(arma::mat& coordinates)
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::string LRSDP::ToString() const
{
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
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp b/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
index bba3a09..9c4e8f5 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
+++ b/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
@@ -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 @@ class LRSDP
*/
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 @@ class LRSDP
*/
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
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp b/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
similarity index 54%
rename from src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp
rename to src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
index af910f2..9eac7e8 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp
+++ b/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
@@ -1,24 +1,67 @@
/**
- * @file lrsdp_impl.hpp
+ * @file lrsdp_function.cpp
* @author Ryan Curtin
+ * @author Abhishek Laddha
*
- * An implementation of Monteiro and Burer's formulation of low-rank
- * semidefinite programs (LR-SDP).
+ * Implementation of the LRSDPFunction class, and also template specializations
+ * for faster execution with the AugLagrangian optimizer.
*/
-#ifndef __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_IMPL_HPP
-#define __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_IMPL_HPP
+#include "lrsdp_function.hpp"
-// In case it hasn't already been included.
-#include "lrsdp.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 {
-
-// Custom specializations of the AugmentedLagrangianFunction for the LRSDP case.
+// Template specializations for function and gradient evaluation.
template<>
-double AugLagrangianFunction<LRSDP>::Evaluate(const arma::mat& coordinates)
- const
+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)) -
@@ -56,9 +99,11 @@ double AugLagrangianFunction<LRSDP>::Evaluate(const arma::mat& coordinates)
return objective;
}
+
template<>
-void AugLagrangianFunction<LRSDP>::Gradient(const arma::mat& coordinates,
- arma::mat& gradient) const
+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
@@ -107,5 +152,3 @@ void AugLagrangianFunction<LRSDP>::Gradient(const arma::mat& coordinates,
}; // namespace optimization
}; // namespace mlpack
-#endif
-
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp b/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp
new file mode 100644
index 0000000..73427fd
--- /dev/null
+++ b/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp
@@ -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-git
mailing list