On the classical logarithmic barrier function method for a class of smooth convex programming problems

In this paper, we describe a natural implementation of the classical logarithmic barrier function method for smooth convex programming. It is assumed that the objective and constraint functions fulfill the so-called relative Lipschitz condition, with Lipschitz constantM>0.In our method, we do line searches along the Newton direction with respect to the strictly convex logarithmic barrier function if we are far away from the central trajectory. If we are sufficiently close to this path, with respect to a certain metric, we reduce the barrier parameter. We prove that the number of iterations required by the algorithm to converge to an -optimal solution isO((1+M ²) log) orO((1+M ²)nlog), depending on the updating scheme for the lower bound.on leave from Eötvös University, Budapest, Hungary.     

A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results.The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a good starting point and a procedure for solving the augmented system arising from stochastic programming with simple recourse. We also present an application to large scale planning problems under uncertainty.     

On the equivalence of some rearrangements of the two-parameter Haar system

h ₁, L _p .

---

---

This research was supported in part by MTA-NSF grants INT-8400708 and 8620153.     

Sphere of Convergence of Newton's Method on Two Equivalent Systems from Nonlinear Programming

We study a local feature of two interior-point methods: a logarithmic barrier function method and a primal-dual method. In particular, we provide an asymptotic analysis on the radius of the sphere of convergence of Newton's method on two equivalent systems associated with the two aforementioned interior-point methods for nondegenerate nonlinear programs. We show that the radii of the spheres of convergence have different asymptotic behavior, as the two methods attempt to follow a solution trajectory {x } that, under suitable conditions, converges to a solution as 0. We show that, in the case of the barrier function method, the radius of the sphere of convergence of Newton's method is (), while for the primal-dual method the radius is bounded away from zero as 0. This work is an extension of the authors earlier work (Ref. 1) on linear programs.     

Representations of distributive lattice-ordered semigroups with binary relations

LetR(, , ¦) denote the class of all algebras isomorphic to ones whose elements are binary relations and whose operations are union, intersection, and relation composition (or relative product) of relations. We prove thatR(, , ¦) is not a variety and is not finitely axiomatizable. LetDLOS denote the class of all structures (A, , , ) where (A, , ) is a distributive lattice, (A, ) is a semigroup and is additive w.r.t. . We prove thatDLOS is the variety generated byR(, , ¦), and moreover, if (A, , , ) DLOS then it is representable whenever we disregard one of its operations.Presented by Boris M. Schein.Research supported by Hungarian National Foundation for Scientific Research grant No. 1810.     

Generalized ornstein-uhlenbeck process having a characteristic operator with polynomial coefficients

Summary Let be a weighted Schwartz's space of rapidly decreasing functions, the dual space and (t) a perturbed diffusion operator with polynomial coefficients from into itself. It is proven that (t) generates the Kolmogorov evolution operator from into itself via stochastic method. As applications, we construct a unique solution of a Langevin's equation on : whereW(t) is a Brownian motion and ^*(t) is the adjoint of (t) and show a central limit theorem for interacting multiplicative diffusions.     

Hypercentral Series and Paired Intersections of Sylow Subgroups of Chevalley Groups

Let G(k) be the Chevalley group of normal type associated with a root system G = , or of twisted type G = ^m,m = 2,3, over a field K. Its root subgroups X_s, for all possible s G⁺, generate a maximal unipotent subgroup U = UG(k) if p = charK < 0, U is a Sylow p-subgroup of G(K). We examine G and K for which there exists a paired intersection U U⁹, g G(K), which is not conjugate in G(K) to a normal subgroup of U. If K is a finite field, this is equivalent to a condition that the normalizer of U U⁹ in G(K)has a p-multiple index. Put p() = max(r,r)/(s,s) | r,s . We prove a statement (Theorem 1) saying the following. Let G(K) be a Chevalley group of Lie rank greater than 1 over a finite field K of characteristic p and U be its Sylow p-subgroup equal to UG(K); also, either G = and p() is distinct from p and 1, or G(K) is a twisted group. Then G(K) contains a monomial element n such that the normalizer U of Uⁿ in G(K) has a p-multiple index. Let K be an associative commutative ring with unity and (K,J) be a congruence subgroup of the Chevalley group (K) modulo a nilpotent ideal J. We examine an hypercentral series 1 Z₁ Z₂ ... Z_c-1 of the group U(K) (K,J). Theorem 2 shows that under an extra restriction on the quotient (J_t : J) of ideals, central series are related via Z_i = T_c-iC, 1 i < c, where C is a subgroup of central diagonal elements. Such a connection exists, in particular, if K = Z_pm and J = (p^d), 1 d < m, d| m.     

Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P _* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n ² ln(1/`)) iterations with a properly chosen starting point.     

On Solutions of the q-Hypergeometric Equation with q N = 1

We consider the q-hypergeometric equation with q ^N = 1 and , , . We solve this equation on the space of functions given by a power series multiplied by a power of the logarithmic function. We prove that the subspace of solutions is two-dimensional over the field of quasi-constants. We get a basis for this space explicitly. In terms of this basis, we represent the q-hypergeometric function of the Barnes type constructed by Nishizawa and Ueno. Then we see that this function has logarithmic singularity at the origin. This is a difference between the q-hypergeometric functions with 0 < |q| < 1 and at |q| = 1.     

On index one covers of two-dimensional purely log terminal singularities in positive characteristic

Let S be a normal surface over an algebraically closed field k and let be a standard boundary. We consider index 1 covers of the purely log terminal pair (S,). We prove that when S is smooth and char k=p3, then is canonical under some conditions. To prove this, we classify the boundary =(1–1/b_i)D_i which makes (S,) a purely log terminal pair, and then reduce equations defining singularity of to the normal forms of RDP. Unfortunately there are some counterexamples in p=2, and we classify them. These results give partial solutions to the index 1 cover conjecture in positive characteristic.Mathematical Subject Classification (2000): 14E20     

On the formulation of mechanical balance laws for structured continua

Force and moment balance laws are derived for structured continua. The approach consists in the use of two hypotheses: the availability of a microscope, mathematized by the introduction of a scale parameter; the existence of total and fine power expenses and the invariance of the corresponding power functionals in the limit 0+.

---

Sommario Vengono dedotte leggi di bilancio delle forze e dei momenti per continui con struttura. L'approccio consiste nell'uso di due ipotesi: la disponibilità di un microscopio, resa matematicamente tramite l'introduzione di un parametro di scala; l'esistenza di forme della potenza spesa totale e fine, e l'invarianza di queste forme per 0+.

     

Large step volumetric potential reduction algorithms for linear programming

We consider the construction of potential reduction algorithms using volumetric, and mixed volumetric — logarithmic, barriers. These are true large step methods, where dual updates produce constant-factor reductions in the primal-dual gap. Using a mixed volumetric — logarithmic barrier we obtain an iteration algorithm, improving on the best previously known complexity for a large step method. Our results complement those of Vaidya and Atkinson on small step volumetric, and mixed volumetric — logarithmic, barrier function algorithms. We also obtain simplified proofs of fundamental properties of the volumetric barrier, originally due to Vaidya.Research supported by a Summer Research Grant from the College of Business Administration, University of Iowa.     

On the complexity of linear programming under finite precision arithmetic

In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the conditioning of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of good numerical behavior of the logarithmic barrier method, in the sense that a problem instance twice as hard as the other from the numerical point of view, requires only at most twice as much precision to be solved. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This research has been supported through grants from Fundación Andes, under agreement C12021/7, and FONDECYT (project number 1930948).     

Growth and Size of the Exceptional Set in Nevanlinna's Second Fundamental Theorem

Let f be a transcendental meromorphic function, T(r,f) its characteristic function and S(r, f) the error term in Nevanlinna's second fundamental theorem. It is shown that for every increasing function (r) such that log (r) = o(r) we have S(r, f) = o(T(r, f)) outside an exceptional set E satisfying _E (T(r, f))dr < . This result makes clear the relationship between the size of the exceptional set and the growth of the characteristic function and implies that for functions of rapid lower growth improved conditions on the size of the exceptional set can be given. A general example of an entire function with a suitable exceptional set is constructed, showing that these results are essentially best possible.     

On the properties of ε(≥0) optimal policies in discounted unbounded return model

This paper investigates the properties of (0) optimal policies in the model of [2]. It is shown that, if * = ( ₀ ^* , ₁ ^* ,..., _n ^* , _n ^+1/* , ...) is a-discounted optimal policy, then ( ₀ ^* , ₁ ^* , ..., _n ^* ) for alln0 is also a-discounted optimal policy. Under some condition we prove that stochastic stationary policy _n ^* corresponding to the decision rule _n ^* is also optimal for the same discounting factor. We have also shown that for each-optimal stochastic stationary policy ₀ ^* , ₀ ^* can be decomposed into several decision rules to which the corresponding stationary policies are also-optimal separately; and conversely, a proper convex combination of these decision rules is identified with the former ₀ ^* . We have further proved that for any (,)-optimal policy, say *=( ₀ ^* , ₁ ^* , ..., _n ^* , _n ^+1/* , ...), _n–1 ^* ) is ((1– ⁿ )^–1 e, ) optimal forn>0. At the end of this paper we mention that the results about convex combinations and decompositions of optimal policies of § 4 in [1] can be extended to our case.Project supported by the Science Fund of the Chinese Academy of Sciences.     

Geometric Properties of Universally Measurable Mappings

We study conditions under which universally measurable mappings from a separable topological space S into a metric space R belong to the class D of mappings f : SR: such that for any compact subset KS and number > 0 there exists an open (in the induced topology) set VK such that the oscillation (f;V) of an R-valued function f on V is less than . Bibliography: 7 titles.     

Linear programming with entropic perturbation

In this paper, we derive an unconstrained convex programming approach to solving standard form linear programs through an entropic perturbation. The whole duality theory is established by using only one simple inequality lnz z –1 forz > 0. A curved search algorithm is also proposed for obtaining a pair of primal and dual-optimal solutions. The proposed algorithm is proven to be globally convergent with a quadratic rate of convergence. Computational results are included in support of theoretic findings.The work is partially supported by the North Carolina Supercomputing Center, the Cray Research Award, and the National Science Council of the Republic of China # NSC 81-0415-E-007-10.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Remarks on V. P. Elizarov's article, “two properties of associative rings”

The concept of a finitary ring is introduced, permitting statement of the conditions under which the concepts of the- and-ring coincide.Translated from Matematicheskie Zametki, Vol. 6, No. 5, pp. 541–544, November, 1969.     

On an application of infinitely divisible distributions to quadrature problems

— - , .