Abstract In this paper we prove a higher dimensional analogue of Carleson’s$$\varepsilon ^{2}$$ conjecture. Given two arbitrary disjoint Borel sets$$\Omega ^{+},\Omega ^{-}\subset \mathbb{R}^{n+1}$$ , and$$x\in \mathbb{R}^{n+1}$$ ,$$r>0$$ , we denote$$ \varepsilon _{n}(x,r) := \frac{1}{r^{n}}\, \inf _{H^{+}} \mathcal{H}^{n} \left ( ((\partial B(x,r)\cap H^{+}) \setminus \Omega ^{+}) \cup (( \partial B(x,r)\cap H^{-}) \setminus \Omega ^{-})\right ), $$ where the infimum is taken over all open affine half-spaces$$H^{+}$$ such that$$x \in \partial H^{+}$$ and we define$$H^{-}= \mathbb{R}^{n+1} \setminus \overline{H^{+}}$$ . Our first main result asserts that the set of points$$x\in \mathbb{R}^{n+1}$$ where$$ \int _{0}^{1} \varepsilon _{n}(x,r)^{2} \, \frac{dr}{r}< \infty $$ is$$n$$ -rectifiable. For our second main result we assume that$$\Omega ^{+}$$ ,$$\Omega ^{-}$$ are open and that$$\Omega ^{+}\cup \Omega ^{-}$$ satisfies the capacity density condition. For each$$x \in \partial \Omega ^{+} \cup \partial \Omega ^{-}$$ and$$r>0$$ , we denote by$$\alpha ^{\pm }(x,r)$$ the characteristic constant of the (spherical) open sets$$\Omega ^{\pm }\cap \partial B(x,r)$$ . We show that, up to a set of$$\mathcal{H}^{n}$$ measure zero,$$x$$ is a tangent point for both$$\partial \Omega ^{+}$$ and$$\partial \Omega ^{-}$$ if and only if$$ \int _{0}^{1} \min (1,\alpha ^{+}(x,r) + \alpha ^{-}(x,r) -2) \frac{dr}{r} < \infty . $$ The first result is new even in the plane and the second one improves and extends to higher dimensions the$$\varepsilon ^{2}$$ conjecture of Carleson. 
                        more » 
                        « less   
                    
                            
                            Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
                        
                    
    
            Abstract In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization withnon-Lipschitzianvalue functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a$$(T+1)$$ -stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$ -optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ , and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$ -optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization. 
        more » 
        « less   
        
    
                            - Award ID(s):
- 2316675
- PAR ID:
- 10369949
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Mathematical Programming
- Volume:
- 196
- Issue:
- 1-2
- ISSN:
- 0025-5610
- Page Range / eLocation ID:
- p. 935-985
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
- 
            
- 
            Abstract Let$$\mathbb {F}_q^d$$ be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ and a fixed nonzero$$t\in \mathbb {F}_q$$ , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ , where$$h_y:E\rightarrow \{0,1\}$$ is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ that if$$|E|\ge Cq^{\frac{11}{4}}$$ andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ isdwhenever$$E\subseteq \mathbb {F}_q^d$$ with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ .more » « less
- 
            Abstract We prove that there are$$\gg \frac{X^{\frac{1}{3}}}{(\log X)^2}$$ imaginary quadratic fieldskwith discriminant$$|d_k|\le X$$ and an ideal class group of 5-rank at least 2. This improves a result of Byeon, who proved the lower bound$$\gg X^{\frac{1}{4}}$$ in the same setting. We use a method of Howe, Leprévost, and Poonen to construct a genus 2 curveCover$$\mathbb {Q}$$ such thatChas a rational Weierstrass point and the Jacobian ofChas a rational torsion subgroup of 5-rank 2. We deduce the main result from the existence of the curveCand a quantitative result of Kulkarni and the second author.more » « less
- 
            Abstract Assuming the Riemann Hypothesis, we study negative moments of the Riemann zeta-function and obtain asymptotic formulas in certain ranges of the shift in {\zeta(s)}. For example, integrating {|\zeta(\frac{1}{2}+\alpha+it)|^{-2k}}with respect totfromTto {2T}, we obtain an asymptotic formula when the shift α is roughly bigger than {\frac{1}{\log T}}and {k<\frac{1}{2}}. We also obtain non-trivial upper bounds for much smaller shifts, as long as {\log\frac{1}{\alpha}\ll\log\log T}. This provides partial progress towards a conjecture of Gonek on negative moments of the Riemann zeta-function, and settles the conjecture in certain ranges. As an application, we also obtain an upper bound for the average of the generalized Möbius function.more » « less
- 
            Abstract Rooted binarygalledtrees generalize rooted binary trees to allow a restricted class of cycles, known asgalls. We build upon the Wedderburn-Etherington enumeration of rooted binary unlabeled trees withnleaves to enumerate rooted binary unlabeled galled trees withnleaves, also enumerating rooted binary unlabeled galled trees withnleaves andggalls,$$0 \leqslant g \leqslant \lfloor \frac{n-1}{2} \rfloor $$ . The enumerations rely on a recursive decomposition that considers subtrees descended from the nodes of a gall, adopting a restriction on galls that amounts to considering only the rooted binarynormalunlabeled galled trees in our enumeration. We write an implicit expression for the generating function encoding the numbers of trees for alln. We show that the number of rooted binary unlabeled galled trees grows with$$0.0779(4.8230^n)n^{-\frac{3}{2}}$$ , exceeding the growth$$0.3188(2.4833^n)n^{-\frac{3}{2}}$$ of the number of rooted binary unlabeled trees without galls. However, the growth of the number of galled trees with only one gall has the same exponential order 2.4833 as the number with no galls, exceeding it only in the subexponential term,$$0.3910n^{\frac{1}{2}}$$ compared to$$0.3188n^{-\frac{3}{2}}$$ . For a fixed number of leavesn, the number of gallsgthat produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of$$g=0$$ and the maximum of$$g=\lfloor \frac{n-1}{2} \rfloor $$ . We discuss implications in mathematical phylogenetics.more » « less
 An official website of the United States government
An official website of the United States government 
				
			 
					 
					
