Browsing by Subject "ADMM"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Efficient and Robust ADMM Methods for Dynamics and Geometry Optimization(2022-01) Brown, GeorgeWe present novel ADMM-based methods for efficiently solving problems in a variety of applications in computer graphics. First, in the domain of physics-based animation we propose new techniques for simulating elastic bodies subject to dissipative forces. Second, in the field of geometry optimization we introduce a new algorithm for quasi-static deformation and surface parameterization. In each of these applications our proposed methods robustly converge to accurate solutions, and do so faster than existing algorithms. We achieve this by using key insights to address and overcome many limitations of standard solvers. Here we highlight the features of our two new algorithms for the aforementioned problems. Then we summarize our preliminary investigations into new techniques we designed in pursuit of faster and more reliable convergence in parameterization problems. Our first method is one for incorporating dissipative forces into optimization-based time integration schemes, which hitherto have been applied almost exclusively to systems with only conservative forces. We represent such forces using dissipation functions that may be nonlinear in both positions and velocities, enabling us to model a range of dissipative effects including Coulomb friction, Rayleigh damping, and power-law dissipation. To improve accuracy and minimize artificial damping, we provide an optimization-based version of the second-order accurate TR-BDF2 integrator. Finally, we present a method for modifying arbitrary dissipation functions to conserve linear and angular momentum, allowing us to eliminate the artificial angular momentum loss caused by Rayleigh damping. Our second method is designed to efficiently solve geometry optimization problems. We observe that in this domain existing local-global solvers such as ADMM struggle to resolve large rotations such as bending and twisting modes, and large distortions in the presence of barrier energies. We propose two improvements to address these challenges. First, we introduce a novel local-global splitting based on the polar decomposition that separates the geometric nonlinearity of rotations from the material nonlinearity of the deformation energy. The resulting ADMM-based algorithm is a combination of an L-BFGS solve in the global step and proximal updates of element stretches in the local step. We also introduce a novel method for dynamic reweighting that is used to adjust element weights at runtime for improved convergence. With both improved rotation handling and element weighting, our WRAPD algorithm is considerably faster than state-of-the-art approaches for quasi-static simulations. WRAPD is also much faster at making early progress in parameterization problems, making it valuable as an initializer to jump-start second-order algorithms. Finally, we investigate two possible extensions to WRAPD for accelerated convergence in parameterization problems. The first extension, P-WRAPD, leverages progressive reference shape updates similar to Liu et al. [2018] to bound distortion. We show that this yields minor improvements in a subset of examples. Our second extension, N-WRAPD, uses a non-scalar weighting scheme that independently assigns unique weights for every mode of deformation. This method shows promising preliminary results. Although slightly less stable, N-WRAPD generally converges significantly faster at a rate comparable to second-order algorithms.Item Unconventional Regression for High-Dimensional Data Analysis(2017-06) Gu, YuwenMassive and complex data present new challenges that conventional sparse penalized mean regressions, such as the penalized least squares, cannot fully solve. For example, in high-dimensional data, non-constant variance, or heteroscedasticity, is commonly present but often receives little attention in penalized mean regressions. Heavy-tailedness is also frequently encountered in many high-dimensional scientific data. To resolve these issues, unconventional sparse regressions such as penalized quantile regression and penalized asymmetric least squares are the appropriate tools because they can infer the complete picture of the entire probability distribution. Asymmetric least squares regression has wide applications in statistics, econometrics and finance. It is also an important tool in analyzing heteroscedasticity and is computationally friendlier than quantile regression. The existing work on asymmetric least squares only considers the traditional low dimension and large sample setting. We systematically study the Sparse Asymmetric LEast Squares (SALES) under high dimensionality and fully explore its theoretical and numerical properties. SALES may fail to tell which variables are important for the mean function and which variables are important for the scale/variance function, especially when there are variables that are important for both mean and scale. To that end, we further propose a COupled Sparse Asymmetric LEast Squares (COSALES) regression for calibrated heteroscedasticity analysis. Penalized quantile regression has been shown to enjoy very good theoretical properties in the literature. However, the computational issue of penalized quantile regression has not yet been fully resolved in the literature. We introduce fast alternating direction method of multipliers (ADMM) algorithms for computing penalized quantile regression with the lasso, adaptive lasso, and folded concave penalties. The convergence properties of the proposed algorithms are established and numerical experiments demonstrate their computational efficiency and accuracy. To efficiently estimate coefficients in high-dimensional linear models without prior knowledge of the error distributions, sparse penalized composite quantile regression (CQR) provides protection against significant efficiency decay regardless of the error distribution. We consider both lasso and folded concave penalized CQR and establish their theoretical properties under ultrahigh dimensionality. A unified efficient numerical algorithm based on ADMM is also proposed to solve the penalized CQR. Numerical studies demonstrate the superior performance of penalized CQR over penalized least squares under many error distributions.