An Algorithm for Portfolio Optimization with Variable Transaction Costs,Part 1: Theory

A portfolio optimization problem consists of maximizing an expected utility function of n assets. At the end of a typical time period, the portfolio will be modified by buying and selling assets in response to changing conditions. Associated with this buying and selling are variable transaction costs that depend on the size of the transaction. A straightforward way of incorporating these costs can be interpreted as the reduction of portfolios’ expected returns by transaction costs if the utility function is the mean-variance or the power utility function. This results in a substantially higher-dimensional problem than the original n-dimensional one, namely (2K+1)n-dimensional optimization problem with (4K+1)n additional constraints, where 2K is the number of different transaction costs functions. The higher-dimensional problem is computationally expensive to solve. This two-part paper presents a method for solving the (2K+1)n-dimensional problem by solving a sequence of n-dimensional optimization problems, which account for the transaction costs implicitly rather than explicitly. The key idea of the new method in Part 1 is to formulate the optimality conditions for the higher-dimensional problem and enforce them by solving a sequence of lower-dimensional problems under the nondegeneracy assumption. In Part 2, we propose a degeneracy resolving rule, address the efficiency of the new method and present the computational results comparing our method with the interior-point optimizer of Mosek. This research was supported by the National Science and Engineering Research Council of Canada and the Austrian National Bank. The authors acknowledge the valuable assistance of Rob Grauer and Associate Editor Franco Giannessi for thoughtful comments and suggestions.     

Machine Learning Approximation Algorithms for High-Dimensional Fully Nonlinear Partial Differential Equations and Second-order Backward Stochastic Differential Equations

High-dimensional partial differential equations (PDEs) appear in a number of models from the financial industry, such as in derivative pricing models, credit valuation adjustment models, or portfolio optimization models. The PDEs in such applications are high-dimensional as the dimension corresponds to the number of financial assets in a portfolio. Moreover, such PDEs are often fully nonlinear due to the need to incorporate certain nonlinear phenomena in the model such as default risks, transaction costs, volatility uncertainty (Knightian uncertainty), or trading constraints in the model. Such high-dimensional fully nonlinear PDEs are exceedingly difficult to solve as the computational effort for standard approximation methods grows exponentially with the dimension. In this work, we propose a new method for solving high-dimensional fully nonlinear second-order PDEs. Our method can in particular be used to sample from high-dimensional nonlinear expectations. The method is based on (1) a connection between fully nonlinear second-order PDEs and second-order backward stochastic differential equations (2BSDEs), (2) a merged formulation of the PDE and the 2BSDE problem, (3) a temporal forward discretization of the 2BSDE and a spatial approximation via deep neural nets, and (4) a stochastic gradient descent-type optimization procedure. Numerical results obtained using TensorFlow in Python illustrate the efficiency and the accuracy of the method in the cases of a 100-dimensional Black–Scholes–Barenblatt equation, a 100-dimensional Hamilton–Jacobi–Bellman equation, and a nonlinear expectation of a 100-dimensional G-Brownian motion.

     

Canonical dual least square method for solving general nonlinear systems of quadratic equations

This paper presents a canonical dual approach for solving general nonlinear algebraic systems. By using least square method, the nonlinear system of m-quadratic equations in n-dimensional space is first formulated as a nonconvex optimization problem. We then proved that, by the canonical duality theory developed by the second author, this nonconvex problem is equivalent to a concave maximization problem in ℝ ^m , which can be solved easily by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.     

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

Given a graphG=[V, E] with positive edge weights, the max-cut problem is to find a cut inG such that the sum of the weights of the edges of this cut is as large as possible. Letg(K) be the class of graphs whose longest odd cycle is not longer than2K+1, whereK is a nonnegative integer independent of the numbern of nodes ofG. We present an O(n ^4K) algorithm for the max-cut problem for graphs ing(K). The algorithm is recursive and is based on some properties of longest and longest odd cycles of graphs. This research was supported by National Science Foundation Grant ECS-8005350 to Cornell University.     

Algorithms for approximate calculation of the minimum of a convex function from its values

The paper deals with a numerical minimization problem for a convex function defined on a convexn-dimensional domain and continuous (but not necessarily smooth). The values of the function can be calculated at any given point. It is required to find the minimum with desired accuracy. A new algorithm for solving this problem is presented, whose computational complexity asn is considerably less than that of similar algorithms known to the author. In fact, the complexity is improved fromCn ⁷ ln²(n+1) [4] toCn ² ln(n+1).Translated fromMatematicheskie Zametki, Vol. 59, No. 1, pp. 95–102, January, 1996.     

An algorithm for then×n optimum assignment problem

In this paper we present an algorithm for finding an optimum assignment for ann×n matrixM inn iterations. The method uses systematic permutations on the rows ofM and is based on the properties of optimum assignments. The implementation presented in the paper requires at mostO(n ³) in time andn ²+6n memory locations for solving a densen×n problem.This work was supported by the National Science Foundation Grant NSF ENG 74-19788.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds

By refining a variant of the Klee–Minty example that forces the central path to visit all the vertices of the Klee–Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is , we prove that solving this n-dimensional linear optimization problem requires at least 2 ⁿ −1 iterations. Dedicated to Professor Emil Klafszky on the occasion of his 70th birthday.     

On the spectrum for Km+2 \ Km designs

The spectrum problem for the decomposition of K_n into copies of the graph K_m+2 \ K_m is solved for n ≡ 0 or 1 (mod 2m + 1). © 1997 John Wiley & Sons, Inc.     

n维双曲空间和n维球面空间中的正弦定理及应用

本文研究了n维双曲空间和n维球面空间中单形的正弦定理和相关几何不等式. 应用距离几何的理论和方法, 给出了n维双曲空间和n维球面空间中一种新形式的正弦定理, 利用建立的正弦定理获得了Hadamard 型和Veljan-Korchmaros型不等式. 另外, 建立了涉及两个n维双曲单形和n维球面单形的"度量加"的一些几何不等式.     

Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.     

The structure of some classes of <Emphasis Type="Italic">K</Emphasis>-contact manifolds

We study projective curvature tensor in K-contact and Sasakian manifolds. We prove that (1) if a K-contact manifold is quasi projectively flat then it is Einstein and (2) a K-contact manifold is ξ-projectively flat if and only if it is Einstein Sasakian. Necessary and sufficient conditions for a K-contact manifold to be quasi projectively flat and φ-projectively flat are obtained. We also prove that for a (2n + 1)-dimensional Sasakian manifold the conditions of being quasi projectively flat, φ-projectively flat and locally isometric to the unit sphere S ²ⁿ⁺¹ (1) are equivalent. Finally, we prove that a compact φ-projectively flat K-contact manifold with regular contact vector field is a principal S ¹-bundle over an almost Kaehler space of constant holomorphic sectional curvature 4.     

Solutions to an inverse monic quadratic eigenvalue problem

Given n+1 pairs of complex numbers and vectors (closed under complex conjugation), the inverse quadratic eigenvalue problem is to construct real symmetric or anti-symmetric matrix C and real symmetric matrix K of size n×n so that the quadratic pencil Q(λ)=λ²I_n+λC+K has the given n+1 pairs as eigenpairs. Necessary and sufficient conditions under which this quadratic inverse eigenvalue problem is solvable are obtained. Numerical algorithms for solving the problem are developed. Numerical examples illustrating these solutions are presented.     

A note on an open problem in linear complementarity

LetK be the class ofn × n matricesM such that for everyn-vectorq for which the linear complementarity problem (q, M) is feasible, then the problem (q, M) has a solution. Recently, a characterization ofK has been obtained by Mangasarian [5] in his study of solving linear complementarity problems as linear programs. This note proves a result which improves on such a characterization.Research sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385.     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

Approximate Hedging of Contingent Claims under Transaction Costs for General Pay-offs

Abstract

In 1985 Leland suggested an approach to price contingent claims under proportional transaction costs. Its main idea is to use the classical Black–Scholes formula with a suitably enlarged volatility for a periodically revised portfolio whose terminal value approximates the pay-off h(S _?T )?=?(S _?T ???K)⁺ of the call option. In subsequent studies, Lott, Kabanov and Safarian, and Gamys and Kabanov provided a rigorous mathematical analysis and established that the hedging portfolio approximates this pay-off in the case where the transaction costs decrease to zero as the number of revisions tends to infinity. The arguments used heavily the explicit expressions given by the Black–Scholes formula leaving open the problem whether the Leland approach holds for more general options and other types of price processes. In this paper we show that for a large class of the pay-off functions Leland's method can be successfully applied. On the other hand, if the pay-off function h(x) is not convex, then this method does not work.     

An embedding theorem for finite planar spaces

LetS be a finite planar space such that any two distinct planes intersect in a line. We show thatk≤n ²+1 for anyk-cap ofS, wheren is the order ofS. Moreover, if a (n ²+1)-cap exists inS, a necessary and sufficient condition is provided forS to be embeddable in a 3-dimensional projective space. Work supported by the National Research Project “Strutture geometriche, Combinatoria e loro applicazioni” of the italian M.U.R.S.T.     

A Blichfeldt-type inequality for the surface area

In 1921, Blichfeldt gave an upper bound on the number of integral points contained in a convex body in terms of the volume of the body. More precisely, he showed that #(K?\Bbb Zⁿ) ￡ n! vol(K)+n\#(K\cap{\Bbb Z}^n)\le n! {\rm vol}(K)+n , whenever K ì \Bbb RⁿK\subset{\Bbb R}^n is a convex body containing n + 1 affinely independent integral points. Here we prove an analogous inequality with respect to the surface area F(K), namely #(K?\Bbb Zⁿ) < vol(K) + ((?n+1)/2) (n-1)! F(K)\#(K\cap{\Bbb Z}^n) < {\rm vol}(K) + ((\sqrt{n}+1)/2) (n-1)! {\rm F}(K) . The proof is based on a slight improvement of Blichfeldt’s bound in the case when K is a non-lattice translate of a lattice polytope, i.e., K = t + P, where t ? \Bbb Rⁿ\\Bbb Zⁿt\in{\Bbb R}^n\setminus{\Bbb Z}^n and P is an n-dimensional polytope with integral vertices. Then we have #((t+P)?\Bbb Zⁿ) ￡ n! vol(P)\#((t+P)\cap{\Bbb Z}^n)\le n! {\rm vol}(P) . Moreover, in the 3-dimensional case we prove a stronger inequality, namely #(K?\Bbb Zⁿ) < vol(K) + 2 F(K)\#(K\cap{\Bbb Z}^n)< {\rm vol}(K) + 2 {\rm F}(K) .     

Maximum Matchings in the n-Dimensional Cube

The problem of efficient computation of maximum matchings in the n-dimensional cube, which is applied in coding theory, is solved. For an odd n, such a matching can be found by the method given in our Theorem 2. This method is based on the explicit construction (Theorem 1) of the maps of the vertex set that induce largest matchings in any bipartite subgraph of the n-dimensional cube for any n.     

A class of polynomial variable metric algorithms for linear optimization

In the paper, the behaviour of interior point algorithms is analyzed by using a variable metric method approach. A class of polynomial variable metric algorithms is given achieving O ((n/β)L) iterations for solving a canonical form linear optimization problem with respect to a wide class of Riemannian metrics, wheren is the number of dimensions and β a fixed value. It is shown that the vector fields of several interior point algorithms for linear optimization is the negative Riemannian gradient vector field of a linear a potential or a logarithmic barrier function for suitable Riemannian metrics. Research Partially supported by the Hungarian National Research Foundation, Grant Nos. OTKA-T016413 and OTKA-2116.