Fixed points for fuzzy mappings

In this paper the problem of the existence and computation of fixed points for fuzzy mappings is approached. A fuzzy mapping R over a set X is defined to be a function attaching to each x in X a fuzzy subset R_χ of X. An element x of X is called fixed point of R iff its membership degree to R_χ is at least equal to the membership degree to R_χ of any y?X, i.e. R_χ(χ)? R_χ(y)(?y?X). Two existence theorems for fixed points of a fuzzy mapping are proved and an algorithm for computing approximations of such a fixed point is described. The convergence theorem of our algorithm is proved under the restrictive assumption that for any x in X, the membership function of R_χ has a ‘complementary function’. Examples of fuzzy mappings having this property are given, but the problem of proving general criteria for a function to have a complementary remain open.     

Bilevel optimization: on the structure of the feasible set

We consider bilevel optimization from the optimistic point of view. Let the pair (x, y) denote the variables. The main difficulty in studying such problems lies in the fact that the lower level contains a global constraint. In fact, a point (x, y) is feasible if y solves a parametric optimization problem L(x). In this paper we restrict ourselves to the special case that the variable x is one-dimensional. We describe the generic structure of the feasible set M. Moreover, we discuss local reductions of the bilevel problem as well as corresponding optimality criteria. Finally, we point out typical problems that appear when trying to extend the ideas to higher dimensional x-dimensions. This will clarify the high intrinsic complexity of the general generic structure of the feasible set M and corresponding optimality conditions for the bilevel problem U.     

Properties of sets admitting stable ɛ-selections

Sets in which some convex subsets admit local (global) continuous ?-selections are studied. In particular, it is shown that if, for any number ? > 0, some neighborhood O(x) of a point x in a Banach space X contains a dense (in O(x)) convex set K admitting an upper semicontinuous acyclic (in particular, continuous single-valued) ?-selection to an approximatively compact set M ? X, then x is a δ-sun point; if, in addition, X ∈ (R), then the set of all points nearest to x in M is a singleton.     

Sharp probability estimates for random walks with barriers

We give sharp, uniform estimates for the probability that a random walk of n steps on the reals avoids a half-line [y,∞) given that it ends at the point x. The estimates hold for general continuous or lattice distributions provided the fourth moment is finite.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Modified quasilinearization algorithm for optimal control problems with nondifferential constraints

This paper considers the numerical solution of optimal control problems involving a functionalI subject to differential constraints, nondifferential constraints, and terminal constraints. The problem is to find the statex(t), the controlu(t), and the parameter π so that the functional is minimized, while the constraints are satisfied to a predetermined accuracy. A modified quasilinearization algorithm is developed. Its main property is the descent property in the performance indexR, the cumulative error in the constraints and the optimality conditions. Modified quasilinearization differs from ordinary quasilinearization because of the inclusion of the scaling factor (or stepsize) α in the system of variations. The stepsize is determined by a one-dimensional search on the performance indexR. Since the first variation δR is negative, the decrease inR is guaranteed if α is sufficiently small. Convergence to the solution is achieved whenR becomes smaller than some preselected value. In order to start the algorithm, some nominal functionsx(t),u(t), π and nominal multipliers λ(t), ρ(t), μ must be chosen. In a real problem, the selection of the nominal functions can be made on the basis of physical considerations. Concerning the nominal multipliers, no useful guidelines have been available thus far. In this paper, an auxiliary minimization algorithm for selecting the multipliers optimally is presented: the performance indexR is minimized with respect to λ(t), ρ(t), μ. Since the functionalR is quadratically dependent on the multipliers, the resulting variational problem is governed by optimality conditions which are linear and, therefore, can be solved without difficulty. To facilitate the numerical solution on digital computers, the actual time θ is replaced by the normalized timet, defined in such a way that the extremal arc has a normalized time length Δt=1. In this way, variable-time terminal conditions are transformed into fixed-time terminal conditions. The actual time τ at which the terminal boundary is reached is regarded to be a component of the parameter π being optimized. The present general formulation differs from that of Ref. 3 because of the inclusion of the nondifferential constraints to be satisfied everywhere over the interval 0?t?1. Its importance lies in that (i) many optimization problems arise directly in the form considered here, (ii) there are problems involving state equality constraints which can be reduced to the present scheme through suitable transformations, and (iii) there are some problems involving inequality constraints which can be reduced to the present scheme through the introduction of auxiliary variables. Numerical examples are presented for the free-final-time case. These examples demonstrate the feasibility as well as the rapidity of convergence of the technique developed in this paper.     

Optimal adaptive solution of initial-value problems with unknown singularities

The optimal solution of initial-value problems in ODEs is well studied for smooth right-hand side functions. Much less is known about the optimality of algorithms for singular problems. In this paper, we study the (worst case) solution of scalar problems with a right-hand side function having r   continuous bounded derivatives in R$\mathbf{R}$, except for an unknown singular point. We establish the minimal worst case error for such problems (which depends on r similarly as in the smooth case), and define optimal adaptive algorithms. The crucial point is locating an unknown singularity of the solution by properly adapting the grid. We also study lower bounds on the error of an algorithm for classes of singular problems. In the case of a single singularity with nonadaptive information, or in the case of two or more singularities, the error of any algorithm is shown to be independent of r.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Dispersion of mass and the complexity of randomized geometric algorithms

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in Rn (the current best algorithm has complexity roughly n⁴, conjectured to be n³). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.     

Testing membership in matroid polyhedra

Given a matroid M on E and a nonnegative real vector x=(x_j:j∈E), a fundamental problem is to determine whether x is in the convex hull P of (incidence vectors of) independent sets of M. An algorithm is described for solving this problem for which the amount of computation is bounded by a polynomial in |E|, independently of x, allowing as steps tests of independence in M and additions, subtractions, and comparisons of numbers. In case x ∈ P, the algorithm finds an explicit representation for x which has additional nice properties; in case x ? P it finds a most-violated inequality of the system defining P. The same technique is applied to the problem of finding a maximum component-sum vector in the intersection of two matroid polyhedra and a box.     

Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain

Linear models are constructed for the numerical solution of the problem of packing the maximum possible number of equal ellipses of given size in a rectangular domain R. It is shown that the l _p metric can be used to determine the conditions under which ellipses with mutually orthogonal major axes (orthogonally oriented ellipses) do not intersect. In R a grid is constructed whose nodes generate a finite set T of points. It is assumed that the centers of the ellipses can be placed only at some points of T. The cases are considered when the major axes of all the ellipses are parallel to the x or y axis or the major axes of some of the ellipses are parallel to the x axis and the others, to the y axis. The problems of packing equal ellipses with centers in T are reduced to integer linear programming problems. A heuristic algorithm based on the linear models is proposed for solving the ellipse packing problems. Numerical results are presented that demonstrate the effectiveness of this approach.     

The Transitive Minimum Manhattan Subnetwork Problem in 3 dimensions

We consider the Minimum Manhattan Subnetwork (MMSN) Problem which generalizes the already known Minimum Manhattan Network (MMN) Problem: Given a set P of n points in the plane, find shortest rectilinear paths between all pairs of points. These paths form a network, the total length of which has to be minimized. From a graph theoretical point of view, a MMN is a 1-spanner with respect to the L₁ metric. In contrast to the MMN problem, a solution to the MMSN problem does not demand L₁-shortest paths for all point pairs, but only for a given set R⊆P×P of pairs. The complexity status of the MMN problem is still unsolved in ≥2 dimensions, whereas the MMSN was shown to be NP-complete considering general relations R in the plane. We restrict the MMSN problem to transitive relations R_T (Transitive Minimum Manhattan Subnetwork (TMMSN) Problem) and show that the TMMSN problem in 3 dimensions is NP-complete.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

A note on duality gaps in linear programming over convex sets

For certain types of mathematical programming problems, a related dual problem can be constructed in which the objective value of the dual problem is equal to the objective function of the given problem. If these two problems do not have equal values, a duality gap is said to exist. No such gap exists for pairs of ordinary dual linear programming problems, but this is not the case for linear programming problems in which the nonnegativity conditionx ? 0 is replaced by the condition thatx lies in a certain convex setK. Duffin (Ref. 1) has shown that, whenK is a cone and a certain interiority condition is fulfilled, there will be no duality gap. In this note, we show that no duality gap exists when the interiority condition is satisfied andK is an arbitrary closed convex set inR ⁿ .     

Standard bases concordant with the norm and computations in ideals and polylinear recurring sequences

Standard bases of ideals of the polynomial ring R[X] = R[x ₁, …, x _k ] over a commutative Artinian chain ring R that are concordant with the norm on R have been investigated by D. A. Mikhailov, A. A. Nechaev, and the author. In this paper we continue this investigation. We introduce a new order on terms and a new reduction algorithm, using the coordinate decomposition of elements from R. We prove that any ideal has a unique reduced (in terms of this algorithm) standard basis. We solve some classical computational problems: the construction of a set of coset representatives, the finding of a set of generators of the syzygy module, the evaluation of ideal quotients and intersections, and the elimination problem. We construct an algorithm testing the cyclicity of an LRS-family L _R (I), which is a generalization of known results to the multivariate case. We present new conditions determining whether a Ferre diagram $\mathcal{F}$ and a full system of $\mathcal{F}$ -monic polynomials form a shift register. On the basis of these results, we construct an algorithm for lifting a reduced Gröbner basis of a monic ideal to a standard basis with the same cardinality.     

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient if it is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.     

A class of quadratically convergent algorithms for constrained function minimization

The problem of minimizing a functionf(x) subject to the constraint ?(x)=0 is considered. Here,f is a scalar,x is ann-vector, and ? is anm-vector, wherem <n. A general quadratically convergent algorithm is presented. The conjugate-gradient algorithm and the variable-metric algorithms for constrained function minimization can be obtained as particular cases of the general algorithm. It is shown that, for a quadratic function subject to a linear constraint, all the particular algorithms behave identically if the one-dimensional search for the stepsize is exact. Specifically, they all produce the same sequence of points and lead to the constrained minimal point in no more thann ?r descent steps, wherer is the number of linearly independent constraints. The algorithms are then modified so that they can also be employed for a nonquadratic function subject to a nonlinear constraint. Some particular algorithms are tested through several numerical examples.     

A unification of the existence theorems of the nonlinear complementarity problem

The nonlinear complementarity problem is the problem of finding a point x in the n-dimensional Euclidean space,R ⁿ , such that x ? 0, f(x) ? 0 and 〈x,f(x)～ = 0, where f is a nonlinear continuous function fromR ⁿ into itself. Many existence theorems for the problem have been established in various ways. The aim of the present paper is to treat them in a unified manner. Eaves's basic theorem of complementarity is generalized, and the generalized theorem is used as a unified framework for several typical existence theorems.