Membership functions,some mathematical programming models and production scheduling

The authors have studied in [5] alternative real variable models based on the function $\text{d(x) =}\text{x}\text{(α + x)}\text{, α >0}$, for certain integer or mixed-interger programming problems. Mainly, we have shown that there exists a vector α > 0 such that the solution to the problem min $\text{σ}{}_1\text{(x, α) = Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{x}{}_{\mathrm{i}}\text{(ga}{}_{\mathrm{i}}\text{+x}{}_{\mathrm{i}}\text{)}\text{, Ax = b, x ? 0}$, is a solution to the problem min σxσ⁺, Ax = b, x ? 0, where σxσ⁺ denotes the cardinal of x, i.e. the number of strictly positive components of x, thus obtaining a new model for solving in real numbers a Generalized Lattice Point Problem (Cabot, [3]).The function d(x) has been introduced by use as a general tool for solving integer or mixed-integer problems due to its property of having almost everywhere almost discrete values. In the meantime we noticed that this function may represent a membership function of a fuzzy set.In this paper, we study in detail the features of this membership function and show that Cabot's results [3] may be derived in this more general setting using the complementary function $\text{s(x) =}\text{1 ? x}\text{(α + x)}\text{=}\text{α}\text{(α+x)}$.At the same time, in the paper there are some production scheduling models within the framework of fuzzy-sets theory. To this end, a nonconvex production model is presented and it is shown that the value of the objective function $\text{μ}{}_2\text{=}\text{1 ? σ}{}_1\text{n}$ for a production programming model whose deman and/or resource vector components are parametrized, may be considered as a grade of membership of the solution of the parametrized model to the feasible set of the nonparametrized production programming model.Consequently, we get a nonconvex production programming model whose convex envelope is linear with coefficients which are in an inverse proportior to the magnitude of the nonparametrized demand or resource vector components. This result agrees with the intuitive idea that a high level of demand or resource allows a greater interval of variation in the production process than a lower level of demand or resource.     

On cone orderings and the linear complementarity problem

This paper first generalizes a characterization of polyhedral sets having least elements, which is obtained by Cottle and Veinott [6], to the situation in which Euclidean space is partially ordered by some general cone ordering (rather than the usual ordering). We then use this generalization to establish the following characterization of the class $\text{C}$ of matrices ($\text{C}$ arises as a generalization of the class of Z-matrices; see [4], [13], [14]): M∈$\text{C}$ if and only if for every vector q for which the linear complementarity problem (q,M) is feasible, the problem (q,M) has a solution which is the least element of the feasible set of (q,M) with respect to a cone ordering induced by some simplicial cone. This latter result generalizes the characterizations of K-and Z-matrices obtained by Cottle and Veinott [6] and Tamir [21], respectively.     

Optimal approximation of convex curves by functions which are piecewise linear

In this paper an efficient method is presented for solving the problem of approximation of convex curves by functions that are piecewise linear, in such a manner that the maximum absolute value of the approximation error is minimized. The method requires the curves to be convex on the approximation interval only. The boundary values of the approximation function can be either free or specified. The method is based on the property of the optimal solution to be such that each linear segment approximates the curve on its interval optimally while the optimal error is uniformly distributed among the linear segments of the approximation function. Using this method the optimal solution can be determined analytically to the full extent in certain cases, as it was done for functions x² and $\text{x}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. In general, the optimal solution has to be computed numerically following the procedure suggested in the paper. Using this procedure, optimal solutions were computed for functions sin x, tg x, and arc tg x. Optimal solutions to these functions were used in practical applications.     

Facility location in the presence of forbidden regions,I: Formulation and the case of Euclidean distance with one forbidden circle

A constrained form of the Weber problem is formulated in which no path is permitted to enter a prespecified forbidden region $\text{R}$ of the plane. Using the calculus of variations the shortest path between two points $\text{x}\text{,}\text{y}\text{?}\text{R}$ which does not intersect $\text{R}$ is determined. If $\text{d(}\text{x}\text{,}\text{y}\text{)}$ is unconstrained distance, we denote the shortes distance along a feasible path by $\text{d}\text{(}\text{x}\text{y}\text{)}$. The constrained Weber problem is, then: given points $\text{x}{}_{\mathrm{j}}\text{?}\text{R}$ and positive weights w_j, j = 1,2,…,n, find a point $\text{x}\text{?}\text{R}$ such that

$\text{f(}\text{x}\text{)=}\text{Σ}\text{n}\text{j=1}\text{d(}\text{x}\text{,}\text{x}{}_{\mathrm{j}}\text{)}$

is a minimum.An algorithm is formulated for the solution of this problem when $\text{d(}\text{x}\text{,}\text{y}\text{)}$ is Euclidean distance and $\text{R}$ is a single circular region. Numerical results are presented.     

Perturbations with several independent parameters

In this paper we discuss the problem of determining a T-periodic solution $\text{x}{}^1\text{(·, λ)}$ of the differential equation x = A(t)x + f(t, x, λ) + b(t), where the perturbation parameter λ is a vector in a parameter-space R^k. The customary approach assumes that λ = λ(?), ??R. One then establishes the existence of an ?₀ > 0 such that the differential equation has a T-periodic solution $\text{x}{}^1\text{(·, λ(?))}$ for all ? satisfying 0 < ? < ?₀. More specifically it is usually assumed that λ(?) has the form λ(?) = ?λ₀ where λ₀ is a fixed vector in R^k. This means that attention is confined in the perturbation procedure to examining the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies along a line segment terminating at the origin in the parameter-space R^k. The results established here generalize this previous work by allowing one to study the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies through a “conical-horn” whose vertex rests at the origin in R^k. In the process an implicit-function formula is developed which is of some interest in its own right.     

Nonoscillation and disconjugacy of systems of linear differential equations

The differential equations under consideration are of the form $\text{dx}\text{dt}\text{= A(t)x}$, (1) where A(t) is a piecewise continuous real n × n matrix on a real interval α, and the vector x = (x₁,…,x_n) is continuous on α. The equation is said to be nonoscillatory on α if every nontrivial real solution vector x has at least one component x_k which does not vanish on α.The principal concern of this paper is the derivation of conditions, expressed in terms of various norms of A, which guarantee the nonoscillation of (1) in a given interval.     

A note on k-plane integral transforms

Let Π be a k-dimensional subspace of Rⁿ, n ? 2, and write x = (x′, x″) with x′ in Π and x″ in the orthogonal complement Π^⊥. The k-plane transform of a measurable function ? in the direction Π at the point x″ is defined by $\text{L?(Π, x″) = ∝Π?(x′, x″) dx′}$. In this article certain a priori inequalities are established which show in particular that if $\text{? ? L}{}^{\mathrm{p}}\text{(R}{}^{\mathrm{n}}\text{)}$, $\text{1 ? p}\text{\$}\text{?}\text{n}\text{k}$, then ? is integrable over almost every translate of almost every k-space. Mapping properties of the k-plane transform between the spaces L^p(Rⁿ), p ? 2, and certain Lebesgue spaces with mixed norm on a vector bundle over the Grassmann manifold of k-spaces in Rⁿ are also obtained.     

Entropic perturbation method for solving a system of linear inequalities

The problem of finding an $\text{x∈}\text{R}{}^{\mathrm{n}}$ such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region.     

Best approximation and numerical methods in solution of differential equations

Let Q(x) bee polynomial of degree q interpolating x^m at the points $\text{x}{}_{\mathrm{<mtext>i</mtext>}}\text{,}\text{i}\text{= 0, 1, /3.,}\text{q}$, where $\text{x}{}_{\mathrm{<mtext>i</mtext>}}$ are zeros of the Tchebysheff polynomial of degree q + 1 on the interval [0, 1]. If q is of order √m, then Q(x) approximates x^m well enough. This result is used to obtain a good approximation to the solution of a system of linear differential equations.     

Diophantine problems in variables restricted to the values 0 and 1

Let $\text{F}$x₁,…,x_s be a form of degree d with integer coefficients. How large must s be to ensure that the congruence $\text{F}$(x₁,…,x_s) ≡ 0 (mod m) has a nontrivial solution in integers 0 or 1? More generally, if $\text{F}$ has coefficients in a finite additive group G, how large must s be in order that the equation $\text{F}$(x₁,…,x_s) = 0 has a solution of this type? We deal with these questions as well as related problems in the group of integers modulo 1 and in the group of reals.     

Subordination,rank, and determinism of multivariate stationary sequences

Necessary and sufficient conditions for an arbitrary q-variate stationary sequence x_t, t ∈ $\text{Z}$, to be deterministic are presented. A characterization of the rank r(x) of x_t, t ∈ $\text{Z}$, and a method to construct the Wold-Cramér decomposition for x_t, t ∈ $\text{Z}$, are given. Subordination of q-variate bounded orthogonally scattered vector measures is considered.     

On the normal density of primes in short intervals

Selberg has shown on the basis of the Riemann hypothesis that for every ε > 0 most intervals |x,x+x^?| of length x^? contain approximately $\text{x}{}^{\mathrm{?}}\text{log}\text{x}$ primes. Here by “most” we mean “for a set of values of x of asymptotic density one.” Prachar has extended Selberg's result to primes in arithmetic progressions. Both authors noted that if we assume the quasi Riemann hypothesis, that ζ(s) has no zeros in the domain {$\text{σ>}\text{1}\text{2}\text{+δ}$} for some $\text{δ<}\text{1}\text{2}$, then the same conclusions hold, provided that ε > 2 δ. Here we give a simple proof of these theorems in a general context, where an arbitrary signed measure takes the place of d[ψ(x)?x]. Then we show by a counterexample that this general theorem is the best of its kind: the condition ε > 2δ cannot be replaced by ε = 2δ. In our example, the associated Dirichlet integral is an entire function which remains bounded on the domain {$\text{σ≥}\text{1}\text{2}\text{+δ}$}. Thus its growth and regularity properties are better than those of $\text{ζ′(s)}\text{ζ(s)}$. Nevertheless the corresponding signed measure behaves badly.     

On a family of connectives for fuzzy sets

In this paper we find the general solution of the functional equation $\text{S}{}^1\text{(T(x, y), T(x, N(y))) = x}$, where $\text{S}{}^1$ is a t-conorm, T is a t-norm and N is a strong negation on the unit interval. In particular the result yields a family of connectives for fuzzy sets.     

On the finite-source G/M/r queue

The aim of the present paper is to give the main characteristics of the finite-source $\text{G}\text{/}\text{M}\text{/r}$ queue in equilibrium. Here unit i stays in the source for a random time having general distribution function F_i(x) with density f_i(x). The service times of all units are assumed to be identically and exponentially distributed random variables with means 1/μ. It is shown that the solution to this $\text{G}\text{/}\text{M}\text{/r}$ model is similar in most important respects to that for the M/M/r model.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

Hilbert space representations of general discrete time stochastic processes

We show that under mild conditions the joint densities Px₁,…,x_n) of the general discrete time stochastic process X_n on $\text{pH}$ can be computed via

$\text{Px}{}_1\text{,…,x}{}_{\mathrm{n}}\text{(x}{}_1\text{,…,x}{}_{\mathrm{n}}\text{) = 6?T(x}{}_1\text{)…T(x}{}_{\mathrm{n}}\text{)6}{}^2$

where ? is in a Hilbert space $\text{pH}$, and T (x), x ? $\text{pH}$ are linear operators on $\text{pH}$. We then show how the Central Limit Theorem can easily be derived from such representations.     

Approximate solutions of functional differential equations

The author discusses the best approximate solution of the functional differential equation x′(t) = F(t, x(t), x(h(t))), 0 < t < l satisfying the initial condition x(0) = x₀, where x(t) is an n-dimensional real vector. He shows that, under certain conditions, the above initial value problem has a unique solution y(t) and a unique best approximate solution $\text{p}\text{?}{}_{\mathrm{k}}\text{(t)}$ of degree k (cf. [1]) for a given positive integer k. Furthermore, $\text{sup}{}_{\mathrm{0?t?l}}\text{¦}\text{p}\text{?}{}_{\mathrm{k}}\text{(t) ? y(t)¦ → 0}\text{as}\text{k → ∞}$, where ¦ · ¦ is any norm in Rⁿ.     

Modèles de Markov Triplet et filtrage de Kalman

Kalman filtering enables to estimate a multivariate unobservable process $\text{x}\text{={}\text{x}{}_{\mathrm{n}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ from an observed multivariate process $\text{y}\text{={}\text{y}{}_{\mathrm{n}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$. It admits a lot of applications, in particular in signal processing. In its classical framework, it is based on a dynamic stochastic model in which $\text{x}$ satisfies a linear evolution equation and the conditional law of $\text{y}$ given $\text{x}$ is given by the laws $\text{p(}\text{y}{}_{\mathrm{n}}\text{|}\text{x}{}_{\mathrm{n}}\text{)}$. In this Note, we propose two successive generalizations of the classical model. The first one, which leads to the “Pairwise” model, consists in assuming that the evolution equation of $\text{x}$ is indeed satisfied by the pair $\text{(}\text{x}\text{,}\text{y}\text{)}$. We show that the new model is strictly more general than the classical one, and yet still enables Kalman-like filtering. The second one, which leads to the “Triplet” model, consists in assuming that the evolution equation of $\text{x}$ is satisfied by a triplet $\text{(}\text{x}\text{,}\text{r}\text{,}\text{y}\text{)}$, in which $\text{r}\text{={}\text{r}{}_{\mathrm{n}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is an (artificial) auxiliary process. We show that the Triplet model is strictly more general than the Pairwise one, and yet still enables Kalman filtering. To cite this article: F. Desbouvries, W. Pieczynski, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Antieigenvalues: method of estimation and calculation

Let T be a linear operator on a Hilbert space $\text{H}$. A method of estimation and calcu+lation of inf{Re(Tx,x)/6Tx6:x?$\text{H}$, 6x6 = 1} as well as some other expressions containing two quadratic forms is proposed. This method is based on the Toeplitz- Hausdorff theorem on the convexity of the numerical range of any operator on $\text{H}$.