Bounded Allocations of Discrete and Binary Resources

Mjelde described methods for the solution of problems of the allocation of discrete resources with binary effectiveness values of 0 or 1 against activities with concave return functions. This note extends these methods to problems with upper bounds on certain sums of allocation.     

Max-min resource allocation

A problem is considered of the allocation of resources so as to maximize the minimum return from several activities. Optimality conditions are given for the case of a single resource, and are used to derive a solution algorithm. Problems with several resources cannot be solved by resourcewise optimization. Concave return functions are treated approximately by linear programming, and optimality or almost optimality of any feasible solution to such a problem can be evaluated by the solution of a linear programming problem. The evaluation measure is extended to certain feasible solutions of problems which have continuous, but not necessarily concave, return functions. A numerical example is given.     

Fast value iteration: an application of Legendre-Fenchel duality to a class of deterministic dynamic programming problems in discrete time*

ABSTRACT

We propose an algorithm, which we call ‘Fast Value Iteration’ (FVI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FVI is an efficient algorithm applicable to a class of multidimensional dynamic programming problems with concave return (or convex cost) functions and linear constraints. In this algorithm, a sequence of functions is generated starting from the zero function by repeatedly applying a simple algebraic rule involving the Legendre-Fenchel transform of the return function. The resulting sequence is guaranteed to converge, and the Legendre-Fenchel transform of the limiting function coincides with the value function.     

Mean-variance models for portfolio selection with fuzzy random returns

This paper develops two novel types of mean-variance models for portfolio selection problems, in which the security returns are assumed to be characterized by fuzzy random variables with known possibility and probability distributions. In the proposed models, we take the expected return of a portfolio as the investment return and the variance of the expected return of a portfolio as the investment risk. We assume that the security returns are triangular fuzzy random variables. To solve the proposed portfolio problems, this paper first presents the variance formulas for triangular fuzzy random variables. Then this paper applies the variance formulas to the proposed models so that the original portfolio problems can be reduced to nonlinear programming ones. Due to the reduced programming problems include standard normal distribution in the objective functions, we cannot employ the conventional solution methods to solve them. To overcome this difficulty, this paper employs genetic algorithm (GA) to solve them, and verify the obtained optimal solutions via Kuhn-Tucker (K-T) conditions. Finally, two numerical examples are presented to demonstrate the effectiveness of the proposed models and methods.     

Trajectories, first return limiting notions and rings of H-connected and iteratively H-connected functions

In the paper the existing results concerning a special kind of trajectories and the theory of first return continuous functions connected with them are used to examine some algebraic properties of classes of functions. To that end we define a new class of functions (denoted Conn*) contained between the families (widely described in literature) of Darboux Baire 1 functions (DB₁) and connectivity functions (Conn). The solutions to our problems are based, among other, on the suitable construction of the ring, which turned out to be in some senses an “optimal construction”. These considerations concern mainly real functions defined on [0, 1] but in the last chapter we also extend them to the case of real valued iteratively H-connected functions defined on topological spaces.     

Generalized-Hukuhara penalty method for optimization problem with interval-valued functions and its application in interval-valued portfolio optimization problems

In this study, a gH-penalty method is developed to obtain efficient solutions to constrained optimization problems with interval-valued functions. The algorithmic implementation of the proposed method is illustrated. In order to develop the gH-penalty method, an interval-valued penalty function is defined and the characterization of efficient solutions of a CIOP is done. As an application of the proposed method, a portfolio optimization problem with interval-valued return is solved.     

Fractional Resource Allocation with S-Shaped Return Functions

A fractional resource allocation problem with S-shaped return functions and an affine cost function is considered. Properties of optimal solutions are derived, including conditions for certain allocations to be zero. Conditions are given for the determination of an optimal solution by concave approximations of the return functions; otherwise an error bound is obtained.     

Improving Solutions of a Class of Allocation Problems by Cyclic Shifts of Resources

A class of multi-resource allocation problems with non-linear return functions is considered, for which some dedicated numerical solution methods exist. The approximate solutions produced by these methods will typically not possess some minimal properties known to be present in the corresponding optimal solutions. The present paper shows how this defect can be corrected by a cyclical shift of resources in the solution matrix. A favourable side-effect is that the shifting process normally leads to an increase in the value of the objective function.     

模拟退火算法的改进及其应用

模拟退火算法是随机优化近似算法。本文首先介绍其物理背景和一般形式，然后通过对算法增加记忆和返回两个功能以及在算法之后链接一个局部搜索过程，改善了算法性能，接着将改进算法应用于解旅游商问题，最后对该算法作简要的性能评论。     

Discrete allocation of a linear resource according to a sum-of-products objective

The allocation of a linear resource according to the sum of the returns from independent activities is considered. The return from each activity is given by a product of concave and nondecreasing functions of a single allocation variable. The model can be used, for instance, to describe probabilities of success of several serial tasks, into which an activity is subdivided. An incremental algorithm is defined and conditions are given for the algorithm to generate an optimal solution; otherwise, the problem is solved by a two-step procedure involving the incremental maximization of the return corresponding to a single activity and the combination of the activities by dynamic programming. Examples are given of problems solvable and not solvable by the incremental algorithm.     

Optimal time-consistent investment and reinsurance policies for mean-variance insurers

This paper investigates the optimal time-consistent policies of an investment-reinsurance problem and an investment-only problem under the mean-variance criterion for an insurer whose surplus process is approximated by a Brownian motion with drift. The financial market considered by the insurer consists of one risk-free asset and multiple risky assets whose price processes follow geometric Brownian motions. A general verification theorem is developed, and explicit closed-form expressions of the optimal polices and the optimal value functions are derived for the two problems. Economic implications and numerical sensitivity analysis are presented for our results. Our main findings are: (i) the optimal time-consistent policies of both problems are independent of their corresponding wealth processes; (ii) the two problems have the same optimal investment policies; (iii) the parameters of the risky assets (the insurance market) have no impact on the optimal reinsurance (investment) policy; (iv) the premium return rate of the insurer does not affect the optimal policies but affects the optimal value functions; (v) reinsurance can increase the mean-variance utility.     

The Dependence of Optimal Returns from Multi-class Queueing Systems on Their Customer Base

We identify structured collections of multi-class queueing systems whose optimal return (a minimised cost) is a supermodular function of the set of customer classes allowed external access to the system. Our results extend considerably the range of systems for which such a claim can be made. The returns from such systems also exhibit a form of directional convexity when viewed as functions of a vector of arrival rates. Applications to load balancing problems are indicated.     

A weak linearization of the Kuhn-tucker conditions for a class of allocation problems

The return obtained from the allocation of resources to an activity is occasionally modelled by means of concave, strictly increasing functions. Exponential functions of a certain class conveniently lend themselves to such modelling. A nonlinear programming formulation of a multiresource allocation problem with return functions of the class appears to have Kuhn-Tucker conditions which in a sense are intrinsically linear. The paper shows how this fact can be utilised to save processing time in the execution of numerical algorithms for the solution of this mathematical programming problem.     

Optimization of a Multiperiod Resource Allocation Model

In this paper we examine multiperiod resource allocation problems, such as allocating a given marketing budget among T periods. The return functions of each period are assumed to be concave functions of the effective effort variable, which is composed of the expenditures in all previous periods and the present one. Assuming that the effect of an amount spent in period t is decreasing by a fixed rate in successive periods, necessary and sufficient conditions for a non-boundary optimal policy are derived. Under these conditions the optimal policy which maximizes total returns is obtained.     

Incremental allocation of a discrete and convex resource to concave activities

The problem considered is that of the allocation of a given quantity of a discrete resource to activities described by concave return functions. The resource-consumption corresponding to each allocation is described by a convex function of the quantity allocated. An incremental solution algorithm is given, which specializes to the algorithm of Fox if the resource is linear, and to an algorithm of Katoh, Ibaraki and Mine if the return functions are linear.     

The determinant of production entry and exit model on financing behavior

This study seeks for equity/debt values and the relevant potential firm value with financing or not when the real options approach is assessed. The paper deals with the following relative problems: (1) the assessment rule of decision whether to stop production or not; (2) whether the (dis) investment cost or salvage could reflect the production scale; (3) whether the rate of capital cost or the rate of return in different stages could reflect the suitable risk premium; (4) when the investment cost, exit cost, and salvage are the linear functions of production volume and follow the geometric Brownian motion to analyze the optimum external financing behavior and to decide the production thresholds of production entry and exit.     

Upper bounds for objective functions of discrete competitive facility location problems

Under study is the problem of locating facilities when two competing companies successively open their facilities. Each client chooses an open facility according to his own preferences and return interests to the leader firm or to the follower firm. The problem is to locate the leader firm so as to realize the maximum profit (gain) subject to the responses of the follower company and the available preferences of clients. We give some formulations of the problems under consideration in the form of two-level integer linear programming problems and, equivalently, as pseudo-Boolean two-level programming problems. We suggest a method of constructing some upper bounds for the objective functions of the competitive facility location problems. Our algorithm consists in constructing an auxiliary pseudo-Boolean function, which we call an estimation function, and finding the minimum value of this function. For the special case of the competitive facility location problems on paths, we give polynomial-time algorithms for finding optimal solutions. Some results of computational experiments allow us to estimate the accuracy of calculating the upper bounds for the competitive location problems on paths.     

Solving continuous min max problem for single period portfolio selection with discrete constraints by DCA

In this article, we consider the application of a continuous min–max model with cardinality constraints to worst-case portfolio selection with multiple scenarios of risk, where the return forecast of each asset belongs to an interval. The problem can be formulated as minimizing a convex function under mixed integer variables with additional complementarity constraints. We first prove that the complementarity constraints can be eliminated and then use Difference of Convex functions (DC) programming and DC Algorithm (DCA), an innovative approach in non-convex programming frameworks, to solve the resulting problem. We reformulate it as a DC program and then show how to apply DCA to solve it. Numerical experiments on several test problems are reported that demonstrate the accuracy of the proposed algorithm.