Non Linear Programming

Lecture 5: Non-Linear Programming (NLP) and The Markowitz portfolio model Thomas Stidsen

1

Learning Objectives

• General introduction to Non-Linear Programming (NLP)

• Warn of a number of NLP problems • Introduction to the Markowitz portfolio model. • Formulation and solution of nonlinear models in GAMS.

• Learn the GAMS looping and printing facilities.

2

Why NLP ? Not all problems can be modeled sufficiently well with “just” Linear Programming (LP) or Mixed Integer Linear Programming (MIP). In these cases we may need Non-Linear Programming (NLP) another type of mathematical model where non-linearities are allowed in the objective function and in the constraints.

3

How NLP ? Very simple: If non-linear functions are used:

• In the objective function (best) • In constraints (worst)

The only thing we need to do in order to optimize the NLP model is to use the keyword NLP instead of LP or MIP in the solve statement.

4

NLP limitations Working with Non-Linear Solvers is technically more difficult ! The NLP solver we use is the CONOPT solver, by Arne Drud (engineer from DTU). It is a general purpose solver which can solve a very general class of problems, the only requirement that the functions used are continuous and differentiable. This is nice, but unfortunately the strength of the solvers is not as good as LP solvers:

• Only guaranteeing local optimality ! • No integer variables allowed (not differentiable !)

• Much smaller problems may be solved .... 5

Warnings There are a couple of things you need to be aware of when using CONOPT (or any other general NLP solver):

• Unless the problem is convex, only a locally optimal solution is found.

• If you use very large numbers or very small numbers, the solver becomes unstable.

• Non-linear constraints are problematic ! Always try to move non-linearities to the objective function.

• Longer running times ... 6

• If you have to raise a variable or a parameter to a certain value e.g. 2, there are three possibilities: – Simple multiplication, e.g. xi · xi – Use the power function, e.g. power(xi , 2) – Use the raise operator, e.g. xi ∗ ∗2. SERIOUS WARNING: THE RAISE OPERATOR IS PROBLEMATIC BECAUSE IT DOES NOT CALCULATE PRECISELY, AVOID IT IF POSSIBLE !!!

In general you will run into a lot more problems with NLP solvers than LP and to some extent MIP solvers.

The (Markowitz) portfolio model

• Assume n securities (e.g- stocks, bonds, etc).

• Average return on security j: µj . • Covariance of the return on one share each of stock i and stock j: σij . • What does covariance means?

7

• Problem. Pick an “optimal” portfolio i.e. how big percentage should be invested in security 1 and so forth.

• Maximize expected return! risk?

What about

• Decision variables xj . • Measure of expected return: R(x) =

n X j=1

µ j xj

8

• Measure of risk (the variance): V (x) =

n X n X i=1 j=1

σij xixj

• Objective function (maximize): (1 − β)R(x) − βV (x). β ∈ [0, 1]. • β measure investor’s trade-off between return and risk.

• Small β implies high risk. • Large β implies small risk.

9

Model: max (1 − β) s.t.

n P j=1

µ j xj − β n P j=1

n P

n P

i=1 j=1

xj

σij xixj = 1

xj ≥ 0 • What is the right β? • Efficient frontier: Optimal R(x) and V(x) for each value of β. • Pick a solution on the optimal frontier. • Why? • An example of multi objective programming. 10

Efficient Frontier 13 Beta = 0 12

11

Return

10

9 Beta = 0.5 8

7 Beta = 1 6

0

1

2

3

4

5 6 Variance

7

8

9 11

10

A GAMS model $Title A Quadratic Programming Model for Portfolio Analysis. $Ontext This is a mini mean-variance portfolio selection problem. $Offtext Set i

securities

/hardware, software, show-biz, t-bills/;

alias (i,j); Scalar

beta Weightning parameter between risk and return / 1 /;

Parameters

mean(i)

/ hardware software show-biz t-bills

Table v(i,j)

mean annual returns on individual securities (%)

8 9 12 7 /

variance-covariance array (%-squared annual return) hardware

hardware software show-biz t-bills Variables

4 3 -1 0

z x(i)

software

show-biz

t-bills

3 6 1 0

-1 1 10 0

0 0 0 0

fraction of portfolio invested in asset i

Positive Variable x; 12

Equations

fsum obj

fractions must add to 1.0 objective function ;

fsum.. sum(i, x(i)) =e=

1.0

;

obj.. (1-beta)*sum(i, mean(i)*x(i)) - beta*sum((i,j), x(i)*v(i,j)*x(j)) =e= z; Model portfolio

/ all / ;

for(beta=0 to 1 by 0.1, solve portfolio using nlp maximizing z; );

13

Comments:

• Note for statement. • General syntax: for(i = start to | downto end [by incr], gams statements; ); • Alternative to for is while: while(condition, GAMS statements; );

14

• Program generates a lot of output! • Want just β and optimal R(x) and V (x). • Answer: Use the GAMS put facility.

15

Example report Beta 0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00

Return 12.0000 12.0000 12.0000 11.8929 11.2909 10.7818 10.4424 9.8827 9.3284 8.8972 8.5522 8.2700 8.0348 7.8358 7.6652 7.5174 7.3881 7.2739 7.1725 7.0817 7.0000

Variance 10.0000 10.0000 10.0000 9.3750 6.5091 4.7273 3.8222 2.6768 1.7463 1.1594 0.7761 0.5196 0.3449 0.2250 0.1426 0.0862 0.0485 0.0242 0.0096 0.0021 0.0000

16

How was that created? GAMS code * Open a file called results.dat and assign the name * results_file to it. file results_file / results.dat /

* All subsequent put output is send to the file results_file. put results_file; put ’Beta’:<10, ’Return’:<>20, ’Variance’:<>20 /; for(beta=0 to 1 by 0.05, solve portfolio using nlp maximizing z; put beta:<10, sum(i, mean(i)*x.l(i)):<>20:4, sum((i,j), x.l(i)*v(i,j)*x.l(j)):<>20:4 /; ); * Closing the output file. putclose results_file;

17

• Text put: put ’text’:<15 means text is printed in a field that is 15 chars wide. – < means left justified. – > means right justified. – <> means centered. • Numerical put: put x.l:<>20:5 means x.l is printed in a field that is 20 chars wide and it has 5 decimals. • put / means start a new line. 18

Summary

• Fairly easy to formulate nonlinear models in GAMS (more about that later).

• for command is powerful to solve several related models.

• put command is useful to created customized reports. – E.g. create files that can be read by Excel. See GAMS user’s guide 15.17.

19