MOAB: Mesh Oriented datABase  (version 5.3.0)
FeasibleNewton.hpp
Go to the documentation of this file.
00001 /* *****************************************************************
00002     MESQUITE -- The Mesh Quality Improvement Toolkit
00003 
00004     Copyright 2004 Sandia Corporation and Argonne National
00005     Laboratory.  Under the terms of Contract DE-AC04-94AL85000
00006     with Sandia Corporation, the U.S. Government retains certain
00007     rights in this software.
00008 
00009     This library is free software; you can redistribute it and/or
00010     modify it under the terms of the GNU Lesser General Public
00011     License as published by the Free Software Foundation; either
00012     version 2.1 of the License, or (at your option) any later version.
00013 
00014     This library is distributed in the hope that it will be useful,
00015     but WITHOUT ANY WARRANTY; without even the implied warranty of
00016     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017     Lesser General Public License for more details.
00018 
00019     You should have received a copy of the GNU Lesser General Public License
00020     (lgpl.txt) along with this library; if not, write to the Free Software
00021     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022 
00023     diachin2@llnl.gov, djmelan@sandia.gov, mbrewer@sandia.gov,
00024     pknupp@sandia.gov, tleurent@mcs.anl.gov, tmunson@mcs.anl.gov
00025 
00026   ***************************************************************** */
00027 // -*- Mode : c++; tab-width: 3; c-tab-always-indent: t; indent-tabs-mode: nil; c-basic-offset: 3
00028 // -*-
00029 //
00030 //    AUTHOR: Thomas Leurent <tleurent@mcs.anl.gov>
00031 //       ORG: Argonne National Laboratory
00032 //    E-MAIL: tleurent@mcs.anl.gov
00033 //
00034 // ORIG-DATE: 15-Jan-03 at 08:05:56
00035 //  LAST-MOD: 23-May-03 at 11:20:14 by Thomas Leurent
00036 //
00037 // DESCRIPTION:
00038 // ============
00039 /*!
00040   \file   FeasibleNewton.hpp
00041   \brief
00042 
00043   The FeasibleNewton Class implements the newton non-linear programming algorythm
00044   in order to move a free vertex to an optimal position given an
00045   ObjectiveFunction object and a QualityMetric object.
00046 
00047   \author Thomas Leurent
00048   \author Todd Munson
00049   \date   2003-01-15
00050 */
00051 // DESCRIP-END.
00052 //
00053 
00054 #ifndef MSQ_FeasibleNewton_hpp
00055 #define MSQ_FeasibleNewton_hpp
00056 
00057 #include "Mesquite.hpp"
00058 #include "VertexMover.hpp"
00059 #include "MsqHessian.hpp"
00060 #include "PatchSetUser.hpp"
00061 
00062 namespace MBMesquite
00063 {
00064 class ObjectiveFunction;
00065 
00066 /*! \class FeasibleNewton
00067 
00068     \brief High Performance implementation of the Feasible Newton algorythm.
00069 
00070     Consider our non-linear objective function
00071     \f$ f: I\!\!R^{3N} \rightarrow I\!\!R \f$ where \f$ N \f$
00072     is the number of vertices of the mesh, and \f$ 3N \f$ is therefore the number
00073     of degrees of freedom of the mesh.
00074     The Taylor expansion of \f$ f \f$ around the point \f$ x_0 \f$ is
00075     \f[ f(x_0+d) = f(x_0) + \nabla f(x_0)d + \frac{1}{2} d^T\nabla^2 f(x_0)d
00076         + ...  \;\;\; .\f]
00077 
00078     Each iteration of the Newton algorithm tries to find a descent vector that
00079     minimizes the above quadratic approximation, i.e. it looks for
00080     \f[ \min_{d} q(d;x_0) = f(x_0) + \nabla f(x_0)d + \frac{1}{2} d^T\nabla^2 f(x_0)d
00081         \;\; . \f]
00082     We know that if a quadratic function has a finite minimum, it is reached at the
00083     point where the function gradient is null and that the function Hessian
00084     is then positive definite.
00085     Therefore we are looking for \f$ d \f$ such that \f$ \nabla q(d;x_0) =0 \f$. We have
00086     \f[ \nabla q(d;x_0) = \nabla f(x_0) + \nabla^2 f(x_0)d \;\;, \f]
00087     therefore we must solve for \f$ d \f$ the system
00088     \f[ \nabla^2 f(x_0)d = -\nabla f(x_0) \;\; . \f]
00089 
00090     We assume that the Hessian is positive definite and we use the conjugate gradient
00091     algebraic solver to solve the above system. If the conjugate gradient solver finds
00092     a direction of negative curvature, the Hessian was not positive definite and we take
00093     a step in that direction of negative curvature, which is a descent direction.
00094 */
00095 class FeasibleNewton : public VertexMover, public PatchSetUser
00096 {
00097   public:
00098     MESQUITE_EXPORT FeasibleNewton( ObjectiveFunction* of );
00099 
00100     MESQUITE_EXPORT virtual ~FeasibleNewton()
00101     {
00102         delete coordsMem;
00103     }
00104 
00105     /*! Sets a minimum value for the gradient. If the gradient is below that value,
00106       we stop iterating. */
00107     MESQUITE_EXPORT void set_lower_gradient_bound( double gradc )
00108     {
00109         convTol = gradc;
00110     }
00111 
00112     PatchSet* get_patch_set();
00113 
00114     MESQUITE_EXPORT std::string get_name() const;
00115 
00116   protected:
00117     virtual void initialize( PatchData& pd, MsqError& err );
00118     virtual void optimize_vertex_positions( PatchData& pd, MsqError& err );
00119     virtual void initialize_mesh_iteration( PatchData& pd, MsqError& err );
00120     virtual void terminate_mesh_iteration( PatchData& pd, MsqError& err );
00121     virtual void cleanup();
00122 
00123   private:
00124     double convTol;
00125     MsqHessian mHessian;
00126     PatchDataVerticesMemento* coordsMem;
00127     bool havePrintedDirectionMessage;
00128 };
00129 
00130 }  // namespace MBMesquite
00131 
00132 #endif  // MSQ_FeasibleNewton_hpp
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines