Canonical analysis of two convex polyhedral cones and applications

Canonical analysis of two convex polyhedral cones consists in looking for two vectors (one in each cone) whose square cosine is a maximum. This paper presents new results about the properties of the optimal solution to this problem, and also discusses in detail the convergence of an alternating least squares algorithm. The set of scalings of an ordinal variable is a convex polyhedral cone, which thus plays an important role in optimal scaling methods for the analysis of ordinal data. Monotone analysis of variance, and correspondence analysis subject to an ordinal constraint on one of the factors are both canonical analyses of a convex polyhedral cone and a subspace. Optimal multiple regression of a dependent ordinal variable on a set of independent ordinal variables is a canonical analysis of two convex polyhedral cones as long as the signs of the regression coefficients are given. We discuss these three situations and illustrate them by examples.     

l(infinity)-Approximation via Subdominants

Given a vector u and a certain subset K of a real vector space E, the problem of l(infinity)-approximation involves determining an element;u in K nearest to u in the sense of the l(infinity)-error norm. The subdominant u * of u is the upper bound (if it exists) of the set {xinK : x precedesu} (we let x precedesy if all coordinates of x are smaller than or equal to the corresponding coordinates of y). We present general conditions on K under which a simple relationship between the subdominant of u and a best l(infinity)-approximation holds. We specify this result by taking as K the cone of isotonic functions defined on a poset (X, precedes), the cone of convex functions defined on a subset of ℝ(N), the cone of ultrametrics on a set X, and the cone of tree metrics on a set X with fixed distances to a given vertex. This leads to simple optimal algorithms for the problem of best l(infinity)-fitting of distances by ultrametrics and by tree metrics preserving the distances to a fixed vertex (the latter provides a 3-approximation algorithm for the problem of fitting a distance by a tree metric). This simplifies the recent results of Farach, Kannan, and Warnow (1995) and of Agarwala et al. (1996). Copyright 2000 Academic Press.     

Experiments comparing qualitative approaches to rank ordering of multiattribute alternatives

ZAPROS, a method to support rank ordering tasks using ordinal input from decision makers, is discussed and compared with a preference cone technique and the analytic hierarchy process (AHP). It provides a means to identify inconsistencies in ordinal decision tasks, yielding verification and explanation of results for partial ordering of a large set of alternatives. The results indicate that ZAPROS provides no less accuracy in task solution, while having some advantages from a behavioural point of view. Comparative analysis of the effectiveness of the methods under consideration in accordance with differences in task characteristics is carried out.     

A multiple-objective dispersion problem

In this paper we study a multiple-objective dispersion problem from an efficient solution and value function perspective. A general fundamental theorem on non-dominance is given and a polar co-ordinate elimination heuristic is given for the case of R². Some general results are given for the existence of a linearly weighted objective function whose maximal value will give a most preferred solution, for convex or concave value functions, and a heuristic is developed for the case where these conditions do not hold.     

Approximation of Value Efficient Solutions

We introduce an approximation set to the value efficient set in multiobjective problems under partial information on the decision maker's preferences modelled by a vector value function. We show monotonicity and convergence properties based on increasingly precise vector value functions with two components, which improve the approximation and might be a support to possible solution methods. © 1997 John Wiley & Sons, Ltd.     

An axiomatic basis for distributional equality in utilitarianism

An axiomatic basis for a social preference ordering with interval-scaled utility levels satisfying the principles of anonymity and pareto superiority is elaborated. The ordering is required to be sensitive to distributional equality: Redistribution of utility income from poor to rich persons without changing their social rank should lead to a superior evaluation. The axiom of separability is weakened in order to make it compatible with distributional equality. We prove that every continuous ordering satisfying the upper axioms can be represented by a utility function which is positively linear on the convex cone of rank-ordered utility vectors. A modified unnormalized Gini coefficient is one possible choice, but it contradicts, as well as related proposals, the principle of adequacy of means for some distribution problems.     

An ordinal evaluation of categorical judgement data by random utilities and a corresponding correlation analysis

Categorical judgement data are analyzed along the lines of random utility theory. A class of orders is introduced (categorical weak orders); their characteristic vectors are regarded as points in a Euclidean space; their convex hull forms a polytope whose facets are fully characterized. This polytope is shown to correspond to an order polytope. Furthermore, its relation to the biorder polytope is pointed out. The convex representations of a given point of the polytope are discussed. The impact of these results on the methods of analyzing data arising from a categorical judgement procedure is outlined. In particular, some consequences are drawn with respect to the usual evaluation of correlations of such data.     

A global optimization approach for generating efficient points for multiobjective concave fractional programs

In this article, we present a global optimization approach for generating efficient points for multiobjective concave fractional programming problems. The main work of the approach involves solving an instance of a concave multiplicative fractional program (W̄). Problem (W̄) is a global optimization problem for which no known algorithms are available. Therefore, to render the approach practical, we develop and validate a branch and bound algorithm for globally solving problem (W̄). To illustrate the performance of the global optimization approach, we use it to generate efficient points for a sample multiobjective concave fractional program. Copyright © 2006 John Wiley & Sons, Ltd.     

Multiple-objective weighting factor auxiliary optimization problems

In this paper we consider the generation of efficient solutions using weighting factor, qth-power approaches for some non-convex auxiliary function optimization forms. Algorithms are given for finding e-optimal solutions for these optimization problems.     

Fourier‐Motzkin elimination method in MOLP problems

This paper introduces a method for finding the non‐dominated set in criterion space of an MOLP problem based on Fourier–Motzkin Elimination. The method incorporates a procedure that eliminates decision variables from constraints and transforms a feasible region from decision space to criterion space. While avoiding characterization of the efficient set in decision space, it finds the non‐dominated set in criterion space. After the decision maker's most preferred criterion vector has been identified, the corresponding efficient solutions can be found by backward substitution. The method was implemented in MATLAB using a tabular form and computational experiments were conducted. The results indicate that although the method performs well for relatively small problems, it can be computationally intensive for larger problems. Nonetheless, the method is intuitively appealing and it provides useful insights into the geometry and theory of MOLP. As such it makes it a valuable educational tool for students of multi‐criteria decision analysis. Copyright © 2003 John Wiley & Sons, Ltd.     

Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem

Untrained adults appear to have access to cognitive processes that allow them to perform well in the Euclidean version of the traveling salesperson problem (E-TSP). They do so despite the famous computational intractability of the problem, which stems from its combinatorial complexity. A current hypothesis is the humans' good performance is based on following a strategy of connecting boundary points in order (the convex hull hypothesis). Recently, an alternative has been proposed, that performance is governed by a strategy of avoiding crossings. We examined the crossing avoidance hypothesis from the perspectives of its capacity to explain existing data, its theoretical adequacy, and its ability to explain the results of three new experiments. In Experiment 1, effects on the solution quality of number of points versus number of interior points were compared. In Experiment 2, the distributions of observed paths were compared with those predicted from the two hypotheses. In Experiment 3, figural effects were varied to induce crossings. The results of the experiments were more consistent with the convex hull than with the crossing avoidance hypothesis. Despite its simplicity and intuitive appeal, crossing avoidance does not provide a complete alternative to the convex hull hypothesis. Further elucidation of human strategies and heuristics for optimization problems such as the E-TSP will aid our understanding of how cognitive processes have adapted to the demands of combinatorial difficulty.     

Constrained multidimensional unfolding of confusion matrices: Goal point and slide vector models

Two constrained multidimensional unfolding models, the goal point and slide vector models, are proposed for analyzing confusion matrices. In both models, the row and column stimuli are expressed as two sets of points in a low-dimensional space, where the difference vector connecting a column point to the corresponding row point indicates the change in the stimulus representation through a cognitive process. The difference vector is constrained by the hypothesis that the trend in the representational change is invariant across stimuli: the goal point model constrains all difference vectors to point toward a single point, and the slide vector model constrains all difference vectors to be parallel to each other. In both models the coordinates of points are estimated by the maximum-likelihood method. Examples illustrate that the two models allow us to examine hypotheses about invariant trends in representational changes and to grasp such trends from the resulting configurations.     

Logical processing of set inclusion relations in meaningful text

The present experiments attempted to resolve some recent conflicting findings in cognitive structure research between processing linear ordering and set inclusion relations described in meaningful paragraphs of text. In a self-paced study-test paradigm, college students studied such paragraphs. Definite processing differences were found for the two set-theoretic relations. Set inclusion test results were found to be due to faulty logical processing and not to memory retrieval problems. Subjects made invalid conversions of universally quantified statements and failed to make valid transitive inferences between such statements. This failure was found to be an increasing function of the distance separating the two terms in the set inclusion. No such problems were observed for linear orderings. The usual distance function was found: Accuracy on test questions about the ordering was an increasing function of the distance between the terms in the question. Results similar to those for linear orderings were observed for set inclusions when subjects were given special instructions about the validity and invalidity of symmetric and transitive inferences.     

Matrix approximations and subspace fitting

The problem of fitting a least-squares linear subspace to a higher dimensional set of points is solved by the use of matrix approximation results, both when the subspace is required to pass through a given point, and when it is not so restricted. In the latter case the subspace is shown to pass through the centroid of the point set. It is noted that the principal axes of the set of points enter into the problem in a natural manner.The author is indebted to Prof. Carl Eckart of the Department of Physics, University of Chicago, for much helpful comment and suggestion. To him are due the example of the last section and various other items throughout.     

A search asymmetry reversed by figure-ground assignment

We report evidence demonstrating that a search asymmetry favoring concave over convex targets can be reversed by altering the figure-ground assignment of edges in shapes. Visual search for a concave target among convex distractors is faster than search for a convex target among concave distractors (a search asymmetry). By using shapes with ambiguous local figure-ground relations, we demonstrated that search can be efficient (with search slopes around 10 ms/item) or inefficient (with search slopes around 30–40 ms/item) with the same stimuli, depending on whether edges are assigned to concave or convex "figures." This assignment process can operate in a top-down manner, according to the task set. The results suggest that attention is allocated to spatial regions following the computation of figure-ground relations in parallel across the elements present. This computation can also be modulated by top-down processes.     

A time–cost optimization of the national postal distribution network

The postal distribution network in the Czech Republic consists actually of 69 local transit centres (according to the administrative division of the Czech Republic). Each of them operates the post offices in the given region. Some of the important local transit centres can be selected as sorting centres—transhipment points for postal consignments. The aim of this paper is to present a bicriterial optimization model for the selection of the subset of transhipment points from the set of transit centres and choosing their appropriate equipment, such as sorting machines. Another important output of the model is the assignment of the transit centres to the sorting centres. There are two basic optimization criteria defined in this model: minimization of the sum of investment and operational costs connected with building and operating of the sorting centres and the maximization of the percentage of postal consignments delivered to the appropriate post office in the desired time (next day). The proposed model contains several thousands of zero‐one variables and constraints. The model has been verified, and the results accepted. Copyright © 1999 John Wiley & Sons, Ltd.     

The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems

The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters.     

Angular homeostasis: III. The formalism of discrete orbits in ontogeny

The formal properties of orbits in a plane are explored by elementary topology. The notions developed from first principles include: convex and polygonal orbits; convexity; orientation, winding number and interior; convex and star-shaped regions. It is shown that an orbit that is convex with respect to each of its interior points bounds a convex region. Also, an orbit that is convex with respect to a fixed point bounds a star-shaped region. Biological considerations that directed interest to these patterns are indicated, and the implications of the prospect of higher orders of star-shapedness mentioned.     

Multiobjective Blockmodeling for Social Network Analysis

To date, most methods for direct blockmodeling of social network data have focused on the optimization of a single objective function. However, there are a variety of social network applications where it is advantageous to consider two or more objectives simultaneously. These applications can broadly be placed into two categories: (1) simultaneous optimization of multiple criteria for fitting a blockmodel based on a single network matrix and (2) simultaneous optimization of multiple criteria for fitting a blockmodel based on two or more network matrices, where the matrices being fit can take the form of multiple indicators for an underlying relationship, or multiple matrices for a set of objects measured at two or more different points in time. A multiobjective tabu search procedure is proposed for estimating the set of Pareto efficient blockmodels. This procedure is used in three examples that demonstrate possible applications of the multiobjective blockmodeling paradigm.     

ERP responses to images of abstract artworks,photographs of natural scenes,and artificially created uncomfortable images

The idea of efficient coding in the visual brain allows for predictions for the processing of various types of images, including certain artworks, natural images and uncomfortable images. Efficient processing is thought to result in lower responses compared to less efficient processing. The efficiency of the processing is suggested to depend on the architecture of the visual system and the properties of the input image. In this study, neural responses were estimated using EEG across the categories of a set of five images of abstract artworks, a set of five photographs of natural images and a set of five computer-generated uncomfortable images. EEG responses to contrast-matched images were found to be lower for the set of five abstract artworks used in the study compared to the set of photographs of natural images, lending preliminary support for the idea that certain abstract artworks, for example the work of Pollock, may be processed efficiently.