OBOE  0.1
Method.h
Go to the documentation of this file.
00001 // Copyright (c) 2004-2007 University of Geneva, HEC, Logilab
00002 //
00003 // OBOE is published under the Common Public License.
00004 //
00005 // Authors :
00006 // Nidhi Sawhney <nsawhney@yahoo.com>
00007 // The OBOE team
00008 //
00009 
00010 #ifndef METHOD_H
00011 #define METHOD_H
00012 
00017 #include "AccpmVector.h"
00018 #include "AccpmGenMatrix.h"
00019 #include "Solution.h"
00020 #include "symd.h"
00021 #include "Parameters.h"
00022 
00023 namespace Accpm 
00024 {
00025   class Manager;
00026   class LocSet;
00032   class Method {
00033   
00034   protected:
00035     int _numIter;
00036     bool _computeLB;
00037     double _ratioCutVsDim;
00038     double _startLB;
00039 
00040   public:
00041     Method() : _numIter(0), _computeLB(true), _ratioCutVsDim(1), _startLB(1e-2) {};
00042     virtual int run(Manager &manager) = 0;
00043     virtual ~Method() {};
00044   };
00045 
00046   class DualMethod : public Method {
00047   
00048   private:
00049 
00050     const Parameters *_param;
00051     
00052     int performNewtonSteps(Manager &manager, LocSet &locSet);
00053     double computeLowerBound(Manager &manager, const LocSet &locSet);
00054 
00055     int computeInfeasibilities(const Manager &manager, const LocSet &locSet, 
00056                    const AccpmVector &y, const AccpmVector &z, double zs,
00057                    AccpmVector &s, double &s0,
00058                    AccpmVector &rs, double &rs0);
00059     void updateRsS(const Manager &manager, const LocSet &locSet,
00060            const AccpmVector &ATy, const AccpmVector &z,
00061            AccpmVector &rs, AccpmVector &s);
00062   
00063     int newtonDualDir(Manager &manager, LocSet &locSet, 
00064               const AccpmVector &ry, const AccpmVector &rz,
00065               const AccpmVector &rs, double rs0, 
00066               const AccpmVector &wsV, double ws0, 
00067               double f2, const AccpmVector *df2,
00068               const AccpmGenMatrix *d2f2, 
00069               const AccpmVector &diagQ,
00070               const NewtonSolution &sol,
00071               NewtonSolution &step, bool eqConstraint = false) const;
00072     
00073     int newtonDualDir1(Manager &manager, LocSet &locSet, 
00074                const AccpmVector &ry, 
00075                const AccpmVector &rs, double rs0,
00076                const AccpmVector &rz, double rzs, double rss,
00077                const AccpmVector &diagQ,
00078                const AccpmVector *df2,
00079                const NewtonSolution &sol,
00080                NewtonSolution &step,
00081                bool eqConstraint) const;
00082 
00083     int newtonDualDir2(Manager &manager, LocSet &locSet, 
00084                const AccpmVector &ry, 
00085                const AccpmVector &rs, double rs0,
00086                const AccpmVector &wsV,
00087                const AccpmVector &rz, double rzs, double rss,
00088                const AccpmVector &diagQ,
00089                const AccpmVector *df2,
00090                const NewtonSolution &sol,
00091                NewtonSolution &step) const;
00096     int newtonDualDirForLargeP(Manager &manager, LocSet &locSet,
00097                    const SymmetricMatrix &H, const AccpmGenMatrix &H21, 
00098                    const AccpmVector &H13, const AccpmVector &ELET, double wsByssSq, 
00099                    double w0Bys0Sq, const AccpmVector &rhs1, const AccpmVector &rhs2, double rhs3, 
00100                    NewtonSolution &step) const;
00101 
00102     int computeRy(const Manager &manager, const LocSet &locSet, const AccpmVector &y,
00103           const AccpmVector &wsV, const AccpmVector *df2, double ss, AccpmVector &ry) const;
00104     int computeRz(const LocSet &locSet, const AccpmVector &wsV, double ws0, AccpmVector &rz) const;
00105    
00106     int prodAQAT(const AccpmGenMatrix &A, const AccpmVector &d, SymmetricMatrix &result) const;
00107     
00108     void computeDiagQ(const Manager &manager, const AccpmVector &y, const AccpmGenMatrix *d2f2,
00109               double ss, AccpmVector &diagQ) const;
00110     
00111     void computeSCBarrier(const Manager &manager, const AccpmVector &y, AccpmVector &result) const;
00112    
00113     void computeH(const SymmetricMatrix &H11, const AccpmGenMatrix &H12, const AccpmVector &H13,
00114           const SymmetricMatrix &H22, const AccpmVector &H23, double H33,
00115           AccpmGenMatrix &H) const;
00116 
00117     void computeFullMatrix(const SymmetricMatrix &H11, AccpmGenMatrix &H) const;
00118 
00119     void updateATQA(Manager &manager, const LocSet &locSet,
00120             const AccpmVector &y, const AccpmVector &diagQ) const;
00121    
00122     double computeStepSize(const Manager &manager, const LocSet &locSet, 
00123                const NewtonSolution &sol, const NewtonSolution &step, 
00124                double maxRs, double uNorm) const;
00125     void computeStepSize(const Manager &manager, const NewtonSolution &sol, const NewtonSolution &step, 
00126             AccpmVector &S, AccpmVector &DS, AccpmVector &W) const;
00127     
00128     double lineSearchDualPot(const Manager &manager, const LocSet &locSet, 
00129                  const NewtonSolution &sol, const NewtonSolution &step, 
00130                  const AccpmVector &S, const AccpmVector &DS, const AccpmVector &W) const;
00131 
00132     double maxStep(const AccpmVector &z, const AccpmVector &dz) const;
00133   
00134     double maxBall(const Manager &manager, const AccpmVector &y, 
00135            const AccpmVector &dy, double alpha) const; //REf: MATLAB: AMaxBall
00136    
00137     double computeTerminationCriterion(const Manager &manager, const LocSet &locSet, 
00138                        const AccpmVector &ry, const AccpmVector &rz,
00139                        const AccpmVector &wsV, 
00140                        double ws0, double maxRs, double uNorm, double nnorm, 
00141                        const AccpmVector *df2, const NewtonSolution &sol, 
00142                        const NewtonSolution &step) const;
00143   
00144     void solveSCSystem(const AccpmVector &a, const AccpmVector &b, const AccpmVector &rhs,
00145             AccpmVector &x) const;
00149     int computeSCInverse(const AccpmVector &A, const AccpmVector &b, AccpmGenMatrix &Inv) const;
00150     
00151     void computeELET(const Manager &manager, const AccpmGenMatrix &E, const AccpmVector &sigma, 
00152              AccpmVector &ELET) const;
00153    
00154     void handleEqualityConstraints(Manager &manager, LocSet &locSet, 
00155                    const AccpmVector &wsV, double ws0, 
00156                    double f2, const AccpmVector *df2,
00157                    const AccpmGenMatrix *d2f2, 
00158                    const AccpmVector &diagQ,
00159                    const NewtonSolution &sol,
00160                    NewtonSolution &step) const;
00161     
00162     int linSolve(Manager &manager, const LocSet &locSet,
00163                  const AccpmGenMatrix &A, RealMatrix &X,
00164                  const RealMatrix &B) const;
00165   public:
00166     DualMethod(const Parameters *param);
00181     int run(Manager &manager);
00182 
00183     virtual ~DualMethod();
00184   };
00185 }
00186     
00187 #endif