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

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: rcurtin
Date: 2012-01-31 01:08:59 -0500 (Tue, 31 Jan 2012)
New Revision: 11309

Added:
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
   mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp
Log:
Basic implementation of LRSDP.  Not yet tested.


Added: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp.hpp	2012-01-31 06:08:59 UTC (rev 11309)
@@ -0,0 +1,50 @@
+/**
+ * @file lrsdp.hpp
+ * @author Ryan Curtin
+ *
+ * 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
+
+#include <mlpack/core.hpp>
+
+namespace mlpack {
+namespace optimization {
+
+class LRSDP
+{
+ public:
+  LRSDP();
+
+  bool Optimize(arma::mat& coordinates)
+//                AugLagrangian<LRSDP> auglag);
+
+//  double Evaluate(const arma::mat& coordinates) const;
+
+//  void Gradient(const arma::mat& coordinates, arma::mat& gradient) const;
+
+  const arma::mat& C() const { return c; }
+  arma::mat& C() { return c; }
+
+  const std::vector<arma::mat> A() const { return a; }
+  arma::mat& A() { return a; }
+
+  const arma::vec& B() const { return b; }
+  arma::vec& B() { return b; }
+
+ private:
+  // Should probably use sparse matrices for some of these.
+  arma::mat c; // For objective function.
+  std::vector<arma::mat> a; // A_i for each constraint.
+  arma::vec b; // b_i for each constraint.
+};
+
+}; // namespace optimization
+}; // namespace mlpack
+
+// Include implementation.
+#include "lrsdp_impl.hpp"
+
+#endif

Added: mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/optimizers/lrsdp/lrsdp_impl.hpp	2012-01-31 06:08:59 UTC (rev 11309)
@@ -0,0 +1,89 @@
+/**
+ * @file lrsdp_impl.hpp
+ * @author Ryan Curtin
+ *
+ * An implementation of Monteiro and Burer's formulation of low-rank
+ * semidefinite programs (LR-SDP).
+ */
+#ifndef __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_IMPL_HPP
+#define __MLPACK_CORE_OPTIMIZERS_LRSDP_LRSDP_IMPL_HPP
+
+// In case it hasn't already been included.
+#include "lrsdp.hpp"
+
+// Augmented Lagrangian solver.
+#include "../aug_lagrangian/aug_lagrangian.hpp"
+
+namespace mlpack {
+namespace optimization {
+
+bool LRSDP::Optimize(arma::mat& coordinates)
+{
+  // Create the Augmented Lagrangian function.
+  AugLagrangian<LRSDP> auglag(*this);
+
+  auglag.Optimize(coordinates);
+}
+
+double LRSDP::Evaluate(const arma::mat& coordinates) const
+{
+  Log::Fatal << "LRSDP::Evaluate() called!  Uh-oh..." << std::endl;
+}
+
+void LRSDP::Gradient(const arma::mat& coordinates, arma::mat& gradient) const
+{
+  Log::Fatal << "LRSDP::Gradient() called!  Uh-oh..." << std::endl;
+}
+
+// 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 = trace(function.A()[i] * rrt) - function.B()[i];
+    objective -= (lambda[i] * constraint);
+    objective += (sigma / 2) * std::pow(constraint, 2.0);
+  }
+
+  return objective;
+}
+
+template<>
+double 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 s = function.C();
+
+  for (size_t i = 0; i < function.B().n_elem; ++i)
+  {
+    double y = lambda[i] - sigma * (trace(function.A()[i] *
+        (coordinates * trans(coordinates))) - function.B()[i]);
+    s -= (y * function.A()[i]);
+  }
+
+  gradient = 2 * s * coordinates;
+}
+
+}; // namespace optimization
+}; // namespace mlpack
+
+#endif