Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints

This paper presents two new trust-region methods for solving nonlinear optimization problems over convex feasible domains. These methods are distinguished by the fact that they do not enforce strict monotonicity of the objective function values at successive iterates. The algorithms are proved to be convergent to critical points of the problem from any starting point. Extensive numerical experiments show that this approach is competitive with the LANCELOT package.     

Variational inequalities and the pricing of American options

This paper is devoted to the derivation of some regularity properties of pricing functions for American options and to the discussion of numerical methods, based on the Bensoussan-Lions methods of variational inequalities. In particular, we provide a complete justification of the so-called Brennan-Schwartz algorithm for the valuation of American put options.Research supported in part by a contract from Banque INDOSUEZ.     

Validation of an Augmented Lagrangian Algorithm with a Gauss-Newton Hessian Approximation Using a Set of Hard-Spheres Problems

An Augmented Lagrangian algorithm that uses Gauss-Newton approximations of the Hessian at each inner iteration is introduced and tested using a family of Hard-Spheres problems. The Gauss-Newton model convexifies the quadratic approximations of the Augmented Lagrangian function thus increasing the efficiency of the iterative quadratic solver. The resulting method is considerably more efficient than the corresponding algorithm that uses true Hessians. A comparative study using the well-known package LANCELOT is presented.     

一种修改的非单调线搜索SQP算法

提出了一种解非线性规划问题的修改的非单调线搜索算法,并给出了它的全局收敛性证明.不需要用罚函数作为价值函数,也不用滤子和可行性恢复阶段.该算法是基于多目标优化的思想一个迭代点被接受当且仅当目标函数值或是约束违反度函数值有充分的下降.数值结果与LANCELOT作了比较,表明该算法是可靠的.     

On the pricing of American options

The problem of valuation for contingent claims that can be exercised at any time before or at maturity, such as American options, is discussed in the manner of Bensoussan [1]. We offer an approach which both simplifies and extends the results of existing theory on this topic.Research supported in part by the National Science Foundation under Grant No. NSF-DMS-84-16736 and by the Air Force Office of Scientific Research under Grant No. F49620-85-C-0144.     

Nonmonotone Strategy for Minimization of Quadratics with Simple Constraints

An algorithm for quadratic minimization with simple bounds is introduced, combining, as many well-known methods do, active set strategies and projection steps. The novelty is that here the criterion for acceptance of a projected trial point is weaker than the usual ones, which are based on monotone decrease of the objective function. It is proved that convergence follows as in the monotone case. Numerical experiments with bound-constrained quadratic problems from CUTE collection show that the modified method is in practice slightly more efficient than its monotone counterpart and has a performance superior to the well-known code LANCELOT for this class of problems.     

A fuzzy approach to R&D project portfolio selection

A major advance in the development of project selection tools came with the application of options reasoning in the field of Research and Development (R&D). The options approach to project evaluation seeks to correct the deficiencies of traditional methods of valuation through the recognition that managerial flexibility can bring significant value to projects. Our main concern is how to deal with non-statistical imprecision we encounter when judging or estimating future cash flows. In this paper, we develop a methodology for valuing options on R&D projects, when future cash flows are estimated by trapezoidal fuzzy numbers. In particular, we present a fuzzy mixed integer programming model for the R&D optimal portfolio selection problem, and discuss how our methodology can be used to build decision support tools for optimal R&D project selection in a corporate environment.     

An Interior-Point Algorithm for Nonconvex Nonlinear Programming

The paper describes an interior-point algorithm for nonconvex nonlinear programming which is a direct extension of interior-point methods for linear and quadratic programming. Major modifications include a merit function and an altered search direction to ensure that a descent direction for the merit function is obtained. Preliminary numerical testing indicates that the method is robust. Further, numerical comparisons with MINOS and LANCELOT show that the method is efficient, and has the promise of greatly reducing solution times on at least some classes of models.     

A modified nearly exact method for solving low-rank trust region subproblem

In this paper, we first discuss how the nearly exact (NE) method proposed by Moré and Sorensen [14] for solving trust region (TR) subproblems can be modified to solve large-scale “low-rank” TR subproblems efficiently. Our modified algorithm completely avoids computation of Cholesky factorizations by instead relying primarily on the Sherman–Morrison–Woodbury formula for computing inverses of “diagonal plus low-rank” type matrices. We also implement a specific version of the modified log-barrier (MLB) algorithm proposed by Polyak [17] where the generated log-barrier subproblems are solved by a trust region method. The corresponding direction finding TR subproblems are of the low-rank type and are then solved by our modified NE method. We finally discuss the computational results of our implementation of the MLB method and its comparison with a version of LANCELOT [5] based on a collection extracted from CUTEr [12] of nonlinear programming problems with simple bound constraints.      

Augmented Lagrangian Algorithms Based on the Spectral Projected Gradient Method for Solving Nonlinear Programming Problems

The spectral projected gradient method SPG is an algorithm for large-scale bound-constrained optimization introduced recently by Birgin, Martínez, and Raydan. It is based on the Raydan unconstrained generalization of the Barzilai-Borwein method for quadratics. The SPG algorithm turned out to be surprisingly effective for solving many large-scale minimization problems with box constraints. Therefore, it is natural to test its perfomance for solving the sub-problems that appear in nonlinear programming methods based on augmented Lagrangians. In this work, augmented Lagrangian methods which use SPG as the underlying convex-constraint solver are introduced (ALSPG) and the methods are tested in two sets of problems. First, a meaningful subset of large-scale nonlinearly constrained problems of the CUTE collection is solved and compared with the perfomance of LANCELOT. Second, a family of location problems in the minimax formulation is solved against the package FFSQP.     

Strong consistency of the empirical martingale simulation option price estimator

A simulation technique known as empirical martingale simulation （EMS） was proposed to improve simulation accuracy. By an adjustment to the standard Monte Carlo simulation, EMS ensures that the simulated price satisfies the rational option pricing bounds and that the estimated derivative contract price is strongly consistent with payoffs that satisfy Lipschitz condition. However, for some currently used contracts such as self-quanto options and asymmetric or symmetric power options, it is open whether the above asymptotic result holds. In this paper, we prove that the strong consistency of the EMS option price estimator holds for a wider class of univariate payoffs than those restricted by Lipschitz condition. Numerical experiments demonstrate that EMS can also substantially increase simulation accuracy in the extended setting.     

On the efficiency of multiplier methods for nonlinear network problems with nonlinear constraints

The minimization of network flow problems with linear/nonlinearside constraints can be performed by minimizing an augmentedLagrangian function, including only the side constraints. Thismethod gives rise to an algorithm that combines first- and superlinear-orderestimators of the multipliers of the side constraints. The codePFNRN03 is the implementation of this algorithm in Fortran 77.The main aim of this work is to compare the efficiency of thiscode on two sets of (industrial, artificial) test problems withthat of the general-purpose solvers MINOS, SNOPT, LANCELOT andLOQO. Numerical results of these four codes are obtained bythe NEOS server with AMPL input. The comparison indicates thatPFNRN03 may be effective on current large-scale network flowproblems with nonlinear side constraints.     

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

Computation of the Delta in Multidimensional Jump-Diffusion Setting with Applications to Stochastic Volatility Models

We study the robustness of options prices to model variation in a multidimensional jump-diffusion framework. In particular, we consider price dynamics in which small variations are modeled either by a Poisson random measure with infinite activity or by a Brownian motion. We consider both European and Exotic options and we study their deltas using two approaches: the Malliavin method and the Fourier method. We prove robustness of the deltas to model variation. We apply these results to the study of stochastic volatility models for the underlying and the corresponding options.     

基于Fourier变换的裂解价差期权定价

本文研究了期货期权和裂解价差期权的定价问题.利用Fourier变换方法,在ASub CIR模型的基础上,获得了单因素期货期权,两因素期货期权以及价差期权价格的表达式,最后用C++和MATLAB计算出期权的价格,解决了利用特征函数展开法计算期权价格时速度较慢且不稳定的问题.     

Separating managerial inefficiency and external conditions in data envelopment analysis

In this paper, we highlight the importance of appropriately dealing with non-controllable inputs in technical efficiency evaluations by using DEA. In order to do this, the two most important options that exclusively use DEA methodology for the incorporation of these variables – the one-stage model by Banker and Morey [Operations Research 34(4) (1986a) 513] and the three-stage method developed by Fried and Lovell [Searching the Zeds, Working paper presented at II Georgia Productivity Workshop, 1996] – are compared both methodologically and empirically. At the same time, we propose a modification to the latter model which allows us to improve its results and interpretation. The education sector has been selected for the empirical application, the reason being that it has the desirable feature that, in the productive process, the students' socio-economic and family status (a non-controllable input) has a direct influence on the school results.The results obtained show the superiority of the multi-stage approach. It is argued that the model developed by Banker and Morey does not deal appropriately with inefficient units, as producer's behaviour in this model does not reflect the objective situation faced by such DMUs.     

The duality of option investment strategies for hedge funds

This paper explores the structure of optimal investment strategies using stochastic programming and duality theory in investment portfolios containing options for a hedge fund manager who attempts to beat a benchmark. Explicit optimal conditions for option investments are obtained for several models. This research was supported by Inquire, the Social Sciences and Humanities Research Council of Canada, the Natural Sciences and Engineering Research Council of Canada, the National Center of Competence in Research FINRISK, a research instrument of the Swiss National Science Foundation, and MIT’s Sloan School of Management. J. R. Rodríguez-Mancilla thanks Gabriel Casillas-Olvera, Deputy Manager of Risk Control at Banco de Mexico, who read several drafts of this paper and made many helpful comments. The opinions in this paper do not necessarily represent those of Banco de México.     

Valuing forestlands with stochastic timber and carbon prices

Annals of Operations Research - We calculate expected bare land values, assuming forestry is the highest and best land use, using a real options methodology with stochastic mean-reverting timber...     

Hedging of game options in discrete markets with transaction costs

Game options introduced in [10] in 2000 were studied, by now, mostly in frictionless both complete and incomplete markets. In complete markets the fair price of a game option coincides with the value of an appropriate Dynkin's game, whereas in markets with friction and in incomplete ones there is a range of arbitrage free prices and superhedging comes into the picture. Here we consider game options in general discrete time markets with transaction costs and construct backward and forward induction algorithms for the computation of their prices and superhedging strategies from both seller's (upper arbitrage free price) and buyer's (lower arbitrage free price) points of view extending to the game options case most of the results from [12].     

Computational Methods for Pricing American Put Options

This work develops computational methods for pricing American put options under a Markov-switching diffusion market model. Two methods are suggested in this paper. The first method is a stochastic approximation approach. It can handle option pricing in a finite horizon, which is particularly useful in practice and provides a systematic approach. It does not require calibration of the system parameters nor estimation of the states of the switching process. Asymptotic results of the recursive algorithms are developed. The second method is based on a selling rule for the liquidation of a stock for perpetual options. Numerical results using stochastic approximation and Monte Carlo simulation are reported. Comparisons of different methods are made. This research was supported in part by the National Science Foundation and in part by the Wayne State University Research Enhancement Program.