Buyback problem with discrete concave valuation functions

We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.     

On inverse crack problems in elastostatics

In solid mechanics, nondestructive testing has been an important technique in gathering information about unknown cracks, or defects in material. From a mathematical point of view, this is described as an inverse problem of partial differential equations, that is, the problem is to extract information about the location and shape of an unknown crack from the surface displacement field and traction on the boundary of the elastic material. By using the enclosure method introduced by Prof. Ikehata we can derive the extraction formula of an unknown linear crack from a single set of measured boundary data. Then, we need to have precise properties of a solution of the corresponding boundary value problem; for instance, an expansion formula around the crack tip. In this paper we consider the inverse problem concentrating on this point. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

One approach to the problem of nonparametric estimation in statistics of random processes based on the method of ill-posed problem

We consider the problem of estimation of integrated volatility, i.e., of the integral of the diffusion coefficient squared, in a stochastic differential equation for a random process that corresponds to geometric Brownian motion. In additon to purely theoretical interest, this problem is of interest for applications since the problem of evaluation of integrated volatility for financial assets is an important part of financial engineering topics. In the present paper, we suggest a new approach to the above-mentioned problem. We derive an integral equation whose solution determines the value of integrated volatility. This integral equation is a typical ill-posed problem of mathematical physics. The main idea of the proposed reduction of the original problem to an ill-posed problem consists of making its solution robust with respect to anomalous values of statistical data which are generated, for example, by market microstructure effects, such as the bid-ask spread. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 351, 2007, pp. 117–128.     

����Ʒ����ת������L\'{e}vy����ģ���е����ŷֺ����

??In this paper, we consider the optimal dividend problem in the spectrally positive L\'{e}vy model with regime switching. By an auxiliary optimal problem, the principle of dynamic programming and the fluctuation theory of L\'{e}vy processes, we show that optimal strategy is a modulated barrier strategy. The value function and the optimal dividend barrier are obtained by iteration.     

Improving port performance in developing countries—A case study

Exchange algorithms are an important class of heuristics for hard combinatorial optimization problems as, e.g., salesman problems or quadratic assignment problems. In Kirkpatrick's and Cerny's exchange algorithms for the travelling salesman problem and placement problem they propose to perform an exchange not only if the objective function value decreases by this exchange, but also in certain cases if the objective function value increases. An exchange increasing the objective function value is performed stochastically depending on the size of the increment.Computational tests with quadratic assignment problems revealed an excellent behaviour in such an approach. Suboptimal solutions differing 1–2% from the best known solutions are obtained by a simple program in short time. By starting this program several times with different starting values all known minimal objective function values were reached. Thus this approach is well suited also for smaller computers and leads in short time to acceptable solutions.     

On infinite horizon optimal stopping of general random walk

The objective of this study is to provide an alternative characterization of the optimal value function of a certain Black–Scholes-type optimal stopping problem where the underlying stochastic process is a general random walk, i.e. the process constituted by partial sums of an IID sequence of random variables. Furthermore, the pasting principle of this optimal stopping problem is studied.      

Competitive evaluation of threshold functions in the priced information model

In Charikar et al. (J. Comput. Syst. Sci. 64(4):785–819, 2002) the authors proposed a new model for studying the function evaluation problem based on a variant of the classical decision tree problem for Boolean functions. In this variant each variable of the function to evaluate has an associated cost which has to be paid in order to read the value of the variable. Given a function f and an assignment σ to the variables of f, the performance of an algorithm for evaluating f is measured via the competitive ratio, i.e., the ratio of the total cost spent by the algorithm and the cost of the cheapest set of variables constituting a certificate for the value of the function on the given assignment.     

An initial-boundary value problem for the Maxwell equations

In this paper, by using methods from complex analysis and quaternionic analysis, we investigate an initial-boundary value problem for the Maxwell equations and obtain the general solutions and solvable conditions of the problem respectively in different cases. In addition, by using a similar method, we also discuss an initial-boundary value problem for a hyperbolic complex system of first order equations in R³.     

Optimal switching problems with an infinite set of modes: An approach by randomization and constrained backward SDEs

We address a general optimal switching problem over finite horizon for a stochastic system described by a differential equation driven by Brownian motion. The main novelty is the fact that we allow for infinitely many modes (or regimes, i.e. the possible values of the piecewise-constant control process). We allow all the given coefficients in the model to be path-dependent, that is, their value at any time depends on the past trajectory of the controlled system. The main aim is to introduce a suitable (scalar) backward stochastic differential equation (BSDE), with a constraint on the martingale part, that allows to give a probabilistic representation of the value function of the given problem. This is achieved by randomization of control, i.e. by introducing an auxiliary optimization problem which has the same value as the starting optimal switching problem and for which the desired BSDE representation is obtained. In comparison with the existing literature we do not rely on a system of reflected BSDE nor can we use the associated Hamilton–Jacobi–Bellman equation in our non-Markovian framework.     

Optimization of polymer extrusion with genetic algorithms

In the manufacture of plastics parts by extrusion or injectionmoulding, polymers are usually plasticized in single-screw units.The mechanisms involved are complex and dependent on the material,the geometry, and the type of operation. Usually, process optimizationis based on trial and error—a very inefficient method.A more efficient approach is to solve the inverse problem, i.e.to determine the operating conditions that produce the desiredoutput and/or product characteristics. An alternative strategyconsists in maximizing the value of an objective function, bysolving the direct problem iteratively. The nature of the objectivefunction—with conflicting criteria—and the characteristicsof the search space make an approach based on genetic algorithmsworth investigating. Therefore, a modelling package, an objectivefunction, and a genetic algorithm are interrelated to solvethe industrial extrusion problem. The advantages and disadvantagesof this implementation are discussed.     

Two boundary value problems for a strongly anisotropic inhomogeneous elastic ring

The second boundary value problem (displacements are given on the boundary) and the improper mixed problem for a cylindrically orthotropic ring are studied. It is assumed that the coefficients of elasticity are continuously differentiable functions of the coordinates and depend on a small parameter in a specific manner. The form of the dependence of the coefficients on the small parameter is selected in such a way that in the case of constant coefficients it describes bonding of the ring by two families of very rigid fibers located along the radius vectors and concentric circles, where the stiffness of the fiber families is of identical order. Consequently, the coefficients of elasticity are represented in the form of products of constants which will later be called provisionally the “stiffnesses”, and functions of the coordinates. It is assumed that the stiffnesses in the radial and circumferential directions are equal and exceed and shear stiffness considerably. The asymptotic form of the solution of the boundary value problems under consideration is constructed when the ratio between the shear stiffness and the stiffness in the radial direction is used as the small parameter. In the case of the second boundary value problem the limit boundary value problem is described by a hyperbolic system of equations and is not solvable uniquely, since one of the families of characteristics is parallel to the boundary. When constructing the asymptotic form the necessity arises to average the coefficients of elasticity with respect to the circumferential coordinate. In this respect, there is an analogy with the results obtained in /1/ where the boundary value problem was studied for a second-order elliptic equation.     

On Well Posedness in Continuum Interface Problems

By considering continuum interface problems like e.g. the modeling of composites, the possible loss of well posedness of the resulting Boundary Value Problem has to be considered, dependent on the choice of material laws in the bulk and in the interface. In this contribution, the problem is discussed for a bulk material connected to a rigid substrate by an interface layer. The isotropic bulk material is linear elastic while for the interface elasticity and elasticity with damage is investigated. A complex surface acoustic tensor is introduced by applying a decaying surface wave ansatz to the incremental boundary value problem. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Kullback-Liebler测度在地震记录反演中的应用

在地震记录反演中,盲目反褶积是一个相当困难的问题.讨论这个问题现有各种方法,如累积矩法等.本文利用Likas等处理图像恢复的变分法来讨论地震记录反演中的盲目反褶积问题.利用Kullback-Liebler信息测度获得一个非常有用的统计函数(即变分函数),此函数的极值点就含有所要求的反射系数序列的信息,并且拟订出求此泛数极值点的一套算法.     

Optimal construction and rebalancing of index-tracking portfolios

Index funds aim to track the performance of a financial index, such as, e.g., the Standard?&?Poor’s?500 index. Index funds have become popular because they offer attractive risk-return profiles at low costs. The index-tracking problem considered in this paper consists of rebalancing the composition of the index fund’s tracking portfolio in response to new market information and cash deposits and withdrawals from investors such that the index fund’s tracking accuracy is maximized. In a frictionless market, maximum tracking accuracy is achieved by investing the index fund’s entire capital in a tracking portfolio that has the same normalized value development as the index. In the presence of transaction costs, which reduce the fund’s capital, one has to manage the trade-off between transaction costs and similarity in terms of normalized value developments. Existing mathematical programing formulations for the index-tracking problem do not optimize this trade-off explicitly, which may result in substantial transaction costs or tracking portfolios that differ considerably from the index in terms of normalized value development. In this paper, we present a mixed-integer linear programing formulation with a novel optimization criterion that directly considers the trade-off between transaction costs and similarity in terms of normalized value development. In an experiment based on a set of real-world problem instances, the proposed formulation achieves a considerably higher tracking accuracy than state-of-the-art formulations.     

Finite Time Merton Strategy under Drawdown Constraint: A Viscosity Solution Approach

We consider the optimal consumption-investment problem under the drawdown constraint, i.e. the wealth process never falls below a fixed fraction of its running maximum. We assume that the risky asset is driven by the constant coefficients Black and Scholes model and we consider a general class of utility functions. On an infinite time horizon, Elie and Touzi (Preprint, [2006]) provided the value function as well as the optimal consumption and investment strategy in explicit form. In a more realistic setting, we consider here an agent optimizing its consumption-investment strategy on a finite time horizon. The value function interprets as the unique discontinuous viscosity solution of its corresponding Hamilton-Jacobi-Bellman equation. This leads to a numerical approximation of the value function and allows for a comparison with the explicit solution in infinite horizon.     

Robust resource allocations in temporal networks

Temporal networks describe workflows of time-consuming tasks whose processing order is constrained by precedence relations. In many cases, the durations of the network tasks can be influenced by the assignment of resources. This leads to the problem of selecting an ‘optimal’ resource allocation, where optimality is measured by network characteristics such as the makespan (i.e., the time required to complete all tasks). In this paper we study a robust resource allocation problem where the task durations are uncertain, and the goal is to minimise the worst-case makespan. We show that this problem is generically ${\mathcal{NP}}$ -hard. We then develop convergent bounds on the optimal objective value, as well as feasible allocations whose objective values are bracketed by these bounds. Numerical results provide empirical support for the proposed method.     

基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法

提出了一类求解带有箱约束的非凸二次规划的新型分支定界算法.首先,把原问题目标函数进行D.C.分解(分解为两个凸函数之差),利用次梯度方法,求出其线性下界逼近函数的一个最优值,也即原问题的一个下界.然后,利用全局椭球算法获得原问题的一个上界,并根据分支定界方法把原问题的求解转化为一系列子问题的求解.最后,理论上证明了算法的收敛性,数值算例表明算法是有效可行的.     

A numerical solution of the elasticity problem of settled of the wronkler ground with variable coefficients

In this paper, we have given numerical solution of the elasticity problem of settled on the wronkler ground with variable coefficient. The approximation solution of boundary value problem which is pertinent to this has been converted to integral equations, and then by using the successive approximation methods, has been reached. In addition to this, the approximation solution of the problem was put into Padé series form. We applied these methods to an example which is the elasticity problem of unit length homogeny beam, which is a special form of boundary value problem. First we calculate the successive approximation of the given boundary value problem then transform it into Padé series form, which give an arbitrary order for solving differential equation numerically.     

An Optimization Model for Stochastic Project Networks with Cash Flows

Project networks – or PERT networks – can be characterized by random completion times of activities and positive or negative cash flows throughout the project. In these cases the decision maker’s problem consists of determining a feasible activities schedule, to maximize the project financial value, where the financial value is measured by the net present value (npv) of cash flows.The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using a heuristic rule. Then the expected npv is calculated. But, due to stochastic job completion times, this problem belongs to the ♯-P complete difficulty class, e.g. problems that involve finding all the Hamiltonian cycles in a network. The problem is such that evaluating one project alone is not sufficient, but the optimal one has to be selected. This involves a further increase in computational time.This paper proposes a stochastic optimization model to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project npv. A feature of this approach is that the scheduling rule is completely deterministic and defined when the project begins. Therefore an upper bound of the expected npv, that is an optimistic estimate, can be calculated through linear programming and a lower bound, that is a pessimistic estimate, can be calculated using simulation before the project begins.     

Scattering by Rough Surfaces: the Dirichlet Problem for the Helmholtz Equation in a Non-locally Perturbed Half-plane

We consider the Dirichlet boundary value problem for the Helmholtz equation in a non-locally perturbed half-plane, this problem arising in electromagnetic scattering by one-dimensional rough, perfectly conducting surfaces. We propose a new boundary integral equation formulation for this problem, utilizing the Green's function for an impedance half-plane in place of the standard fundamental solution. We show, at least for surfaces not differing too much from the flat boundary, that the integral equation is uniquely solvable in the space of bounded and continuous functions, and hence that, for a variety of incident fields including an incident plane wave, the boundary value problem for the scattered field has a unique solution satisfying the limiting absorption principle. Finally, a result of continuous dependence of the solution on the boundary shape is obtained.