A primal-dual large-update interior-point algorithm for <Emphasis Type="Italic">P</Emphasis><Subscript>*</Subscript>(<Emphasis Type="Italic">κ</Emphasis>)-LCP based on a new class of kernel functions

In this paper, we propose a large-update primal-dual interior point algorithm for P_*(κ)-linear complementarity problem. The method is based on a new class of kernel functions which is neither classical logarithmic function nor self-regular functions. It is determines both search directions and the proximity measure between the iterate and the center path. We show that if a strictly feasible starting point is available, then the new algorithm has \(o\left( {(1 + 2k)p\sqrt n {{\left( {\frac{1}{p}\log n + 1} \right)}^2}\log \frac{n}{\varepsilon }} \right)\)iteration complexity which becomes \(o\left( {(1 + 2k)\sqrt n log{\kern 1pt} {\kern 1pt} n\log \frac{n}{\varepsilon }} \right)\)with special choice of the parameter p. It is matches the currently best known iteration bound for P_*(κ)-linear complementarity problem. Some computational results have been provided.     

New parameterized kernel functions for linear optimization

Recent studies on the kernel function-based primal-dual interior-point algorithms indicate that a kernel function not only represents a measure of the distance between the iteration and the central path, but also plays a critical role in improving the computational complexity of an interior-point algorithm. In this paper, we propose a new class of parameterized kernel functions for the development of primal-dual interior-point algorithms for solving linear programming problems. The properties of the proposed kernel functions and corresponding parameters are investigated. The results lead to a complexity bounds of ${O\left(\sqrt{n}\,{\rm log}\,n\,{\rm log}\,\frac{n}{\epsilon}\right)}$ for the large-update primal-dual interior point methods. To the best of our knowledge, this is the best known bound achieved.     

Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term

In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(\sqrt{n}\log(\frac{n}{\epsilon}))$ for small-update methods and $O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods.     

A full-Newton step feasible interior-point algorithm for P_*(\kappa )-linear complementarity problems

In this paper, a full-Newton step feasible interior-point algorithm is proposed for solving $P_*(\kappa )$ -linear complementarity problems. We prove that the full-Newton step to the central path is local quadratically convergent and the proposed algorithm has polynomial iteration complexity, namely, $O\left( (1+4\kappa )\sqrt{n}\log {\frac{n}{\varepsilon }}\right) $ , which matches the currently best known iteration bound for $P_*(\kappa )$ -linear complementarity problems. Some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithm.     

Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier

In this paper, we present primal-dual interior-point methods for convex quadratic optimization based on a finite barrier, which has been investigated earlier for the case of linear optimization by Bai et al. (SIAM J Optim 13(3):766–782, 2003). By means of the feature of the finite kernel function, we study the complexity analysis of primal-dual interior-point methods based on the finite barrier and derive the iteration bounds that match the currently best known iteration bounds for large- and small-update methods, namely, $O(\sqrt{n}\log{n}\log{\frac{n}{\varepsilon}})$ and $O(\sqrt{n}\log{\frac{n}{\varepsilon}})$ , respectively, which are as good as the linear optimization analogue. Numerical tests demonstrate the behavior of the algorithms with different parameters.     

First-order algorithm with {\mathcal{O}({\rm ln}(1{/}\epsilon))} convergence for {\epsilon}-equilibrium in two-person zero-sum games

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x \in Q_1}\max_{y \in Q_2} {x}^{\rm T}{Ay} = \max_{y \in Q_2} \min_{x \in Q_1} {x}^{\rm T}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an ${\epsilon}$ -equilibrium to this min-max problem in ${\mathcal {O}\left(\frac{\|A\|}{\delta(A)} \, {\rm ln}(1{/}\epsilon)\right)}$ first-order iterations, where δ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required ${\mathcal {O}(1{/}\epsilon)}$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on ${\epsilon}$ . Unlike interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov’s method with an outer loop that lowers the target ${\epsilon}$ between iterations (this target affects the amount of smoothing in the inner loop). Computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).     

On a theorem of Jackson

We prove that $$\mathop {L_n \in Z_n }\limits^{\inf } \mathop \omega \limits^{sup^* } \mathop {f \in H_\omega }\limits^{\sup } \frac{{\left\| {f - L_n \left( f \right)} \right\|}}{{\omega \left( {\frac{\pi }{{n + 1}}} \right)}} = 1\left( {n = 0,1,2,...} \right)$$ (n=0,1,2,...), where \(\mathop {L_n \in Z_n }\limits^{\inf } \) is taken over all linear polynomial approximation methods of degree not higher than n and \(\mathop \omega \limits^{sup^* } \) over all convex moduli of continuity ω(δ).     

Asymptotic properties for the loglog laws under positive association

Let {X _n : n ?? 1} be a strictly stationary sequence of positively associated random variables with mean zero and finite variance. Set $S_n = \sum\limits_{k = 1}^n {X_k }$ , $Mn = \mathop {\max }\limits_{k \leqslant n} \left| {S_k } \right|$ , n ?? 1. Suppose that $0 < \sigma ^2 = EX_1^2 + 2\sum\limits_{k = 2}^\infty {EX_1 X_k < \infty }$ . In this paper, we prove that if E|X ₁|^2+?? < for some ?? ?? (0, 1], and $\sum\limits_{j = n + 1}^\infty {Cov\left( {X_1 ,X_j } \right) = O\left( {n^{ - \alpha } } \right)}$ for some ?? > 1, then for any b > ?1/2 $$\mathop {\lim }\limits_{\varepsilon \searrow 0} \varepsilon ^{2b + 1} \sum\limits_{n = 1}^\infty {\frac{{(\log \log n)^{b - 1/2} }} {{n^{3/2} \log n}}} E\left\{ {M_n - \sigma \varepsilon \sqrt {2n\log \log n} } \right\}_ + = \frac{{2^{ - 1/2 - b} E\left| N \right|^{2(b + 1)} }} {{(b + 1)(2b + 1)}}\sum\limits_{k = 0}^\infty {\frac{{( - 1)^k }} {{(2k + 1)^{2(b + 1)} }}}$$ and $$\mathop {\lim }\limits_{\varepsilon \nearrow \infty } \varepsilon ^{ - 2(b + 1)} \sum\limits_{n = 1}^\infty {\frac{{(\log \log n)^b }} {{n^{3/2} \log n}}E\left\{ {\sigma \varepsilon \sqrt {\frac{{\pi ^2 n}} {{8\log \log n}}} - M_n } \right\}} _ + = \frac{{\Gamma (b + 1/2)}} {{\sqrt 2 (b + 1)}}\sum\limits_{k = 0}^\infty {\frac{{( - 1)^k }} {{(2k + 1)^{2b + 2} }}} ,$$ where x ₊ = max{x, 0}, N is a standard normal random variable, and ??(·) is a Gamma function.     

Interior-point algorithms for P_{*}(\kappa )-LCP based on a new class of kernel functions

In this paper, we propose interior-point algorithms for $P_* (\kappa )$ -linear complementarity problem based on a new class of kernel functions. New search directions and proximity measures are defined based on these functions. We show that if a strictly feasible starting point is available, then the new algorithm has $\mathcal{O }\bigl ((1+2\kappa )\sqrt{n}\log n \log \frac{n\mu ^0}{\epsilon }\bigr )$ and $\mathcal{O }\bigl ((1+2\kappa )\sqrt{n} \log \frac{n\mu ^0}{\epsilon }\bigr )$ iteration complexity for large- and small-update methods, respectively. These are the best known complexity results for such methods.     

Expose-and-merge exploration and the chromatic number of a random graph

The expose-and-merge paradigm for exploring random graphs is presented. An algorithm of complexityn ^O(logn) is described and used to show that the chromatic number of a random graph for any edge probability 0<p<1 falls in the interval $$\left[ {\left( {\frac{1}{2} - \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}, \left( {\frac{2}{3} + \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}} \right]$$ with probability approaching unity asn→∞.     

On the entire self-shrinking solutions to Lagrangian mean curvature flow

The authors prove that the logarithmic Monge?CAmpère flow with uniformly bound and convex initial data satisfies uniform decay estimates away from time t?=?0. Then applying the decay estimates, we conclude that every entire classical strictly convex solution of the equation $$ \det D^{2}u=\exp\left\{n\left(-u+\frac{1}{2} \sum_{i=1}^{n}x_{i} \frac{\partial u}{\partial x_{i}} \right)\right\}, $$ should be a quadratic polynomial if the inferior limit of the smallest eigenvalue of the function |x|² D ² u at infinity has an uniform positive lower bound larger than 2(1 ? 1/n). Using a similar method, we can prove that every classical convex or concave solution of the equation $$ \sum_{i=1}^{n} \arctan\lambda_{i}=-u+\frac{1}{2} \sum_{i=1}^{n}x_{i} \frac{\partial u}{\partial x_{i}} $$ must be a quadratic polynomial, where ?? _i are the eigenvalues of the Hessian D ² u.     

Sharp weak-type inequalities for Hilbert transform and Riesz projection

The paper is devoted to the study of the weak norms of the classical operators in the vector-valued setting.

1. Let S, H denote the singular integral involution operator and the Hilbert transform on $L^p \left( {\mathbb{T}, \ell _\mathbb{C}^2 } \right)$ , respectively. Then for 1 ≤ p ≤ 2 and any f, $$\left\| {\mathcal{S}f} \right\|_{p,\infty } \leqslant \left( {\frac{1} {\pi }\int_{ - \infty }^\infty {\frac{{\left| {\tfrac{2} {\pi }\log \left| t \right|} \right|^p }} {{t^2 + 1}}dt} } \right)^{ - 1/p} \left\| f \right\|p,$$ $$\left\| {\mathcal{H}f} \right\|_{p,\infty } \leqslant \left( {\frac{1} {\pi }\int_{ - \infty }^\infty {\frac{{\left| {\tfrac{2} {\pi }\log \left| t \right|} \right|^p }} {{t^2 + 1}}dt} } \right)^{ - 1/p} \left\| f \right\|p.$$ Both inequalities are sharp.
2. Let P ₊ and P _? stand for the Riesz projection and the co-analytic projection on $L^p \left( {\mathbb{T}, \ell _\mathbb{C}^2 } \right)$ , respectively. Then for 1 ≤ p ≤ 2 and any f, $$\left\| {P + f} \right\|_{p,\infty } \leqslant \left\| f \right\|_p ,$$ $$\left\| {P - f} \right\|_{p,\infty } \leqslant \left\| f \right\|_p .$$ Both inequalities are sharp.
3. We establish the sharp versions of the estimates above in the nonperiodic case.

The results are new even if the operators act on complex-valued functions. The proof rests on the construction of an appropriate plurisubharmonic function and probabilistic techniques.     

On the discrepancy function in arbitrary dimension, close to L 1

Let A _N to be N points in the unit cube in dimension d, and consider the discrepancy function $$ D_N (\vec x): = \sharp \left( {\mathcal{A}_N \cap \left[ {\vec 0,\vec x} \right)} \right) - N\left| {\left[ {\vec 0,\vec x} \right)} \right| $$ Here, $$ \vec x = \left( {\vec x,...,x_d } \right),\left[ {0,\vec x} \right) = \prod\limits_{t = 1}^d {\left[ {0,x_t } \right),} $$ and $ \left| {\left[ {0,\vec x} \right)} \right| $ denotes the Lebesgue measure of the rectangle. We show that necessarily $$ \left\| {D_N } \right\|_{L^1 (log L)^{(d - 2)/2} } \gtrsim \left( {log N} \right)^{\left( {d - 1} \right)/2} . $$ In dimension d = 2, the ‘log L’ term has power zero, which corresponds to a Theorem due to [11]. The power on log L in dimension d ≥ 3 appears to be new, and supports a well-known conjecture on the L ¹ norm of D _N . Comments on the discrepancy function in Hardy space also support the conjecture.     

The Concentration Function of Additive Functions with Special Weight

Suppose that $${g\left( n \right)}$$ is an additive real-valued function, W(N) = 4+ $$\mathop {\min }\limits_\lambda $$ ( λ₂ + $$\sum\limits_{p < N} {\frac{1}{2}} $$ min (1, ( g(p) - λlog p)²), E(N) = 4+1 $$\sum\limits_{\mathop {p < N,}\limits_{g(p) \ne 0} } {\frac{1}{p}.} $$ In this paper, we prove the existence of constants C₁, C₂ such that the following inequalities hold: $\mathop {\sup }\limits_a \geqslant \left| {\left\{ {n, m, k: m, k \in \mathbb{Z},n \in \mathbb{N},n + m^2 + k^2 } \right.} \right. = \left. {\left. {N,{\text{ }}g(n) \in [a,a + 1)} \right\}} \right| \leqslant \frac{{C_1 N}}{{\sqrt {W\left( N \right)} }},$ $\mathop {\sup }\limits_a \geqslant \left| {\left\{ {n, m, k: m, k \in \mathbb{Z},n \in \mathbb{N},n + m^2 + k^2 } \right.} \right. = \left. {\left. {N,{\text{ }}g(n) = a} \right\}} \right| \leqslant \frac{{C_2 N}}{{\sqrt {E\left( N \right)} }},$ . The obtained estimates are order-sharp.     

Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement

The induced path number ρ(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path.Broere et al.proved that if G is a graph of order n,then n~(1/2) ≤ρ(G) + ρ(■) ≤ [3n/2].In this paper,we characterize the graphs G for which ρ(G) + ρ(■) = [3n/2],improve the lower bound on ρ(G) + ρ(■) by one when n is the square of an odd integer,and determine a best possible upper bound for ρ(G) + ρ(■) when neither G nor ■ has isolated vertices.     

Strong convergence in nonparametric estimation of regression functions

The nonparametric regression problem has the objective of estimating conditional expectation. Consider the model $$Y = R(X) + Z$$ , where the random variableZ has mean zero and is independent ofX. The regression functionR(x) is the conditional expectation ofY givenX = x. For an estimator of the form $$R_n (x) = \sum\limits_{i = 1}^n {Y_i K{{\left[ {{{\left( {x - X_i } \right)} \mathord{\left/ {\vphantom {{\left( {x - X_i } \right)} {c_n }}} \right. \kern-\nulldelimiterspace} {c_n }}} \right]} \mathord{\left/ {\vphantom {{\left[ {{{\left( {x - X_i } \right)} \mathord{\left/ {\vphantom {{\left( {x - X_i } \right)} {c_n }}} \right. \kern-\nulldelimiterspace} {c_n }}} \right]} {\sum\limits_{i = 1}^n {K\left[ {{{\left( {x - X_i } \right)} \mathord{\left/ {\vphantom {{\left( {x - X_i } \right)} {c_n }}} \right. \kern-\nulldelimiterspace} {c_n }}} \right]} }}} \right. \kern-\nulldelimiterspace} {\sum\limits_{i = 1}^n {K\left[ {{{\left( {x - X_i } \right)} \mathord{\left/ {\vphantom {{\left( {x - X_i } \right)} {c_n }}} \right. \kern-\nulldelimiterspace} {c_n }}} \right]} }}} $$ , we obtain the rate of strong uniform convergence $$\mathop {\sup }\limits_{x\varepsilon C} \left| {R_n (x) - R(x)} \right|\mathop {w \cdot p \cdot 1}\limits_ = o({{n^{{1 \mathord{\left/ {\vphantom {1 {(2 + d)}}} \right. \kern-\nulldelimiterspace} {(2 + d)}}} } \mathord{\left/ {\vphantom {{n^{{1 \mathord{\left/ {\vphantom {1 {(2 + d)}}} \right. \kern-\nulldelimiterspace} {(2 + d)}}} } {\beta _n \log n}}} \right. \kern-\nulldelimiterspace} {\beta _n \log n}}),\beta _n \to \infty $$ . HereX is ad-dimensional variable andC is a suitable subset ofR ^d .     

Some properties of elliptic Riesz means at critical index on Hp(TH)

Suppose f∈H^p(Tⁿ), 0 _r ^δ , δ=n/p?(n+1)/2. In this paper we eastablish the following inequality $$\mathop {\sup }\limits_{R > 1} \left\{ {\frac{1}{{\log R}}\int_1^R {\left\| {\sigma _r^\delta } \right\|_{H^p (T^R )}^p \frac{{dr}}{r}} } \right\}^{1/p} \leqslant C_{R,p} \left\| f \right\|_{H^p (T^R )} $$ It implies that $$\mathop {\lim }\limits_{R \to \infty } \frac{1}{{\log R}}\int_1^R {\left\| {\sigma _r^\delta - f} \right\|_{H^p (T^R )}^p \frac{{dr}}{r}} = 0$$ Moreover we obtain the same conclusion when p=1 and n=1.     

The Concentration Function of Additive Functions with Nonmultiplicative Weight

Suppose that g(n) is a real-valued additive function and τ(n) is the number of divisors of n. In this paper, we prove that there exists a constant C such that $\sup \limits_a \sum\limits_{n<N}{g(n) \in [a,a+1)} \tau(N-n) \leqslant C \frac{N \log N}{\sqrt{W(N)}},$ where $W(N) = 4 + \mathop {min}\limits_\lambda \left( {\lambda ^2 + \sum\limits_{p < N} {\frac{1}{p}} min(1,(g(p) - \lambda log p)^2 )} \right).$ . In particular, it follows from this result that $\mathop {\sup }\limits_a |\{ m,n:mn < N,g(N - mn) = a\} | \ll N\log N\left( {\sum\limits_{p < N,g\left( p \right) \ne 0} {(1/p)} } \right)^{ - 1/2} .$ The implicit constant is absolute.     

Height of a Superposition

We observe that, given a poset ${\left( {E,{\user1{\mathcal{R}}}} \right)}$ and a finite covering ${\user1{\mathcal{R}}} = {\user1{\mathcal{R}}}_{1} \cup \cdots \cup {\user1{\mathcal{R}}}_{n} $ of its ordering, the height of the poset does not exceed the natural product of the heights of the corresponding sub-relations: $$\mathfrak{h}{\left( {E,{\user1{\mathcal{R}}}} \right)} \leqslant \mathfrak{h}{\left( {E,{\user1{\mathcal{R}}}_{1} } \right)} \otimes \cdots \otimes \mathfrak{h}{\left( {E,{\user1{\mathcal{R}}}_{n} } \right)}.$$ Conversely for every finite sequence $(\xi_1,\cdots,\xi_n)$ of ordinals, every poset ${\left( {E,{\user1{\mathcal{R}}}} \right)}$ of height at most $\xi_1\otimes\cdots\otimes\xi_n$ admits a partition ${\left( {{\user1{\mathcal{R}}}_{1} , \cdots ,{\user1{\mathcal{R}}}_{n} } \right)}$ of its ordering ${\user1{\mathcal{R}}}$ such that each ${\left( {E,{\user1{\mathcal{R}}}_{k} } \right)}$ has height at most $\xi_k$ . In particular for every finite sequence $(\xi_1,\cdots,\xi_n)$ of ordinals, the ordinal $$\xi _{1} \underline{ \otimes } \cdots \underline{ \otimes } \xi _{n} : = \sup {\left\{ {{\left( {\xi ^{\prime }_{1} \otimes \cdots \otimes \xi ^{\prime }_{n} } \right)} + 1:\xi ^{\prime }_{1} < \xi _{1} , \cdots ,\xi ^{\prime }_{n} < \xi _{n} } \right\}}$$ is the least $\xi$ for which the following partition relation holds $$\mathfrak{H}_{\xi } \to {\left( {\mathfrak{H}_{{\xi _{1} }} , \cdots ,\mathfrak{H}_{{\xi _{n} }} } \right)}^{2} $$ meaning: for every poset ${\left( {A,{\user1{\mathcal{R}}}} \right)}$ of height at least $\xi$ and every finite covering ${\left( {{\user1{\mathcal{R}}}_{1} , \cdots ,{\user1{\mathcal{R}}}_{n} } \right)}$ of its ordering ${\user1{\mathcal{R}}}$ , there is a $k$ for which the relation ${\left( {A,{\user1{\mathcal{R}}}_{k} } \right)}$ has height at least $\xi_k$ . The proof will rely on analogue properties of vertex coverings w.r.t. the natural sum.