Directional differentiation of marginal functions in mathematical programming problems

We consider regular mathematical programming problems of the form f(x, y) inf, y F(x), x Rⁿ, where F(x) = {y R^m h_i| (x, y) 0, , h_i (x, y) = 0, . The directional derivatives offunctions (x) = inf{f(x, y)|y F(x)} are estimated.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–77, November–December, 1991.     

The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

Linear Interval Tolerance Problem and Linear Programming Techniques

In this paper, we consider the linear interval tolerance problem, which consists of finding the largest interval vector included in ([A], [b]) = {x R ⁿ | A [A], b [b], Ax = b}. We describe two different polyhedrons that represent subsets of all possible interval vectors in ([A], [b]), and we provide a new definition of the optimality of an interval vector included in ([A], [b]). Finally, we show how the Simplex algorithm can be applied to find an optimal interval vector in ([A], [b]).     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Duality in Quantum Information Geometry

Let H be a separable Hilbert space. We consider the manifold M consisting of density operators on H such that ^p is of trace class for some p (0, 1). We say M is nearby if there exists C > 1 such that C ^–1C. We show that the space of nearby points to can be furnished with the two flat connections known as the (±)-affine structures, which are dual relative to the BKM metric. We furnish M with a norm making it into a Banach manifold.     

Records of turing machines

Suppose a Turing machine is equipped with an extra tape. At each step of a computation being performed, it prints symbol read move symbol symbol printed on a square of the extra tape. It then moves the extra tape one square to the left. This procedure yields arecord of the computation.If is a finite alphabet, let be the set of triples (a, b, c) wherea ,c , andb {–1, 0, 1}. We will characterize those sequences of symbols of that are records of computations of Turing machines.This research was supported in part by AFOSR Grant GP-68-1402.     

Multi-time scale zero-sum differential games with perfect state measurements

We obtain necessary and sufficient conditions for the existence of approximate saddle-point solutions in linear-quadratic zero-sum differential games when the state dynamics are defined on multiple (three) time scales. These different time scales are characterized in terms of two small positive parameters ₁, and ₂, and the terminology approximate saddle-point solution is used to refer to saddle-point policies that do not depend on ₁ and ₂, while providing cost levels withinO(₁) of the full-order game. It is shown in the paper that, under perfect state measurements, the original game can be decomposed into three subgames-slow, fast and fastest, the composite saddle-point solution of which make up the approximate saddle-point solution of the original game. Specifically, for the minimizing player, it is necessary to use a composite policy that uses the solutions of all three subgames, whereas for the maximizing player, it is sufficient to use a slow policy. In the finite-horizon case this slow policy could be a feedback policy, whereas in the infinite-horizon case it has to be chosen as an open-loop policy that is generated from the solution and dynamics of the slow subgame. These results have direct applications in theH -optimal control of three-time scale singularly perturbed linear systems under perfect state measurements.Research supported in part by the National Science Foundation under Grant ECS 91-13153, and in part by the U.S. Department of Energy under Grant DE-FG-02-88-ER-13939. This paper is dedicated to the memory of John Breakwell.     

Towards optimal simulations of formulas by bounded-width programs

We show that, over an arbitrary ring, for any fixed >0, all balanced algebraic formulas of sizes are computed by algebraic straight-line programs that employ a constant number of registers and have lengthO (s ¹⁺). In particular, in the special case where the ring isGF(2), we obtain a technique for simulating balanced Boolean formulas of sizes by bounded-width branching programs of lengthO(s ¹⁺), for any fixed >0. This is an asymptotic improvement in efficiency over previous simulations in both the Boolean and algebraic settings.     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

Almost surely continuous solutions of a nonlinear stochastic integral equation

A nonlinear stochastic integral equation of the Hammerstein type in the formx(t; ) = h(t, x(t; )) + _s k(t, s; )f(s, x(s; ); )d(s) is studied wheret S, a measure space with certain properties, , the supporting set of a probability measure space (,A, P), and the integral is a Bochner integral. A random solution of the equation is defined to be an almost surely continuousm-dimensional vector-valued stochastic process onS which is bounded with probability one for eacht S and which satisfies the equation almost surely. Several theorems are proved which give conditions such that a unique random solution exists. AMS (MOS) subject classifications (1970): Primary; 60H20, 45G99. Secondary: 60G99.     

Three ∑ P 2 -complete problems in computational learning theory

The consistency problem associated with a concept classC is to determine, given two setsA andB of examples, whether there exists a conceptc inC such that eachx inA is a positive example ofc and eachy inB is a negative example ofc. We explore in this paper the following intuition: for a concept classC, if the membership problem of determining whether a given example is positive for a concept isNP-complete, then the corresponding consistency problem is likely to be _P ² -complete. To support this intuition, we prove that the following three consistency problems for concept classes of patterns, graphs and generalized Boolean formulas, whose membership problems are known to beNP-complete, are _P ² -complete: (a) given two setsA andB of strings, determine whether there exists a patternp such that every string inA is in the languageL(p) and every string inB is not in the languageL(p); (b) given two setsA andB of graphs, determine whether there exists a graphG such that every graph inA is isomorphic to a subgraph ofG and every graph inB is not isomorphic to any subgraph ofG; and (c) given two setsA andB of Boolean formulas, determine whether there exists a 3-CNF Boolean formula such that for every A, is satisfiable and for every B, is not satisfiable. These results suggest that consistendy problems in machine learning are natural candidates for _P ² -complete problems if the corresponding membership problems are known to beNP-complete.In addition, we prove that the corresponding prediction problems for concept classes of polynomial-time nondeterministic Turing machines, nondeterministic Boolean circuits, generalized Boolean formulas, patterns and graphs are prediction-complete for the classR _NP of all concept classes whose membership problems are inNP.     

An Entropy Theoretic Inversion Formula for the Distribution of Proper Values of a Compact Positive Operator

A formula for estimating -entropy of a compact positive operator in terms of the distribution of proper values of such an operator was given by Prosser and Root. In this paper, an inversion formula for estimating the distribution of proper values of a compact positive operator in terms of -entropy of such an operator is given.     

Bounding Perturbations in Zeros of Nonlinear Systems

Algorithms for determining computationally rigorous componentwise bounds on the solutions x R ⁿ of equations F(x, t) = 0 R ^m containing parameters t R ^l due to small perturbations in t when m n and when F is at most twice continuously differentiable in x and in t are described. Numerical results which illustrate the behaviour of the algorithms are presented.     

Dynamic half-space range reporting and its applications

We consider the half-space range-reporting problem: Given a setS ofn points in ^d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n ^d/2 and an arbitrarily small positive constant , we achieveO(m ¹⁺) space and preprocessing time, O((n/m ^d/2 logn+k) query time, and O(m¹⁺n) amortized update time (d 3). We present, among others, the following applications: an O(n¹⁺)-time algorithm for computing convex layers in ³, and an output sensitive algorithm for computing a level in an arrangements of planes in ³, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees.     

Stabilizability of linear systems defined overC *-algebras

LetF andG be elements of aC ^*-algebraA. Assume that, for each irreducible^*-representation ofA on a Hilbert space210B; , there is a bounded linear operatorL B( ) such that the spectrum of(F) –(G)L is contained in the open left half plane. We prove that there is then an elementL A such that the spectrum ofF — GL is contained in the open left half plane. That is, if the system (F, G) is locally stabilizable, then it is stabilizable. We also consider the analogous problem with the open left half plane replaced by the open unit disk.This paper was supported in part by the National Science Foundation under Grant NSF-MCS-8002138.     

Probabilistic analysis of the application of the cross ratio to model based vision: Misclassification

The cross ratio of four colinear points is of fundamental importance in model based vision, because it is the simplest numerical property of an object that is invariant under projection to an image. It provides a basis for algorithms to recognise objects from images without first estimating the position and orientation of the camera.A quantitative analysis of the effectiveness of the cross ratio in model based vision is made. A given imageI of four colinear points is classified by making comparisons between the measured cross ratio of the four image points and the cross ratios stored in the model database. The imageI is accepted as a projection of an objectO with cross ratio if |–|ntu, wheren is the standard deviation of the image noise,t is a threshold andu=. The performance of the cross ratio is described quantitatively by the probability of rejectionR, the probability of false alarmF and the probability of misclassificationp (), defined for two model cross ratios , . The trade off between these different probabilities is determined byt.It is assumed that in the absence of an object the image points have identical Gaussian distributions, and that in the presence of an object the image points have the appropriate conditional densities. The measurements of the image points are subject to small random Gaussian perturbations. Under these assumptions the trade offs betweenR,F andp () are given to a good approximation byR=2(1–(t)),F=r _F t, t|–|^–1, where is the relative noise level, is cumulative distribution function for the normal distribution,r _F is constant, ande is a function of only. The trade off betweenR andF is obtained in Maybank (1994). In this paper the trade off betweenR andp () is obtained.It is conjectured that the general form of the above trade offs betweenR,F andp () is the same for a range of invariants useful in model based vision. The conjecture prompts the following definition: an invariant which has trade offs betweenR,F,p () of the above form is said to benon-degenerate for model based vision.The consequences of the trade off betweenR andp () are examined. In particular, it is shown that for a fixed overall probability of misclassification there is a maximum possible model cross ratio _m , and there is a maximum possible numberN of models. Approximate expressions for _m andN are obtained. They indicate that in practice a model database containing only cross ratio values can have a size of order at most ten, for a physically plausible level of image noise, and for a probability of misclassification of the order 0.1.     

A logic for the specification and proof of regular controllable processes of CCS

Summary This work has been motivated by the following general problem: find logics for the specification and proof of programs, described by terms of some algebra with given congruence relation. This relation is supposed to define a satisfactory concept for the behavioural comparison of programs. We require these logics to be adequate with respect to the term language, in the sense that two programs, behaviourally equivalent satisfy the same formulas and conversely. The term language considered is the subset of controllable, regular terms of CCS, on a vocabulary of actions A, with observational congruence. A term is said to be controllable if it is congruent to some term without occurrence of . We obtain an adequate logic whose language of formulas is obtained from constants true, false and ¦Nil¦ by using operators , , fixpoint operators, + and a for aA; the latter can be considered as extensions of the operators + and a for aA of CCS. As a result, controllable CCS terms can be considered as formulas of this logic and the problem of program verification is reduced to the proof of the validity of a formula.     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

What holds in a context?

In order to establish that [A] = [B] follows from a set of assumptions often one provesA =B and then invokes the principle of substitution of equals for equals. It has been observed that in the ancillary proof ofA =B one is allowed to use, in addition to those assumptions of which are free for , certain (open) sentencesP which may not be part of and may not follow from , but are related to the context . We show that in an appropriate formal system there is a closed form solution to the problem of determining precisely what sentencesP can be used. We say that those sentenceshold in the context under the set of assumptions . We suggest how the solution could be exploited in an interactive theorem prover.