[mlpack-git] master: Port LR-SDP to use the new SDP problem object (8004059)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Mon Feb 2 15:16:36 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/bb6e5c56aab07e6449d86021246b52a9e323f3a0...bd6cb33f8d8270b02a84e81e38727679bb6c319a
>---------------------------------------------------------------
commit 800405915ecc04f0d7d52ef165da4074e5c90146
Author: Stephen Tu <stephent at berkeley.edu>
Date: Wed Jan 21 17:34:04 2015 -0800
Port LR-SDP to use the new SDP problem object
>---------------------------------------------------------------
800405915ecc04f0d7d52ef165da4074e5c90146
src/mlpack/core/optimizers/CMakeLists.txt | 1 -
src/mlpack/core/optimizers/lrsdp/CMakeLists.txt | 13 --
src/mlpack/core/optimizers/sdp/CMakeLists.txt | 4 +
.../core/optimizers/{lrsdp => sdp}/lrsdp.hpp | 34 +++--
.../optimizers/{lrsdp => sdp}/lrsdp_function.hpp | 118 +++++++--------
.../lrsdp_function_impl.hpp} | 159 +++++++++++++--------
.../{lrsdp/lrsdp.cpp => sdp/lrsdp_impl.hpp} | 26 ++--
src/mlpack/core/optimizers/sdp/sdp.hpp | 19 ++-
src/mlpack/core/optimizers/sdp/sdp_impl.hpp | 16 ++-
.../matrix_completion/matrix_completion.cpp | 2 +-
.../matrix_completion/matrix_completion.hpp | 9 +-
src/mlpack/methods/mvu/mvu.cpp | 4 +-
src/mlpack/tests/lrsdp_test.cpp | 24 ++--
src/mlpack/tests/to_string_test.cpp | 4 +-
14 files changed, 240 insertions(+), 193 deletions(-)
diff --git a/src/mlpack/core/optimizers/CMakeLists.txt b/src/mlpack/core/optimizers/CMakeLists.txt
index 3579a2a..25a0c8a 100644
--- a/src/mlpack/core/optimizers/CMakeLists.txt
+++ b/src/mlpack/core/optimizers/CMakeLists.txt
@@ -1,7 +1,6 @@
set(DIRS
aug_lagrangian
lbfgs
- lrsdp
sa
sdp
sgd
diff --git a/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt b/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
deleted file mode 100644
index 7f21124..0000000
--- a/src/mlpack/core/optimizers/lrsdp/CMakeLists.txt
+++ /dev/null
@@ -1,13 +0,0 @@
-set(SOURCES
- lrsdp.hpp
- lrsdp.cpp
- lrsdp_function.hpp
- lrsdp_function.cpp
-)
-
-set(DIR_SRCS)
-foreach(file ${SOURCES})
- set(DIR_SRCS ${DIR_SRCS} ${CMAKE_CURRENT_SOURCE_DIR}/${file})
-endforeach()
-
-set(MLPACK_SRCS ${MLPACK_SRCS} ${DIR_SRCS} PARENT_SCOPE)
\ No newline at end of file
diff --git a/src/mlpack/core/optimizers/sdp/CMakeLists.txt b/src/mlpack/core/optimizers/sdp/CMakeLists.txt
index 266d514..ecb803f 100644
--- a/src/mlpack/core/optimizers/sdp/CMakeLists.txt
+++ b/src/mlpack/core/optimizers/sdp/CMakeLists.txt
@@ -1,4 +1,8 @@
set(SOURCES
+ lrsdp.hpp
+ lrsdp_impl.hpp
+ lrsdp_function.hpp
+ lrsdp_function_impl.hpp
primal_dual.hpp
primal_dual_impl.hpp
sdp.hpp
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp b/src/mlpack/core/optimizers/sdp/lrsdp.hpp
similarity index 76%
rename from src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
rename to src/mlpack/core/optimizers/sdp/lrsdp.hpp
index 5f97fc8..52f2f78 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
+++ b/src/mlpack/core/optimizers/sdp/lrsdp.hpp
@@ -5,8 +5,8 @@
* An implementation of Monteiro and Burer's formulation of low-rank
* semidefinite programs (LR-SDP).
*/
-#ifndef __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_HPP
-#define __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_HPP
+#ifndef __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_HPP
+#define __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_HPP
#include <mlpack/core.hpp>
#include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian.hpp>
@@ -21,6 +21,7 @@ namespace optimization {
* semidefinite programs (LR-SDP). This solver uses the augmented Lagrangian
* optimizer to solve low-rank semidefinite programs.
*/
+template <typename SDPType>
class LRSDP
{
public:
@@ -44,17 +45,11 @@ class LRSDP
*/
double Optimize(arma::mat& coordinates);
- //! Return the sparse objective function matrix (sparseC).
- const arma::sp_mat& SparseC() const { return function.SparseC(); }
+ //! Return the objective function matrix (c).
+ const typename SDPType::objective_matrix_type& C() const { return function.C(); }
- //! Modify the sparse objective function matrix (sparseC).
- arma::sp_mat& SparseC() { return function.SparseC(); }
-
- //! Return the dense objective function matrix (denseC).
- const arma::mat& DenseC() const { return function.DenseC(); }
-
- //! Modify the dense objective function matrix (denseC).
- arma::mat& DenseC() { return function.DenseC(); }
+ //! Modify the objective function matrix (c).
+ typename SDPType::objective_matrix_type& C() { return function.C(); }
//! Return the vector of sparse A matrices (which correspond to the sparse
// constraints).
@@ -83,27 +78,30 @@ class LRSDP
arma::vec& DenseB() { return function.DenseB(); }
//! Return the function to be optimized.
- const LRSDPFunction& Function() const { return function; }
+ const LRSDPFunction<SDPType>& Function() const { return function; }
//! Modify the function to be optimized.
- LRSDPFunction& Function() { return function; }
+ LRSDPFunction<SDPType>& Function() { return function; }
//! Return the augmented Lagrangian object.
- const AugLagrangian<LRSDPFunction>& AugLag() const { return augLag; }
+ const AugLagrangian<LRSDPFunction<SDPType>>& AugLag() const { return augLag; }
//! Modify the augmented Lagrangian object.
- AugLagrangian<LRSDPFunction>& AugLag() { return augLag; }
+ AugLagrangian<LRSDPFunction<SDPType>>& AugLag() { return augLag; }
//! Return a string representation of the object.
std::string ToString() const;
private:
//! Function to optimize, which the AugLagrangian object holds.
- LRSDPFunction function;
+ LRSDPFunction<SDPType> function;
//! The AugLagrangian object which will be used for optimization.
- AugLagrangian<LRSDPFunction> augLag;
+ AugLagrangian<LRSDPFunction<SDPType>> augLag;
};
}; // namespace optimization
}; // namespace mlpack
+// Include implementation
+#include "lrsdp_impl.hpp"
+
#endif
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp b/src/mlpack/core/optimizers/sdp/lrsdp_function.hpp
similarity index 55%
rename from src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp
rename to src/mlpack/core/optimizers/sdp/lrsdp_function.hpp
index 7eeaf14..1f86410 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp_function.hpp
+++ b/src/mlpack/core/optimizers/sdp/lrsdp_function.hpp
@@ -5,11 +5,12 @@
*
* 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
+#ifndef __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_FUNCTION_HPP
+#define __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_FUNCTION_HPP
#include <mlpack/core.hpp>
#include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian.hpp>
+#include <mlpack/core/optimizers/sdp/sdp.hpp>
namespace mlpack {
namespace optimization {
@@ -17,15 +18,30 @@ namespace optimization {
/**
* The objective function that LRSDP is trying to optimize.
*/
+template <typename SDPType>
class LRSDPFunction
{
public:
+
+ /**
+ * Construct the LRSDPFunction from the given SDP.
+ *
+ * @param sdp
+ * @param initialPoint
+ */
+ LRSDPFunction(const SDPType& sdp,
+ const arma::mat& initialPoint);
+
/**
* Construct the LRSDPFunction with the given initial point and number of
* constraints. Note n_cols of the initialPoint specifies the rank.
*
* Set the A_x, B_x, and C_x matrices for each constraint using the A_x(),
* B_x(), and C_x() functions, for x in {sparse, dense}.
+ *
+ * @param numSparseConstraints
+ * @param numDenseConstraints
+ * @param initialPoint
*/
LRSDPFunction(const size_t numSparseConstraints,
const size_t numDenseConstraints,
@@ -57,110 +73,86 @@ class LRSDPFunction
arma::mat& gradient) const;
//! Get the number of sparse constraints in the LRSDP.
- size_t NumSparseConstraints() const { return sparseB.n_elem; }
+ size_t NumSparseConstraints() const { return sdp.NumSparseConstraints(); }
//! Get the number of dense constraints in the LRSDP.
- size_t NumDenseConstraints() const { return denseB.n_elem; }
+ size_t NumDenseConstraints() const { return sdp.NumDenseConstraints(); }
//! Get the total number of constraints in the LRSDP.
- size_t NumConstraints() const {
- return NumSparseConstraints() + NumDenseConstraints();
- }
+ size_t NumConstraints() const { return sdp.NumConstraints(); }
//! Get the initial point of the LRSDP.
const arma::mat& GetInitialPoint() const { return initialPoint; }
- size_t n() const { return initialPoint.n_rows; }
-
- //! Return the sparse objective function matrix (sparseC).
- const arma::sp_mat& SparseC() const { return sparseC; }
-
- //! Modify the sparse objective function matrix (sparseC).
- arma::sp_mat& SparseC() {
- hasModifiedSparseObjective = true;
- return sparseC;
- }
+ size_t N() const { return sdp.N(); }
- //! Return the dense objective function matrix (denseC).
- const arma::mat& DenseC() const { return denseC; }
+ //! Return the objective function matrix (C).
+ const typename SDPType::objective_matrix_type& C() const { return sdp.C(); }
- //! Modify the dense objective function matrix (denseC).
- arma::mat& DenseC() {
- hasModifiedDenseObjective = true;
- return denseC;
- }
+ //! Modify the objective function matrix (C).
+ typename SDPType::objective_matrix_type& C() { return sdp.C(); }
//! Return the vector of sparse A matrices (which correspond to the sparse
// constraints).
- const std::vector<arma::sp_mat>& SparseA() const { return sparseA; }
+ const std::vector<arma::sp_mat>& SparseA() const { return sdp.SparseA(); }
//! Modify the veector of sparse A matrices (which correspond to the sparse
// constraints).
- std::vector<arma::sp_mat>& SparseA() { return sparseA; }
+ std::vector<arma::sp_mat>& SparseA() { return sdp.SparseA(); }
//! Return the vector of dense A matrices (which correspond to the dense
// constraints).
- const std::vector<arma::mat>& DenseA() const { return denseA; }
+ const std::vector<arma::mat>& DenseA() const { return sdp.DenseA(); }
//! Modify the veector of dense A matrices (which correspond to the dense
// constraints).
- std::vector<arma::mat>& DenseA() { return denseA; }
+ std::vector<arma::mat>& DenseA() { return sdp.DenseA(); }
//! Return the vector of sparse B values.
- const arma::vec& SparseB() const { return sparseB; }
+ const arma::vec& SparseB() const { return sdp.SparseB(); }
//! Modify the vector of sparse B values.
- arma::vec& SparseB() { return sparseB; }
+ arma::vec& SparseB() { return sdp.SparseB(); }
//! Return the vector of dense B values.
- const arma::vec& DenseB() const { return denseB; }
+ const arma::vec& DenseB() const { return sdp.DenseB(); }
//! Modify the vector of dense B values.
- arma::vec& DenseB() { return denseB; }
-
- bool hasSparseObjective() const { return hasModifiedSparseObjective; }
-
- bool hasDenseObjective() const { return hasModifiedDenseObjective; }
+ arma::vec& DenseB() { return sdp.DenseB(); }
//! Return string representation of object.
std::string ToString() const;
private:
- //! Sparse objective function matrix c.
- arma::sp_mat sparseC;
-
- //! Dense objective function matrix c.
- arma::mat denseC;
- //! If false, sparseC is zero
- bool hasModifiedSparseObjective;
-
- //! If false, denseC is zero
- bool hasModifiedDenseObjective;
-
- //! A_i for each sparse constraint.
- std::vector<arma::sp_mat> sparseA;
- //! b_i for each sparse constraint.
- arma::vec sparseB;
-
- //! A_i for each dense constraint.
- std::vector<arma::mat> denseA;
- //! b_i for each dense constraint.
- arma::vec denseB;
+ //! SDP object representing the problem
+ SDPType sdp;
//! Initial point.
arma::mat initialPoint;
};
// Declare specializations in lrsdp_function.cpp.
-template<>
-double AugLagrangianFunction<LRSDPFunction>::Evaluate(
+template <>
+inline double AugLagrangianFunction<LRSDPFunction<SDP<arma::sp_mat>>>::Evaluate(
const arma::mat& coordinates) const;
-template<>
-void AugLagrangianFunction<LRSDPFunction>::Gradient(
+template <>
+inline double AugLagrangianFunction<LRSDPFunction<SDP<arma::mat>>>::Evaluate(
+ const arma::mat& coordinates) const;
+
+template <>
+inline void AugLagrangianFunction<LRSDPFunction<SDP<arma::sp_mat>>>::Gradient(
const arma::mat& coordinates,
arma::mat& gradient) const;
-};
-};
+template <>
+inline void AugLagrangianFunction<LRSDPFunction<SDP<arma::mat>>>::Gradient(
+ const arma::mat& coordinates,
+ arma::mat& gradient) const;
+
+}; // namespace optimization
+}; // namespace mlpack
+
+// Include implementation
+#include "lrsdp_function_impl.hpp"
-#endif // __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_FUNCTION_HPP
+#endif // __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_FUNCTION_HPP
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp b/src/mlpack/core/optimizers/sdp/lrsdp_function_impl.hpp
similarity index 52%
rename from src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
rename to src/mlpack/core/optimizers/sdp/lrsdp_function_impl.hpp
index 9bbdd22..06252ac 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp_function.cpp
+++ b/src/mlpack/core/optimizers/sdp/lrsdp_function_impl.hpp
@@ -6,84 +6,88 @@
* Implementation of the LRSDPFunction class, and also template specializations
* for faster execution with the AugLagrangian optimizer.
*/
+#ifndef __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_FUNCTION_IMPL_HPP
+#define __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_FUNCTION_IMPL_HPP
+
#include "lrsdp_function.hpp"
-using namespace mlpack;
-using namespace mlpack::optimization;
-using namespace std;
-
-LRSDPFunction::LRSDPFunction(const size_t numSparseConstraints,
- const size_t numDenseConstraints,
- const arma::mat& initialPoint):
- sparseC(initialPoint.n_rows, initialPoint.n_rows),
- denseC(initialPoint.n_rows, initialPoint.n_rows),
- hasModifiedSparseObjective(false),
- hasModifiedDenseObjective(false),
- sparseA(numSparseConstraints),
- sparseB(numSparseConstraints),
- denseA(numDenseConstraints),
- denseB(numDenseConstraints),
+namespace mlpack {
+namespace optimization {
+
+template <typename SDPType>
+LRSDPFunction<SDPType>::LRSDPFunction(const SDPType& sdp,
+ const arma::mat& initialPoint):
+ sdp(sdp),
+ initialPoint(initialPoint)
+{
+ if (initialPoint.n_rows < initialPoint.n_cols)
+ Log::Warn << "LRSDPFunction::LRSDPFunction(): solution matrix will have "
+ << "more columns than rows. It may be more efficient to find the "
+ << "transposed solution." << std::endl;
+}
+
+template <typename SDPType>
+LRSDPFunction<SDPType>::LRSDPFunction(const size_t numSparseConstraints,
+ const size_t numDenseConstraints,
+ const arma::mat& initialPoint):
+ sdp(initialPoint.n_rows, numSparseConstraints, numDenseConstraints),
initialPoint(initialPoint)
{
- denseC.zeros();
if (initialPoint.n_rows < initialPoint.n_cols)
Log::Warn << "LRSDPFunction::LRSDPFunction(): solution matrix will have "
<< "more columns than rows. It may be more efficient to find the "
- << "transposed solution." << endl;
+ << "transposed solution." << std::endl;
}
-double LRSDPFunction::Evaluate(const arma::mat& coordinates) const
+template <typename SDPType>
+double LRSDPFunction<SDPType>::Evaluate(const arma::mat& coordinates) const
{
const arma::mat rrt = coordinates * trans(coordinates);
- double objective = 0.;
- if (hasSparseObjective())
- objective += trace(SparseC() * rrt);
- if (hasDenseObjective())
- objective += trace(DenseC() * rrt);
- return objective;
+ return accu(C() % rrt);
}
-void LRSDPFunction::Gradient(const arma::mat& /* coordinates */,
- arma::mat& /* gradient */) const
+template <typename SDPType>
+void LRSDPFunction<SDPType>::Gradient(const arma::mat& /* coordinates */,
+ arma::mat& /* gradient */) const
{
- Log::Fatal << "LRSDP::Gradient() not implemented for arbitrary optimizers!"
+ Log::Fatal << "LRSDPFunction::Gradient() not implemented for arbitrary optimizers!"
<< std::endl;
}
-double LRSDPFunction::EvaluateConstraint(const size_t index,
- const arma::mat& coordinates) const
+template <typename SDPType>
+double LRSDPFunction<SDPType>::EvaluateConstraint(const size_t index,
+ const arma::mat& coordinates) const
{
const arma::mat rrt = coordinates * trans(coordinates);
if (index < NumSparseConstraints())
- return trace(sparseA[index] * rrt) - sparseB[index];
+ return trace(SparseA()[index] * rrt) - SparseB()[index];
const size_t index1 = index - NumSparseConstraints();
- return trace(denseA[index1] * rrt) - denseB[index1];
+ return trace(DenseA()[index1] * rrt) - DenseB()[index1];
}
-void LRSDPFunction::GradientConstraint(const size_t /* index */,
- const arma::mat& /* coordinates */,
- arma::mat& /* gradient */) const
+template <typename SDPType>
+void LRSDPFunction<SDPType>::GradientConstraint(const size_t /* index */,
+ const arma::mat& /* coordinates */,
+ arma::mat& /* gradient */) const
{
- Log::Fatal << "LRSDP::GradientConstraint() not implemented for arbitrary "
+ Log::Fatal << "LRSDPFunction::GradientConstraint() not implemented for arbitrary "
<< "optimizers!" << std::endl;
}
// Return a string representation of the object.
-std::string LRSDPFunction::ToString() const
+template <typename SDPType>
+std::string LRSDPFunction<SDPType>::ToString() const
{
std::ostringstream convert;
convert << "LRSDPFunction [" << this << "]" << std::endl;
convert << " Number of constraints: " << NumConstraints() << std::endl;
- convert << " Problem size: n=" << initialPoint.n_rows << ", r="
+ convert << " Problem size: n=" << GetInitialPoint().n_rows << ", r="
<< initialPoint.n_cols << std::endl;
- convert << " Sparse Constraint b_i values: " << sparseB.t();
- convert << " Dense Constraint b_i values: " << denseB.t();
+ convert << " Sparse Constraint b_i values: " << SparseB().t();
+ convert << " Dense Constraint b_i values: " << DenseB().t();
return convert.str();
}
-namespace mlpack {
-namespace optimization {
-
//! Utility function for calculating part of the objective when AugLagrangian is
//! used with an LRSDPFunction.
template <typename MatrixType>
@@ -125,10 +129,12 @@ UpdateGradient(arma::mat& s,
}
}
-// Template specializations for function and gradient evaluation.
-template<>
-double AugLagrangianFunction<LRSDPFunction>::Evaluate(
- const arma::mat& coordinates) const
+template <typename SDPType>
+static inline double
+EvaluateImpl(const LRSDPFunction<SDPType>& function,
+ const arma::mat& coordinates,
+ const arma::vec& lambda,
+ const double sigma)
{
// We can calculate the entire objective in a smart way.
// L(R, y, s) = Tr(C * (R R^T)) -
@@ -144,11 +150,7 @@ double AugLagrangianFunction<LRSDPFunction>::Evaluate(
//
// Similarly for the constraints, taking A*R first should be more efficient
const arma::mat rrt = coordinates * trans(coordinates);
- double objective = 0.;
- if (function.hasSparseObjective())
- objective += trace(function.SparseC() * rrt);
- if (function.hasDenseObjective())
- objective += trace(function.DenseC() * rrt);
+ double objective = trace(function.C() * rrt);
// Now each constraint.
UpdateObjective(objective, rrt, function.SparseA(), function.SparseB(),
@@ -159,11 +161,13 @@ double AugLagrangianFunction<LRSDPFunction>::Evaluate(
return objective;
}
-
-template<>
-void AugLagrangianFunction<LRSDPFunction>::Gradient(
- const arma::mat& coordinates,
- arma::mat& gradient) const
+template <typename SDPType>
+static inline void
+GradientImpl(const LRSDPFunction<SDPType>& function,
+ const arma::mat& coordinates,
+ const arma::vec& lambda,
+ const double sigma,
+ arma::mat& gradient)
{
// We can calculate the gradient in a smart way.
// L'(R, y, s) = 2 * S' * R
@@ -171,13 +175,7 @@ void AugLagrangianFunction<LRSDPFunction>::Gradient(
// S' = C - sum_{i = 1}^{m} y'_i A_i
// y'_i = y_i - sigma * (Trace(A_i * (R R^T)) - b_i)
const arma::mat rrt = coordinates * trans(coordinates);
- arma::mat s(function.n(), function.n());
- s.zeros();
-
- if (function.hasSparseObjective())
- s += function.SparseC();
- if (function.hasDenseObjective())
- s += function.DenseC();
+ arma::mat s(function.C());
UpdateGradient(
s, rrt, function.SparseA(), function.SparseB(),
@@ -189,5 +187,40 @@ void AugLagrangianFunction<LRSDPFunction>::Gradient(
gradient = 2 * s * coordinates;
}
+// Template specializations for function and gradient evaluation.
+// Note that C++ does not allow partial specialization of class members,
+// so we have to go about this in a somewhat round-about way.
+template <>
+inline double AugLagrangianFunction<LRSDPFunction<SDP<arma::sp_mat>>>::Evaluate(
+ const arma::mat& coordinates) const
+{
+ return EvaluateImpl(function, coordinates, lambda, sigma);
+}
+
+template <>
+inline double AugLagrangianFunction<LRSDPFunction<SDP<arma::mat>>>::Evaluate(
+ const arma::mat& coordinates) const
+{
+ return EvaluateImpl(function, coordinates, lambda, sigma);
+}
+
+template <>
+inline void AugLagrangianFunction<LRSDPFunction<SDP<arma::sp_mat>>>::Gradient(
+ const arma::mat& coordinates,
+ arma::mat& gradient) const
+{
+ GradientImpl(function, coordinates, lambda, sigma, gradient);
+}
+
+template <>
+inline void AugLagrangianFunction<LRSDPFunction<SDP<arma::mat>>>::Gradient(
+ const arma::mat& coordinates,
+ arma::mat& gradient) const
+{
+ GradientImpl(function, coordinates, lambda, sigma, gradient);
+}
+
}; // namespace optimization
}; // namespace mlpack
+
+#endif
diff --git a/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp b/src/mlpack/core/optimizers/sdp/lrsdp_impl.hpp
similarity index 52%
rename from src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
rename to src/mlpack/core/optimizers/sdp/lrsdp_impl.hpp
index 636224e..f3b1c35 100644
--- a/src/mlpack/core/optimizers/lrsdp/lrsdp.cpp
+++ b/src/mlpack/core/optimizers/sdp/lrsdp_impl.hpp
@@ -5,20 +5,24 @@
* An implementation of Monteiro and Burer's formulation of low-rank
* semidefinite programs (LR-SDP).
*/
+#ifndef __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_IMPL_HPP
+#define __MLPACK_CORE_OPTIMIZERS_SDP_LRSDP_IMPL_HPP
+
#include "lrsdp.hpp"
-using namespace mlpack;
-using namespace mlpack::optimization;
-using namespace std;
+namespace mlpack {
+namespace optimization {
-LRSDP::LRSDP(const size_t numSparseConstraints,
- const size_t numDenseConstraints,
- const arma::mat& initialPoint) :
+template <typename SDPType>
+LRSDP<SDPType>::LRSDP(const size_t numSparseConstraints,
+ const size_t numDenseConstraints,
+ const arma::mat& initialPoint) :
function(numSparseConstraints, numDenseConstraints, initialPoint),
augLag(function)
{ }
-double LRSDP::Optimize(arma::mat& coordinates)
+template <typename SDPType>
+double LRSDP<SDPType>::Optimize(arma::mat& coordinates)
{
augLag.Sigma() = 20;
augLag.Optimize(coordinates, 1000);
@@ -27,10 +31,16 @@ double LRSDP::Optimize(arma::mat& coordinates)
}
// Convert the object to a string.
-std::string LRSDP::ToString() const
+template <typename SDPType>
+std::string LRSDP<SDPType>::ToString() const
{
std::ostringstream convert;
convert << "LRSDP [" << this << "]" << std::endl;
convert << " Optimizer: " << util::Indent(augLag.ToString(), 1) << std::endl;
return convert.str();
}
+
+}; // namespace optimization
+}; // namespace mlpack
+
+#endif
diff --git a/src/mlpack/core/optimizers/sdp/sdp.hpp b/src/mlpack/core/optimizers/sdp/sdp.hpp
index c0de4f3..c276ca6 100644
--- a/src/mlpack/core/optimizers/sdp/sdp.hpp
+++ b/src/mlpack/core/optimizers/sdp/sdp.hpp
@@ -26,13 +26,25 @@ class SDP
typedef ObjectiveMatrixType objective_matrix_type;
+ /**
+ * Initialize this SDP to an empty state.
+ */
+ SDP();
+
+ /**
+ * Initialize this SDP to one which structurally has size n.
+ *
+ * @param n
+ * @param numSparseConstraints
+ * @param numDenseConstraints
+ */
SDP(const size_t n,
const size_t numSparseConstraints,
const size_t numDenseConstraints);
- size_t N() const { return n; }
+ size_t N() const { return c.n_rows; }
- size_t N2bar() const { return n * (n + 1) / 2; }
+ size_t N2bar() const { return N() * (N() + 1) / 2; }
size_t NumSparseConstraints() const { return sparseB.n_elem; }
@@ -81,9 +93,6 @@ class SDP
private:
- //! Dimension of the objective variable.
- size_t n;
-
//! Objective function matrix c.
ObjectiveMatrixType c;
diff --git a/src/mlpack/core/optimizers/sdp/sdp_impl.hpp b/src/mlpack/core/optimizers/sdp/sdp_impl.hpp
index 1da53f4..bd40f94 100644
--- a/src/mlpack/core/optimizers/sdp/sdp_impl.hpp
+++ b/src/mlpack/core/optimizers/sdp/sdp_impl.hpp
@@ -12,16 +12,30 @@ namespace mlpack {
namespace optimization {
template <typename ObjectiveMatrixType>
+SDP<ObjectiveMatrixType>::SDP() :
+ c(),
+ sparseA(),
+ sparseB(),
+ denseA(),
+ denseB()
+{
+
+}
+
+template <typename ObjectiveMatrixType>
SDP<ObjectiveMatrixType>::SDP(const size_t n,
const size_t numSparseConstraints,
const size_t numDenseConstraints) :
- n(n),
c(n, n),
sparseA(numSparseConstraints),
sparseB(numSparseConstraints),
denseA(numDenseConstraints),
denseB(numDenseConstraints)
{
+ for (size_t i = 0; i < numSparseConstraints; i++)
+ sparseA[i].zeros(n, n);
+ for (size_t i = 0; i < numDenseConstraints; i++)
+ denseA[i].zeros(n, n);
}
template <typename ObjectiveMatrixType>
diff --git a/src/mlpack/methods/matrix_completion/matrix_completion.cpp b/src/mlpack/methods/matrix_completion/matrix_completion.cpp
index 15224b5..4e19fe7 100644
--- a/src/mlpack/methods/matrix_completion/matrix_completion.cpp
+++ b/src/mlpack/methods/matrix_completion/matrix_completion.cpp
@@ -68,7 +68,7 @@ void MatrixCompletion::CheckValues()
void MatrixCompletion::InitSDP()
{
- sdp.SparseC().eye(m + n, m + n);
+ sdp.C().eye(m + n, m + n);
sdp.SparseB() = 2. * values;
const size_t p = indices.n_cols;
for (size_t i = 0; i < p; i++)
diff --git a/src/mlpack/methods/matrix_completion/matrix_completion.hpp b/src/mlpack/methods/matrix_completion/matrix_completion.hpp
index 718f46c..263b349 100644
--- a/src/mlpack/methods/matrix_completion/matrix_completion.hpp
+++ b/src/mlpack/methods/matrix_completion/matrix_completion.hpp
@@ -8,7 +8,8 @@
#ifndef __MLPACK_METHODS_MATRIX_COMPLETION_MATRIX_COMPLETION_HPP
#define __MLPACK_METHODS_MATRIX_COMPLETION_MATRIX_COMPLETION_HPP
-#include <mlpack/core/optimizers/lrsdp/lrsdp.hpp>
+#include <mlpack/core/optimizers/sdp/sdp.hpp>
+#include <mlpack/core/optimizers/sdp/lrsdp.hpp>
namespace mlpack {
namespace matrix_completion {
@@ -106,9 +107,9 @@ class MatrixCompletion
void Recover(arma::mat& recovered);
//! Return the underlying SDP.
- const optimization::LRSDP& Sdp() const { return sdp; }
+ const optimization::LRSDP<optimization::SDP<arma::sp_mat>>& Sdp() const { return sdp; }
//! Modify the underlying SDP.
- optimization::LRSDP& Sdp() { return sdp; }
+ optimization::LRSDP<optimization::SDP<arma::sp_mat>>& Sdp() { return sdp; }
private:
//! Number of rows in original matrix.
@@ -121,7 +122,7 @@ class MatrixCompletion
arma::mat values;
//! The underlying SDP to be solved.
- optimization::LRSDP sdp;
+ optimization::LRSDP<optimization::SDP<arma::sp_mat>> sdp;
//! Validate the input matrices.
void CheckValues();
diff --git a/src/mlpack/methods/mvu/mvu.cpp b/src/mlpack/methods/mvu/mvu.cpp
index 908f42c..4026c24 100644
--- a/src/mlpack/methods/mvu/mvu.cpp
+++ b/src/mlpack/methods/mvu/mvu.cpp
@@ -9,7 +9,7 @@
#include "mvu.hpp"
//#include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian.hpp>
-#include <mlpack/core/optimizers/lrsdp/lrsdp.hpp>
+#include <mlpack/core/optimizers/sdp/lrsdp.hpp>
#include <mlpack/methods/neighbor_search/neighbor_search.hpp>
@@ -33,7 +33,7 @@ void MVU::Unfold(const size_t newDim,
outputData.randu(data.n_cols, newDim);
// The number of constraints is the number of nearest neighbors plus one.
- LRSDP mvuSolver(numNeighbors * data.n_cols + 1, outputData);
+ LRSDP<arma::sp_mat> mvuSolver(numNeighbors * data.n_cols + 1, outputData);
// Set up the objective. Because we are maximizing the trace of (R R^T),
// we'll instead state it as min(-I_n * (R R^T)), meaning C() is -I_n.
diff --git a/src/mlpack/tests/lrsdp_test.cpp b/src/mlpack/tests/lrsdp_test.cpp
index 4913b14..6c448af 100644
--- a/src/mlpack/tests/lrsdp_test.cpp
+++ b/src/mlpack/tests/lrsdp_test.cpp
@@ -2,10 +2,10 @@
* @file lrsdp_test.cpp
* @author Ryan Curtin
*
- * Tests for LR-SDP (core/optimizers/lrsdp/).
+ * Tests for LR-SDP (core/optimizers/sdp/).
*/
#include <mlpack/core.hpp>
-#include <mlpack/core/optimizers/lrsdp/lrsdp.hpp>
+#include <mlpack/core/optimizers/sdp/lrsdp.hpp>
#include <boost/test/unit_test.hpp>
#include "old_boost_test_definitions.hpp"
@@ -52,14 +52,14 @@ void CreateLovaszThetaInitialPoint(const arma::mat& edges,
* initial point coordinates should be given also.
*/
void SetupLovaszTheta(const arma::mat& edges,
- LRSDP& lovasz)
+ LRSDP<SDP<arma::mat>>& lovasz)
{
// Get the number of vertices in the problem.
const size_t vertices = max(max(edges)) + 1;
// C = -(e e^T) = -ones().
- lovasz.DenseC().ones(vertices, vertices);
- lovasz.DenseC() *= -1;
+ lovasz.C().ones(vertices, vertices);
+ lovasz.C() *= -1;
// b_0 = 1; else = 0.
lovasz.SparseB().zeros(edges.n_cols + 1);
@@ -97,7 +97,7 @@ BOOST_AUTO_TEST_CASE(Johnson844LovaszThetaSDP)
CreateLovaszThetaInitialPoint(edges, coordinates);
- LRSDP lovasz(edges.n_cols + 1, 0, coordinates);
+ LRSDP<SDP<arma::mat>> lovasz(edges.n_cols + 1, 0, coordinates);
SetupLovaszTheta(edges, lovasz);
@@ -163,9 +163,9 @@ BOOST_AUTO_TEST_CASE(ErdosRenyiRandomGraphMaxCutSDP)
coordinates(i, i % coordinates.n_cols) = 1.;
}
- LRSDP maxcut(laplacian.n_rows, 0, coordinates);
- maxcut.SparseC() = laplacian;
- maxcut.SparseC() *= -1.; // need to minimize the negative
+ LRSDP<SDP<arma::sp_mat>> maxcut(laplacian.n_rows, 0, coordinates);
+ maxcut.C() = laplacian;
+ maxcut.C() *= -1.; // need to minimize the negative
maxcut.SparseB().ones(laplacian.n_rows);
for (size_t i = 0; i < laplacian.n_rows; ++i)
{
@@ -238,8 +238,8 @@ BOOST_AUTO_TEST_CASE(GaussianMatrixSensingSDP)
arma::mat coordinates;
coordinates.eye(m + n, ceil(r));
- LRSDP sensing(0, p, coordinates);
- sensing.SparseC().eye(m + n, m + n);
+ LRSDP<SDP<arma::sp_mat>> sensing(0, p, coordinates);
+ sensing.C().eye(m + n, m + n);
sensing.DenseB() = 2. * b;
const auto block_rows = arma::span(0, m - 1);
@@ -287,7 +287,7 @@ BOOST_AUTO_TEST_CASE(Keller4LovaszThetaSDP)
CreateLovaszThetaInitialPoint(edges, coordinates);
- LRSDP lovasz(edges.n_cols, coordinates);
+ LRSDP<SDP<arma::mat>> lovasz(edges.n_cols, coordinates);
SetupLovaszTheta(edges, lovasz);
diff --git a/src/mlpack/tests/to_string_test.cpp b/src/mlpack/tests/to_string_test.cpp
index bdb6f6e..bc7d436 100644
--- a/src/mlpack/tests/to_string_test.cpp
+++ b/src/mlpack/tests/to_string_test.cpp
@@ -21,7 +21,7 @@
#include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian.hpp>
#include <mlpack/core/optimizers/lbfgs/lbfgs.hpp>
-#include <mlpack/core/optimizers/lrsdp/lrsdp.hpp>
+#include <mlpack/core/optimizers/sdp/lrsdp.hpp>
#include <mlpack/core/optimizers/sgd/sgd.hpp>
#include <mlpack/methods/nca/nca_softmax_error_function.hpp>
#include <mlpack/core/optimizers/aug_lagrangian/aug_lagrangian_test_functions.hpp>
@@ -255,7 +255,7 @@ BOOST_AUTO_TEST_CASE(LRSDPString)
arma::mat c(40, 40);
c.randn();
const size_t b=3;
- mlpack::optimization::LRSDP d(b,b,c);
+ mlpack::optimization::LRSDP<mlpack::optimization::SDP<arma::sp_mat>> d(b,b,c);
Log::Debug << d;
testOstream << d;
std::string s = d.ToString();
More information about the mlpack-git
mailing list