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.     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

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.     

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.     

A Predictor-corrector algorithm with multiple corrections for convex quadratic programming

Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convex quadratic programming (QP). We introduce a (scaled) proximity measure and a dynamical forcing factor (centering parameter). The latter is used to force the duality gap to decrease. The algorithm can decrease the duality gap monotonically. Polynomial complexity can be proved and the result coincides with the best one for LP, namely, $O(\sqrt{n}\log n\mu^{0}/\varepsilon)$ .     

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\mathcal D $ D , consisting of $n$ n tetrahedra with positive weights, and a real number $\varepsilon \in (0,1)$ ε ∈ ( 0 , 1 ) , our algorithm constructs paths in $\mathcal D $ D from a fixed source vertex to all vertices of $\mathcal D $ D , the costs of which are at most $1+\varepsilon $ 1 + ε times the costs of (weighted) shortest paths, in $O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$ O ( C ( D ) n ε 2.5 log n ε log 3 1 ε ) time, where $\mathcal{C }(\mathcal D )$ C ( D ) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.     

Polynomial interior-point algorithm for P * {(\kappa)} horizontal linear complementarity problems

In this paper an interior-point algorithm for P _*(κ) horizontal linear complementarity problems is proposed that uses new search directions. The theoretical complexity of the new algorithm is calculated. It is investigated that the proposed algorithm has quadratically convergent with polynomial iteration complexity $O((1+\kappa)\sqrt{n}\log\frac{n}{\varepsilon})$ , coincide with the best known iteration bound for P _*(κ) horizontal linear complementarity problems.     

A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function

In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be $O\left( {\sqrt n \left( {\log n} \right)^2 \log \frac{n} {\varepsilon }} \right)$ . This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization fields. Some computational results have been provided.     

Optimal rate of integration and ɛ-entropy of a class of analytic functions

The author considers a class F of analytic functions real in the interval [-1, 1] and bounded in the unit circle. As an estimate of the optimal quadrature error R(n) over the class F it is shown that $$_e - \left( {2\sqrt 2 + \frac{1}{{\sqrt 2 }}} \right)\pi \sqrt n \leqslant R(n) \leqslant e^{ - \frac{\pi }{{\sqrt 2 }}n} .$$ With the additional condition that \(\mathop {max}\limits_{x \in [ - 1,1]}\) ¦f(x)¦?B, an estimate is obtained for the ?-entropy H_?(F): $$\frac{8}{{27}}\frac{{(1n2)^2 }}{{\pi ^2 }} \leqslant \mathop {\lim }\limits_{\varepsilon \to 0} \frac{{H_\varepsilon (F)}}{{\left( {\log \frac{1}{\varepsilon }} \right)^3 }} \leqslant \frac{2}{{\pi ^2 }}(1n2)^2 .$$      

The geometric Neumann problem for the Liouville equation

Let Ω denote the upper half-plane ${\mathbb{R}_+^2}$ or the upper half-disk ${D_{\varepsilon}^+\subset \mathbb{R}_+^2}$ of center 0 and radius ${\varepsilon}$ . In this paper we classify the solutions ${v\in\;C^2(\overline{\Omega}\setminus\{0\})}$ to the Neumann problem $$\left\{\begin{array}{lll}{\Delta v+2 Ke^v=0\quad {\rm in}\,\Omega\subseteq \mathbb{R}^2_+=\{(s, t)\in \mathbb{R}^2: t >0 \},}\\ {\frac{\partial v}{\partial t}=c_1e^{v/2}\quad\quad\quad{\rm on}\,\partial\Omega\cap\{s >0 \},}\\ {\frac{\partial v}{\partial t}=c_2e^{v/2}\quad\quad\quad{\rm on}\,\partial\Omega\cap\{s <0 \},}\end{array}\right.$$ where ${K, c_1, c_2 \in \mathbb{R}}$ , with the finite energy condition ${\int_{\Omega} e^v < \infty}$ As a result, we classify the conformal Riemannian metrics of constant curvature and finite area on a half-plane that have a finite number of boundary singularities, not assumed a priori to be conical, and constant geodesic curvature along each boundary arc.     

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.     

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.     

Symplectic mean curvature flow in CP 2

Let Σ be an immersed symplectic surface in CP ² with constant holomorphic sectional curvature k > 0. Suppose Σ evolves along the mean curvature flow in CP ². In this paper, we show that the symplectic mean curvature flow exists for long time and converges to a holomorphic curve if the initial surface satisfies ${|A|^2 \leq \lambda|H|^2 + \frac{2\lambda-1}{\lambda}k}$ and ${\cos\alpha\geq\sqrt{\frac{7\lambda-3}{3\lambda}}\left(\frac{1}{2} < \lambda\leq\frac{2}{3}\right) {\rm or} |A|^2\leq \frac{2}{3}|H|^2+\frac{4}{5}k\cos\alpha\, {\rm and} \cos\alpha\geq 1-\varepsilon}$ , for some ${\varepsilon}$ .     

Zur Abschätzung der Partitionsfunktion p(n) mit elementaren Mitteln

If p(n) denotes the number of all partitions n=n₁+...+=n_r of a natural number n, the inequality $$(\alpha - \varepsilon )\sqrt n< \log p(n)(with3\alpha = \pi \sqrt 6 )$$ (with 3α=π√6) holds for all n>N(ε). It is shown in the paper, that one can choose $$N(\varepsilon ) = \left( {\frac{{16}}{\varepsilon }} \right)^{\frac{2}{\varepsilon } + 2} $$ The elementary proof, given by GROSSWALD in [2], is modified in such a way, that one needs no results from integral calculus. Furthermore one can see, that the connection of α and π is not essential for the proof. All facts about the constant α, which are needed, can be derived from the formula $$\alpha ^2 = 4 \cdot (1 + \frac{1}{{2^2 }} + \frac{1}{{3^2 }} + ... + \frac{1}{{n^2 }} + ...).$$      

New complexity analysis of a full-Newton step feasible interior-point algorithm for $$P_*(\kappa )$$-LCP

In this paper, we consider a full-Newton step feasible interior-point algorithm for \(P_*(\kappa )\)-linear complementarity problem. The perturbed complementarity equation \(xs=\mu e\) is transformed by using a strictly increasing function, i.e., replacing \(xs=\mu e\) by \(\psi (xs)=\psi (\mu e)\) with \(\psi (t)=\sqrt{t}\), and the proposed interior-point algorithm is based on that algebraic equivalent transformation. Furthermore, we establish the currently best known iteration bound for \(P_*(\kappa )\)-linear complementarity problem, namely, \(O((1+4\kappa )\sqrt{n}\log \frac{n}{\varepsilon })\), which almost coincides with the bound derived for linear optimization, except that the iteration bound in the \(P_{*}(\kappa )\)-linear complementarity problem case is multiplied with the factor \((1+4\kappa )\).     

New smoothing SVM algorithm with tight error bound and efficient reduced techniques

The quadratically convergent algorithms for training SVM with smoothing methods are discussed in this paper. By smoothing the objective function of an SVM formulation, Lee and Mangasarian [Comput. Optim. Appl. 20(1):5-22, 2001] presented one such algorithm called SSVM and proved that the error bound between the new smooth problem and the original one was $O(\frac{1}{p})$ for large positive smoothing parameter p. We derive a new method by smoothing the optimality conditions of the SVM formulation, and we prove that the error bound is $O(\frac{1}{p^{2}})$ , which is better than Lee and Mangasarian’s result. Based on SMW identity and updating Hessian iteratively, some boosting skills are proposed to solve Newton equation with lower computational complexity for reduced smooth SVM algorithms. Many experimental results show that the proposed smoothing method has the same accuracy as SSVM, whose error bound is also tightened to $O(\frac{1}{p^{2}})$ in this paper, and the proposed boosting skills are efficient for solving large-scale problems by RSVM.     

The second pinching theorem for hypersurfaces with constant mean curvature in a sphere

We generalize the second pinching theorem for minimal hypersurfaces in a sphere due to Peng–Terng, Wei–Xu, Zhang, and Ding–Xin to the case of hypersurfaces with small constant mean curvature. Let $M^n$ be a compact hypersurface with constant mean curvature $H$ in $S^{n+1}$ . Denote by $S$ the squared norm of the second fundamental form of $M$ . We prove that there exist two positive constants $\gamma (n)$ and $\delta (n)$ depending only on $n$ such that if $|H|\le \gamma (n)$ and $\beta (n,H)\le S\le \beta (n,H)+\delta (n)$ , then $S\equiv \beta (n,H)$ and $M$ is one of the following cases: (i) $S^{k}\Big (\sqrt{\frac{k}{n}}\Big )\times S^{n-k}\Big (\sqrt{\frac{n-k}{n}}\Big )$ , $\,1\le k\le n-1$ ; (ii) $S^{1}\Big (\frac{1}{\sqrt{1+\mu ^2}}\Big )\times S^{n-1}\Big (\frac{\mu }{\sqrt{1+\mu ^2}}\Big )$ . Here $\beta (n,H)=n+\frac{n^3}{2(n-1)}H^2+\frac{n(n-2)}{2(n-1)} \sqrt{n^2H^4+4(n-1)H^2}$ and $\mu =\frac{n|H|+\sqrt{n^2H^2+ 4(n-1)}}{2}$ .     

Closed geodesics on Finsler spheres

In this paper, we prove that for every Finsler n-sphere (S ⁿ ,?F) all of whose prime closed geodesics are non-degenerate with reversibility λ and flag curvature K satisfying ${\left(\frac{\lambda}{\lambda+1}\right)^2 < K \le 1,}$ there exist ${2[\frac{n+1}{2}]-1}$ prime closed geodesics; moreover, there exist ${2[\frac{n}{2}]-1}$ non-hyperbolic prime closed geodesics provided the number of prime closed geodesics is finite.     

An entire space polynomial-time algorithm for linear programming

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than $O(nL\log (nL/ {\varepsilon }))$ , and moreover, in short step, it is no more than $O(\sqrt{n}\log (nL/{\varepsilon }))$ .