“Inexact descent methods for elastic parameter optimization”
Conference:
Type(s):
Title:
- Inexact descent methods for elastic parameter optimization
Session/Category Title: Optimizing structures & materials
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Elastic parameter optimization has revealed its importance in 3D modeling, virtual reality, and additive manufacturing in recent years. Unfortunately, it is known to be computationally expensive, especially if there are many parameters and data samples. To address this challenge, we propose to introduce the inexactness into descent methods, by iteratively solving a forward simulation step and a parameter update step in an inexact manner. The development of such inexact descent methods is centered at two questions: 1) how accurate/inaccurate can the two steps be; and 2) what is the optimal way to implement an inexact descent method. The answers to these questions are in our convergence analysis, which proves the existence of relative error thresholds for the two inexact steps to ensure the convergence. This means we can simply solve each step by a fixed number of iterations, if the iterative solver is at least linearly convergent. While the use of the inexact idea speeds up many descent methods, we specifically favor a GPU-based one powered by state-of-the-art simulation techniques. Based on this method, we study a variety of implementation issues, including backtracking line search, initialization, regularization, and multiple data samples. We demonstrate the use of our inexact method in elasticity measurement and design applications. Our experiment shows the method is fast, reliable, memory-efficient, GPU-friendly, flexible with different elastic models, scalable to a large parameter space, and parallelizable for multiple data samples.
References:
1. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques (SIGGRAPH ’98). ACM, New York, NY, USA, 43–54. Google ScholarDigital Library
2. Markus Becker and Matthias Teschner. 2007. Robust and Efficient Estimation of Elasticity Parameters Using the Linear Finite Element Method. In SimVis. 15–28.Google Scholar
3. Luca Bergamaschi, Igor Moret, and Giovanni Zilli. 2001. Inexact Quasi-Newton Methods for Sparse Systems of Nonlinear Equations. Future Generation Computer Systems 18, 1 (Sept. 2001), 41–53. Google ScholarDigital Library
4. Hans-Uwe Berger. 2009. Inverse Problems in Soft Tissue Elastography using Boundary Element Methods. Ph.D. Dissertation. University of Canterbury.Google Scholar
5. Kiran S. Bhat, Christopher D. Twigg, Jessica K. Hodgins, Pradeep K. Khosla, Zoran Popović, and Steven M. Seitz. 2003. Estimating Cloth Simulation Parameters from Video. In Proceedings of SCA. 37–51. Google ScholarDigital Library
6. Bernd Bickel, Moritz Bächer, Miguel A. Otaduy, Hyunho Richard Lee, Hanspeter Pfister, Markus Gross, and Wojciech Matusik. 2010. Design and Fabrication of Materials with Desired Deformation Behavior. ACM Trans. Graph. (SIGGRAPH) 29, 4, Article 63 (July 2010), 10 pages. Google ScholarDigital Library
7. Bernd Bickel, Moritz Bächer, Miguel A. Otaduy, Wojciech Matusik, Hanspeter Pfister, and Markus Gross. 2009. Capture and Modeling of Non-linear Heterogeneous Soft Tissue. ACM Trans. Graph. (SIGGRAPH) 28, 3, Article 89 (July 2009), 9 pages. Google ScholarDigital Library
8. Ernesto G. Birgin, Nataša Krejić, and José Mario Martínez. 2003. Globally Convergent Inexact Quasi-Newton Methods for Solving Nonlinear Systems. Numerical Algorithms 32, 2 (April 2003), 249–260.Google ScholarCross Ref
9. Marc Bonnet and Andrei Constantinescu. 2005. Inverse Problems in Elasticity. Inverse Problems 21, 2 (2005), 1–50.Google ScholarCross Ref
10. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans. Graph. (SIGGRAPH) 33, 4, Article 154 (July 2014), 11 pages. Google ScholarDigital Library
11. Regina Burachik and Joydeep Dutta. 2010. Inexact Proximal Point Methods for Variational Inequality Problems. SIAM Journal on Optimization 20, 5 (2010), 2653–2678. Google ScholarDigital Library
12. Richard H. Byrd, Frank E. Curtis, and Jorge Nocedal. 2008. An Inexact SQP Method for Equality Constrained Optimization. SIAM Journal on Optimization 19, 1 (2008), 351–369. Google ScholarDigital Library
13. Romain Casati, Gilles Daviet, and Florence Bertails-Descoubes. 2016. Inverse Elastic Cloth Design with Contact and Friction. Technical report. Inria Grenoble Rhône-Alpes, Université de Grenoble.Google Scholar
14. Xiang Chen, Changxi Zheng, Weiwei Xu, and Kun Zhou. 2014. An Asymptotic Numerical Method for Inverse Elastic Shape Design. ACM Trans. Graph. (SIGGRAPH) 33, 4, Article 95 (July 2014), 11 pages. Google ScholarDigital Library
15. Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug. 1982. Inexact Newton Methods. SIAM J. Numer. Anal. 19, 2 (April 1982), 400–408.Google ScholarCross Ref
16. Marvin M. Doyley. 2012. Model-Based Elastography: A Survey of Approaches to the Inverse Elasticity Problem. Physics in Medicine and Biology 57, 3 (2012), 35–73.Google ScholarCross Ref
17. Stanley C. Eisenstat and Homer F. Walker. 1994. Globally Convergent Inexact Newton Methods. SIAM Journal on Optimization 4, 2 (1994), 393–422.Google ScholarCross Ref
18. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: A Practical Gauss-Seidel Method for Stable Soft Body Dynamics. ACM Trans. Graph. (SIGGRAPH Asia) 35, 6, Article 214 (Nov. 2016), 9 pages. Google ScholarDigital Library
19. Mark S. Gockenbach, Baasansuren Jadamba, Akhtar A. Khan, Christiane Tammer, and Brian Winkler. 2015. Proximal Methods for the Elastography Inverse Problem of Tumor Identification Using an Equation Error Approach. In Advances in Variational and Hemivariational Inequalities. Springer, Chapter 10, 173–197.Google Scholar
20. Gene H. Golub and Charles F. Van Loan. 2012. Matrix Computations (4th Ed.). Johns Hopkins University Press, Baltimore, MD, USA.Google Scholar
21. Eldad Haber, Uri M. Ascher, and Douglas W. Oldenburg. 2004. Inversion of 3D Electromagnetic Data in Frequency and Time Domain Using an Inexact All-At-Once Approach. Geophysics 69, 5 (2004), 1216–1228.Google ScholarCross Ref
22. Tyler S. Kaster, Ira Sack, and Afshan Samani. 2011. Measurement of the Hyperelastic Properties of ex vivo Brain Tissue Slices. Journal of Biomechanics 44, 6 (April 2011), 1158–1163.Google ScholarCross Ref
23. Mahmud Khodadad and Mohsen Dashti Ardakani. 2009. Application of the Inverse Elasticity Problem to Identify Irregular Interfacial Configurations. Engineering Analysis with Boundary Elements 33, 6 (June 2009), 872–879.Google ScholarCross Ref
24. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast Simulation of Mass-Spring Systems. ACM Trans. Graph. (SIGGRAPH Asia) 32, 6, Article 214 (Nov. 2013), 7 pages. Google ScholarDigital Library
25. Zohreh Barani Lonbani. 2010. Elastographic Reconstruction Methods for Orthotropic Materials. Master’s thesis. University of Canterbury.Google Scholar
26. Erik Lund, Henrik Møller, and Lars A. Jakobsen. 2003. Shape Design Optimization of Stationary Fluid-Structure Interaction Problems with Large Displacements and Turbulence. Structural and Multidisciplinary Optimization 25, 5–6 (Dec. 2003), 383–392. Google ScholarDigital Library
27. Christopher W. Macosko. 1994. Rheology: Principles, Measurement and Applications. VCH Publishers.Google Scholar
28. Nicholas Maratos. 1978. Exact Penalty Function Algorithms for Finite-Dimensional and Control Optimization Problems. Ph.D. Dissertation. University of London.Google Scholar
29. Vittorio Megaro, Jonas Zehnder, Moritz Bächer, Stelian Coros, Markus Gross, and Bernhard Thomaszewski. 2017. A Computational Design Tool for Compliant Mechanisms. ACM Trans. Graph. (SIGGRAPH) 36, 4, Article 82 (July 2017), 12 pages. Google ScholarDigital Library
30. Eder Miguel, Derek Bradley, Bernhard Thomaszewski, Bernd Bickel, Wojciech Matusik, Miguel A. Otaduy, and Steve Marschner. 2012. Data-Driven Estimation of Cloth Simulation Models. Comput. Graph. Forum (Eurographics) 31, 2 (May 2012), 519–528. Google ScholarDigital Library
31. Eder Miguel, David Miraut, and Miguel A. Otaduy. 2016. Modeling and Estimation of Energy-Based Hyperelastic Objects. Computer Graphics Forum (Eurographics) 35, 2 (May 2016), 385–396.Google ScholarCross Ref
32. Matthias Müller. 2008. Hierarchical Position Based Dynamics. In Proceedings of VRIPHYS. 1–10.Google Scholar
33. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless Deformations Based on Shape Matching. ACM Trans. Graph. (SIGGRAPH) 24, 3 (July 2005), 471–478. Google ScholarDigital Library
34. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ Projective Dynamics: Fast Simulation of General Constitutive Models. In Proceedings of SCA. 21–28. Google ScholarDigital Library
35. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2rd Ed.). Springer.Google Scholar
36. James F. O’Brien and Jessica K. Hodgins. 1999. Graphical Modeling and Animation of Brittle Fracture. In Proceedings of SIGGRAPH 98 (Annual Conference Series). 137–146. Google ScholarDigital Library
37. Ray W. Ogden. 1997. Non-linear Elastic Deformations. Dover Publications, Inc.Google Scholar
38. Joseph J. O’Hagan and Afshan Samani. 2008. Measurement of the Hyperelastic Properties of Tissue Slices with Tumour Inclusion. Physics in Medicine and Biology 53, 24 (Dec. 2008), 7087–7106.Google ScholarCross Ref
39. Dinesh K. Pai, Kees van den Doel, Doug L. James, Jochen Lang, John E. Lloyd, Joshua L. Richmond, and Som H. Yau. 2001. Scanning Physical Interaction Behavior of 3D Objects. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). 87–96. Google ScholarDigital Library
40. Roger P. Pawlowski, Joseph P. Simonis, Homer F. Walker, and John N. Shadid. 2008. Inexact Newton Dogleg Methods. SIAM J. Numer. Anal. 46, 4 (May 2008), 2112–2132. Google ScholarDigital Library
41. Jesús Pérez, Miguel A. Otaduy, and Bernhard Thomaszewski. 2017. Computational Design and Automated Fabrication of Kirchhoff-Plateau Surfaces. ACM Trans. Graph. (SIGGRAPH) 36, 4, Article 62 (July 2017), 12 pages. Google ScholarDigital Library
42. Jesús Pérez, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, José A. Canabal, Robert Sumner, and Miguel A. Otaduy. 2015. Design and Fabrication of Flexible Rod Meshes. ACM Trans. Graph. (SIGGRAPH) 34, 4, Article 138 (July 2015), 12 pages. Google ScholarDigital Library
43. Xavier Provot. 1996. Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behavior. In Proceedings of Graphics Interface. 147–154.Google Scholar
44. Rien Quirynen, Sebastien Gros, and Moritz Diehl. 2017. Inexact Newton-Type Optimization with Iterated Sensitivities. SIAM Journal on Optimization 28, 1 (July 2017), 74–95.Google Scholar
45. Mikhail V. Solodov and Benar F. Svaiter. 2001. A Unified Framework for Some Inexact Proximal Point Algorithms. Numerical Functional Analysis and Optimization 22, 7–8 (2001), 1013–1035.Google ScholarCross Ref
46. Joseph Teran, Silvia Blemker, V Ng Thow Hing, and Ron Fedkiw. 2003. Finite Volume Methods for the Simulation of Skeletal Muscle. In Proceedings of SCA. 68–74. Google ScholarDigital Library
47. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust Quasistatic Finite Elements and Flesh Simulation. In Proceedings of SCA. 181–190. Google ScholarDigital Library
48. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. SIGGRAPH Comput. Graph. 21, 4 (Aug. 1987), 205–214. Google ScholarDigital Library
49. Bernhard Thomaszewski, Simon Pabst, and Wolfgang Strasser. 2009. Continuum-Based Strain Limiting. Computer Graphics Forum (Eurographics) 28, 2 (2009), 569–576.Google ScholarCross Ref
50. Nobuyuki Umetani, Danny M. Kaufman, Takeo Igarashi, and Eitan Grinspun. 2011. Sensitive Couture for Interactive Garment Modeling and Editing. ACM Trans. Graph. (SIGGRAPH) 30, 4, Article 90 (July 2011), 12 pages. Google ScholarDigital Library
51. Bin Wang, Longhua Wu, KangKang Yin, Uri Ascher, Libin Liu, and Hui Huang. 2015. Deformation Capture and Modeling of Soft Objects. ACM Trans. Graph. (SIGGRAPH) 34, 4, Article 94 (July 2015), 12 pages. Google ScholarDigital Library
52. Huamin Wang. 2015. A Chebyshev Semi-Iterative Approach for Accelerating Projective and Position-Based Dynamics. ACM Trans. Graph. (SIGGRAPH Asia) 34, 6, Article 246 (Oct. 2015), 9 pages. Google ScholarDigital Library
53. Huamin Wang. 2018. Rule-Free Sewing Pattern Adjustment with Precision and Efficiency. ACM Trans. Graph. (SIGGRAPH) 37, 4, Article 53 (July 2018), 13 pages. Google ScholarDigital Library
54. Huamin Wang, James O’Brien, and Ravi Ramamoorthi. 2010. Multi-Resolution Isotropic Strain Limiting. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6, Article 156 (Dec. 2010), 10 pages. Google ScholarDigital Library
55. Huamin Wang, James F. O’Brien, and Ravi Ramamoorthi. 2011. Data-Driven Elastic Models for Cloth: Modeling and Measurement. ACM Trans. Graph. (SIGGRAPH) 30, 4, Article 71 (July 2011), 12 pages. Google ScholarDigital Library
56. Huamin Wang and Yin Yang. 2016. Descent Methods for Elastic Body Simulation on the GPU. ACM Trans. Graph. (SIGGRAPH Asia) 35, 6, Article 212 (Nov. 2016), 10 pages. Google ScholarDigital Library
57. Hongyi Xu, Yijing Li, Yong Chen, and Jernej Barbič. 2015a. Interactive Material Design Using Model Reduction. ACM Trans. Graph. 34, 2, Article 18 (March 2015), 14 pages. Google ScholarDigital Library
58. Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbič. 2015b. Nonlinear Material Design Using Principal Stretches. ACM Trans. Graph. (SIGGRAPH) 34, 4, Article 75 (July 2015), 11 pages. Google ScholarDigital Library
59. Jonas Zehnder, Espen Knoop, Moritz Bächer, and Bernhard Thomaszewski. 2017. Metasilicone: Design and Fabrication of Composite Silicone with Desired Mechanical Properties. ACM Trans. Graph. (SIGGRAPH Asia) 36, 6, Article 240 (Nov. 2017), 13 pages. Google ScholarDigital Library
