wb-solve.h

Go to the documentation of this file.

// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2014-2015 Tsinghua University
// Author: wb.th08@gmail.com (Bin Wang), ozj@tsinghua.edu.cn (Zhijian Ou) 
//
// All h, cpp, cc, and script files (e.g. bat, sh, pl, py) should include the above 
// license declaration. Different coding language may use different comment styles.

#pragma once
#include "wb-win.h"
#include "wb-log.h"
#include "wb-vector.h"
#include <algorithm>

namespace wb
{
    class Solve;
    class Func
    {
        friend class Solve;
        friend class LBFGS;
    protected:
        Solve *m_pSolve; 
        int m_nParamNum; 
    public:
        
        Func(int nParamNum = 0):m_pSolve(NULL) { SetParamNum(nParamNum); };
        void SetParamNum(int n) { m_nParamNum = n; }
        int GetParamNum() const { return m_nParamNum; }
        virtual void SetParam(double *pdParams) = 0;
        virtual double GetValue() = 0;
        virtual void GetGradient(double *pdGradient) = 0;
        static const int cn_exvalue_max_num = 100; 

        virtual int GetExtraValues(int k, double *pdValues) { return 0; }
    };

#define lout_Solve wb::lout<<m_pAlgorithmName<<" "

    class Solve
    {
    protected:
        const char *m_pAlgorithmName; 
    public:
        Func *m_pfunc; 

        double *m_pdRoot; 

        int m_nIterNum; 
        int m_nIterMin; 
        int m_nIterMax; 

        double m_dSpendMinute; 

        double m_dStop; 
        double m_dGain; 

    public:
        Solve(Func *pfunc = NULL, double dtol=1e-5) 
        { 
            m_pAlgorithmName = "[Solve]";
            m_pfunc = pfunc;
            m_pfunc->m_pSolve = this;
            m_pdRoot = NULL;

            m_nIterNum = 0;
            m_nIterMin = 1;
            m_nIterMax = 10000;

            m_dStop = dtol;
            m_dGain = 0;
        }
        
        virtual bool Run(const double *pInitParams = NULL);
        virtual void IterInit() {};

        virtual void ComputeDir(int k, const double *pdParam, const double *pdGradient, double *pdDir);

        virtual double LineSearch(double *pdDir, double dValue, const double *pdParam, const double *pdGradient);
        virtual void Update(double *pdParam, const double *pdDir, double dStep);
        virtual bool StopDecision(int k, double dValue, const double *pdGradient);

    public:
        static double VecProduct(const double *pdVec1, const double *pdVec2, int nSize);
        static double VecNorm(const double *pdVec, int nSize);
        static double VecDist(const double *pdVec1, const double *pdVec2, int nSize);
    };

    /*
     * \class LBFGS
     * \brief LBFGS method
    */
    class LBFGS : public Solve
    {
        typedef struct {
            double *s;
            double *y;
        } sy;
    protected:
        int m_nLimitiedNum; 
        sy *m_pCirQueueBuf; 
        int m_nCirQueueBufTail; 
        double *m_pd_s, *m_pd_y; 

        double *m_pdPrevGradient; 
        double *m_pdPrevParam;    
        double *m_pdAlpha;        

    public:
        LBFGS(Func *pfunc = NULL, double dtol = 1e-5) :Solve(pfunc, dtol)
        {
            m_nLimitiedNum = 8;
            m_pCirQueueBuf = NULL;
            m_nCirQueueBufTail = 0;
            m_pd_s = NULL;
            m_pd_y = NULL;

            m_pdPrevGradient = NULL;
            m_pdPrevParam = NULL;
            m_pdAlpha = NULL;
        }
        ~LBFGS()
        {
            SAFE_DELETE_ARRAY(m_pdPrevParam);
            SAFE_DELETE_ARRAY(m_pdPrevGradient);
            SAFE_DELETE_ARRAY(m_pdAlpha);

            CirQueueBuf_Release();
        }
        virtual void IterInit();
        virtual void ComputeDir(int k, const double *pdParam, const double *pdGradient, double *pdDir);
        void CirQueueBuf_Init();
        void CirQueueBuf_Release();
        void CirQueueBuf_Prev(int i, double *&pd_s, double *&pd_y);
        void CirQueueBuf_In(double *&pd_s, double *&pd_y);
    };
}