Putting D'Wave's 'Orion' to the Test - (Part 4)

....Continued from Part 3

Note: I've heard (today: 26 August 2009) from the folks at Orion web services and they told me that my optimization job failed because it exceeded the maximum quota...for the job run time (10 mins). Looks like I'll have to figure out news ways of streamlining my problems!

As my problem was successfully 'parsing' through Orion, I was thoroughly enthralled by the thought of parallel universes entangling, at that very moment, to wrestle the binary quadratic portfolio optimization problem that I had submitted. Unfortunately, my extreme excitement was destined to morph into an admixture of disappointment and anger.

Approximately ten minutes after I had submitted my problem into the Orion application, I received this message from the application:

Click on Image for a Better View

Hence, I attempted to figure out what went wrong; was there an error in the problem structure, or in the parameters that I set when I submitted the problem?

I revised my problem matrix, and the parameters that I had set, and everything appeared to be sound:

Click on Image for a Better View

This part of the Job status revealed what went wrong:

Click on Image for a Better View

Apparently, Orion's Binary Quadratic Optimization Annealing Solver had completed the process of computing my portfolio optimization problem, but it timed-out just before it could produce the solution... Strange.

Maybe there could be a bug in Orion, or I have just witnessed the effects of decoherence in a quantum system (after all, quantum data is very fragile). I know that Orion is currently powered by an interconnected computing grid that simulates a quantum computer. Maybe something perturbed the grid whilst it was compiling the answer.

I'll try again at random intervals just to make sure.

Putting DWave's 'Orion' to the Test - (Part 3)

....Continued from Part 2

The general assumption underpinning equation 8, is that the asset returns (of what? Duh! the assets in question) follow a multivariate normal distribution.

***

Now, here's a hypothetical problem from which we'll derive the parameters that we'll use in the formulation of a problem matrix for Orion to solve:

Let us postulate that a regulated financial institution is required by law to keep 50% of its capital reserves in liquid risk-free assets like T-bills. The institution is free to invest the entire unregulated half (50%) of its reserves as it wishes. Therefore, the institution's management decide to invest in the stock of Google (NYSE: GOOG) and Apple (NYSE: AAPL). Hence, the management tasks the Chief Risk Officer to calibrate the lowest level of risk (variance) that the institution would be exposed to owing to a 50-50 investment of the unregulated capital in Apple and Google stocks.

The risk manager starts by examining the volatility patterns and the correlation matrix of Google and Apple stock in the following tables that were prepared by his analyst:

Hence, from the data he derives the following parameters:

• Annual Standard deviation of Google shares, σ1 = 0.4926
• Annual Standard deviation of Apple shares, σ2 = 0.5508
  
• Anual Covariance of Apple and Google shares, p12σ1σ2 = 0.1826 (to 4 s.fs.)
  

To conserve computing resources, he decides to treat the optimization problem as a two asset binary quadratic problem, and thus plugs the values he derived from the tables into equation 8, and gets an expression that looks like this (which we'll call equation 9):

min{0.2427(x1.x1) + 0.3034(x2.x2) + 0.3652(x1.x2)}

The risk manager decides that in binary notation, x1 and x2 = 1 and derives the following binary quadratic portfolio optimization problem for DWave's Orion to minimize:


...Not so fast: The matrix above will not work in Orion because The third column in each row specifies the value to be assigned to the selected Q_ij element of the matrix. Q_ij must be an integer value. Therefore, we round-off everything in the third column to 1 significant figure and multiply it by ten to get this matrix (which will work in Orion):


Stay tuned for Part 4 of this installation. It will contain the result of the computation plus an evaluation of Orion

Putting DWave's 'Orion' to the Test - (Part 2)

....Continued from Part 1

Below is an efficient frontier, i.e. the navy-blue continuous curve that passes between points a b c and d. It illustrates the trade-off between return and risk. The efficient frontier is essentially a universe of assets, or a set of portfolios of assets that offer the minimum risk for a given level of return. The black line, that is a tangent to the efficient frontier, and is passing between points c and d is the CAPM line. It contains, at its intersection with the efficient frontier, all iterations of portfolios containing the risk free asset that rational market participants can select.

Therefore, given the objective stated in Part 1, we seek to find point c on the intersection of the CAPM and the efficient frontier.

Click on Image for Better Visibility

As I mentioned before, the optimization problem introduced in part 1 is unconstrained, and generally it is standard practice to trace-out the efficient frontier by introducing a weighting parameter λ (λ is greater than or equal to zero but less than or equal to one), and considering:

We'll call the expression above equation 5 and it is subject to equations 6 and 7 which follow respectively:

In equation five, the case λ = 1 represents minimizing the risk, and when we substitute λ for 1 in equation 5, we get equation 4, which can be expanded into the following expression (which we'll call equation 8), in the case of a two asset portfolio:

Where:

• X1 and x2 represent wi and wj respectively
• σ1 and σ2 represent the standard deviation of asset i and the standard deviation of asset j respectively
• p12σ1σ2 is equivalent to σij and represents the covariance of asset i and asset j
  

Stay tuned for the third part of this installation, where I'll convert the optimization problem into a binary quadratic problem, and plug in variables to generate a problem matrix for DWave's Orion to solve.

Putting DWave's 'Orion' to the Test - (Part 1)

I have been steadfastly tracking DWave Systems's progress for approximately two years now, and I was immensely overjoyed when I discovered that they had opened-up the initial trials of their operating system (called Orion) to the general public.

As you probably know (by now), I am always on the hunt for technologies that have the potential to enhance the quantitative aspects of portfolio structuring decisions, and I was thoroughly ecstatic when I found-out that Orion has a facility for portfolio optimization.

Generally, quantitative portfolio structuring decisions, like most optimization problems, are amenable to quantum acceleration, and thus, DWave's operating system should be able to tackle them (this assertion is underpinned by the assumption that Orion is, in its current form robust).

Yesterday, I decided to put DWave's Orion operating system to the test, and to chronicle every minute thing I did in this, and subsequent blog posts.

I started my journey by visiting DWave's Menu of problem types to select the best algorithm to solve portfolio optimization problems. On the menu the choices included:

• A Binary Quadratic Program (BQP) problem algorithm;
  
• An Ising problem algorithm;
• A Chimera (BQP) problem algorithm;
• A Chimera (Ising) problem algorithm;
• A Maximum Satisfiability (MAX-SAT) problem algorithm;
• A Cardinality SAT problem algorithm;
• A Weighted Maximum Satisfiability (Weighted MAX-SAT) problem algorithm;
  
• A Model Expansion (MX) problem algorithm;
  
• A Maximum Independent Set (MIS) problem algorithm, and;
  
• A Clique (CLQ) problem algorithm.

I noticed that both the Binary Quadratic Program (BQP) problem algorithm and the Chimera (BQP) problem algorithm resembled the general form of Harry Markowitz's portfolio optimization formula.

Therefore, since I desired simplicity, I decided to settle for the Binary Quadratic Program (BQP) problem algorithm which was in the following form:


Interestingly, this particular problem is an unconstrained binary quadratic programming problem of minimizing a quadratic objective by suitable choice of binary (zero-one) variables.

When expressed in mean-variance portfolio optimization parlance, the binary quadratic programming problem assumes the following form (the equations are from a paper entitled Heuristics For Cardinality Constrained Portfolio Optimization by T.J. Chang, N. Meade, J.E. Beasley and Y.M. Sharaiha):

We'll call this new expression equation 1, which is subject to equation 2, 3 and 4 which follow respectively:


Equation 1 minimizes the total variance (risk) associated with the portfolio whilst Equation 2 ensures that the portfolio has an expected return of R*. Equation 3 ensures that the proportions add to one.

Where:

N is the number of assets available,
μi is the expected return of asset i (i = 1, 2, ...... N),
σij is the covariance between assets i and j (i = 1, 2, ...... N),
R* is the desired expected return.

Then the decision variables are:
wi is the proportion held of asset i (i = 1, 2, ...... N), and is greater than or equal to zero but less than or equal to one.

Stay tuned for the second part of this installation, where I'll convert the optimization problem into a binary quadratic problem, and plug in variables to generate a problem matrix for DWave's Orion to solve.