An interior point multiplicative method for optimization under positivity constraints

We analyze an algorithm for the problem minf(x) s.t.x 0 suggested, without convergence proof, by Eggermont. The iterative step is given by x _j ^k+1 =x _j ^k (1-_kf(x ^k)_j) with _k > 0 determined through a line search. This method can be seen as a natural extension of the steepest descent method for unconstrained optimization, and we establish convergence properties similar to those known for steepest descent, namely weak convergence to a KKT point for a generalf, weak convergence to a solution for convexf and full convergence to the solution for strictly convexf. Applying this method to a maximum likelihood estimation problem, we obtain an additively overrelaxed version of the EM Algorithm. We extend the full convergence results known for EM to this overrelaxed version by establishing local Fejér monotonicity to the solution set.Research for this paper was partially supported by CNPq grant No 301280/86.     

Fourier Analysis of Semistable Distributions

We consider the generalized convolution powers G _α ^*u (x) of an arbitrary semistable distribution function G _α (x) of exponent α∈(0,2), and prove that for all j, k∈{0,1,2,…} and u>0 the derivatives G _α ^(k,j)(x;u)=∂ ^k+j G _α ^*u (x)/∂ x ^k ∂ u ^j , x∈ℝ, are of bounded variation on the whole real line ℝ. The proof, along with an integral recursion in j, is new even in the special case of stable laws, and the result provides a framework for possible asymptotic expansions in merge theorems from the domain of geometric partial attraction of semistable laws. An erratum to this article can be found at     

The relationship between theorems of the alternative,least norm problems,steepest descent directions,and degeneracy: A review

Recently, it has been observed that several nondifferentiable minimization problems share the property that the question of whether a given point is optimal can be answered by solving a certain bounded least squares problem. If the resulting residual vector,r, vanishes then the current point is optimal. Otherwise,r is a descent direction. In fact, as we shall see,r points at the steepest descent direction. On the other hand, it is customary to characterize the optimality conditions (and the steepest descent vector) of a convex nondifferentiable function via its subdifferential. Also, it is well known that optimality conditions are usually related to theorems of the alternative. One aim of our survey is to clarify the relations between these subjects. Another aim is to introduce a new type of theorems of the alternative. The new theorems characterize the optimality conditions of discretel ₁ approximation problems and multifacility location problems, and provide a simple way to obtain the subdifferential and the steepest descent direction in such problems. A further objective of our review is to demonstrate that the ability to compute the steepest descent direction at degenerate dead points opens a new way for handling degeneracy in active set methods.     

Accurate approximation of time-varying matrices of linear differential systems

We consider the problem of the identification of the time-varying matrix A(t) of a linear m-dimensional differential system y′ = A(t)y. We develop an approximation A_n,k = ∑ⁿ_{j ? 1}c_j{Y(t_k + τ_j) Y^?1(t_k) ? I} to A(t_k) for grid points t_k = a + kh, k = 0,…, N using specified τ_j = θ_jh, 0 < θ_j < 1, j = 1, …, n, and show that for each t_k, the L₁ norm of the error matrix is $\text{O}$(hⁿ). We demonstrate an efficient scheme for the evaluation of A_n,k and treat sample problems.     

ANALYTIC SPREAD AND SCHEME-THEORETIC GENERATION

Let I be a homogeneous ideal in a positively graded affine k-algebra (where k is an infinite field). We characterize the scheme-theoretic generations J of I which are reductions of I; we deduce that l(I) ≤ σ(I) where l(I) is the analytic spread of I and σ(I) denotes the minimal number of the scheme-theoretic generations of I. As application, in the polynomial ring k[x ₀,…,x _{d ? 1}], we prove the uniqueness of the degrees of every scheme-th. generation of minimal length for a quasi complete intersection I when codim(I) < d ? 1.     

On Polynomials with Low Peak Signal to Power (L∞ to L2 Norm) Ratios and Theorems of Kashin and Spencer

In many engineering problems such as optical communications, radar and sonar problems, the electronic synthesis of speech, etc., as well as mathematical applications, a problem that arises is that of finding a waveform (trigonometric polynomial) with a specified spectrum, such that its crest factor is minimum, where the crest factor is the ratio of the peak signal energy (L_∞ norm) to the power (L₂ norm) of the waveform. The mathematical formulation of the problem is as follows: Given 1 ≤ m₁ < m₂ < … m_k ≤ n and arbitrary complex numbers a_j j = 1,…, k, we want to find signs ε_j = ±1 such that the growth of the crest factor is minimized as k and n are allowed to become arbitrarily large. Recently B. Kashin has solved special cases of this general problem using some deep geometrical results. We solve the general problem just stated and in particular obtain Kashin's results as a special case. The analogous problem where the ε_j are replaced by α_j and where the α_j are complex numbers with | α_j | = 1 is also solved. The results obtained are best possible in the sense that the asymptotic growth of the crest factors of the polynomials found is optimal. The preceding results are obtained by a solution of the following geometrical problem of independent interest: Given vectors υ₁,…, υ_k in complex n-dimensional space, where k ≤ n, we want to find signs ε_j = ±1 such that the growth of ‖ε₁υ₁ + … + ε_kυ_k‖_∞ is minimized as k and n go to infinity. As a special case of this geometrical result we obtain some combinatorial discrepancy results of J. Spencer.     

The Essential Norm of Weighted Composition Operators on Weighted Banach Spaces of Analytic Functions

For a wide class of radial weights we calculate the essential norm of a weighted composition operator uC_j{uC_\varphi} on the weighted Banach spaces of analytic functions in terms of the analytic function u \colon \mathbb D ? \mathbb C{u \colon \mathbb D \to \mathbb C} and the nth power of the analytic selfmap j{\varphi} of the open unit disc \mathbb D{\mathbb D} . We also apply our result to calculate the essential norm of composition operators acting on Bloch type spaces with general radial weights.     

Modal Aggregation and the Theory of Paraconsistent Filters

This paper articulates the structure of a two species of weakly aggregative necessity in a common idiom, neighbourhood semantics, using the notion of a k-filter of propositions. A k-filter on a non-empty set I is a collection of subsets of I which (i) contains I, (ii) is closed under supersets on I, and (iii) contains ∪{X_i ≤ X_j : 0 ≤ i < j ≤ k} whenever it contains the subsets X₀,…, X_k. The mathematical content of the proof that weakly aggregative modal logic is complete relative to k-ary frame theory, the standard semantic idiom for weakly aggregative modal logic (see [1]) is presented in language-independent terms as a representation theorem for k-filters: every non-trivial k-filter is included in the union of ≤ k non-trivial filters. The elementary theory of k-filters is developed and then applied in the form of an ultrafilter extension result for k-ary frame theory. Mathematics Subject Classification: 03B45.     

Solvability of fourth‐order Sturm‐Liouville problems with abstract linear functionals in boundary‐transmission conditions

This study deals with the solvability of one nonclassical boundary‐value problem for fourth‐order differential equation on two disjoint intervals I₁=(−1,0)and I₂=(0,1). The boundary conditions contain not only endpoints x=−1and x=1but also a point of interaction x=0, finite number internal points x_jki∈I_j and abstract linear functionals S_k. So, our problem is not a pure differential one. We investigate such important properties as isomorphism, Fredholmness and coerciveness with respect to the spectral parameter. Note that the obtained results are new even in the case of the boundary conditions without internal points x_jki and without abstract linear functionals S_k.     

On the Problem of Parameter Estimation in Exponential Sums

Let I≥1 be an integer, ω ₀=0<ω ₁<⋯<ω _I ≤π, and for j=0,…,I, a _j ∈ℂ, a_-j=[`(a_j)]a_{-j}={\overline{{a_{j}}}}, ω _−j =−ω _j , and a_j 1 0a_{j}\not=0 if j 1 0j\not=0. We consider the following problem: Given finitely many noisy samples of an exponential sum of the form

Über gerade unimodulare Gitter der Dimension 32, III

Let A_j, B_j be complex B-spaces, j = 0, 1, A_θ and B_θ–the complex-interpolation spaces generated by the couples (A₀, A₁) and (B₀, B₁), resp., by CALDERON'S/LIONS'S method. Let T: A₀ ∧ A₁ → B₀ → B₁ be an operator satisfying some conditions such as continuity, estimates etc. in terms of the norms of A_j, B_j (j = 0, 1). We consider the question which one of these properties is inherited to T when A₀ → A₁ and B₀ → B₁ are equipped with the norm of A_θ and B_θ.     

Approximation of zonoids by zonotopes in fixed directions

A construction is given which, for any zonoidZ⊂R ^d and any unit vectorsu ₁,...,u _k , produces a zonotopeZ′ which is a sum of at mostk segments and has the same support values asZ in the directionsu ₁ ,..., u _k . Applications to an estimation problem for fiber processes are also given as well as some related results for convex bodies.     

A generalization of the Gagliardo inequality

Consider functions u₁, u₂,..., u_n ∈ D(ℝ^k) and assume that we are given a certain set of linear combinations of the form ∑_{i, j} a _ij ^(l) ∂_ju_i. Sufficient conditions in terms of coefficients a _ij ^(l) are indicated under which the norms are controlled in terms of the L¹-norms of these linear combinations. These conditions are mostly transparent if k = 2. The classical Gagliardo inequality corresponds to a single function u₁ = u and the collection of its partial derivatives ∂₁u,..., ∂_ku. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 345, 2007, pp. 120–139.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

On split Lie algebras with symmetric root systems

We develop techniques of connections of roots for split Lie algebras with symmetric root systems. We show that any of such algebras L is of the form L = + Σ _j I _j with a subspace of the abelian Lie algebra H and any I _j a well described ideal of L, satisfying [I _j , I _k ] = 0 if j ≠ k. Under certain conditions, the simplicity of L is characterized and it is shown that L is the direct sum of the family of its minimal ideals, each one being a simple split Lie algebra with a symmetric root system and having all its nonzero roots connected.     

Isomorphism Checking of I-graphs

We consider the class of I-graphs, which is a generalization of the class of the generalized Petersen graphs. We show that two I-graphs I(n, j, k) and I(n, j ₁, k ₁) are isomorphic if and only if there exists an integer a relatively prime to n such that either {j ₁, k ₁} =? {a j mod n, a k mod n } or {j ₁, k ₁} =? {a j mod n, ? a k mod n }. This result has an application in the enumeration of non-isomorphic I-graphs and unit-distance representations of generalized Petersen graphs.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

An approximation result for solutions of Hessian equations

We show that W ^2,p weak solutions of the k-Hessian equation F _k (D ² u) = g(x) with k≥ 2 can be approximated by smooth k-convex solutions v _j of similar equations with the right hands sides controlled uniformly in C ^0,1 norm, and so that the quantities are bounded independently of j. This result simplifies the proof of previous interior regularity results for solutions of such equations. It also permits us to extend certain estimates for smooth solutions of degenerate two dimensional Monge–Ampère equations to W ^2,p solutions. Supported by an Australian Research Council Senior Fellowship.