The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high‐accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed‐point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas‐Rachford splitting reveals that ADMM is in fact a fixed‐point iteration in a lower‐dimensional space. By applying Anderson acceleration to such lower‐dimensional fixed‐point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.

No abstract uploaded!

No abstract uploaded!

The Hamiltonian cycle problem is an important problem in graph theory and computer science. It is a special case of the famous traveling salesman problem. A signicant amount of research has been done on the special cases of nding Hamiltonian cycles in subgraphs of triangular, square and hexagonal grids. However, there is little work on more complicated grids. In this paper, we investigate the hardness of Hamiltonian cycle problem in grid graphs of semiregular tessellations, which are tessellations formed by two or more kinds of regular polygons. There are only eight semiregular tessellations, and we prove that the Hamiltonian cycle problem in all of them are NP-complete by reducing from NP-complete problems, such as the Hamiltonian cycle problem in max degree 3 bipartite planar graphs. Knowing the NP-completeness of Hamiltonian cycle problem in semiregular grids indicates that there will not be any polynomial time algorithm that solves the Hamiltonian path problem in these tessellations if NP does not equal to P, which helps show the limits of ecient motion planning algorithms and provides new information about what makes problems computationally dicult to solve.

There is gained interest in understanding statistical inference under possibly non-sparse high-dimensional models. For a given component of the regression coefficient, we show that the difficulty of the problem depends on the sparsity of the corresponding row of the precision matrix of the covariates, not the sparsity of the regression coefficients. We develop new concepts of uniform and essentially uniform non-testability that allow the study of limitations of tests across a broad set of alternatives. Uniform non-testability identifies a collection of alternatives such that the power of any test, against any alternative in the group, is asymptotically at most equal to the nominal size of the test. Implications of the new constructions include new minimax testability results that in sharp contrast to the existing results, do not depend on the sparsity of the regression parameters. We identify new tradeoffs between testability and feature correlation. In particular, we show that in models with weak feature correlations minimax lower bound can be attained by a test whose power has the parametric rate regardless of the size of the model sparsity.