Global Optimization in Practice: An Application to Interactive Multiple Objective Linear Programming

A multiple objective linear programming problem (P) involves the simultaneous maximization of two or more conflicting linear objective functions over a nonempty polyhedron X. Many of the most popular methods for solving this type of problem, including many well-known interactive methods, involve searching the efficient set X _E of the problem. Generally, however, X _E is a complicated, nonconvex set. As a result, concepts and methods from global optimization may be useful in searching X _E. In this paper, we will explain in theory, and show via an actual application to citrus rootstock selection in Florida, how the potential usefulness of the well-known interactive method STEM for solving problem (P) in this way, can depend crucially upon how accurately certain global optimization problems involving minimizations over X _E are solved. In particular, we will show both in theory and in practice that the choice of whether to use the popular but unreliable payoff table approach or to use one of the lesser known, more accurate global optimization methods to solve these problems can determine whether STEM succeeds or fails as a decision aid. Several lessons and conclusions of transferable value derived from this research are also given.     

A geometrical analysis of the efficient outcome set in multiple objective convex programs with linear criterion functions

This article performs a geometrical analysis of the efficient outcome setY _E of a multiple objective convex program (MLC) with linear criterion functions. The analysis elucidates the facial structure ofY _E and of its pre-image, the efficient decision setX _E . The results show thatY _E often has a significantly-simpler structure thanX _E . For instance, although both sets are generally nonconvex and their maximal efficient faces are always in one-to-one correspondence, large numbers of extreme points and faces inX _E can map into non-facial subsets of faces inY _E , but not vice versa. Simple tests for the efficiency of faces in the decision and outcome sets are derived, and certain types of faces in the decision set are studied that are immune to a common phenomenon called collapsing. The results seem to indicate that significant computational benefits may potentially be derived if algorithms for problem (MLC) were to work directly with the outcome set of the problem to find points and faces ofY _E , rather than with the decision set.     

Ambiguous loci of the metric projection onto compact starshaped sets in a Banach space

LetE be a real Banach space andL(E) the family of all nonempty compact starshaped subsets ofE. Under the Hausdorff distance,L(E) is a complete metric space. The elements of the complement of a first Baire category subset ofL(E) are called typical elements ofL(E). ForXL(E) we denote by the metrical projection ontoX, i.e. the mapping which associates to eachaE the set of all points inX closest toa. In this note we prove that, ifE is strictly convex and separable with dimE2, then for a typicalXL(E) the map is not single valued at a dense set of points. Moreover, we show that a typical element ofL(E) has kernel consisting of one point and set of directions dense in the unit sphere ofE.     

Unbounded Components in the Solution Sets of Strictly Quasiconcave Vector Maximization Problems

Let (P) denote the vector maximization problem

Function Spaces and Dieudonné Completeness

Abstract

For a completely regular space X and a normed space E let C_k (x, E) (resp., C_p (x, E)) be the set of all E-valued continuous maps on X endowed with the compact-open (resp., pointwise convergence) topology. It is shown that the set of all F-valued linear continuous maps on C_k (x, E) when equipped with the topology of uniform convergence on the members of some families of bounded subsets of C_k (x, E) is a complete uniform space if F is a Band space and X is Dieudonné complete. This result is applied to prove that Dieudonné completeness is preserved by linear quotient surjections from C_k (x, E) onto C_k (Y, E) (resp., from C_p (x, E) onto C_p (x, E)) provided E, F are Band spaces and Y is a k-space.     

Minimum L1-Distance Projection onto the Boundary of a Convex Set: Simple Characterization

We show that the minimum distance projection in the L ₁-norm from an interior point onto the boundary of a convex set is achieved by a single, unidimensional projection. Application of this characterization when the convex set is a polyhedron leads to either an elementary minmax problem or a set of easily solved linear programs, depending upon whether the polyhedron is given as the intersection of a set of half spaces or as the convex hull of a set of extreme points. The outcome is an easier and more straightforward derivation of the special case results given in a recent paper by Briec (Ref. 1).     

Exact and explicit analytic solutions of an extended Jabotinsky functional differential equation

A Banach space X will be called extensible if every operator E → X from a subspace E ⊂ X can be extended to an operator X → X. Denote by dens X. The smallest cardinal of a subset of X whose linear span is dense in X, the space X will be called automorphic when for every subspace E ⊂ X every into isomorphism T: E → X for which dens X/E = dens X/TE can be extended to an automorphism X → X. Lindenstrauss and Rosenthal proved that c ₀ is automorphic and conjectured that c ₀ and ℓ₂ are the only separable automorphic spaces. Moreover, they ask about the extensible or automorphic character of c ₀(Γ), for Γ uncountable. That c ₀(Γ) is extensible was proved by Johnson and Zippin, and we prove here that it is automorphic and that, moreover, every automorphic space is extensible while the converse fails. We then study the local structure of extensible spaces, showing in particular that an infinite dimensional extensible space cannot contain uniformly complemented copies of ℓ _n ^p , 1 ≤ p < ∞, p ≠ 2. We derive that infinite dimensional spaces such as L _p (μ), p ≠ 2, C(K) spaces not isomorphic to c ₀ for K metric compact, subspaces of c ₀ which are not isomorphic to c ₀, the Gurarij space, Tsirelson spaces or the Argyros-Deliyanni HI space cannot be automorphic. The work of the first author has been supported in part by project MTM2004-02635     

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.     

On well posedness of best simultaneous approximation problems in Banach spaces

The well posedness of best simultaneous approximation problems is considered. We establish the generic results on the well posedness of the best simultaneous approximation problems for any closed weakly compact nonempty subset in a strictly convex Kadec Banach space. Further, we prove that the set of all points inE(G) such that the best simultaneous approximation problems are not well posed is a u- porous set inE(G) whenX is a uniformly convex Banach space. In addition, we also investigate the generic property of the ambiguous loci of the best simultaneous approximation.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Hyperfinite Dimensional Representations of Spaces and Algebras of Measures

Let X be a locally compact topological space and (X, E, X_ω) be any triple consisting of a hyperfinite set X in a sufficiently saturated nonstandard universe, a monadic equivalence relation E on X, and an E-closed galactic set X_ω ⊆ X, such that all internal subsets of X_ω are relatively compact in the induced topology and X is homeomorphic to the quotient X_ω/E. We will show that each regular complex Borel measure on X can be obtained by pushing down the Loeb measure induced by some internal function X ? ^*\Bbb CX \rightarrow {}{^{\ast}{\Bbb C}} . The construction gives rise to an isometric isomorphism of the Banach space M(X) of all regular complex Borel measures on X, normed by total variation, and the quotient M_w(X)/M₀(X){\cal M}_{\omega}(X)/{\cal M}_0(X) , for certain external subspaces M₀(X), M_w(X){\cal M}_0(X), {\cal M}_{\omega}(X) of the hyperfinite dimensional Banach space ^*\Bbb C^X{}{^{\ast}{\Bbb C}}^X , with the norm ‖f‖₁ = ∑_{x ∈ X} |f(x)|. If additionally X = G is a hyperfinite group, X_ω = G_ω is a galactic subgroup of G, E is the equivalence corresponding to a normal monadic subgroup G₀ of G_ω, and G is isomorphic to the locally compact group G_ω/G₀, then the above Banach space isomorphism preserves the convolution, as well, i.e., M(G) and M_w(G)/M₀(G){\cal M}_{\omega}(G)/{\cal M}_0(G) are isometrically isomorphic as Banach algebras.     

Remotal Sets in Orlicz Spaces

Let X be a Banach space, (I, μ) be a finite measure space. By L ^Φ(I, X), let us denote the space of all X-valued Bochner Orlicz integrable functions on the unit interval I equipped with the Luxemburg norm. A closed bounded subset G of X is called remotal if for any x ∈ X, there exists g ∈ G such that ‖x ? g‖ = ρ(x, G) = sup {‖x ? y‖: y ∈ G}. In this article, we show that for a separable remotal set G ? X, the set of Bochner integrable functions, L ^Φ(I, G) is remotal in L ^Φ(I, X). Some other results are presented.     

On the Density of Positive Proper Efficient Points in a Normed Space

In the context of vector optimization and generalizing cones with bounded bases, we introduce and study quasi-Bishop-Phelps cones in a normed space X. A dual concept is also presented for the dual space X*. Given a convex subset A of a normed space X partially ordered by a closed convex cone S with a base, we show that, if A is weakly compact, then positive proper efficient points are sequentially weak dense in the set E(A, S) of efficient points of A; in particular, the connotation weak dense in the above can be replaced by the connotation norm dense if S is a quasi-Bishop-Phelps cone. Dually, for a convex subset of X* partially ordered by the dual cone S ⁺, we establish some density results of positive weak* efficient elements of A in E(A, S ⁺).     

Relations between ΛBV and BV(p(n) ↑∞) Classes of Functions

The base radical class L _b(X), generated by a class X was introduced in [12]. It consists of those rings whose nonzero homomorphic images have nonzero accessible subrings in X. When X is homomorphically closed, L _b(X) is the lower radical class defined by X, but otherwise X may not be contained in L _b(X). We prove that for a hereditary radical class L with semisimple class S(R), L _b(S(R)) is the class of strongly R-semisimple rings if and only if R is supernilpotent or subidempotent. A number of further examples of radical classes of the form L _b(X) are discussed. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal recovery of linear functionals on sets of finite dimension

Suppose that X is a linear space and L ₁, …, L _n is a system of linearly independent functionals on P, where P ? X is a bounded set of dimension n + 1. Suppose that the linear functional L ₀ is defined in X. In this paper, we find an algorithm that recovers the functional L ₀ on the set P with the least error among all linear algorithms using the information L ₁ f, …, L _n f, f ∈ P.     

<Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>(<Emphasis Type="Italic">μ</Emphasis>) for vector-valued measure <Emphasis Type="Italic">μ</Emphasis>

Let μ be a measure from a σ-algebra of subsets of a set T into a sequentially complete Hausdorff topological vector space X. Assume that μ is convexly bounded, i.e., the convex hull of its range is bounded in X, and denote by L ¹(μ) the space of scalar valued functions on T which are integrable with respect to the vector measure μ. We study the inheritance of some properties from X to L ¹(μ). We show that the bounded multiplier property passes from X to L ¹(μ). Answering a 1972 problem of Erik Thomas, we show that for a rather large class of F-spaces X the non-containment of c ₀ passes from X to L ¹(μ).     

Spherical Maximal Operators on Radial Functions

Let A_tf(x) denote the mean of f over a sphere of radius t and center x. We prove sharp estimates for the maximal function M_E f(X) = sup_t∈_E |Atf(x)| where E is a fixed set in IR⁺ and f is a radial function ∈ L^p(IR^d). Let P_d = d/(d?1) (the critical exponent for Stein's maximal function). For the cases (i) p < p_d, d ? 2, and (ii) p = p_d, d ? 3, and for p ? q ? ∞ we prove necessary and sufficient conditions on E for M_E to map radial functions in L^p to the Lorentz space L^P,q.     

On metrizable enveloping semigroups

When a topological group G acts on a compact space X, its enveloping semigroup E(X) is the closure of the set of g-translations, g ∈ G, in the compact space X ^X . Assume that X is metrizable. It has recently been shown by the first two authors that the following conditions are equivalent: (1) X is hereditarily almost equicontinuous; (2) X is hereditarily nonsensitive; (3) for any compatible metric d on X the metric d _G (x, y) ≔ sup{d(gx, gy): g ∈ G} defines a separable topology on X; (4) the dynamical system (G, X) admits a proper representation on an Asplund Banach space. We prove that these conditions are also equivalent to the following: the enveloping semigroup E(X) is metrizable.