A set scalarization function based on the oriented distance and relations with other set scalarizations

ABSTRACT

The aim of this paper is, in the setting of normed spaces with a cone K non necessarily solid, to study new relations among set scalarization functions that are extensions of the oriented distance of Hiriart-Urruty. Moreover, we deal with a set scalarization function of sup-inf type, we investigate its relation to the cone-properness and cone-boundedness and it is related to other set scalarizations existing in the literature. In particular, with the norm induced by the Minkowski's functional, we obtain relations with a set scalarization which is an extension of the so called Gerstewitz's scalarization function.     

Projective Minkowski set

The Minkowski set or the central symmetry set (CSS) of a smooth curve Γ on the affine plane is the envelope of chords connecting pairs of points such that the tangents to Γ at them are parallel. Singularities of CSS are of interest, in particular, for applications (for example, in computer graphics). A generalization of the Minkowski set is considered in the paper, namely, the projective Minkowski set with respect to a line on the plane; in the case of general position, we describe its singularities and the bifurcation set of lines corresponding to lines defining the projective Minkowski set having singularities being more degenerate than those of the Minkowski set for a generic line.     

Upper Semicontinuity of the Solution set to Parametric Vector Quasivariational Inequalities

We prove the upper semicontinuity (in term of the closedness) of the solution set with respect to parameters of vector quasivariational inequalities involving multifunctions in topological vector spaces under the semicontinuity of the data, avoiding monotonicity assumptions. In particular, a new quasivariational inequality problem is proposed. Applications to quasi-complementarity problems are considered This work was partially supported by the program “Optimisation et Mathématiques Appliquées” of C.I.U.F-C.U.D./C.U.I. of Belgium and by the National Basic Research Program in Natural Sciences of NCSR of Vietnam     

On the Julia set of the perturbed Mandelbrot map

In this work, we present numerical results which support the smooth decomposition method of the generalized Julia set by Peintge et al., in the case of other perturbations of the Mandelbrot map studied in our previous work (Argyris J, Andreadis I, Karakasidis T. Chaos, Solitons & Fractals 1999). We also calculate the generalized Julia set of a Mandelbrot map subject to noise. Hence, we are in a position to examining numerically the stability of this set under small noise.     

Ranking fuzzy numbers with maximizing set and minimizing set

Up to now, these are five methods of ranking n fuzzy numbers in order, but these methods contain some confusions and occasionally conflict with intuition. This paper introduces the concept of maximizing set and minimizing set to decide the ordering value of each fuzzy number and uses these values to determine the order of the n fuzzy numbers. In addition, we give a method for calculating the ordering value of each fuzzy number with triangular, trapezoidal, and two-sided drum-like shaped membership functions.     

Ultrafilters on the collection of finite subsets of an infinite set

Let $J$ be an infinite set and let $I={\cal P}_{f}( J)$, i.e., $I$ is the collection of all non empty finite subsets of $J$. Let $\beta I$ denote the collection of all ultrafilters on the set $I$. In this paper, we consider $( \beta I,\uplus ),$ the compact (Hausdorff) right topological semigroup that is the {\it Stone-$\check{C}\!\!$ech} $Compactification$ of the semigroup $\left( I,\cup \right)$ equipped with the discrete topology. It is shown that there is an injective map $A\rightarrow \beta _{A}( I) $ of ${\cal P}( J) $ into ${\cal P}( \beta I) $ such that each $\beta _{A}( I) $ is a closed subsemigroup of $ ( \beta I,\uplus ) $, the set $\beta _{J}( I) $ is a closed ideal of $( \beta I,\uplus ) $and the collection $\{ \beta _{A}( I) \mid A\in {\cal P} ( J) \} $ is a partition of $\beta I$. The algebraic structure of $\beta I$ is explored. In particular, it is shown that {\bf (1)} $\beta _{J}\left( I\right) =\overline{K( \beta I) }$, i.e., $\beta _{J}( I) $is the closure of the smallest ideal of $\beta I$, and {\bf (2)} for each non empty $A\subset J$, the set ${\cal V}_{A}=\tbigcup \{ \beta_{B}( I) \mid B\subset A\} $is a closed subsemigroup of $( \beta I,\uplus ) ,$ $\beta _{A}( I) $ is a proper ideal of ${\cal V}_{A},$ and ${\cal V}_{A}$ is the largest subsemigroup of $( \beta I,\uplus ) $ that has $ \beta _{A}( I) $ as an ideal.     

Back and forth error compensation and correction methods for semi-lagrangian schemes with application to level set interface computations

Semi-Lagrangian schemes have been explored by several authors recently for transport problems, in particular for moving interfaces using the level set method. We incorporate the backward error compensation method developed in our paper from 2003 into semi-Lagrangian schemes with almost the same simplicity and three times the complexity of a first order semi-Lagrangian scheme but with improved order of accuracy. Stability and accuracy results are proved for a constant coefficient linear hyperbolic equation. We apply this technique to the level set method for interface computation.

     

Texture separation via a reference set

Patch-based de-noising algorithms and patch manifold smoothing have emerged as efficient de-noising methods. This paper provides a new insight on these methods. We show how to extend them to separate oscillatory patterns that could be entangled. A collection of particular patches, that we call reference set, is selected by the user. We define a notion of similarity relative to this reference set that is used to extend the Non-Local Means (see Buades et al., 2005) [1] and the graph-based de-noising method (see Szlam et al., 2008) [12].     

Algorithms for large scale set covering problems

This paper is concerned with the set covering problem (SCP), and in particular with the development of a new algorithm capable of solving large-scale SCPs of the size found in real-life situations. The set covering problem has a wide variety of practical applications which, in general, yield large and sparse instances, normally with hundreds of rows and thousands of columns. In this paper, we present an algorithm capable of solving problems of this size and test problems up to 400 rows and 4000 columns are solved. The method developed in this paper consists of a tree-search procedure based on a combination of decomposition and state space relaxation which is a technique developed for obtaining lower bounds on the dynamic program associated with a combinatorial optimization problem. The large size SCPs are decomposed into many smaller SCPs which are then solved or bounded by state space relaxation (SSR). Before using the decomposition and SSR, reductions both in the number of columns and the number of rows of the problem are made by applying Lagrangian relaxation, linear programming and heuristic methods.     

A partial order for the set of meanders

In this paper, we present a new approach for studying meanders in terms of noncrossing partitions. We show how this approach leads to a natural partial order on the set of meanders. In particular, meanders form a graded poset with regard to this partial order.     

Nested set complexes for posets and the Bier construction

We generalize the concept of combinatorial nested set complexes to posets and exhibit the topological relationship between the arising nested set complexes and the order complex of the underlying poset. In particular, a sufficient condition is given so that this relationship is actually a subdivision.

We use the results to generalize the proof method of Čukić and Delucchi, so far restricted to semilattices, for a result of Björner, Paffenholz, Sjöstrand and Ziegler on the Bier construction on posets.

     

SimultaneousL 1 approximation of a compact set of real-valued functions

Summary In this paper the uniqueness results found in simultaneous Chebychev approximation are extended to simultaneousL ₁ approximation. In particular a sufficient condition to guarantee uniqueness of a best approximate to aL ₁ compact set is given.This paper is taken in part from a thesis to be submitted by M. P. Carroll in partial fulfillment of the requirements for the Ph. D. degree in the Department of Mathematics at Rensselaer Polytechnic Institute.     

Trees with extremal numbers of maximal independent sets including the set of leaves

A subset S of vertices of a graph G is independent if no two vertices in S are adjacent. In this paper we study maximal (with respect to set inclusion) independent sets in trees including the set of leaves. In particular the smallest and the largest number of these sets among n-vertex trees are determined characterizing corresponding trees. We define a local augmentation of trees that preserves the number of maximal independent sets including the set of leaves.     

On the structure of a random sum-free set

Summary There is a natural probability measure on the set of all sum-free sets of natural numbers. If we represent such a set by its characteristic functions, then the zero-one random variabless(i) are far from independent, and we cannot expect a law of large numbers to hold for them. In this paper I conjecture a decomposition of into countably many more tractible pieces (up to a null set). I prove that each piece has positive measure, and show that, within each piece, a random set almost surely has a density which is a fixed rational number depending only on the piece. For example, the first such piece is made up of sets consisting entirely of odd numbers; it has probability 0.218 ..., and its members almost surely have density 1/4.     

Technical diagnostic of a fleet of vehicles using rough set theory

The paper presents a process of technical diagnostic applied to a fleet of vehicles utilized in the delivery system of express mail. It is focused on evaluation of diagnostic capacity of particular characteristics, reduction of a set of initially selected characteristics to a minimal and satisfactory subset, recognition of a technical condition of vehicles resulting in their condition-based classification. In addition, the decision rules facilitating technical diagnostic and management of a fleet of vehicles are generated and utilized. N-fold cross validation is applied to estimate the efficiency of the decision rules. The rough set theory is applied to support the diagnostic process of vehicles. Classical rough set (CRS) theory is compared with the dominance-based rough set (DRS) approach. The results of computational experiments for both approaches are compared.     

On the Dedekind-MacNeille closure of an ordered set and a theorem of Novák

V. Novák proved: If H is an ordered set and G ? H a subset such that every element of H is = supS = in f T for sets S, T ? G, then H has the same dimension as G. In particular this implies that the Dedekind-MacNeille closure of an ordered set S has the same dimension as S. In this paper we give a short proof of the latter statement.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

A polygonal upper bound for the efficient set for single-facility location problems with mixed norms

Summary In this paper it is shown that, in a multiobjective single-facility location problem in which distances are measured by arbitrary mixed norms, the set of efficient points is a subset of apolygonal hull of the demand points. Using a certain type of projection, this hull can be easily built. We apply this to a certain family of norms, containing the set ofl _p -norms, and, in a particular case, classical results are obtained.     

Simple and fast surrogate constraint heuristics for the maximum independent set problem

In a recent paper Glover (J. Heuristics 9:175–227, 2003) discussed a variety of surrogate constraint-based heuristics for solving optimization problems in graphs. The key ideas put forth in the paper were illustrated by giving specializations designed for certain covering and coloring problems. In particular, a family of methods designed for the maximum cardinality independent set problem was presented. In this paper we report on the efficiency and effectiveness of these methods based on considerable computational testing carried out on test problems from the literature as well as some new test problems.     

Optimal competence set expansion using deduction graphs

A competence set is a collection of skills used to solve a problem. Based on deduction graph concepts, this paper proposes a method of finding an optimal process so as to expand a decision maker's competence set to enable him to solve his problem confidently. Using the concept of minimum spanning tree, Yu and Zhang addressed the problem of the optimal expansion of competence sets. In contrast, the method proposed here enjoys the following advantages: it can deal with more general problems involving intermediate skills and compound skills; it can find the optimal solution by utilizing a 0–1 integer program; and it can be directly extended to treat multilevel competence set problems, and thus is more practically useful.This work was supported by the National Science Council, Taipei, Taiwan, Republic of China, Grant No. NSC-81-0301-H-009-501.