Thursday, April 13, 2017

QP as LP: piecewise linear functions

I am facing a (convex) QP problem that has some numerical issues for some data sets. Hence as backup I’d like to be able to solve the problem as an LP. One way to do this is using a simple piecewise linear approximation.

Consider the objective function \(\min\> f(x)=x^2\). Instead of solving this directly we can invent a few linear functions \(y = a_i x + b_i\) and approximate the problem by:

\[\begin{align} \min\>&z\\
                             &z \ge a_i x + b_i\end{align}\]

Here is an example how these linear functions can look like:

image

To derive a single linear function we observe the following:

  1. Pick a point \(t_i\), e.g. \(t_i=2\) in the picture below.
  2. We want the function value to match: \(f(t_i) = a_i t_i + b_i\). I.e. \(a_i t_i + b_i=t_i^2\).
  3. We also want the slope to match: \(\nabla f(t_i) = a_i\). I.e. \(a_i = 2 t_i\).

image

This means we can choose:

\[\begin{align} &a_i = 2 t_i\\
                     &b_i = –t_i^2\end{align}\]

The net effect of this strategy is that we formed a piecewise linear objective that approximates our original quadratic function:

image

Note that there are other linear approximation schemes. This is just a particularly simple one.

Example: portfolio optimization

To try this out on a more realistic problem, we consider a standard portfolio optimization problem:

\[\boxed{\begin{align} \min \>& \sum_t w_t^2\\
                              & w_t = \sum_i r’_{i,t} x_i\\
                              & \sum_i \mu_i x_i \ge R\\
                              & \sum_i x_i = 1\\
                              &x_i\ge 0\end{align}}
\]

Here \(r’=r-\mu\) are the mean adjusted returns.\(R\) is the minimum expected portfolio return.

In this case our linear model can look like:

\[\boxed{\begin{align} \min \>& \sum_t z_t\\
                              & z_t \ge a_{t,j} w_t + b_{t,j}\>\forall t,j\\
                              & w_t = \sum_i r’_{i,t} x_i\\
                              & \sum_i \mu_i x_i \ge R\\
                              & \sum_i x_i = 1\\
                              &x_i\ge 0\end{align}}
\]

The \(w_t\)’s vary from \(L_t=\displaystyle\min_i r’_{i,t}\) to \(U_t=\displaystyle\max_i r’_{i,t}\). For each \(w_t\) we choose \(n=10\) equidistant points between \([L_t,U_t]\). We use the FTSE100 dataset from (1), which has:

  • number of time periods \(t\): 717
  • number of stocks \(i\): 83

We see the following results:

  • The optimal QP objective is 0.41202816
  • The optimal LP objective is 0.37728185

This looks bad, but actually things are better than they appear. When we evaluate \(\displaystyle\sum_i w_t^2\) for the optimal LP values of \(w_t\) we have:

  • QP objective of LP solution: 0.41246149

Here are the differences in the selected portfolio:

----     87 PARAMETER report 

QP objective 0.41202816,    LP objective 0.37728185,    w'w from LP  0.41246149


----     87 PARAMETER xval 

                 QP          LP

stock2   0.11723384  0.10298780
stock11  0.13629495  0.14992714
stock22  0.06253534  0.06202882
stock40  0.09082870  0.10523583
stock64  0.08521849  0.08348895
stock66  0.17247021  0.17267818
stock69  0.00180266
stock78  0.09462530  0.09761814
stock79  0.05184550  0.04383311
stock83  0.18714501  0.18220203

Performance

Although the LP model is much larger, it solves in about the same time as the original QP. I see:

image

Note that barrier iterations should really not be compared to simplex iterations. A finer or more coarse grid in the piecewise linear approximation has only affect on the the number of equations in the model (the number of variables will stay the same).

References
  1. Renato Bruni, Francesco Cesarone, Andrea Scozzari, Fabio Tardella, Real-world datasets for portfolio selection and solutions of some stochastic dominance portfolio models, Data in Brief, Volume 8, September 2016, Pages 858-862
  2. QP as LP: cutting planes, http://yetanothermathprogrammingconsultant.blogspot.com/2017/04/qp-as-lp-cutting-planes.html