Maximal Element Theorems with Applications to Generalized Games and Systems of Generalized Vector Quasi-Equilibrium Problems in <Emphasis Type="Italic">G</Emphasis>-Convex Spaces

By applying the maximal element theorems on product of G-convex spaces due to the first author, some equilibrium existence theorems for generalized games with fuzzy constraint correspondences are proved in G-convex spaces. As applications, some existence theorems of solutions for the system of generalized vector quasiequilibrium problem are established in noncompact product of G-convex spaces. Our results improve and generalize some recent results in the literature to product of G-convex spaces.The authors thank the referees for valuable comments and suggestionsThe research of this author was supported by the National Science Foundation of China, Sichuan Education Department.The research of this author was supported by the National Science Council of the Republic of China.     

ℱ<Emphasis Type="Italic">K</Emphasis>-convex functions on metric spaces

 By an ℱK-convex function on a length metric space, we mean one that satisfies f ⁿ ≥ −Kf on all unitspeed geodesics. We show that natural ℱK-convex (-concave) functions occur in abundance on metric spaces of curvature bounded above (below) by K in the sense of Alexandrov. We prove Lipschitz extension and approximation theorems for ℱK-convex functions on CAT(K) spaces. Received: 10 May 2002 Mathematics Subject Classification (2000): 53C70, 52A41     

Optimality conditions and duality for a class of nondifferentiable multi-objective fractional programming problems

A class of multi-objective fractional programming problems (MFP) are considered where the involved functions are locally Lipschitz. In order to deduce our main results, we give the definition of the generalized (F,θ,ρ,d)-convex class about the Clarke’s generalized gradient. Under the above generalized convexity assumption, necessary and sufficient conditions for optimality are given. Finally, a dual problem corresponding to (MFP) is formulated, appropriate dual theorems are proved.      

The geometry of p-convex intersection bodies

Busemann's theorem states that the intersection body of an origin-symmetric convex body is also convex. In this paper we provide a version of Busemann's theorem for p-convex bodies. We show that the intersection body of a p-convex body is q-convex for certain q. Furthermore, we discuss the sharpness of the previous result by constructing an appropriate example. This example is also used to show that IK, the intersection body of K, can be much farther away from the Euclidean ball than K. Finally, we extend these theorems to some general measure spaces with log-concave and s-concave measures.     

Second Order (F, α, ρ, d,E)-convex function and the Duality Problem

A class of second order (F, α, ρ, d, E)-convex functions and their generalization on functions involved, weak, strong, and converse duality theorems are established for a second order Mond-Weir type dual problem.     

Property A in an Infinite-Dimensional Space. I

   Abstract. We prove that an infinite-dimensional space of piecewise polynomial functions of degree at most n-1 with infinitely many simple knots, n ≥ 2 , satisfies Property A. Apart from its independent interest, this result allows us to solve an open classical problem (n ≥ 3 ) in theory of best approximation: the uniqueness of best L ₁ -approximation by n -convex functions to an integrable, continuous function defined on a bounded interval. In this first part of the paper we prove the case n=2 and give key results in order to complete the general proof in the second part.     

Outer Γ-Convexity in Vector Spaces

A subset S of some vector space X is said to be outer Γ-convex w.r.t. some given balanced subset Γ ? X if for all x ₀, x ₁ ? S there exists a closed subset Λ ? [0,1] such that {x _λ | λ ? Λ} ? S and [x ₀, x ₁] ? {x _λ | λ ? Λ} + 0.5 Γ, where x _λ: = (1 ? λ)x ₀ + λ x ₁. A real-valued function f:D → ? defined on some convex D ? X is called outer Γ-convex if for all x ₀, x ₁ ? D there exists a closed subset Λ ? [0,1] such that [x ₀, x ₁] ? {x _λ | λ ? Λ} + 0.5 Γ and f(x _λ) ≤ (1 ? λ)f(x ₀) + λ f(x ₁) holds for all λ ? Λ. Outer Γ-convex functions possess some similar optimization properties as these of convex functions, e.g., lower level sets of outer Γ-convex functions are outer Γ-convex and Γ-local minimizers are global minimizers. Some properties of outer Γ-convex sets and functions are presented, among others a simplex property of outer Γ-convex sets, which is applied for establishing a separation theorem and for proving the existence of modified subgradients of outer Γ-convex functions.     

From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective

We design an algorithm, called the fluid synchronization algorithm (FSA), for the job shop scheduling problem with the objective of minimizing the makespan. We round an optimal solution to a fluid relaxation, in which we replace discrete jobs with the flow of a continuous fluid, and use ideas from fair queueing in the area of communication networks in order to ensure that the discrete schedule is close to the one implied by the fluid relaxation. FSA produces a schedule with makespan at most C _max+(I+2)P _max J _max, where C _max is the lower bound provided by the fluid relaxation, I is the number of distinct job types, J _max is the maximum number of stages of any job-type, and P _max is the maximum processing time over all tasks. We report computational results based on all benchmark instances chosen from the OR library when N jobs from each job-type are present. The results suggest that FSA has a relative error of about 10% for N=10, 1% for N=100, 0.01% for N=1000. In comparison to eight different dispatch rules that have similar running times as FSA, FSA clearly dominates them. In comparison to the shifting bottleneck heuristic whose running time and memory requirements are several orders of magnitude larger than FSA, the shifting bottleneck heuristic produces better schedules for small N (up to 10), but fails to provide a solution for larger values of N. Received: September 1999 / Accepted: September 2001?Published online March 14, 2002     

On the E-Epigraph of an E-Convex Function

In Ref 1, Yang shows that some of the results obtained in Ref. 2 on E-convex programming are incorrect, but does not prove that the results which make the connection between an E-convex function and its E-epigraph are incorrect. In this note, we show that the results obtained in Ref. 2 concerning the characterization of an E-convex function f in terms of its E-epigraph are incorrect. Afterward, some characterizations of E-convex functions using a different notion of epigraph are given.     

Asymptotic Behavior of Solutions of Inverse Problems for Degenerate Parabolic Equations

We obtain theorems on the proximity as t → +∞ between the solution of the inverse problem for a second-order degenerate parabolic equation with one spatial variable and the solution of the inverse problem for a second-order degenerate ordinary differential equation under an additional integral observation condition. The conditions imposed on the input data admit oscillations of the functions on the right-hand side in the parabolic equation under study.     

E-Convex Sets, E-Convex Functions, and E-Convex Programming

A class of sets and a class of functions called E-convex sets and E-convex functions are introduced by relaxing the definitions of convex sets and convex functions. This kind of generalized convexity is based on the effect of an operator E on the sets and domain of definition of the functions. The optimality results for E-convex programming problems are established.     

On the uniqueness of an element of the best L 1-approximation for functions with values in a banach space

We study the problem of uniqueness of an element of the best L ₁-approximation for continuous functions with values in a Banach space. We prove two theorems that characterize the uniqueness subspaces in terms of certain sets of test functions.     

Nondifferentiable multiobjective second-order symmetric duality

In this paper, a pair of Wolfe type second-order multiobjective symmetric dual programs involving nondifferentiable functions is formulated. Weak, strong and converse duality theorems are then established using the notion of second-order F-convexity assumptions. An example which is second-order F-convex but not convex is also illustrated. Further, special cases are discussed to show that this paper extends some known results of the literature.     

Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing

We propose asymptotically optimal algorithms for the job shop scheduling and packet routing problems. We propose a fluid relaxation for the job shop scheduling problem in which we replace discrete jobs with the flow of a continuous fluid. We compute an optimal solution of the fluid relaxation in closed form, obtain a lower bound C_max to the job shop scheduling problem, and construct a feasible schedule from the fluid relaxation with objective value at most where the constant in the O( · ) notation is independent of the number of jobs, but it depends on the processing time of the jobs, thus producing an asymptotically optimal schedule as the total number of jobs tends to infinity. If the initially present jobs increase proportionally, then our algorithm produces a schedule with value at most C_max + O(1). For the packet routing problem with fixed paths the previous algorithm applies directly. For the general packet routing problem we propose a linear programming relaxation that provides a lower bound C_max and an asymptotically optimal algorithm that uses the optimal solution of the relaxation with objective value at most Unlike asymptotically optimal algorithms that rely on probabilistic assumptions, our proposed algorithms make no probabilistic assumptions and they are asymptotically optimal for all instances with a large number of jobs (packets). In computational experiments our algorithms produce schedules which are within 1% of optimality even for moderately sized problems.     

Optimality conditions and duality models for generalized fractional programming problems containing locally subdifferentiable and ρ:-convex functions

Both parametric and nonparametric necessary and sufficient optimality conditions are established for a class of nonsmooth generalized fractional programming problems containing ρ-convex functions. Subsequently, these optimality criteria are utilized as a basis for constructing two parametric and four parameter-free duality models and proving appropriate duality theorems. Several classes of generalized fractional programming problems, including those with arbitrary norms, square roots of positive semidefinite quadratic forms, support functions, continuous max functions, and discrete max functions, which can be viewed as special cases of the main problem are briefly discussed. The optimality and duality results developed here also contain, as special cases, similar results for nonsmooth problems with fractional, discrete max, and conventional objective functions which are particular cases of the main problem considered in this paper     

Comparison theorems for symplectic systems of difference equations

In the present paper, we prove comparison theorems for symplectic systems of difference equations, which generalize difference analogs of canonical systems of differential equations. We obtain general relations between the number of focal points of conjoined bases of two symplectic systems with matrices W _i and $ \hat W_i $ \hat W_i as well as their corollaries, which generalize well-known comparison theorems for Hamiltonian difference systems. We consider applications of comparison theorems to spectral theory and in the theory of transformations. We obtain a formula for the number of eigenvalues λ of a symplectic boundary value problem on the interval (λ ₁, λ ₂]. For an arbitrary symplectic transformation, we prove a relationship between the numbers of focal points of the conjoined bases of the original and transformed systems. In the case of a constant transformation, we prove a theorem that generalizes the well-known reciprocity principle for discrete Hamiltonian systems.     

Optimization of Second-Order Discrete Approximation Inclusions

The present article studies the approximation of the Bolza problem of optimal control theory with a fixed time interval given by convex and non-convex second-order differential inclusions (P _C ). Our main goal is to derive necessary and sufficient optimal conditions for a Cauchy problem of second-order discrete inclusions (P _D ). As a supplementary problem, discrete approximation problem (P _DA ) is considered. Necessary and sufficient conditions, including distinctive transversality, are proved by incorporating the Euler-Lagrange and Hamiltonian type of inclusions. The basic concept of obtaining optimal conditions is the locally adjoint mappings (LAM) and equivalence theorems, one of the most characteristic features of such approaches with the second-order differential inclusions that are peculiar to the presence of equivalence relations of LAMs. Furthermore, the application of these results are demonstrated by solving some non-convex problem with second-order discrete inclusions.     

The Inverse Problem of Simultaneous Determination of the Two Time-Dependent Lower Coefficients in a Nondivergent Parabolic Equation in the Plane

We prove existence and uniqueness theorems for the solution of the inverse problem of simultaneous determination of the t-dependent coefficients of u and u_x in a nondivergent parabolic equation with two independent variables from integral observation of x. Estimates of the maxima of the moduli of these coefficients with constants explicitly expressed in terms of the input data of the problem are given. An example of an inverse problem to which the proved theorems apply is presented.

     

On a Class of p- Valently α-Convex Functions

The object of the present is to prove some properties of a class M_p(α) of p-valently α-convex Functions in the unit disk. Also, an integral representation for functions belonging to the class M_p(α) is shown.     

Constrained Lp-Approximation by Generalized n-Convex Functions Induced by ECT-Systems

The problem of finding a best L_p-approximation (1 ≤ p < ∞) to a function in L_p from a special subcone of generalized n-convex functions induced by an ECT-system is considered. Tchebycheff splines with a countably infinite number of knots are introduced and best approximations are characterized in terms of local best approximations by these splines. Various properties of best approximations and their uniqueness in L₁ are investigated. Some special results for generalized monotone and convex cases are obtained.