Introduction. Linear programming provides a powerful framework for modeling and solving
numerous problems in industrial applications like resource management, transportation,
scheduling, structural design, telecommunications, etc. In many other important applications,
however, non-linearity can be crucial for modeling the underlying problem accurately.
In this laboratory, we will take our first steps into non-linear programming and study a
problem in portfolio optimization, where the objective function is quadratic.
The main purpose of this lab is to delve deeper into one area of the theory of linear
programming. Part of the work is therefore to read and understand a fairly complex
description of new material.
We start by formulating the portfolio optimization problem. Then we derive an algorithm
for solving this formulation and we prove convergence guarantees of the proposed algorithm.
Finally, we implement and use this algorithm for solving the problem in a computer
experiment.
Problem and model: Portfolio Optimization. Sonya wants to build an investment
portfolio and she needs to decide how to allocate her savings into different assets. She has
a low tolerance for risk and her goal is to design a portfolio which minimizes the risk while
maintaining an expected return roughly around the inflation rate.
Her advisor in the bank provides historical data on monthly returns of N assets for the
last T months. We denote the return of asset n = 1, . . . ,N in month t = 1, . . . , T by an,t.
Empirically, the expected return of asset n is its average return, μn = 1
T PT
t=1 an,t.
We can write a mathematical program to model Sonya’s goals and constraints. Without
loss of generality, we denote the total amount of investment by 1 and the amount invested
in asset n by xn. We assume that xn must be non-negative (since we do not allow investing
negative amounts, or shorting) and sum up to 1.
She wants her savings to protect their value by maintaining a minimum expected value
around the inflation rate. Her empirical expected return is PN
n=1 μnxn. Let  2 R be the
inflation rate. Then we have the following minimum expected return constraint:
N
Xn
=1
μnxn  .
In statistics, we often model the risk as the variance. The variance associated to asset
n (denoted by 2n
) is its expected squared deviation from its expected return, i.e., 2n
=
1
T PT
t=1 |an,t − μn|2. The goal is minimizing the total risk f(x1, . . . , xN), given by
f(x1, . . . , xN) =
N
X
n=1
1
T
T
X t=1
|an,txn − μnxn|2
=
N
X
n=1
x2
n
1
T
T
X t=1
|an,t − μn|2
=
N
X
n=1
x2
n2n
.
Hence, we can find a proper strategy for Sonya by solving the following program:
(P)
minimize
N
X
n=1
2n
x2
n
subject to
N
X
n=1
μnxn  
N
X
n=1
xn = 1
xn  0 n = 1, . . . ,N
This problem has linear constraints but also a non-linear (convex quadratic) objective
function. The algorithms that we learned in the course are not directly applicable because
of this non-linearity. Nevertheless, we can find a solution to this problem by solving a
sequence of linear programs. This classical approach in non-linear programming is called
the conditional gradient method (CGM).
Theory, solution method: Conditional Gradient Method. CGM (also known as the
Frank-Wolfe Algorithm1) is a classical method in non-linear programming dating back to
1956. Despite its old age, CGM is still very popular today and widely used in the fields of
computer vision and artificial intelligence. In this laboratory, we consider a basic version
of CGM for solving the portfolio optimization problem.
The main strategy of CGM is as follows:
Initialize the algorithm from a feasible point x(1) = (x(1)
1 , . . . , x(1)
N ). Then, for iteration
k = 1, 2, . . .,
(1) Form a linear surrogate ˆ fk for the objective function f by using its first-order Taylor
expansion at the current estimate x(k):
ˆ fk(x) = f(x(k)) +
N
X
n=1
@f
@xn
(x(k)) · (x − x(k))
Recall that Taylor’s expansion gives the best linear approximation of function f
around x(k). Note that · is the dot-product.
NOTE! Since Calculus is not formally a prerequisite for this course, it is very
much allowed to ask questions about this particular part of the theory.
For (P), we can specify ˆ fk as
ˆ fk(x) =
N
X
n=1
2n 􀀀x(k)
n 2 + 2
N
X
n=1
2n
x(k)
n (xn − x(k)
n )
= 2
N
X
n=1
2n
x(k)
n xn −
N
X
n=1
2n
􀀀x(k)
n 2.
(2) Form an auxiliary problem with the same constraints as the original problem, but
with the linear surrogate objective ˆ fk instead of the original non-linear objective
function. This auxiliary problem is a linear program, so we can use the simplex
method for solving it. Denote the solution by y(k).
1Frank, M. & Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics
Quarterly. 3 (1–2): pp. 95–110.
For (P), we can specify the auxiliary problem (ˆPk) as2
(ˆPk)
minimize 2
N
X
n=1
2n
x(k)
n xn
subject to
N
X
n=1
μnxn  
N
X
n=1
xn = 1
xn  0 n = 1, . . . ,N
(3) Update the estimate x(k+1) by moving from x(k) towards y(k):
x(k+1) = (1 − k)x(k) + ky(k) with some step-size k 2 [0, 1].
Go back to step 1 and repeat the procedure.
With a suitable choice of step-size k, the sequence x(k) generated by CGM converges to a
solution of the original problem3. Common choices are the agnostic step-size k = 2/(k+1)
and the greedy step-size
k = argmin
η∈[0,1]
f􀀀(1 − )x(k) + y(k).
2We discarded the second term of ˆ fk in (ˆ Pk) because that term is constant with respect to x and does
not affect the solution.
3The proof is simple and provided in the appendix of this document. You do not need to read the proof
to complete this laboratory, but you are encouraged to read it, especially if you are interested in analysis.
Computer Experiment
The main task of this laboratory is to implement and use CGM for solving Sonya’s portfolio
optimization problem. Download historical data on the return of S&P 500 stock companies
from the website below:
http://www.cs.technion.ac.il/rani/portfolios/portfolios.htm
Suggested steps in the process:
(1) Process the data format from the source above so that it can be used as input data
for your software / programming language.
(2) Implement an LP routine for solving the auxiliary problems in Step 2 of CGM. You
are allowed to use, for instance, MatLab’s built-in LP solver as a component of your
implementation.
(3) Implement CGM. Your implementation should call the LP routine for Step 2 of the
algorithm.
(4) Suppose the inflation rate is  = μav = 1
N PN
n=1 μn. Run CGM for 1000 iterations
and note the results. Do the results seem to be numerically stable after this many
iterations? How many iterations do you need? What happens if you change the
step size and re-run your implementation of CGM? Investigate this in a systematic
way.
(5) Try again with a more ambitious goal of expected return,  = 1
2 (μav +μmax), where
μmax = maxn μn. Compare your result (i.e., the total variance / risk) with your
previous result. Does it increase or decrease? Is it reasonable? Investigate this in a
systematic way, and comment on the results. do this in python with pulp