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.     

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.     

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.     

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).     

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.     

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.     

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.     

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.     

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.     

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.     

Convergence in measure of strong logarithmic means of double Fourier series

Nörlund strong logarithmic means of double Fourier series acting from space L log L \(\left( {\mathbb{T}^2 } \right)\) into space L _p \(\left( {\mathbb{T}^2 } \right)\) , 0 < p < 1, are studied. The maximal Orlicz space such that the Nörlund strong logarithmic means of double Fourier series for the functions from this space converge in two-dimensional measure is found.     

Orthogonality properties of linear combinations of orthogonal polynomials II

Let and be polynomials orthogonal on the unit circle with respect to the measures dσ and dμ, respectively. In this paper we consider the question how the orthogonality measures dσ and dμ are related to each other if the orthogonal polynomials are connected by a relation of the form , for , where . It turns out that the two measures are related by if , where and are known trigonometric polynomials of fixed degree and where the 's are the zeros of on . If the 's and 's are uniformly bounded then (under some additional conditions) much more can be said. Indeed, in this case the measures dσ and dμ have to be of the form and , respectively, where are nonnegative trigonometric polynomials. Finally, the question is considered to which weight functions polynomials of the form where denotes the reciprocal polynomial of , can be orthogonal. This revised version was published online in June 2006 with corrections to the Cover Date.     

Lower Bounds for the Riemann Zeta Function on the Critical Line

We establish a relation between the lower bound for the maximum of the modulus of $\zeta (1/2 + iT + s)$ in the disk $|s| \leqslant H$ and the lower bound for the maximum of the modulus of $\zeta (1/2 + iT + it)$ on the closed interval $|t| \leqslant H$ for $0 < H(T) \leqslant {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}$ . We prove a theorem on the lower bound for the maximum of the modulus of $0 < H(T) \leqslant {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}$ on the closed interval $|t| \leqslant H$ for $40 \leqslant H(T) \leqslant \log \log T$ .     

Extreme Values of Automorphic L-Functions

Ω-theorems for some automorphic L-functions and, in particular, for the Rankin?Selberg L-function L(s, f × f) are considered. For example, as t tends to infinity, $$ \log \left| {L\left( {\frac{1}{2}+it,f\times f} \right)} \right|={\varOmega_{+}}\left( {{{{\left( {\frac{{\log t}}{{\log\;\log t}}} \right)}}^{1/2 }}} \right) $$ and $$ \log \left| {L\left( {{\sigma_0}+it,f\times f} \right)} \right|={\varOmega_{+}}\left( {{{{\left( {\frac{{\log t}}{{\log\;\log t}}} \right)}}^{{1-{\sigma_0}}}}} \right) $$ For a fixed σ ₀ ∈ $ \left( {\frac{1}{2},1} \right) $ . Bibliography: 15 titles.     

Asymptotic behavior of multiperiodic functionsG(x) = \prod\limits_{n = 1}^\infty {g(x/2^n )}

Let 0≤g be a dyadic Hölder continuous function with period 1 and g(0)=1, and let $G(x) = \prod\nolimits_{n = 0}^\infty {g(x/{\text{2}}^n )} $ . In this article we investigate the asymptotic behavior of $\smallint _0^{\rm T} \left| {G(x)} \right|^q dx$ and $\frac{1}{n}\sum\nolimits_{k = 0}^n {\log g(2^k x)} $ using the dynamical system techniques: the pressure function and the variational principle. An algorithm to calculate the pressure is presented. The results are applied to study the regulatiry of wavelets and Bernoulli convolutions.