q-Pseudoconvexity and Regularity at the Boundary for Solutions of the \bar \partial -problem

For a domain of we introduce a fairly general and intrinsic condition of weak q-pseudoconvexity, and prove, in Theorem 4, solvability of the -complex for forms with -coefficients in degree . All domains whose boundary have a constant number of negative Levi eigenvalues are easily recognized to fulfill our condition of q-pseudoconvexity; thus we regain the result of Michel (with a simplified proof). Our method deeply relies on the L ²-estimates by Hörmander (with some variants). The main point of our proof is that our estimates (both in weightened-L ² and in Sobolev norms) are sufficiently accurate to permit us to exploit the technique by Dufresnoy for regularity up to the boundary.     

Interior path following primal-dual algorithms. part II: Convex quadratic programming

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n ³ L).     

Interior path following primal-dual algorithms. part I: Linear programming

We describe a primal-dual interior point algorithm for linear programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.     

Computing an Integer Point of a Class of Convex Sets

A simplicial algorithm is proposed for computing an integer point of a convex set ^CRn satisfying

Complexity of a Noninterior Path-Following Method for the Linear Complementarity Problem

We study the complexity of a noninterior path-following method for the linear complementarity problem. The method is based on the Chen–Harker–Kanzow–Smale smoothing function. It is assumed that the matrix M is either a P-matrix or symmetric and positive definite. When M is a P-matrix, it is shown that the algorithm finds a solution satisfying the conditions Mx-y+q=0 and in at most

Epsilon-inflation with contractive interval functions

For contractive interval functions [g] we show that results from the iterative process after finitely many iterations if one uses the epsilon-inflated vector as input for [g] instead of the original output vector [x] ^k . Applying Brouwer's fixed point theorem, zeros of various mathematical problems can be verified in this way.     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Lines,line-point incidences and crossing families in dense sets

LetP be a set ofn points in the plane. We say thatP isdense if the ratio between the maximum and the minimum distance inP is of order . A setC of line segments in the plane is calleda crossing family if the relative interiors of any two line segments ofC intersect. Vertices of line segments of a crossing familyC are calledvertices of C. It is known that for any setP ofn points in general position in the plane there is a crossing family of size with vertices inP. In this paper we show that ifP is dense then there is a crossing family of almost linear size with vertices inP.The above result is related to well-known results of Beck and of Szemerédi and Trotter. Beck proved that any setP ofn points in the plane, not most of them on a line, determines at least (n ²) different line. Szemerédi and Trotter proved that ifP is a set ofn points and is a set ofm lines then there are at mostO(m ^2/3 n ^2/3 +m+n) incidences between points ofP and lines of . We study whether or not the bounds shown by Beck and by Szemerédi and Trotter hold for any dense setP even if the notion of incidence is extended so that a point is considered to be incident to a linel if it lies in a small neighborhood ofl. In the first case we get very close to the conjectured bound (n ²). In the second case we obtain a bound of order .The work on this paper was supported by Czech Republic grant GAR 201/94/2167, by Charles University grants No. 351 and 361, by Deutsche Forschungsgemeinschaft, grant We 1265/2-1, and by DIMACS.     

On the Superlinear Convergence Order of the Logarithmic Barrier Algorithm

Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter r_k +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if r_k+1=r _k with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods.     

The Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

The free \mathfrak{m} -lattice on the poset H

Let H={a ₀, a ₁, a ₂, b ₀, b ₁, b ₂} be the poset defined by a ₀<a ₂<a ₁, b ₀<b ₂<b ₁, a ₀<b ₁, and b ₀<a ₁. For an infinite regular cardinal , we describe the free -lattice on H. This continues the work of I. Rival and R. Wille who accomplished the same for =. In subsequent papers, we show how to apply this result to describe the free -lattice on a poset for a large class of posets, called slender posets.     

Geometry of \mathbb{Z}^d and the Central Limit Theorem for Weakly Dependent Random Fields

We study the asymptotic distribution of where A is a subset of , A _N = A[–N, N] ^d , v(A) = lim _N card(A _N) (2N+1) ^–d (0, 1) and X is a stationary weakly dependent random field. We show that the geometry of A has a relevant influence on the problem. More specifically, S _N(A, X) is asymptotically normal for each X that satisfies certain mixting hypotheses if and only if has a limit F(n; A) as N for each . We also study the class of sets A that satisfy this condition.     

A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

We consider the standard linear complementarity problem (LCP): Find (x, y) R ²ⁿ such that y = M x + q, (x, y) 0 and x _i y _i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P ₀ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.     

Two Splittings of a Square Matrix

In this note it is shown that any square matrix AC ^n×n can be represented as the sum A= , where is complex symmetric and rank . The corresponding persymmetric result can be used in finding the terms of a small rank perturbed Toeplitz matrix via an O(n ²) computation. This allows one to perform fast matrix–vector products in case n is large.     

Critical Points of Real Polynomials and Topology of Real Algebraic T-Surfaces

The paper is devoted to a special class of real polynomials, so-called T-polynomials, which arise in the combinatorial version of the Viro theorem. We study the relation between the numbers of real critical points of a given index of a T-polynomial and the combinatorics of lattice triangulations of Newton polytopes. We obtain upper bounds for the numbers of extrema and saddles of generic T-polynomials of a given degree in three variables, and derive from them upper bounds for Betti numbers of real algebraic surfaces in defined by T-polynomials. The latter upper bounds are stronger than the known upper bounds for arbitrary real algebraic surfaces in . Another result is the existence of an asymptotically maximal family of real polynomials of degree min three variables with 31m ³/36 + O(m ²) saddle points.     

An application of Shoenfield's absoluteness theorem to the theory of uniform distribution

IfC is a Polish probability space, a Borel set whose sectionsW _x ( have measure one and are decreasing , then we show that the set _x W _x has measure one. We give two proofs of this theorem—one in the language of set theory, the other in the language of probability theory, and we apply the theorem to a question on completely uniformly distributed sequences.Supported by DFG grant Ko 490/7-1.     

Regularity of a Boundary Point for Degenerate Parabolic Equations with Measurable Coefficients

We investigate the continuity of solutions of quasilinear parabolic equations in the neighborhood of the nonsmooth boundary of a cylindrical domain. As a special case, one can consider the equation with the p-Laplace operator p. We prove a sufficient condition for the regularity of a boundary point in terms of C _p-capacity.     

A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

Change of variables in a multiple integral for local fields

A proof of the formula for locally compact fields andC ¹-isomorphisms :UV, whereU andV are open subsets of , was never published. In this paper we give two short proofs, one of them is a more elementary variant of the other.