Kirchhoff's theorem: Difference between revisions
en>David Eppstein matroids |
en>David Eppstein Undo. The math is not broken, and the matrix is degenerate, having only n-1 *nonzero* eigenvalues. |
||
Line 1: | Line 1: | ||
'''Shape optimization''' is part of the field of [[optimal control]] theory. The typical problem is to find the [[shape]] which is optimal in that it minimizes a certain cost [[functional (mathematics)|functional]] while satisfying given [[constraint (mathematics)|constraints]]. In many cases, the functional being solved depends on the solution of a given partial differential equation defined on the variable domain. | |||
[[Topology optimization]] is, in addition, concerned with the number of connected components/boundaries belonging to the domain. Such methods are needed since typically shape optimization methods work in a subset of allowable shapes which have fixed topological properties, such as having a fixed number of holes in them. Topological optimization techniques can then help work around the limitations of pure shape optimization. | |||
==Definition== | |||
[[Mathematics|Mathematically]], shape optimization can be posed as the problem of finding a [[bounded set]] <math>\Omega</math>, [[maxima and minima|minimizing]] a [[functional (mathematics)|functional]] | |||
:<math>\mathcal{F}(\Omega)</math>, | |||
possibly subject to a [[constraint (mathematics)|constraint]] of the form | |||
:<math>\mathcal{G}(\Omega)=0.</math> | |||
Usually we are interested in sets <math>\Omega</math> which are [[Lipschitz continuity|Lipschitz]] or C<sup>1</sup> [[Boundary (topology)|boundary]] and consist of finitely many [[connected component (analysis)|components]], which is a way of saying that we would like to find a rather pleasing shape as a solution, not some jumble of rough bits and pieces. Sometimes additional constraints need to be imposed to that end to ensure well-posedness of the problem and uniqueness of the solution. | |||
Shape optimization is an [[infinite-dimensional optimization]] problem. Furthermore, the space of allowable shapes over which the optimization is performed does not admit a [[vector space]] structure, making application of traditional optimization methods more difficult. | |||
==Examples== | |||
<ul> | |||
<li>Among all three-dimensional shapes of given volume, find the one which has minimal surface area. Here: | |||
:<math>\mathcal{F}(\Omega)=\mbox{Area}(\partial \Omega)</math>, | |||
with | |||
:<math>\mathcal{G}(\Omega)=\mbox{Volume}(\Omega)-\mbox{const.}</math> | |||
The answer is the inside of a [[sphere]]. | |||
</li> | |||
<li>Find the shape of an airplane wing which minimizes [[Drag (physics)|drag]]. Here the constraints could be | |||
the wing strength, or the wing dimensions. | |||
</li> | |||
<li>Find the shape of various mechanical structures, which can resist a given [[Stress (physics)|stress]] while having a minimal mass/volume. | |||
</li> | |||
<li>Given a known three-dimensional object with a fixed radiation source inside, deduce the shape and size of the source based on measurements done on part of the boundary of the object. A formulation of this [[inverse problem]] using [[least-squares]] fit leads to a shape optimization problem. | |||
</li> | |||
</ul> | |||
==Techniques== | |||
Shape optimization problems are usually solved [[numerical analysis|numerically]], by using [[iterative method]]s. That is, one starts with an initial guess for a shape, and then gradually evolves it, | |||
until it morphs into the optimal shape. | |||
=== Keeping track of the shape === | |||
To solve a shape optimization problem, one needs to find a way to | |||
represent a shape in the [[Computer storage|computer memory]], and follow its evolution. Several approaches are usually used. | |||
One approach is to follow the boundary of the shape. For that, one can | |||
sample the shape boundary in a relatively dense and uniform manner, that is, to consider enough points to get a sufficiently accurate outline of the shape. Then, one can evolve the shape by gradually moving the boundary points. This is called the ''Lagrangian approach''. | |||
Another approach is to consider a [[function (mathematics)|function]] defined on a rectangular box around the shape, which is positive inside of the shape, zero on the boundary of the shape, and negative outside of the shape. One can then evolve this function instead of the shape itself. One can consider a rectangular grid on the box and sample the function at the grid points. As the shape evolves, the grid points do not change; only the | |||
function values at the grid points change. This approach, of using a fixed | |||
grid, is called the ''Eulerian approach''. The idea of using a function | |||
to represent the shape is at the basis of the [[level set method]]. | |||
A third approach is to think of the shape evolution as of a flow problem. That is, one can imagine that the shape is made of a plastic material gradually deforming such that any point inside or on the boundary | |||
of the shape can be always traced back to a point of the original shape in a one-to-one fashion. Mathematically, if <math>\Omega_0</math> is the initial shape, and <math>\Omega_t</math> is the shape at time ''t'', | |||
one considers the [[diffeomorphism]]s | |||
:<math>f_t:\Omega_0\to \Omega_t, \mbox{ for } 0\le t\le t_0.</math> | |||
The idea is again that shapes are difficult entities to be dealt with directly, so manipulate them by means of a function. | |||
=== Iterative methods using shape gradients === | |||
Consider a smooth velocity field <math>V</math> and the family of transformations <math>T_s</math> of the initial domain <math>\Omega_0</math> under the velocity field <math>V</math>: | |||
:<math>x(0) = x_0 \in \Omega_0, \quad x'(s) = V(x(s)), \quad T_s(x_0) = x(s), \quad s \geq 0 </math>, | |||
and denote | |||
:<math>\Omega_0 \mapsto T_s(\Omega_0) = \Omega_s.</math> | |||
Then the Gâteaux or shape derivative of <math>\mathcal{F}(\Omega)</math> at <math>\Omega_0</math> with respect to the shape is the limit of | |||
:<math>d\mathcal{F}(\Omega_0;V) = \lim_{s \to 0}\frac{\mathcal{F}(\Omega_s) - \mathcal{F}(\Omega_0)}{s}</math> | |||
if this limit exists. If in addition the derivative is linear with respect to <math>V</math>, there is a unique element of <math>\nabla \mathcal{F} \in L^2(\partial \Omega_0)</math> and | |||
:<math>d\mathcal{F}(\Omega_0;V) = \langle \nabla \mathcal{F}, V \rangle_{\partial \Omega_0}</math> | |||
where <math>\nabla \mathcal{F}</math> is called the shape gradient. This gives a natural idea of [[gradient descent]], where the boundary <math>\partial \Omega</math> is evolved in the direction of negative shape gradient in order to reduce the value of the cost functional. Higher order derivatives can be similarly defined, leading to Newtonlike methods. | |||
Typically, gradient descent is preferred, even if requires a large number of iterations, because, it can be hard to compute the second-order derivative (that is, the [[Hessian matrix|Hessian]]) of the objective functional <math>\mathcal{F}</math>. | |||
If the shape optimization problem has constraints, that is, the functional | |||
<math>\mathcal{G}</math> is present, one has to find ways to convert the | |||
constrained problem into an unconstrained one. Sometimes ideas based on [[Lagrange multipliers]] can work. | |||
=== Geometry parametrization === | |||
Shape optimization can be faced using standard optimization methods if a parametrization of the geometry is defined. Such parametrization is very important in CAE field where goal functions are usually complex functions evaluated using numerical models (CFD, FEA,...). A convenient approach, suitable for a wide class of problems, consists in the parametrization of the CAD model coupled with a full automation of all the process required for function evaluation (meshing, solving and result processing). [[Mesh morphing]] is a valid choice for complex problems. In this case the parametrization is defined after the meshing stage acting directly on the numerical model used for calculation that is changed using mesh updating methods. There are several algorithms available for mesh morphing ([[deforming volume]]s, [[pseudosolid]]s, [[radial basis function]]s). | |||
The selection of the parametrization approach depends mainly on the size of the problem: the CAD approach is preferred for small-to-medium sized models whilst the mesh morphing approach is the best (and sometimes the only feasible one) for large and very large models. | |||
==See also== | |||
* [[Topological derivative]] | |||
== References == | |||
* Allaire, G. (2002) ''Shape optimization by the homogenization method''. Applied Mathematical Sciences 146, Springer Verlag. ISBN 0-387-95298-5 | |||
* Ashok D. Belegundu, Tirupathi R. Chandrupatla. (2003) ''Optimization Concepts and applications in Engineering'' Prentice Hall. ISBN 0-13-031279-7. | |||
* Bendsøe M. P.; Sigmund O. (2003) ''Topology Optimization: Theory, Methods and Applications''. Springer. ISBN 3-540-42992-1. | |||
* Burger, M.; Osher, S.L. (2005) ''A Survey on Level Set Methods for Inverse Problems and Optimal Design''. European Journal of Applied Mathematics, vol.16 pp.263-301. | |||
* Delfour, M.C.; Zolesio, J.-P. (2001) ''Shapes and Geometries - Analysis, Differential Calculus, and Optimization''. SIAM. ISBN 0-89871-489-3. | |||
* Haslinger, J.; Mäkinen, R. (2003) ''Introduction to Shape Optimization: Theory, Approximation and Computation''. Society for Industrial and Applied Mathematic. ISBN 0-89871-536-9. | |||
* Laporte, E.; Le Tallec, P. (2003) ''Numerical Methods in Sensitivity Analysis and Shape Optimization. Birkhäuser. ISBN 0-8176-4322-2. | |||
* Mohammadi, B.; Pironneau, O. (2001) ''Applied Shape Optimization for Fluids''. Oxford University Press. ISBN 0-19-850743-7. | |||
==External links== | |||
*[http://www.topopt.dtu.dk TopOpt Group] — Free interactive programs for 2D and 3D compliance optimization, free MATLAB programme and more information on theory and applications. | |||
*[http://www.cmap.polytechnique.fr/~optopo Optopo Group] — Simulations and bibliography of the optopo group at Ecole Polytechnique (France). Homogenization method and level set method. | |||
*[http://www.intelnics.com/opennn OpenNN: Open Neural Networks Library] | |||
[[Category:Mathematical optimization]] |
Revision as of 17:50, 20 October 2013
Shape optimization is part of the field of optimal control theory. The typical problem is to find the shape which is optimal in that it minimizes a certain cost functional while satisfying given constraints. In many cases, the functional being solved depends on the solution of a given partial differential equation defined on the variable domain.
Topology optimization is, in addition, concerned with the number of connected components/boundaries belonging to the domain. Such methods are needed since typically shape optimization methods work in a subset of allowable shapes which have fixed topological properties, such as having a fixed number of holes in them. Topological optimization techniques can then help work around the limitations of pure shape optimization.
Definition
Mathematically, shape optimization can be posed as the problem of finding a bounded set , minimizing a functional
possibly subject to a constraint of the form
Usually we are interested in sets which are Lipschitz or C1 boundary and consist of finitely many components, which is a way of saying that we would like to find a rather pleasing shape as a solution, not some jumble of rough bits and pieces. Sometimes additional constraints need to be imposed to that end to ensure well-posedness of the problem and uniqueness of the solution.
Shape optimization is an infinite-dimensional optimization problem. Furthermore, the space of allowable shapes over which the optimization is performed does not admit a vector space structure, making application of traditional optimization methods more difficult.
Examples
- Among all three-dimensional shapes of given volume, find the one which has minimal surface area. Here: with The answer is the inside of a sphere.
- Find the shape of an airplane wing which minimizes drag. Here the constraints could be the wing strength, or the wing dimensions.
- Find the shape of various mechanical structures, which can resist a given stress while having a minimal mass/volume.
- Given a known three-dimensional object with a fixed radiation source inside, deduce the shape and size of the source based on measurements done on part of the boundary of the object. A formulation of this inverse problem using least-squares fit leads to a shape optimization problem.
Techniques
Shape optimization problems are usually solved numerically, by using iterative methods. That is, one starts with an initial guess for a shape, and then gradually evolves it, until it morphs into the optimal shape.
Keeping track of the shape
To solve a shape optimization problem, one needs to find a way to represent a shape in the computer memory, and follow its evolution. Several approaches are usually used.
One approach is to follow the boundary of the shape. For that, one can sample the shape boundary in a relatively dense and uniform manner, that is, to consider enough points to get a sufficiently accurate outline of the shape. Then, one can evolve the shape by gradually moving the boundary points. This is called the Lagrangian approach.
Another approach is to consider a function defined on a rectangular box around the shape, which is positive inside of the shape, zero on the boundary of the shape, and negative outside of the shape. One can then evolve this function instead of the shape itself. One can consider a rectangular grid on the box and sample the function at the grid points. As the shape evolves, the grid points do not change; only the function values at the grid points change. This approach, of using a fixed grid, is called the Eulerian approach. The idea of using a function to represent the shape is at the basis of the level set method.
A third approach is to think of the shape evolution as of a flow problem. That is, one can imagine that the shape is made of a plastic material gradually deforming such that any point inside or on the boundary of the shape can be always traced back to a point of the original shape in a one-to-one fashion. Mathematically, if is the initial shape, and is the shape at time t, one considers the diffeomorphisms
The idea is again that shapes are difficult entities to be dealt with directly, so manipulate them by means of a function.
Iterative methods using shape gradients
Consider a smooth velocity field and the family of transformations of the initial domain under the velocity field :
and denote
Then the Gâteaux or shape derivative of at with respect to the shape is the limit of
if this limit exists. If in addition the derivative is linear with respect to , there is a unique element of and
where is called the shape gradient. This gives a natural idea of gradient descent, where the boundary is evolved in the direction of negative shape gradient in order to reduce the value of the cost functional. Higher order derivatives can be similarly defined, leading to Newtonlike methods.
Typically, gradient descent is preferred, even if requires a large number of iterations, because, it can be hard to compute the second-order derivative (that is, the Hessian) of the objective functional .
If the shape optimization problem has constraints, that is, the functional is present, one has to find ways to convert the constrained problem into an unconstrained one. Sometimes ideas based on Lagrange multipliers can work.
Geometry parametrization
Shape optimization can be faced using standard optimization methods if a parametrization of the geometry is defined. Such parametrization is very important in CAE field where goal functions are usually complex functions evaluated using numerical models (CFD, FEA,...). A convenient approach, suitable for a wide class of problems, consists in the parametrization of the CAD model coupled with a full automation of all the process required for function evaluation (meshing, solving and result processing). Mesh morphing is a valid choice for complex problems. In this case the parametrization is defined after the meshing stage acting directly on the numerical model used for calculation that is changed using mesh updating methods. There are several algorithms available for mesh morphing (deforming volumes, pseudosolids, radial basis functions). The selection of the parametrization approach depends mainly on the size of the problem: the CAD approach is preferred for small-to-medium sized models whilst the mesh morphing approach is the best (and sometimes the only feasible one) for large and very large models.
See also
References
- Allaire, G. (2002) Shape optimization by the homogenization method. Applied Mathematical Sciences 146, Springer Verlag. ISBN 0-387-95298-5
- Ashok D. Belegundu, Tirupathi R. Chandrupatla. (2003) Optimization Concepts and applications in Engineering Prentice Hall. ISBN 0-13-031279-7.
- Bendsøe M. P.; Sigmund O. (2003) Topology Optimization: Theory, Methods and Applications. Springer. ISBN 3-540-42992-1.
- Burger, M.; Osher, S.L. (2005) A Survey on Level Set Methods for Inverse Problems and Optimal Design. European Journal of Applied Mathematics, vol.16 pp.263-301.
- Delfour, M.C.; Zolesio, J.-P. (2001) Shapes and Geometries - Analysis, Differential Calculus, and Optimization. SIAM. ISBN 0-89871-489-3.
- Haslinger, J.; Mäkinen, R. (2003) Introduction to Shape Optimization: Theory, Approximation and Computation. Society for Industrial and Applied Mathematic. ISBN 0-89871-536-9.
- Laporte, E.; Le Tallec, P. (2003) Numerical Methods in Sensitivity Analysis and Shape Optimization. Birkhäuser. ISBN 0-8176-4322-2.
- Mohammadi, B.; Pironneau, O. (2001) Applied Shape Optimization for Fluids. Oxford University Press. ISBN 0-19-850743-7.
External links
- TopOpt Group — Free interactive programs for 2D and 3D compliance optimization, free MATLAB programme and more information on theory and applications.
- Optopo Group — Simulations and bibliography of the optopo group at Ecole Polytechnique (France). Homogenization method and level set method.