Cost allocation and convex data envelopment

This paper considers allocation rules. First, we demonstrate that costs allocated by the Aumann–Shapley and the Friedman–Moulin cost allocation rules are easy to determine in practice using convex envelopment of registered cost data and parametric programming. Second, from the linear programming problems involved it becomes clear that the allocation rules, technically speaking, allocate the non-zero value of the dual variable for a convexity constraint on to the output vector. Hence, the allocation rules can also be used to allocate inefficiencies in non-parametric efficiency measurement models such as Data Envelopment Analysis (DEA). The convexity constraint of the BCC model introduces a non-zero slack in the objective function of the multiplier problem and we show that the cost allocation rules discussed in this paper can be used as candidates to allocate this slack value on to the input (or output) variables and hence enable a full allocation of the inefficiency on to the input (or output) variables as in the CCR model.     

Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions

The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.     

Adaptive methods for solvings minimax problems ∗

We consider finite-dimensional minimax problems for two traditional models: firstly,with box constraints at variables and,secondly,taking into account a finite number of tinear inequalities. We present finite exact primal and dual methods. These methods are adapted to a great extent to the specific structure of the cost function which is formed by a finite number of linear functions. During the iterations of the primal method we make use of the information from the dual problem, thereby increasing effectiveness. To improve the dual method we use the “long dual step” rule (the principle of ullrelaxation).The results are illustrated by numerical experiments.     

Constructive Approximation by Superposition of Sigmoidal Functions

In this paper, a constructive theory is developed for approximating functions of one or more variables by superposition of sigmoidal functions. This is done in the uniform norm as well as in the $L^p$ norm. Results for the simultaneous approximation, with the same order of accuracy, of a function and its derivatives (whenever these exist), are obtained. The relation with neural networks and radial basis functions approximations is discussed. Numerical examples are given for the purpose of illustration.     

Differential sensitivity of solutions of convex constrained optimal control problems for discrete systems

A family of optimal control problems for discrete systems that depend on a real parameter is considered. The problems are strongly convex and subject to state and control constraints. Some regularity conditions are imposed on the constraints.The control problems are reformulated as mathematical programming problems. It is shown that both the primal and dual optimal variables for these problems are right-differentiable functions of a parameter. The right-derivatives are characterized as solutions to auxiliary quadratic control problems. Conditions of continuous differentiability are discussed, and some estimates of the rate of convergence of the difference quotients to the respective derivatives are given.     

Slopes of shadow prices and Lagrange multipliers

Many economic models and optimization problems generate (endogenous) shadow prices—alias dual variables or Lagrange multipliers. Frequently the “slopes” of resulting price curves—that is, multiplier derivatives—are of great interest. These objects relate to the Jacobian of the optimality conditions. That particular matrix often has block structure. So, we derive explicit formulas for the inverse of such matrices and, as a consequence, for the multiplier derivatives.     

Comparison Between Baumann and Admissible Simplex Forms in Interval Analysis

Two ways for bounding n-variables functions over a box, based on interval evaluations of first order derivatives, are compared. The optimal Baumann form gives the best lower bound using a center within the box. The admissible simplex form, proposed by the two last authors, uses point evaluations at n + 1 vertices of the box. We show that the Baumann center is within any admissible simplex and can be represented as a linear convex combination of its vertices with coefficients equal to the dual variables of the linear program used to compute the corresponding admissible simplex lower bound. This result is applied in a branch-and-bound global optimization and computational results are reported.     

Adaptation of the plant location model for regional environmental facilities and cost allocation strategy

This paper is divided into two parts. In the first part of the paper, the plant location model is adapted for the special case of siting wastewater treatment facilities when the wastewater sources and treatment facilities are arranged in a chain or linear configuration. In this problem, flows or shipments may be merged in common pipes that provide economies of scale in transport. In order to apply the plant location model, an appropriate definition of the additional cost incurred when a waste source joins a regional facility is required. In addition, sequential priority constraints are developed in the siting model in order to make possible proper accounting of transport costs. The new siting model can be conveniently solved by linear programming.In the second part of the paper, a dual of the plant location model is explored as a cost allocation method for the fixed charge facility siting problem. The constraint sets of the dual model can be shown to imply the core conditions of the related cost game; hence, a set of the dual variables from the dual problem can be regarded as rational cost allocations. The analysis places both facility siting and cost allocation in a common framework.     

多变量、多约束连续或离散的非线性规划的一个通用算法

利用目标函数对约束函数关于设计变量的一阶微分或差分之比,给出了一个求解非线性规划的通用算法．不论变量和约束有多少,也不论变量是连续的还是离散的,这一算法都比较有效,尤其对离散非线性规划更有效．该方法是一种搜索法,勿需解任何数学方程,只需要计算函数值以及函数对变量的偏微分或差分值．许多数值例题和运筹学中一些经典问题,如1) 一、二维的背包问题;2) 一、二维资源分配问题;3) 复合系统工作可靠性问题;4) 机器负荷问题等,经用此法求解验证均较传统方法更有效和可靠．该方法的主要优点是:1) 不受问题的规模限制;2) 只要在可行域（集）内存在目标函数和约束函数及其一阶导数或差分的值,肯定可以搜索到最优的解,没有不收敛和不稳定的问题．     

Dual multilevel optimization

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.      

Auction algorithms for network flow problems: A tutorial introduction

This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.     

A Multidimensional Nonautonomous Equation Containing a Product of Powers of Partial Derivatives

A class of multidimensional differential equations containing products of powers of partial derivatives of any order is considered. Solutions with additive, multiplicative, and combined separation of variables are obtained. A family of pseudopolynomial solutions expressed in terms of polynomials in independent variables with arbitrary coefficients and functions being solutions of certain ordinary differential equations is also obtained. Solutions of the type of traveling wave and self-similar solutions, as well as families of solutions having the form of a sum or a product of solutions of the type of a traveling wave and self-similar solutions, are found. Finally, solutions that can be represented as functions of more complicated arguments expressed in terms of linear combinations and products of the initial independent variables are found. For all of the obtained solutions, conditions on the righthand side of the equation and its parameters under which these solutions exist are determined.     

An elementary survey of general duality theory in mathematical programming

We survey some recent developments in duality theory with the idea of explaining and unifying certain basic duality results in both nonlinear and integer programming. The idea of replacing dual variables (prices) by price functions, suggested by Everett and developed by Gould, is coupled with an appropriate dual problem with the consequence that many of the results resemble those used in linear programming. The dual problem adopted has a (traditional) economic interpretation and dual feasibility then provides a simple alternative to concepts such as conjugate functions or subdifferentials used in the study of optimality. In addition we attempt to make precise the relationship between primal, dual and saddlepoint results in both the traditional Lagrangean and the more general duality theories and to see the implications of passing from prices to price functions. Finally, and perhaps surprisingly, it appears that all the standard algorithms terminate by constructing primal and dual feasible solutions of equal value, i.e., by satisfying generalised optimality conditions.     

On per-iteration complexity of high order Chebyshev methods for sparse functions with banded Hessians

Some algorithms for unconstrained and differentiable optimization problems involve the evaluation of quantities related to high order derivatives. The cost of these evaluations depends widely on the technique used to obtain the derivatives and on some characteristics of the objective function: its size, structure and complexity. Functions with banded Hessian are a special case that we study in this paper. Because of their partial separability, the cost of obtaining their high order derivatives, subtly computed by the technique of automatic differentiation, makes High order Chebyshev methods more interesting for banded systems than for dense functions. These methods have an attractive efficiency as we can improve their convergence order without increasing significantly their algorithmic costs. This paper provides an analysis of the per-iteration complexities of High order Chebyshev methods applied to sparse functions with banded Hessians. The main result can be summarized as: the per-iteration complexity of a High order Chebyshev method is of order of the objective function’s. This theoretical analysis is verified by numerical illustrations.     

An efficient dimension-adaptive uncertainty propagation approach

In recent years, there has been a growing interest in uncertainty propagation, and a wide variety of uncertainty propagation methods exist in literature. In this paper, an uncertainty propagation approach is developed by using high-dimensional model representation (HDMR) and dimension reduction (DR) method technique in the stochastic space to represent the model output as a finite hierarchical correlated function expansion in terms of the stochastic inputs starting from lower-order to higher-order component functions. To save the computational cost, a dimension-adaptive version of the additive decomposition is proposed to detect the important component functions to reduce the terms. The proposed method requires neither the calculation of partial derivatives of response, as in commonly used Taylor expansion/perturbation methods, nor the inversion of random matrices, as in the Neumann expansion method. Two numerical examples show the efficiency and accuracy of the proposed method.     

Some characterizations of perturbational dual problems

Continuing our papers [4] - [7], where we have given an axiomatic approach to unperturbational dual problems, we study here perturbational dual problems. we give some characterizations of various classes of perturbations and the associated marginal functions and of various classes of perturbational dual objective functions and the associated Lagrangians, regarded as functions of their natural variables and of the primal parameters     

Calculation of Stresses and Consistent Tangent Moduli from Automatic Differentiation of Hyerelastic Strain Energy Functions Through the Use of Hyper Dual Numbers

Many materials as e.g. engineering rubbers, polymers and soft biological tissues are often described by hyperelastic strain energy functions. For their finite element implementation the stresses and consistent tangent moduli are required and obtained mainly in terms of the first and second derivative of the strain energy function. Depending on its mathematical complexity in particular for anisotropic media the analytic derivatives may be expensive to be calculated or implemented. Then numerical approaches may be a useful alternative reducing the development time. Often-used classical finite difference schemes are however quite sensitive with respect to perturbation values and they result in a poor accuracy. The complex-step derivative approximation does never suffer from round-off errors, cf. [1], [2], but it can only provide first derivatives. A method which also provides higher order derivatives is based on hyper dual numbers [3]. This method is independent on the choice of perturbation values and does thus neither suffer from round-off errors nor from approximation errors. Therefore, here we make use of hyper dual numbers and propose a numerical scheme for the calculation of stresses and tangent moduli which are almost identical to the analytic ones. Its uncomplicated implementation and accuracy is illustrated by some representative numerical examples. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Algebra of Exponential Polynomials as the Cofinite Dual of the Hopf Algebra of Polynomials

We prove that the cofinite dual of the Hopf algebra of polynomials in several variables can be represented as a Hopf algebra ? of exponential polynomials that contains the polynomials as a Hopf subalgebra. We also present some algebras isomorphic to ? whose elements are rational functions or multi-sequences.