Optimal execution with weighted impact functions: a quadratic programming approach

In this paper, we develop optimal trading strategies for a risk averse investor by minimizing the expected cost and the risk of execution. Here we consider a law of motion for price which uses a convex combination of temporary and permanent market impact. In the special case of unconstrained problem for a risk neutral investor, we obtain a closed form solution for optimal trading strategies by using dynamic programming. For a general problem, we use a quadratic programming approach to get approximate dynamic optimal trading strategies. Further, numerical examples of optimal execution strategies are provided for illustration purposes.     

A model for optimal execution of atomic orders

Atomic Orders are the basic elements of any algorithm for automated trading in electronic stock exchanges. The main concern in their execution is achieving the most efficient price. We propose two optimal strategies for the execution of atomic orders based on minimization of impact and volatility costs. The first considered strategy is based on a relatively simple nonlinear optimization model while the second allows re-optimization at some time point within a given execution time. In both cases a combination of market and limit orders is used. The key innovation in our approach is the introduction of a Fill Probability function which allows a combination of market and limit orders in the two optimization models we are discussing in this paper. Under certain conditions the objective functions of both considered problems are convex and therefore standard optimization tools can be applied. The efficiency of the resulting strategies is tested against two benchmarks representing common market practice on a representative sample of real trading data.     

Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.     

A model to optimize project resource allocation by construction of a balanced histogram

This paper examines a scheduling method to improve productivity in resource-constrained projects. When resources are nonrenewable the duration of each activity has only one value. Optimal solutions are derived through criticalism of groups of activities using the same resource so as to eliminate interruption times and associated costs. The corresponding resource histogram is balanced and its design is derived by means of a program suitable for personal computer implementation.In the case where resources are renewable, activity durations are resource driven. We introduce a new view of discreetness for activity execution times which enables us to obtain optimal solutions relating to the cost functions of the activities.Finally we account for doubly constrained resources by (a) defining a maximum level of resource utilization and a maximum cost increase per period of usage of renewable resources and (b) considering as acceptable only those optimal solutions which keep total cost increase for the overall project below a tolerable limit.An application example is given using personal computer and commercially available software.     

电子市场与期权合约市场并存下的供应链优化

在电子市场与期权合约市场并存条件下,构建供应商的生产成本函数模型,找出供应商的最优产能决策,分销商的最优期权订货量决策,集成化供应链的最优产能决策等.然后借助数值分析,找出供应商的最优期权合约参数,及各最优解的变化规律.分析得到,电子市场准入程度的增大、电子市场价格的增大都会促使供应商提高产能;电子市场价格的增大、供应商期权预订价格的降低、期权执行价格的降低、终端市场需求的增大都会促使分销商增大期权订货量和期权执行量,供应商应选择(期权预定价格较小,期权执行价格较大)的优化决策,并针对不同的市场风险选择不同的期权合约参数组合.     

Optimal portfolio execution under time-varying liquidity constraints

In this article, we take an algorithmic approach to solve the problem of optimal execution under time-varying constraints on the depth of a limit order book (LOB). Our algorithms are within the resilience model proposed by Obizhaeva and Wang (2013) with a more realistic assumption on the order book depth; the amount of liquidity provided by an LOB market is finite at all times. For the simplest case where the order book depth stays at a fixed level for the entire trading horizon, we reduce the optimal execution problem into a one-dimensional root-finding problem which can be readily solved by standard numerical algorithms. When the depth of the order book is monotone in time, we apply the Karush-Kuhn-Tucker conditions to narrow down the set of candidate strategies. Then, we use a dichotomy-based search algorithm to pin down the optimal one. For the general case, we start from the optimal strategy subject to no liquidity constraints and iterate over execution strategy by sequentially adding more constraints to the problem in a specific fashion until primal feasibility is achieved. Numerical experiments indicate that our algorithms give comparable results to those of current existing convex optimization toolbox CVXOPT with significantly lower time complexity.     

机构投资者的最优变现策略

在投资、变现等大宗交易过程中,资产交易价格与交易策略密切相关,因此,交易的完成过程需要很高的技巧.文章讨论了机构投资者的最优变现策略问题,假设证券价格服从几何布朗运动,以均值方差效用为目标函数,得到了最优变现策略所满足的二阶微分方程,并由差分法得到其数值解.最后,由参数的敏感性分析知:最优变现策略与瞬时冲击、市场波动率及风险厌恶系数等参数有关,但与永久冲击无关,且最优变现策略对市场波动率和瞬时冲击的变化较敏感.     

Mean–Variance Optimal Adaptive Execution

Abstract

Electronic trading of equities and other securities makes heavy use of ‘arrival price’ algorithms that balance the market impact cost of rapid execution against the volatility risk of slow execution. In the standard formulation, mean–variance optimal trading strategies are static: they do not modify the execution speed in response to price motions observed during trading. We show that substantial improvement is possible by using dynamic trading strategies and that the improvement is larger for large initial positions.

We develop a technique for computing optimal dynamic strategies to any desired degree of precision. The asset price process is observed on a discrete tree with an arbitrary number of levels. We introduce a novel dynamic programming technique in which the control variables are not only the shares traded at each time step but also the maximum expected cost for the remainder of the program; the value function is the variance of the remaining program. The resulting adaptive strategies are ‘aggressive-in-the-money’: they accelerate the execution when the price moves in the trader's favor, spending parts of the trading gains to reduce risk.     

Self-Adaptive Genetic Algorithm for Clustering

Clustering is a hard combinatorial problem which has many applications in science and practice. Genetic algorithms (GAs) have turned out to be very effective in solving the clustering problem. However, GAs have many parameters, the optimal selection of which depends on the problem instance. We introduce a new self-adaptive GA that finds the parameter setup on-line during the execution of the algorithm. In this way, the algorithm is able to find the most suitable combination of the available components. The method is robust and achieves results comparable to or better than a carefully fine-tuned non-adaptive GA.     

New computational results on the discrete time/cost trade-off problem in project networks

We describe a new exact procedure for the discrete time/cost trade-off problem in deterministic activity-on-the-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single resource (money) committed to it. The objective is to construct the complete and efficient time/cost profile over the set of feasible project durations. The procedure uses a horizon-varying approach based on the iterative optimal solution of the problem of minimising the sum of the resource use over all activities subject to the activity precedence constraints and a project deadline. This optimal solution is derived using a branch-and-bound procedure which computes lower bounds by making convex piecewise linear underestimations of the discrete time/cost trade-off curves of the activities to be used as input for an adapted version of the Fulkerson labelling algorithm for the linear time/cost trade-off problem. Branching involves the selection of an activity in order to partition its set of execution modes into two subsets which are used to derive improved convex piecewise linear underestimations. The procedure has been programmed in Visual C ++ under Windows NT and has been validated using a factorial experiment on a large set of randomly generated problem instances.     

Optimal clustering of frequency-constrained maintenance jobs with shared set-ups

Since maintenance jobs often require one or more set-up activities, joint execution or clustering of maintenance jobs is a powerful instrument to reduce shut-down costs. We consider a clustering problem for frequency-constrained maintenance jobs, i.e. maintenance jobs that must be carried out with a prescribed (or higher) frequency. For the clustering of maintenance jobs with identical, so-called common set-ups, several strong dominance rules are provided. These dominance rules are used in an efficient dynamic programming algorithm which solves the problem in polynomial time. For the clustering of maintenance jobs with partially identical, so-called shared set-ups, similar but less strong dominance rules are available. Nevertheless, a surprisingly well-performing greedy heuristic and a branch and bound procedure have been developed to solve this problem. For randomly generated test problems with 10 set-ups and 30 maintenance jobs, the heuristic was optimal in 47 out of 100 test problems, with an average deviation of 0.24% from the optimal solution. In addition, the branch and bound method found an optimal solution in only a few seconds computation time on average.     

Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound

In this paper we study the Resource Constrained Project Scheduling Problem (RCPSP) with “Feeding Precedence” (FP) constraints and minimum makespan objective. This problem typically arises in production planning environment, like make-to-order manufacturing, where the effort associated with the execution of an activity is not univocally related to its duration percentage and the traditional finish-to-start precedence constraints or the generalized precedence relations cannot completely represent the overlapping among activities. In this context, we need to introduce in the RCPSP the FP constraints. For this problem we propose a new mathematical formulation and define a lower bound based on the Lagrangian relaxation of the resource constraints. A computational experimentation on randomly generated instances of sizes of up to 100 activities shows a better performance of this lower bound when compared to other lower bounds. Moreover, for the optimally solved instances, its value is very close to the optimal one. Furthermore, in order to show the effectiveness of the proposed lower bound on large instances for which the optimal solution is known, we adapted our approach to solve the benchmarks of the basic RCPSP from the PSLIB with 120 activities.     

Mean–variance optimal trading problem subject to stochastic dominance constraints with second order autoregressive price dynamics

The efficient modeling of execution price path of an asset to be traded is an important aspect of the optimal trading problem. In this paper an execution price path based on the second order autoregressive process is proposed. The proposed price path is a generalization of the existing first order autoregressive price path in literature. Using dynamic programming method the analytical closed form solution of unconstrained optimal trading problem under the second order autoregressive process is derived. However in order to incorporate non-negativity constraints in the problem formulation, the optimal static trading problems under second order autoregressive price process are formulated. For a risk neutral investor, the optimal static trading problem of minimizing expected execution cost subject to non-negativity constraints is formulated as a quadratic programming problem. Whereas, for a risk averse investor the variance of execution cost is considered as a measure for the timing risk, and the mean–variance problem is formulated. Moreover, the optimal static trading problem subject to stochastic dominance constraints with mean–variance static trading strategy as the reference strategy is studied. Using Static approximation method the algorithm to solve proposed optimal static trading problems is presented. With numerical illustrations conducted on simulated data and the real market data, the significance of second order autoregressive price path, and the optimal static trading problems is presented.     

Optimal portfolio execution under cointegrated vector autoregressive systems

Abstract

In this paper, an optimal portfolio execution problem under price model which exhibits cointegration behaviour is proposed. The proposed problem is formulated as a quadratic programming problem. With different statistical procedures and parameter estimation methods, employed on real market financial data, the four portfolios are constructed with which, computational study is performed. It is shown that the trading strategies constructed out of portfolios with cointegrated price dynamics show significant reduction in execution cost.     

The optimal execution strategy of employee stock options

In this paper, we develop an optimal execution strategy for employee stock options by means of the fluid model, in which a voluntary turnover is considered. We show that the value function is the viscosity solution of the Hamilton-Jacobi-Bellman variational inequality and prove the uniqueness of the viscosity solution. Finally, we present numerical illustrative examples and numerical solutions of optimal strategies which are computed by the finite difference method.     

Gradient-projection and policy-iteration methods for solving optimization problems in STEOR networks

The problem of optimal time-cost trade-offs in STEOR networks is considered. An optimal control approach is presented where the control variables are the time-dependent execution probabilities of the activities of the underlying project. An optimal controller can be determined by means of a gradient-projection method or a policy-improvement routine.

---

Zusammenfassung Gegenstand der Arbeit ist die Kostenplanung mit Hilfe von STEO-Netzplänen. Das Kostenminimierungsproblem wird auf ein Kontrollproblem zurückgeführt, wobei die Steuervariablen die zeitabhängigen Ausführungswahrscheinlichkeiten der Vorgänge des zugrunde liegenden Projektes sind. Eine optimale Steuerung kann mit einer Gradientprojektionsmethode oder einem Verfahren der Politikiteration bestimmt werden.

---

---

The research was partly supported by the Deutsche Forschungsgemeinschaft.     

Dismantling of nuclear power plants at optimal NPV

Today, worldwide far more than 100 nuclear power plants, which have been decommissioned in the recent years, are waiting for their complete dismantling. Since the dismantling of a single reactor causes costs of up to one billion Euros and lasts up to 15 years, the elaboration of a scheduling approach helping to optimize the net present value of a dismantling project seems to be worthwhile. In this paper we present a resource-constrained project scheduling approach optimizing the total discounted disbursements of dismantling a nuclear power plant. For the corresponding NP-hard optimization problem, we introduce an appropriate project scheduling model with minimum and maximum time lags, renewable and cumulative resources as well as multiple execution modes. To solve this model, we introduce a relaxation-based enumeration approach that delivers optimal solutions for problem instances containing up to 50 activities.     

Query Optimization in Distributed Relational Databases

The query optimizer is the DBMS (data base management system) component whose task is to find an optimal execution plan for a given input query. Typically, optimization is performed using dynamic programming. However, in distributed execution environments, this approach becomes intractable, due to the increase in the search space incurred by distribution. We propose the use of the tabu search metaheuristic for distributed query optimization. A hashing-based data structure is used to keep track of the search memory, simplifying significantly the implementation of tabu search. To validate this proposal, we implemented the tabu search strategy in the scope of an existing optimizer, which runs several search strategies. We focus our attention on the more difficult problems in terms of the query execution space, in which the solution space includes bushy execution plans and Cartesian products, which are not dealt with very often in the literature. Using a real-life application, we show the effectiveness of tabu search when compared to other strategies.     

A Hamilton-Jacobi-Bellman approach to optimal trade execution

The optimal trade execution problem is formulated in terms of a mean-variance tradeoff, as seen at the initial time. The mean-variance problem can be embedded in a linear-quadratic (LQ) optimal stochastic control problem. A semi-Lagrangian scheme is used to solve the resulting nonlinear Hamilton-Jacobi-Bellman (HJB) PDE. This method is essentially independent of the form for the price impact functions. Provided a strong comparison property holds, we prove that the numerical scheme converges to the viscosity solution of the HJB PDE. Numerical examples are presented in terms of the efficient trading frontier and the trading strategy. The numerical results indicate that in some cases there are many different trading strategies which generate almost identical efficient frontiers.     

Real time task scheduling allowing fuzzy due dates

The paper deals with periodical task scheduling. The tasks are described by fuzzy due dates and fuzzy execution times. The goal of scheduling is to find an optimal assignment of priorities such that the satisfaction associated with due dates and execution times be minimized. The paper shows how the rules associated with task priorities improve the optimal assignment search.