A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with -iteration complexity

An interior point method for monotone linear complementarity problems acting in a wide neighborhood of the central path is presented. The method has -iteration complexity and is superlinearly convergent even when the problem does not possess a strictly complementary solution. Mathematics Subject Classification (2000): 49M15, 65K05, 90C33 Work supported by the National Science Foundation under Grant No. 0139701. An erratum to this article is available at.     

Fisher information inequalities and the central limit theorem

We give conditions for an O(1/n) rate of convergence of Fisher information and relative entropy in the Central Limit Theorem. We use the theory of projections in L² spaces and Poincaré inequalities, to provide a better understanding of the decrease in Fisher information implied by results of Barron and Brown. We show that if the standardized Fisher information ever becomes finite then it converges to zero.OTJ is a Fellow of Christs College, Cambridge, who helped support two trips to Yale University during which this paper was written.Mathematics Subject Classification (2000):Primary: 62B10 Secondary: 60F05, 94A17     

Energy release rate along a kinked path

Considering anti‐plane elasticity we provide an existence result for the energy release rate along a piecewise C^{1, 1} path that admits a kink. We provide two representations: an asymptotic one in terms of the stress intensity factor and an integral one in terms of the Eshelby tensor. Both the formulas make use of an implicit coefficient, depending on the kink angle and obtained by a minimum problem. Copyright © 2010 John Wiley & Sons, Ltd.     

A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with $$O(\sqrt{n}L)$$-iteration complexity

We correct an error in Algorithm 2 from [1]. The online version of the original article can be found at     

Globalizing a nonsmooth Newton method via nonmonotone path search

We give a framework for the globalization of a nonsmooth Newton method. In part one we start with recalling B. Kummer’s approach to convergence analysis of a nonsmooth Newton method and state his results for local convergence. In part two we give a globalized version of this method. Our approach uses a path search idea to control the descent. After elaborating the single steps, we analyze and prove the global convergence resp. the local superlinear or quadratic convergence of the algorithm. In the third part we illustrate the method for nonlinear complementarity problems.     

A FUNCTIONAL CENTRAL LIMIT THEOREMFOR NEGATIVELY ASSOCIATED SEQUENCE

Let(x1,j≥1)be a sequence of negatively associated random variables with ex1=o,ex^21＜∞.in this paper a functional central limit theorem for negatively associated random variables under some conditions withbout stationarity is proved which is the same as the results for positively associated random variables.     

On Shige Peng’s central limit theorem

We give error estimates in Peng’s central limit theorem for not necessarily nondegenerate case. The exposition uses the language of the classical probability theory instead of the language of the theory of sublinear expectations. We only consider the one-dimensional case. The higher dimensional extension is left to the interested reader.     

Existence, uniqueness, and convergence of the regularized primal-dual central path

In a recent work [J. Castro, J. Cuesta, Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming, in press (doi:10.1007/s10107-010-0341-2)] the authors improved one of the most efficient interior-point approaches for some classes of block-angular problems. This was achieved by adding a quadratic regularization to the logarithmic barrier. This regularized barrier was shown to be self-concordant, thus fitting the general structural optimization interior-point framework. In practice, however, most codes implement primal-dual path-following algorithms. This short paper shows that the primal-dual regularized central path is well defined, i.e., it exists, it is unique, and it converges to a strictly complementary primal-dual solution.     

Calmness of partially perturbed linear systems with an application to the central path

ABSTRACT

In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Cánovas MJ, López MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375–389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.     

Analyticity of the central path at the boundary point in semidefinite programming

In this paper we study the limiting behavior of the central path for semidefinite programming (SDP). We show that the central path is an analytic function of the barrier parameter even at the limit point, provided that the semidefinite program has a strictly complementary solution. A consequence of this property is that the derivatives – of any order – of the central path have finite limits as the barrier parameter goes to zero.     

Rate of convergence in the central limit theorem for empirical processes

Let _n and be an empirical process and a generalized Brownian bridge, respectively, indexed by a class of real measurable functions. From the central limit theorem for empirical processes it follows that for allr0. In this paper, assuming the class to be countably determined, under certain conditions we obtain an estimate for some constantC. Vapnik-ervonenkis class and the indicators of lower left orthants provide examples of classes considered here.     

On the speed of convergence in the central limit theorem of log-likelihood ratio processes

Let , the parameter space, be an open subset ofR ^k ,k1. For each , let the r.v.'sX _n ,n=1, 2,... be defined on the probability space (X, P ) and take values in (S,S,L) whereS is a Borel subset of a Euclidean space andL is the -field of Borel subsets ofS. ForhR _k and a sequence of p.d. normalizing matrices _n = _n ^{k × k} (₀ set _n ^* = ^* = ₀ + _n h, where ₀ is the true value of , such that ^*, . Let _n (^*, _*)( be the log-likelihood ratio of the probability measure with respect to the probability measure , whereP _n is the restriction ofP over _n = (X ₁,X ₂,...,X _n . In this paper we, under a very general dependence setup obtain a rate of convergence of the normalized log-likelihood ratio statistic to Standard Normal Variable. Two examples are taken into account.     

Analytical properties of the central path at boundary point in linear programming

Received October 15, 1996 / Revised version received January 28, 1998 Published online October 21, 1998     

Asymptotic behavior of the central path for a special class of degenerate SDP problems

This paper studies the asymptotic behavior of the central path (X(ν),S(ν),y(ν)) as ν↓0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” of the central path are assumed to satisfy We establish the convergence of the central path towards a primal-dual optimal solution, which is characterized as being the unique optimal solution of a certain log-barrier problem. A characterization of the class of SDP problems which satisfy our assumptions are also provided. It is shown that the re-parametrization t>0→(X(t⁴),S(t⁴),y(t⁴)) of the central path is analytic at t=0. The limiting behavior of the derivative of the central path is also investigated and it is shown that the order of convergence of the central path towards its limit point is Finally, we apply our results to the convex quadratically constrained convex programming (CQCCP) problem and characterize the class of CQCCP problems which can be formulated as SDPs satisfying the assumptions of this paper. In particular, we show that CQCCP problems with either a strictly convex objective function or at least one strictly convex constraint function lie in this class.This author was supported in part by CAPES and PRONEX-Otimização (FAPERJ/CNPq).This author was supported in part by FUNAPE/UFG, CAPES, PADCT-CNPq and PRONEX-Otimização (FAPERJ/CNPq).This author was supported in part by NSF Grants CCR-9902010, CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.Mathematics Subject Classification (1991): 90C20, 90C22, 90C25, 90C30, 90C33, 90C45, 90C51     

Two-sided bounds and leading term for rates of convergence in the multivariate central limit theorem

For a sequence of independent and identically distributed random vectors, upper and lower bounds are obtained for the discrepancy between the probability measure P_n, induced by their normalized sum, and the Normal measure Φ. The upper and lower bounds are of the same order of magnitude. These results may be derived by a “leading term” approach, in which a signed measure Q_n is introduced as a first order approximation to P_n − Φ. The purpose of this paper is to investigate properties of the leading term.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

On the complexity of following the central path of linear programs by linear extrapolation II

A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, ) of steps needed to go from an initial pointx(R) to a final pointx(), R>>0, by an integral of the local weighted curvature of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constm log(R/), where < 1/2 e.g. = 1/4 or = 3/8 (note that = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only for 1/3.As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.On leave from the Institute of Mathematics, Eötvös University Budapest, H-1080 Budapest, Hungary.     

Another view on martingale central limit theorems

Based on the martingale version of the Skorokhod embedding Heyde and Brown (1970) established a bound on the rate of convergence in the central limit theorem (CLT) for discrete time martingales having finite moments of order 2+2δ with 0<δ1. An extension for all δ>0 was proved in Haeusler (1988). This paper presents a rather quick access based solely on truncation, optional stopping, and prolongation techniques for martingale difference arrays to obtain other upper bounds for sup

Full-size image

(φbeing the standard normal d.f.) yielding weak sufficient conditions for the asymptotic normality of . It is shown that our approach also yields two types of martingale central limit theorems with random norming.     

Limiting behavior of weighted central paths in linear programming

We study the limiting behavior of the weighted central paths{(x(), s())} > 0 in linear programming at both = 0 and = . We establish the existence of a partition (B ,N ) of the index set { 1, ,n } such thatx _i() ands _j () as fori B , andj N , andx _N (),s _B () converge to weighted analytic centers of certain polytopes. For allk 1, we show that thekth order derivativesx ^(k) () ands ^(k) () converge when 0 and . Consequently, the derivatives of each order are bounded in the interval (0, ). We calculate the limiting derivatives explicitly, and establish the surprising result that all higher order derivatives (k 2) converge to zero when .