On metric spaces and local extrema

The main aim of this paper is to give a positive answer to a question of Behrends, Geschke and Natkaniec regarding the existence of a connected metric space and a non-constant real-valued continuous function on it for which every point is a local extremum. Moreover we show that real-valued continuous functions on connected spaces such that every family of pairwise disjoint non-empty open sets is of size <|R| are constant provided that every point is a local extremum.     

Condition number based complexity estimate for computing local extrema

In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables.     

Functional equations with extrema

Exact solutions of sine Gordon and multiple sine Gordon equations are constructed in terms of solutions of a linear base equation, the Klein Gordon equation and also in terms of nonlinear base equations where the nonlinearity is polynomial in the dependent variable. Further, exact solutions of nonlinear generalizations of the Schrodinger equation and of additional nonlinear generalizations of the Klein Gordon equation are constructed in terms of solutions of linear base equations. Finally, solutions with spherical symmetry, of nonlinear Klein Gordon equations are given.     

On realistic terrains

We study worst-case complexities of visibility and distance structures on terrains under realistic assumptions on edge length ratios and the angles of the triangles, and a more general low-density assumption. We show that the visibility map of a point for a realistic terrain with n triangles has complexity . We also prove that the shortest path between two points p and q on a realistic terrain passes through triangles, and that the bisector of p and q has complexity . We use these results to show that the shortest path map for any point on a realistic terrain has complexity , and that the Voronoi diagram for any set of m points on a realistic terrain has complexity and . Our results immediately imply more efficient algorithms for computing the various structures on realistic terrains.     

Existence and regularity of extrema

Consider the minimization of a possibly noncoercive Gâteaux differentiable functional $\text{F:X→}\text{R}$. A modified notion of coercivity is introduced which may be usable to show existence of a minimum. Alternatively, $\text{F}\text{?}\text{:D→}\text{R}$ has a minimum at $\text{y}\text{ε}$$\text{D}$ ($\text{F}\text{?}$ not differentiable but the restriction F of $\text{F}\text{?}$ to $\text{X}$?$\text{D}$ differentiable), one may be able to show $\text{y}\text{?}$ is actually in $\text{X}$. The latter case is related to justification of formally calculated “necessary conditions” for optimal controls. The arguments are applications of Ekeland's “approximate variational principle” (J. Math. Anal. Appl.47 (1974), 324–353).     

Constrained extrema of bilinear functionals

LetA be an operator on a finite dimensional unitary space. This paper contains results on the set of values taken on by the conjugate bilinear functional (A x, y) asx andy range over all unit vectors with prescribed inner product. By analyzing the same problem for the induced functional on the Grassmannian, results on non-principal subdeterminants are also obtained.The research of this author was supported by the U.S. Air Force Office of Scientific Research under Grant AFOSR 72-2164.     

Local extrema in genus-stratified graphs

Beyond the obvious organization of all the orientable imbeddings of a graph according to the genus of the imbedding surface, there are several seemingly natural ways to ascribe proximity of imbeddings. One of these is to stipulate that two imbeddings are adjacent if one imbedding can be obtained from the other by moving one end of an edge in its rotation. If one associates “altitude” with genus, then one might hope to construct algorithms for minimum genus and maximum genus by descent and ascent, respectively. This investigation of the structure of the system of orientable graph imbeddings reveals that although there may occur arbitrarily deep traps among the local minima, there cannot exist any strict local maxima. These new discoveries seem consistent with a known contrast in the computational complexity of the maximum genus and minimum genus problems. That is, whereas Furst, Gross, and McGeoch have devised a polynomial-time algorithm to find the maximum genus of an arbitrary graph, Thomassen has proved that the problem of finding the minimum genus is NP-complete.     

Forecasting with imprecise probabilities

We review de Finetti’s two coherence criteria for determinate probabilities: coherence₁ defined in terms of previsions for a set of events that are undominated by the status quo – previsions immune to a sure-loss – and coherence₂ defined in terms of forecasts for events undominated in Brier score by a rival forecast. We propose a criterion of IP-coherence₂ based on a generalization of Brier score for IP-forecasts that uses 1-sided, lower and upper, probability forecasts. However, whereas Brier score is a strictly proper scoring rule for eliciting determinate probabilities, we show that there is no real-valued strictly proper IP-score. Nonetheless, with respect to either of two decision rules – Γ-maximin or (Levi’s) E-admissibility-+-Γ-maximin – we give a lexicographic strictly proper IP-scoring rule that is based on Brier score.     

Local extrema of analytic functions

We give a complete answer to the problem of the finite decidability of the local extremality character of a real analytic function at a given point, a problem that found partial answers in some works by Severi and ojasiewicz. Consider a real analytic functionf defined in a neighbourhood of a pointx ₀R ⁿ . Restrictf to the spherical surface centered inx ₀ and with radiusr0 and take its infimumm(r) and its supremumM(r). We establish some properties ofm(r) andM(r) for smallr>0. In particular, we prove that they have asymptotic expansions of the formf(x ₀)+c·(r +o(r )) asr0 for a realc and a rational 1 (of course the parameters will usually be different form andM).This work was supported by the Brazilian Fundação Carlos Chagas and by the Italian Consiglio Nazionale delle Ricerche.     

Nondegeneracy of certain constrained extrema

The isolation and nondegeneracy of constrained extrema arising in geometric problems and mathematical models of electrostatics are studied. In particular, it is proved that a convex concyclic configuration of polygonal linkages is a nondegenerate maximum of the oriented area. Geometric properties of equilibrium configurations of point charges with Coulomb interaction on convex curves are considered, and methods for constructing them are presented. It is shown that any configuration of an odd number of points on a circle is an equilibrium point for the Coulomb potential of nonzero point charges. The stability of the equilibrium configurations under consideration is discussed.     

Large deviations of bivariate Gaussian extrema

We establish sharp tail asymptotics for componentwise extreme values of bivariate Gaussian random vectors with arbitrary correlation between the components. We consider two scaling regimes for the tail event in which we demonstrate the existence of a restricted large deviations principle and identify the unique rate function associated with these asymptotics. Our results identify when the maxima of both coordinates are typically attained by two different versus the same index, and how this depends on the correlation between the coordinates of the bivariate Gaussian random vectors. Our results complement a growing body of work on the extremes of Gaussian processes. The results are also relevant for steady-state performance and simulation analysis of networks of infinite server queues.

     

Reasoning with imprecise belief structures

This paper extends the theory of belief functions by introducing new concepts and techniques, allowing to model the situation in which the beliefs held by a rational agent may only be expressed (or are only known) with some imprecision. Central to our approach is the concept of interval-valued belief structure (IBS), defined as a set of belief structures verifying certain constraints. Starting from this definition, many other concepts of Evidence Theory (including belief and plausibility functions, pignistic probabilities, combination rules and uncertainty measures) are generalized to cope with imprecision in the belief numbers attached to each hypothesis. An application of this new framework to the classification of patterns with partially known feature values is demonstrated.     

Decision making with imprecise parameters

We analyze the impact of imprecise parameters on performance of an uncertainty-modeling tool presented in this paper. In particular, we present a reliable and efficient uncertainty-modeling tool, which enables dynamic capturing of interval-valued clusters representations sets and functions using well-known pattern recognition and machine learning algorithms. We mainly deal with imprecise learning parameters in identifying uncertainty intervals of membership value distributions and imprecise functions. In the experiments, we use the proposed system as a decision support tool for a production line process. Simulation results indicate that in comparison to benchmark methods such as well-known type-1 and type-2 system modeling tools, and statistical machine-learning algorithms, proposed interval-valued imprecise system modeling tool is more robust with less error.     

High extrema of Gaussian chaos processes

Let ξ ( t)=(ξ ₁(t),…,ξ _d (t)) be a Gaussian stationary vector process. Let \(g:{\mathbb {R}}^{d}\rightarrow {\mathbb {R}}\) be a homogeneous function. We study probabilities of large extrema of the Gaussian chaos process g(ξ(t)). Important examples include \(g(\mathbf {\boldsymbol {\xi }}(t))={\prod }_{i=1}^{d}\xi _{i}(t)\) and \(g(\mathbf {\boldsymbol {\xi }}(t))={\sum }_{i=1}^{d}a_{i}{\xi _{i}^{2}}(t)\). We review existing results partially obtained in collaboration with E. Hashorva, D. Korshunov, and A. Zhdanov. We also present the principal methods of our investigations which are the Laplace asymptotic method and other asymptotic methods for probabilities of high excursions of Gaussian vector process’ trajectories.     

Using imprecise estimates for weights

In multi-attribute decision problems the decision to differentiate between alternatives will be affected by the precision with which weights are specified. Specifications are imprecise because of the uncertainty characteristic of the judgements on which weights are based. Uncertainties are from two sources, the accuracy with which judgements are articulated and the inconsistency when multiple judgements are made and must be reconciled. These uncertainties are modelled using probabilistic weight estimates integrated by the Dirichlet distribution. This ensures the consistency of the estimates and leads to the calculation of significance of the differences between alternatives. A simple plot of these significant differences helps in the final decision whether this is selection or ranking. The method is used to find weight estimates in the presence of both types of uncertainty acting separately and together.     

Removing Laver functions from supercompactness arguments

We show how the use of a Laver function in the proof of the consistency, relative to the existence of a supercompact cardinal, of both the Proper Forcing Axiom and the Semiproper Forcing Axiom can be eliminated via the use of lottery sums of the appropriate partial orderings. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Three-way analysis of imprecise data

Data are often affected by uncertainty. Uncertainty is usually referred to as randomness. Nonetheless, other sources of uncertainty may occur. In particular, the empirical information may also be affected by imprecision. Also in these cases it can be fruitful to analyze the underlying structure of the data. In this paper we address the problem of summarizing a sample of three-way imprecise data. In order to manage the different sources of uncertainty a twofold strategy is adopted. On the one hand, imprecise data are transformed into fuzzy sets by means of the so-called fuzzification process. The so-obtained fuzzy data are then analyzed by suitable generalizations of the Tucker3 and CANDECOMP/PARAFAC models, which are the two most popular three-way extensions of Principal Component Analysis. On the other hand, the statistical validity of the obtained underlying structure is evaluated by (nonparametric) bootstrapping. A simulation experiment is performed for assessing whether the use of fuzzy data is helpful in order to summarize three-way uncertain data. Finally, to show how our models work in practice, an application to real data is discussed.     

Improved second derivative test for relative extrema

In this note, a modified Second Derivative Test is introduced for the relative extrema of a single variable function. This improved test overcomes the difficulty of the second derivative vanishing at the critical point, while in contrast the traditional test fails for this case. A proof for this improved Second Derivative Test is presented, followed by an example.