Anderson Acceleration For Geometry Optimization

Many computer graphics problems need to calculate the geometry of the model under certain constraints.This can usually be expressed as a nonlinear non-convex op-timization problem involving global coupled variables.The difficulty of solving this kind of problem brings challenges to the development of interactive applications.Iter-ative solvers can quickly calculate approximate solutions to such problems,so they are widely used in computer graphics,computer vision,machine learning and other fields.In most problems,various constraints are imposed on variables,which can be divided into two categories.Soft constraints are satisfied by adding a penalty term to the tar-get function,forcing the variables as close to the feasible sets as possible,while hard constraints define the conditions that must be met during optimization.Solving hard constraints can be tedious and complicated compared to solving soft ones,however,they can better express the requirements of users.Local-Global solver is an iterative method designed for solving optimizaiton prob-lems with soft constraints.However,this solver converges very slowly,and it is difficult to obtain a high-precision solution in a limited time.In order to accelerate the conver-gence of this type of algorithm and improve the accuracy of the solution,a simple and effective method is proposed to accelerate the convergence of the solver.After rewriting the scheme of Local-Global iterates,we express it as the fixed-point solution,and speed it up using Anderson acceleration,which is a mature tool to accelerate the fixed-point iteration.In order to overcome the instability of Anderson acceleration,we propose a strategy to promise the monotonic decreasing of the lower bounded target function,which ensures the convergence of the algorithm.However,Local-Global solver cannot be applied to solve optimization for hard constraints,which prevents the method from being extended to more general and trivial problems.So we further explore the fast solving method for geometry optimizaiton.The alternating direction method of multipliers(ADMM)is an algorithm to handle the non-smooth target function with hard constraints.Similarly,it suffers from a slow and fluctuating"tail convergence".We have observed that ADMM is actually a kind of fixed-point iteration,so that Anderson acceleration can be used to improve its con-vergence speed.By adjusting the energy reduction strategy,Anderson acceleration is robust when applied to accelerate ADMM.This paper studies how to express the super-elastic body material simulation and geometric optimization problems in a unified framework,and explains that the elastic body simulation can also be accelerated by the aforementioned acceleration methods.In addition,we analyzed the relationship between Anderson acceleration and quasi-Newton method(quasi-Newton).By using the energy function values of the previous iterations,combined with Anderson's accelerated quasi-Newtonian nature,the next can-didate point can be inferred.Therefore,our method is also valid outside the classic local-global solver,and it can be applied to iterative algorithms with similar structures.We have conducted tests on various geometric optimization and physical simula-tion problems to comprehensively evaluate the performance of our method.It signif-icantly reduces the number of iterations required to calculate accurate results,and the calculation cost of each iteration only slightly increases.Its simplicity and effectiveness make it a potential tool for accelerating existing algorithms and designing efficient new algorithms.