Local indicators for plurisubharmonic functions

The notion of index, classical in number theory and its calculation by P. Lelong (1997) for plurisubharmonic functions, allows to define an indicator which is applied to the study of the Monge–Ampère operator and a pluricomplex Green function.     

DC programming approaches for discrete portfolio optimization under concave transaction costs

The paper investigates DC programming and DCA for both modeling discrete portfolio optimization under concave transaction costs as DC programs, and their solution. DC reformulations are established by using penalty techniques in DC programming. A suitable global optimization branch and bound technique is also developed where a DC relaxation technique is used for lower bounding. Numerical simulations are reported that show the efficiency of DCA and the globality of its computed solutions, compared to standard algorithms for nonconvex nonlinear integer programs.     

A general two-sided matching market with discrete concave utility functions

In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley and (ii) the assignment model due to Shapley and Shubik. Recently, Eriksson and Karlander introduced a hybrid model, which was further generalized by Sotomayor. In this paper, we propose a common generalization of these models by utilizing the framework of discrete convex analysis introduced by Murota, and verify the existence of a pairwise-stable outcome in our general model.     

Using shortest paths in some transshipment problems with concave costs

This paper deals with the problem of solving an uncapacitated transshipment problem with either one source and several sinks or one sink and several sources. The cost function of the problem is concave in the amount shipped on each arc and thus local optima are possible. A characterization of adjacent extreme flows in terms of corresponding arborescences is given for this type of networks.This characterization together with shortest path methods is then used to attack the problems of finding local optima and of ranking extreme points.A real-world problem and computational evidence for the usefulness of the method are produced.     

A production-transportation problem with stochastic demand and concave production costs

Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs, at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges, so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand points. The objective function can then be represented as the difference of two convex functions, and is therefore called a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space, then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP]. We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently. Problems up to the size of 100 supply points and 500 demand points are solved. Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998     

The optimal mass transport problem for relativistic costs

In this paper, we study the optimal mass transportation problem in ${\mathbb{R}^{d}}$ for a class of cost functions that we call relativistic cost functions. Consider as a typical example, the cost function c(x, y) = h(x ? y) being the restriction of a strictly convex and differentiable function to a ball and infinite outside this ball. We show the existence and uniqueness of the optimal map given a relativistic cost function and two measures with compact support, one of the two being absolutely continuous with respect to the Lebesgue measure. With an additional assumption on the support of the initial measure and for supercritical speed of propagation, we also prove the existence of a Kantorovich potential and study the regularity of this map. Besides these general results, a particular attention is given to a specific cost because of its connections with a relativistic heat equation as pointed out by Brenier (Extended Monge–Kantorovich Theory. Optimal Transportation and Applications, 2003).     

Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints

We will propose a branch and bound algorithm for calculating a globally optimal solution of a portfolio construction/rebalancing problem under concave transaction costs and minimal transaction unit constraints. We will employ the absolute deviation of the rate of return of the portfolio as the measure of risk and solve linear programming subproblems by introducing (piecewise) linear underestimating function for concave transaction cost functions. It will be shown by a series of numerical experiments that the algorithm can solve the problem of practical size in an efficient manner. Received: July 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000     

Local search heuristics for multi-index assignment problems with decomposable costs

The multi-index assignment problem (MIAP) with decomposable costs is a natural generalization of the well-known assignment problem. Applications of the MIAP arise, for instance, in the field of multi-target multi-sensor tracking. We describe an (exponentially sized) neighbourhood for a solution of the MIAP with decomposable costs, and show that one can find a best solution in this neighbourhood in polynomial time. Based on this neighbourhood, we propose a local search algorithm. We empirically test the performance of published constructive heuristics and the local search algorithm on random instances; a straightforward iterated local search algorithm is also tested. Finally, we compute lower bounds to our problem, which enable us to assess the quality of the solutions found.     

Local a-posteriori error indicators for the Galerkin discretization of boundary integral equations

In this paper we present local a-posteriori error indicators for the Galerkin discretization of boundary integral equations. These error indicators are introduced and investigated by Babuška-Rheinboldt [3] for finite element methods. We transfer them from finite element methods onto boundary element methods and show that they are reliable and efficient for a wide class of integral operators under relatively weak assumptions. These local error indicators are based on the computable residual and can be used for controlling the adaptive mesh refinement. Received March 4, 1996 / Revised version received September 25, 1996     

Local optimality conditions for multicommodity flow problems with separable piecewise convex costs

We consider here a multicommodity flow network optimization problem with non-convex but piecewise convex arc cost functions. We derive complete optimality conditions for local minima based on negative-cost cycles associated with each commodity. These conditions do not extend to the convex non-smooth case.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Optimization for products of concave functions

Ifh denotes the product of finitely many concave non-negative functions on a compact interval [a, b], then it is shown that there exist pointsα andβ witha≤α≤β≤b such thath is strictly increasing on [α, α), constant on (α, β), and strictly decreasing on (β, b]. This structure theorem leads to an extension of several classical optimization results for concave functions on convex sets to the case of products of concave functions.     

Local expansion concepts for detecting transport barriers in dynamical systems

In the last two decades, the mathematical analysis of material transport has received considerable interest in many scientific fields such as ocean dynamics and astrodynamics. In this contribution we focus on the numerical detection and approximation of transport barriers in dynamical systems. Starting from a set-oriented approximation of the dynamics we combine discrete concepts from graph theory with established geometric ideas from dynamical systems theory. We derive the global transport barriers by computing the local expansion properties of the system. For the demonstration of our results we consider two different systems. First we explore a simple flow map inspired by the dynamics of the global ocean. The second example is the planar circular restricted three body problem with Sun and Jupiter as primaries, which allows us to analyze particle transport in the solar system.     

A deterministic inventory/production model with general inventory cost rate function and piecewise linear concave production costs

We present a thorough analysis of the economic production quantity model with shortages under a general inventory cost rate function and piecewise linear concave production costs. Consequently, an effective solution procedure, particularly useful for an approximation scheme, is proposed. A computational study is appended to illustrate the performance of the proposed solution procedure.     

Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs

Given two densities on with the same total mass, the Monge transport problem is to find a Borel map rearranging the first distribution of mass onto the second, while minimizing the average distance transported. Here distance is measured by a norm with a uniformly smooth and convex unit ball. This paper gives a complete proof of the existence of optimal maps under the technical hypothesis that the distributions of mass be compactly supported. The maps are not generally unique. The approach developed here is new, and based on a geometrical change-of-variables technique offering considerably more flexibility than existing approaches.

     

Convex dual for quadratic concave fractional programs

For a fractional program with a quadratic numerator and an arbitrary concave denominator, a new convex dual program is derived. Concepts of conjugate duality are used to obtain an explicit representation of the dual.The authors are grateful to two anonymous referees and the Associate Editor for their comments.