General upper tail estimates are given for counting edges in a random induced subhypergraph of a fixed hypergraph ℋ, with an easy proof by estimating the moments. As an application we consider the numbers of arithmetic progressions and Schur triples in random subsets of integers. In the second part of the paper we return to the subgraph counts in random graphs and provide upper tail estimates in the rooted case.

We propose an efficient threshold dynamics method for topology optimization for fluids modeled with the Stokes equation. The proposed algorithm is based on minimization of an objective energy function that consists of the dissipation power in the fluid and the perimeter approximated by nonlocal energy, subject to a fluid volume constraint and the incompressibility condition. We show that the minimization problem can be solved with an iterative scheme in which the Stokes equation is approximated by a Brinkman equation. The indicator functions of the fluid-solid regions are then updated according to simple convolutions followed by a thresholding step. We demonstrate mathematically that the iterative algorithm has the total energy decaying property. The proposed algorithm is simple and easy to implement. A simple adaptive time strategy is also used to accelerate the convergence of the iteration. Extensive numerical experiments in both two and three dimensions show that the proposed iteration algorithm is quite robust and converges in much fewer iterations and is more efficient than many existing methods.

In a uniform random recursive$k$-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to$n$, chooses$k$uniform random parents from among the nodes of smaller index. If$S$_{$n$}is the shortest path distance from node$n$to the root, then we determine the constant$σ$such that$S$_{$n$}/log$n$→$σ$in probability as$n$→∞. We also show that max_{1≤$i$≤$n$}$S$_{$i$}/log$n$→$σ$in probability.

In this paper,we establish the convergence of the proximal alternating direction method of multipliers (ADMM) and block coordinate descent (BCD) method for nonseparable minimization models with quadratic coupling terms. The novel convergence results presented in this paper answer several open questions that have been the subject of considerable discussion. We firstly extend the 2-block proximal ADMM to linearly constrained convex optimization with a coupled quadratic objective function, an area where theoretical understanding is currently lacking, and prove that the sequence generated by the proximal ADMM converges in point-wise manner to a primal-dual solution pair. Moreover, we apply randomly permuted ADMM (RPADMM) to nonseparable multi-block convex optimization, and prove its expected convergence for a class of nonseparable quadratic programming problems. When the linear constraint vanishes, the 2-block proximal ADMM and RPADMM reduce to the 2-block cyclic proximal BCD method and randomly permuted BCD (RPBCD). Our study provides the first iterate convergence result for 2-block cyclic proximal BCD without assuming the boundedness of the iterates. We also theoretically establish the expected iterate convergence result concerning multi-block RPBCD for convex quadratic optimization. In addition, we demonstrate that RPBCD may have a worse convergence rate than cyclic proximalBCDfor 2-block convex quadratic minimization problems. Although the results on RPADMM and RPBCD are restricted to quadratic minimization models, they provide some interesting insights: (1) random permutation makes ADMM and BCD more robust for multi-block convex minimization problems; (2) cyclic BCD may outperform RPBCD for “nice” problems, and RPBCD should be applied with caution when solving general convex optimization problems especially with a few blocks.

Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an “inspect” phase to existing algorithms that helps escape from non-global stationary points. The inspection samples a set of points in a radius R around the current point. When a sample point yields a sufficient decrease in the objective, we resume an existing algorithm from that point. If no sufficient decrease is found, the current point is called an approximate R-local minimizer. We show that an R-local minimizer is globally optimal, up to a specific error depending on R, if the objective function can be implicitly decomposed into a smooth convex function plus a restricted function that is possibly nonconvex, nonsmooth. Therefore, for such nonconvex objective functions, verifying global optimality is fundamentally easier. For high-dimensional problems, we introduce blockwise inspections to overcome the curse of dimensionality while still maintaining optimality bounds up to a factor equal to the number of blocks. Our method performs well on a set of artificial and realistic nonconvex problems by coupling with gradient descent, coordinate descent, EM, and prox-linear algorithms.