Transforming a QP Problem to an SOCP Problem

A Quadratic Programming problem (QP) in the form of where , can be transformed to a Second-Order Cone Programming (SOCP) problem in the form of Consider , and As is non-negative, minimizing is equivalent to minimizing , and hence is equivalent to minimizing . If we have  and , then the objective function in QP  can be written as . We can thus minimize . Thus, the QP problem can now be written as As , by definition of QP, is symmetric, a symmetric can be found such that . If the QP is assumed to be a convex QP, is positive semidefinite, applying Cholesky factorization gives (or ). In this case, (or ). Next, as is always non-negative, the equality constraint can be written as Finally, each row in the inequality constraint can be written as where is the i-th row of , and is the i-th element of . Therefore, a QP problem can be transformed to an equivalent SOCP problem in the following way. We need to introduce a few variables first. The sub-vector with the first elements in the solution of the transformed SOCP problem is the solution of the original QP problem. SuanShu has implementations to solve both SOCP and QP problems. SOCP interior point solver QP active set... read more

Fastest Java Matrix Multiplication

Introduction Matrix multiplication occupies a central role in scientific computing with an extremely wide range of applications. Many numerical procedures in linear algebra (e.g. solving linear systems, matrix inversion, factorizations, determinants) can essentially be reduced to matrix multiplication [5, 3]. Hence, there is great interest in investigating fast matrix multiplication algorithms, to accelerate matrix multiplication (and other numerical procedures in turn). SuanShu was already the fastest in matrix multiplication and hence linear algebra per our benchmark. SuanShu v3.0.0 benchmark Starting version 3.3.0, SuanShu has implemented an advanced algorithm for even faster matrix multiplication. It makes some operations 100x times faster those of our competitors! The new benchmark can be found here: SuanShu v3.3.0 benchmark In this article, we briefly describe our implementation of a matrix multiplication algorithm that dramatically accelerates dense matrix-matrix multiplication compared to the classical IJK algorithm. Parallel IJK We first describe the method against which our new algorithm is compared against, IJK. Here is the algorithm performing multiplication for is ,  is , and  is : for (i = 1; i < = m; i ++){ for (j = 1; j <= p; j ++){ for (k = 1; k <= n; k ++){ C[i,k] += A[i,j] * B[j,k]; } } } 1234567 for (i = 1; i < = m; i ++){    for (j = 1; j <= p; j ++){        for (k = 1; k <= n; k ++){            C[i,k] += A[i,j] * B[j,k];        }    }} In Suanshu, this is implemented in parallel; the outermost loop is passed to a  ParallelExecutor . As there are often more rows than threads available, the time complexity of this parallelized IJK is still roughly the same as IJK: ,... read more

Using Returns in Pairs Trading

This blog article is taken from our book [1]. In most entry-level materials on pairs trading such as in [2],  a mean reverting basket is usually constructed by this relationship: , where is the price of asset at time t, the price of asset at time t, and the price of the mean reverting asset to trade. One way to find is to use cointegration. There are numerous problems in this approach as detailed in [1]. To mention a few: the identified portfolios are dense; executions involve considerable transaction costs; the resultant portfolios behave like insignificant and non-tradable noise; cointegration is too stringent and often unnecessary a requirement to satisfy. This article highlights one important problem: it is much better to work in the space of (log) returns than in the space of prices. Therefore, we would like to build a mean reverting portfolio using a similar relationship to (eq. 1) but in returns rather than in prices. The Benefits of Using Log Returns When we compare the prices of two assets, [… TODO …]   A Model for a Mean Reverting Synthetic Asset Let’s assume prices are log-normally distributed, which is a popular assumption in quantitative finance, esp. in options pricing. Then, prices are always positive, satisfying the condition of “limited liability” of stocks. The upside is unlimited and may go to infinity. [5] We have: is the return for asset between times 0 and t; likewise for asset . Instead of applying a relationship, e.g., cointegration (possible but not a very good way), to the pair on prices, we can do it on returns. This is possible because, just like prices, the returns at... read more

On Some Practical Issues when Using AlgoQuant to Compute the Markowitz Efficient Frontier

Markowitz suggests in his Nobel Prize-winning paper Markowitz(1952) that when one selects a portfolio, he/she should consider both the return and the risk of the portfolio. Most of us, if not all, are risk-averse. Risk-averse means that if there are two  portfolios with the same return, but different risks (in this article by risk we mean the standard deviation of the portfolio), we would choose the one with the smaller risk without any hesitation. Therefore given a set of risky assets and an expected return, we are interested in finding their best combination, i.e. the weights which will minimize the risk of the portfolio. And if we find the minimum risk of the portfolio for any return, we can draw a curve on risk-return plane. This curve is the famous efficient frontier. Assuming there are  risky assets, and their return vector and covariance matrix are  and  respectively, then the points on the efficient frontier are computed by solving the following problem: where is the pre-defined expected return, and is the weight vector. The above problem can be solved using Lagrange multipliers. And we denote this problem as “Problem 1”. In AlgoQuant, we use another approach to compute the efficient frontier. The problem we solve is based on the utility function: , ,  and  are the same parameters in Problem 1. The newly added parameter , is risk-averse coefficient. And this problem is denoted as “Problem 2”. The larger the , the less risk the investor is willing to take. Although most of us are risk-averse, the degrees of risk-averse are different among individuals. As a result, a coefficient that describes the risk-averse degree is introduced. Note that in some papers, risk... read more

Certificate in Quantitative Investment (CQI)

Numerical Method Inc. has the vision to promote rational investment and trading. Jointly organized with top universities, we are offering a 6-months 9-courses program that teach mathematics, programming and quantitative or algorithmic trading. We invite famous and established traders from Wall Street banks and funds to share their experience. Students may choose to participate in classroom or online. More information can be found here: read more

Solving the "Corner Solution Problem" of Portfolio Optimization

Many portfolio optimization methods (e.g., Markowitz/Modern Portfolio Theory in 1952) face the well-known predicament called the “corner portfolio problem”. When short selling is allowed, they usually give efficient allocation weighting that is highly concentrated in only a few assets in the portfolio. This means that the portfolio is not as diversified as we would like, which makes the optimized portfolio less practically useful. In [Corvalan, 2005], the author suggests to look for instead an “almost efficient” but “more diversified” portfolio within the close neighborhood of the Mean-Variance (MV) optimal solution. The paper shows that there are many eligible portfolios around the MV optimal solution on the efficient frontier. Specificially, given the MV optimal solution, those “more diversified” portfolios can be computed by relaxing the requirements for the portfolio return and risk in an additional optimization problem: where , is the Markowitz MV optimal weights, are the relaxation tolerance parameters, and is a diversification measure for the portfolio (for example, , ). In other words, the new optimization problem looks for a portfolio with the maximal diversification around the optimal solution. Corvalan’s approach can be extended to create an approximate, sufficiently optimal and well diversified portfolio from the optimal portfolio. The approximate portfolio keeps the constraints from the original optimization problem. References: SuanShu Javadoc Alejandro Corvalan (2005). Well Diversified Efficient Portfolios. Documentos de trabajo del Banco Central, no.... read more

Change of Measure/Girsanov’s Theorem Explained

Change of Measure or Girsanov’s Theorem is such an important theorem in Real Analysis or Quantitative Finance. Unfortunately, I never really understood it until much later after having left school. I blamed it to the professors and the textbook authors, of course.  The textbook version usually goes like this. Given a probability space , and a non-negative random variable Z satisfying (why 1?). We then defined a new probability measure Q by the formula, for all . Any random variable X, a measurable process adapted to the natural filtration of the , now has two expectations, one under the original probability measure P, which denoted as , and the other under the new probability measure Q, denoted as . They are related to each other by the formula If , then P and Q agree on the null sets. We say Z is the Radon-Nikodym derivatives of Q with respect to P, and we write . To remove the mean, μ, of a Brownian motion, we define Then under the probability measure Q, the random variable Y = X + μ is standard normal. In particular, (so what?). This text made no sense to me when I first read it in school. It was very frustrated that the text was filled with unfamiliar terms like probability space and adaptation, and scary symbols like integration and . (I knew what meant when y was a function and x a variable. But what on earth were dQ over dP?) Now after I have become a professor to teach students in finance or financial math, I would get rid of all the jargon... read more

Mean-Variance Portfolio Optimization When Means And Covariances Are Unknown

[Lai, Xing and Chen, 2010], in the paper “Mean-Variance Portfolio Optimization When Means And Covariances Are Unknown”, proposed a ground breaking method to do portfolio optimization. In what follows we summarize their idea and use it to implement a periodic rebalancing strategy based on the AlgoQuant framework. Harry Markowitz won the Nobel prize for his work in mean-variance (MV) portfolio optimization in 1950s. The theory is widely regarded as fundamental in financial economics. It says, given a target return of a portfolio of m assets, the optimal (in terms of information ratio) weighting is given by where is the expected future returns, and is the expected covariance matrix of future returns. This problem is readily solved by quadratic programming. Nonetheless, the assumption that and are known in advance is very dubious. This has been referred to as the “Markowitz optimization engima”. The attempts made so far are to better forecast these estimators, namely and , as accurately as possible. The maximum likelihood estimate (MLE) from the training sample is an example. It turns out, however, that MLE performs poorly because the estimators are quite different from the realized values [Michaud, 1989]. Since then, three approaches have been proposed to address the difficulty. The first approach uses a multi-factor model to reduce the dimensionality in estimating [Fan, Fan and Lv, 2008]. The second approach uses Bayes or other shrinkage estimates of [Ledoit and Wolf, 2004]. Both approaches attempt to use improved estimates of for the plug-in efficient frontier. They have also been modified to provide better estimates of , for example, in the quasi-Bayesian approach of [Black and Litterman, 1990]. The third approach uses bootstrapping... read more

FREE .NET/C# Numerical/Math library

On this Christmas Day, we are happy to announce that is FREE for all! has all the features as its Java sibling as well as has undergone the same many thousands of test cases daily. There are a tutorial and examples that show you how to build a SuanShu application in Visual Studio. One major advantage of using over the Java version is that it integrates seamlessly with Microsoft Excel. By incorporating SuanShu library in your spreadsheet, you literally have access to hundreds of numerical algorithms when manipulating and analyzing your data, significantly enhancing Excel’s productivity. We hope that you enjoy using in your work. If you have any interesting story, comments or feedback, we’d love to hear from you. Starting downloading read more

Shopping Cart