SOCP.hh

/*
This file is part of the BIAS library (Basic ImageAlgorithmS).

Copyright (C) 2003-2009    (see file CONTACT for details)
  Multimediale Systeme der Informationsverarbeitung
  Institut fuer Informatik
  Christian-Albrechts-Universitaet Kiel


BIAS is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

BIAS is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License
along with BIAS; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef __SOCP_hh__
#define __SOCP_hh__

#include <bias_config.h>
#include <Base/Debug/Debug.hh>
#include <Base/Math/Vector.hh>
#include <Base/Math/Matrix.hh>
#include <vector>

namespace BIAS
{

  /** @class SOCP
      @brief Wrapper for Second-Order Cone Programming implementation,
             by Miguel S. Lobo et al. from Stanford university provided
             at http://www.stanford.edu/~boyd/old_software/socp/
             See User's Guide [1] and [2] for details about the algorithm
             and socp/README.txt for information about the authors.

      Solves Second-Order Cone Programming (SOCP) problems defined by:

      min f^T * x s.t. ||A_i * x + b_i|| <= c_i * x + d_i for i = 1, ..., L

      [1] M. S. Lobo, L. Vandenberghe, S. Boyd: SOCP Software for
          Second-Order Cone Programming - User's Guide, April 1997.
      [2] M. S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret: Second-Order Cone
          Programming: Interior-Point Methods and Engineering Applications,
          Linear Algebra and Applications, 1997.

      @see socp/socp.h
      @author esquivel 05/2012
  */
  class BIASMathAlgo_EXPORT SOCP : public BIAS::Debug
  {
  
  public:

    /** @brief Create SOCP solver with default parameters. */
    SOCP();

    /** @brief Release memory used. */
    ~SOCP();

    /** @brief Set maximal number of iterations performed by SOCP algorithm. */
    void SetMaxIterations(int iter) { MaxIters_ = iter; }

    /** @brief Get maximal number of iterations performed by SOCP algorithm. */
    int GetMaxIterations() const { return MaxIters_; }

    /** @brief Set parameter nu that controls the rate of convergence.
               Recommended range is 5 to 50.
        @see   See SOCP user guide [1] for details about this parameter.
    */
    void SetNu(double nu) { Nu_ = nu; }

    /** @brief Get parameter nu that controls the rate of convergence. */
    double GetNu() const { return Nu_; }

    /** @brief Set target value used in convergence criterion only when
               relative tolerance given is < 0.
        @see   See SOCP user guide [1] for details about this parameter.
    */
    void SetTargetValue(double target) { TargetValue_ = target; }

    /** @brief Get target value used in convergence criterion. */
    double GetTargetValue() const { return TargetValue_; }

    /** @brief Set absolute tolerance used to determine convergence.
               See SOCP user guide [1] for details about this parameter.
    */
    void SetAbsoluteTolerance(double tol) { AbsTolerance_ = tol; }

    /** @brief Get absolute tolerance used to determine convergence. */
    double GetAbsoluteTolerance() const { return AbsTolerance_; }

    /** @brief Set relative tolerance used to determine convergence.
        @see   See SOCP user guide [1] for details about this parameter.
    */
    void SetRelativeTolerance(double tol) { RelTolerance_ = tol; }

    /** @brief Get relative tolerance used to determine convergence. */
    double GetRelativeTolerance() const { return RelTolerance_; }
  
    /** @brief Solve Second-Order Cone Programming instance with L constraints.

        Compute vector x minimizing f * x subject to the constraints
        ||A_i * x + b_i|| <= c_i * x + d_i for i = 1, ..., L starting with
        the given solution x.

        L is the number of constraints, m is the number of variables.
        Vector N = (N_1, ..., N_L) specifies the problem size of the
        i-th constraint, i.e. A_i is a N_i x m matrix, b_i is a vector
        of size N_i, c_i is a vector of size m and d_i is a scalar.
        Both f and x are vectors of size m.

        The vectors z_1, ..., z_L and scalars w_1, ..., w_L describe the
        solution to the dual problem. Each vector z_i is of size N_i.
        Note that a feasable dual solution must be given as a start point
        in addition to the primal solution x.

        @return Returns < 0 in case of errors, 0 otherwise.
    */
    int Compute(int L, int m, const std::vector<int> &N,
                const Vector<double> &f,
                const std::vector< Matrix<double> > &A,
                const std::vector< Vector<double> > &b,
                const std::vector< Vector<double> > &c,
                const std::vector<double> &d,
                Vector<double> &x, std::vector< Vector<double> > &z,
                std::vector<double> &w);

    /** @brief Solve single-constraint Second-Order Cone Programming instance.

        Compute vector x minimizing f * x subject to the constraint
        ||A * x + b|| <= c * x + d starting with the given solution x.

        m is the number of variables, n specifies the problem size of the
        constraint, i.e. A is a n x m matrix, b is a vector of size n,
        c is a vector of size m and d is a scalar.
        Both f and x are vectors of size m.
        Vector z of size n and scalar w describe the solution to the dual
        problem. A feasable dual solution must be given as a start point in
        addition to the primal solution x.

        @return Returns < 0 in case of errors, 0 otherwise.
    */
    int Compute(int m, int n, const Vector<double> &f,
                const Matrix<double> &A, const Vector<double> &b,
                const Vector<double> &c, double d,
                Vector<double> &x, Vector<double> &z, double &w);

  private:
    
    int MaxIters_;
    double AbsTolerance_, RelTolerance_;
    double TargetValue_;
    double Nu_;
    
  };
  
}

#endif // __SOCP_hh__