Branch data Line data Source code
1 : : /* *****************************************************************
2 : : MESQUITE -- The Mesh Quality Improvement Toolkit
3 : :
4 : : Copyright 2004 Sandia Corporation and Argonne National
5 : : Laboratory. Under the terms of Contract DE-AC04-94AL85000
6 : : with Sandia Corporation, the U.S. Government retains certain
7 : : rights in this software.
8 : :
9 : : This library is free software; you can redistribute it and/or
10 : : modify it under the terms of the GNU Lesser General Public
11 : : License as published by the Free Software Foundation; either
12 : : version 2.1 of the License, or (at your option) any later version.
13 : :
14 : : This library is distributed in the hope that it will be useful,
15 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : : Lesser General Public License for more details.
18 : :
19 : : You should have received a copy of the GNU Lesser General Public License
20 : : (lgpl.txt) along with this library; if not, write to the Free Software
21 : : Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 : :
23 : : [email protected], [email protected], [email protected],
24 : : [email protected], [email protected], [email protected]
25 : :
26 : : ***************************************************************** */
27 : : // -*- Mode : c++; tab-width: 3; c-tab-always-indent: t; indent-tabs-mode: nil; c-basic-offset: 3
28 : : // -*-
29 : : //
30 : : // AUTHOR: Thomas Leurent <[email protected]>
31 : : // ORG: Argonne National Laboratory
32 : : // E-MAIL: [email protected]
33 : : //
34 : : // ORIG-DATE: 15-Jan-03 at 08:05:56
35 : : // LAST-MOD: 23-May-03 at 11:20:14 by Thomas Leurent
36 : : //
37 : : // DESCRIPTION:
38 : : // ============
39 : : /*!
40 : : \file FeasibleNewton.hpp
41 : : \brief
42 : :
43 : : The FeasibleNewton Class implements the newton non-linear programming algorythm
44 : : in order to move a free vertex to an optimal position given an
45 : : ObjectiveFunction object and a QualityMetric object.
46 : :
47 : : \author Thomas Leurent
48 : : \author Todd Munson
49 : : \date 2003-01-15
50 : : */
51 : : // DESCRIP-END.
52 : : //
53 : :
54 : : #ifndef MSQ_FeasibleNewton_hpp
55 : : #define MSQ_FeasibleNewton_hpp
56 : :
57 : : #include "Mesquite.hpp"
58 : : #include "VertexMover.hpp"
59 : : #include "MsqHessian.hpp"
60 : : #include "PatchSetUser.hpp"
61 : :
62 : : namespace MBMesquite
63 : : {
64 : : class ObjectiveFunction;
65 : :
66 : : /*! \class FeasibleNewton
67 : :
68 : : \brief High Performance implementation of the Feasible Newton algorythm.
69 : :
70 : : Consider our non-linear objective function
71 : : \f$ f: I\!\!R^{3N} \rightarrow I\!\!R \f$ where \f$ N \f$
72 : : is the number of vertices of the mesh, and \f$ 3N \f$ is therefore the number
73 : : of degrees of freedom of the mesh.
74 : : The Taylor expansion of \f$ f \f$ around the point \f$ x_0 \f$ is
75 : : \f[ f(x_0+d) = f(x_0) + \nabla f(x_0)d + \frac{1}{2} d^T\nabla^2 f(x_0)d
76 : : + ... \;\;\; .\f]
77 : :
78 : : Each iteration of the Newton algorithm tries to find a descent vector that
79 : : minimizes the above quadratic approximation, i.e. it looks for
80 : : \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
81 : : \;\; . \f]
82 : : We know that if a quadratic function has a finite minimum, it is reached at the
83 : : point where the function gradient is null and that the function Hessian
84 : : is then positive definite.
85 : : Therefore we are looking for \f$ d \f$ such that \f$ \nabla q(d;x_0) =0 \f$. We have
86 : : \f[ \nabla q(d;x_0) = \nabla f(x_0) + \nabla^2 f(x_0)d \;\;, \f]
87 : : therefore we must solve for \f$ d \f$ the system
88 : : \f[ \nabla^2 f(x_0)d = -\nabla f(x_0) \;\; . \f]
89 : :
90 : : We assume that the Hessian is positive definite and we use the conjugate gradient
91 : : algebraic solver to solve the above system. If the conjugate gradient solver finds
92 : : a direction of negative curvature, the Hessian was not positive definite and we take
93 : : a step in that direction of negative curvature, which is a descent direction.
94 : : */
95 : : class FeasibleNewton : public VertexMover, public PatchSetUser
96 : : {
97 : : public:
98 : : MESQUITE_EXPORT FeasibleNewton( ObjectiveFunction* of );
99 : :
100 : 56 : MESQUITE_EXPORT virtual ~FeasibleNewton()
101 : 56 : {
102 [ - + ]: 56 : delete coordsMem;
103 [ - + ]: 56 : }
104 : :
105 : : /*! Sets a minimum value for the gradient. If the gradient is below that value,
106 : : we stop iterating. */
107 : : MESQUITE_EXPORT void set_lower_gradient_bound( double gradc )
108 : : {
109 : : convTol = gradc;
110 : : }
111 : :
112 : : PatchSet* get_patch_set();
113 : :
114 : : MESQUITE_EXPORT std::string get_name() const;
115 : :
116 : : protected:
117 : : virtual void initialize( PatchData& pd, MsqError& err );
118 : : virtual void optimize_vertex_positions( PatchData& pd, MsqError& err );
119 : : virtual void initialize_mesh_iteration( PatchData& pd, MsqError& err );
120 : : virtual void terminate_mesh_iteration( PatchData& pd, MsqError& err );
121 : : virtual void cleanup();
122 : :
123 : : private:
124 : : double convTol;
125 : : MsqHessian mHessian;
126 : : PatchDataVerticesMemento* coordsMem;
127 : : bool havePrintedDirectionMessage;
128 : : };
129 : :
130 : : } // namespace MBMesquite
131 : :
132 : : #endif // MSQ_FeasibleNewton_hpp
|