FE501 – 1207 - NLP Week 2

Portfolio Optimization Problem.

The problem was first introduced by Markowitz in 1981 (in Modern Portfolio Theory).

More information about this topic can be found here.

Generic types of portfolio optimization problems

1. Risk minimization

2. Profit Maximization

Statistaical Supplementary Knowledges about the Problem

1. Expectation

   

2. Variance

   

3. Covariance

   

Note: Also check the supplementary PDF file from Hocam here.

Calculations

Solving Portfolio Optimization Problems with Excel Solver

NOTE:

For ramdom variables $(x_1,x_2,...x_n):$$(x_1,x_2,...x_n):$

$$\begin{array}{rl}& var(c_1{X}_1+c_2{X}_2+...+c_n{X}_n)=\\ & [c_1,c_2,...c_n](\text{coveriance matrix})[c_1,c_2,.....c_n{]}^T\end{array}$$

Formula for coveriance matrix is:

So that for the original problem, we have:

Notice: My exel file did not work on Mac, so I’ve attached the original excel file from Hocam.

Excel: here

Notice: Variance always positive (cause there is a square in the formula) and coveriance can be negative.

Sensitivity Report

For an NLP we can also obtain a sensitivity report, but there are several changes.

For NLP we have Lagrange Multiplier, it is similar to the shadow price in LP, which is :

An estimated value change for a small amount of change in the RHS. (not for 1 unit, cause the function is not linear, it is a curve)

When we change the

RHS constraint 1000 to 1001, the objectvie value will become smaller, but not exactly as the

“180.95” but will be close because of the nonlinearity.

Generalization of Nonlinear Programming

where $f(\overrightarrow{x})$$f(\vec x)$ is a fucntion of n decision variables and $g(\overrightarrow{x})$$g(\vec x)$ is the inequality constraints, and

$h(\overrightarrow{x})$$h(\vec x)$ is the equality constraints.

For a NLP (minimization) we have,

Iff :

1. objective function is convex
2. feasible region is convex

Any local optimal solution is the global optimal point.

For a NLP (maximization) we have,

Iff :

1. objective function is concave
2. feasible region is convex

Any local optimal solution is the global optimal point.

Feasible region can be :

2
1
- convex
2
- Non convex 

A objective function can be :

• Convex
• Concave
• Neither Convex nor Concave

Convex and Concave Functions

A function $f(x_1,x_2,...x_n)$$f(x_1,x_2,...x_n)$ is a convex function on a convex set S (S is the domain of the function) if for any $x^{\prime }\in S$$x' \in S$ and $x^{″}\in S$$x'' \in S$

$$\begin{array}{}\text{(3)}& f[\lambda x^{\prime }+(1-\lambda )x^{″}]\le \lambda f(x^{\prime })+(1-\lambda )f(x^{″})\end{array}$$

holds for $0\le \lambda \le 1$$0 \le \lambda \le 1$

A function $f(x_1,x_2,...x_n)$$f(x_1,x_2,...x_n)$ is a concave function on a convex set S (S is the domain of the function) if for any $x^{\prime }\in S$$x' \in S$ and $x^{″}\in S$$x'' \in S$

$$\begin{array}{}\text{(4)}& f[\lambda x^{\prime }+(1-\lambda )x^{″}]\ge \lambda f(x^{\prime })+(1-\lambda )f(x^{″})\end{array}$$

holds for $0\le \lambda \le 1$$0 \le \lambda \le 1$

Explanation:

for any $0\le \lambda \le 1$$0 \le \lambda \le 1$ , the new point $x^{\ast }=\lambda x_1+(1-\lambda )x_2$$x^* = \lambda x_1 + (1-\lambda)x_2$ is a point between $x_1$$x_1$ and $x_2$$x_2$ (and iff $\lambda =0,x^{\ast }=x_2$$\lambda = 0, x^* = x_2$, and iff $\lambda =1,x^{\ast }=x_1$$\lambda = 1, x^*=x_1$ )

This means that, if we took two random points from the domain of the function, function value of the new point, will always below(3) (or above (4)) the line connects those two points.

This is a convex function.

This is a concave function.

This function is NOT a convex function NEITHER a concave function.

Question: Determine the type ( convex/concave) of function: $f(x)=lnx$$f(x)=lnx$

Answer:

f(x)=ln is a concave function.

Also: $f(x)=x^{1/2}$$f(x)=x^{1/2}$ is concave function.

Properties

• Sum of two convex function is convex
• sum of two concave function is concave
• Set S is convex if $x^{\prime }\in S$$x' \in S$ and $x^{″}\in S$$x'' \in S$ imply that all points on the line segment joining $x^{\prime }$$x'$ and $x^{″}$$x''$ are member of S. This ensures that $\lambda x^{\prime }+(1-\lambda )x^{″}$$\lambda x' + (1-\lambda)x''$ will be a member of S.

Determining convexity (concavity) of the function using slope.

f(x) is a convex function if $f(x_2)\ge f(x_1)+f(x_1)(x2-x1)$$f(x_2) \ge f(x_1) + f(x_1)(x2-x1)$ , $x_2\ge x_1$$x_2 \ge x_1$ .

Determine Convexity of a single variable function (concavity) with Second derivitive check

Recall that if f (x) is a convex function of a single variable, the line joining anytwo points on y   f (x) is never below the curve y   f (x).

Theorem: Suppose $f^{″}(x)$$f''(x)$ exists for all x in a convext set S. Then $f(x)$$f(x)$ is a convex function on S if and only if $f^{″}(X)\ge 0$$f''(X) \ge 0$ for all x in S.

Theorem: Suppose $f^{″}(x)$$f''(x)$ exists for all x in a convext set S. Then $f(x)$$f(x)$ is a concave function on S if and only if $f^{″}(X)\ge 0$$f''(X) \ge 0$ for all x in S.

Single Variable Examples: Determine if A function is Convex or Concave

1. $f(x)=x^2$$f(x)=x^2$

   $$\begin{array}{}\text{(5)}& \begin{array}{c}{f}^{\prime }(x)=2x\\ f^{″}(x)=2\ge 0\\ \therefore convex\end{array}\end{array}$$

2. $f(x)=e^x$$f(x)=e^x$

   $$\begin{array}{}\text{(6)}& \begin{array}{c}{f}^{\prime }(X)=e^x\\ f^{″}(x)=e^x\ge 0\therefore convex\end{array}\end{array}$$

   

3. $f(x)=x^{\frac{1}{2}}$$f(x)=x^{\frac{1}{2}}$

   $$\begin{array}{}\text{(7)}& \begin{array}{c}{f}^{\prime }(x)=\frac{1}{2}{x}^{1/2-1}=\frac{1}{2}{x}^{\frac{-1}{2}}\\ f^{″}(x)=-1/4x^{-2/3}\le 0(x\in (0,\mathrm{\infty }))\\ \therefore concave\end{array}\end{array}$$

4.  

Convexity of the Feasible Set

A set S of points in $R^n$$R^n$ is a convex set, if the segment joining two points of S also belongs to the set, then the set is convext.

Parsing: Take two points randomly from the set, connect the two points with a segment, if the all points of segment is inside the Set, then the set is convex.

Example: Check convexity of $y^2\le x(x\ge 0)$$y^2 \le x \quad (x\ge0)$

This is a convex set.

Convex Optimization Problem

A problem is convex optimization problem when objective function is convex and feasible region is a convex set for minimization,

OR,

when objective function is concave and feasible region is a convex set for maximization problem.

Tailor Series, Tailor Expansion and Hessian Matrix

Higher order derivitives

Source: https://www.youtube.com/watch?v=BLkz5LGWihw

Taylor Series

Taylor series is the approximation of a given complex function.

Hessian Matrix

Hessian Matrix is a way of packing (organizing all the second partial derivative onformation of a multivariable function).

OR:

Quadratic Approximation

The basic formula for quadratic approximation with base point $x_0=0$$x_0=0$ is:

This works for values of x near 0; it is just the formula for linear approximation with one new term.

Wher did that extra term come from, and what is the $\frac{1}{2}$$\frac{1}{2}$ doing in front of the $x^2$$x^2$ ? We'll explain this in terms of what happens if the graph of our function is aparabola. If the graph of a function is a parabola, that function is a quadraticfunction.

Ideally, the quadratic approximation of a quadratic function shouldbe identical to the original function.

Is there a reason why a is the constant term? I'd be inclined to rewrite thisas $ax2+bx+c$$ax2 + bx + c$.

For instance, consider:

Set the base point $x0=0$$x0 = 0$. Now we try to recover the values of a, b and c fromour information about the derivatives of f(x).

This tells us what the coe cients of the quadratic approximation formula mustbe in order for the quadratic approximation of a quadratic function to equalthat function.

Determining convexicty of a multiple variables function using Hessian Matrix

Calculating Hessian

The Hessian of $f(x_1,x_2,..x_n)$$f(x_1,x_2,..x_n)$ is the $n\times n$$n\times n$ matrix whose $ij$$ij$th entry is:

$$\begin{array}{}\text{(14)}& \frac{{\partial }^{2}f}{\partial x_i\partial x_j}\end{array}$$

We let $H(x_1,x_2,..x_n)$$H(x_1,x_2,..x_n)$ denote the value of the Hessian at $(x_1,x_2,,,,x_n)$$(x_1,x_2,,,,x_n)$. For example, if

then:

And we have:

Principle Minor Calculation

An $i$$i$th principal minor of an $m\times n$$m\times n$ matrix is the determinant of any $i\times i$$i \times i$ matrix obtained by deleting $n-i$$n-i$ rows and the corresponding $n-i$$n-i$ columns of the matrix.

Thus, for the matrix

The first principle minors are $P{M}_1^1=-2$$PM^1_1=-2$ and $P{M}_2^1=-4$$PM^1_2=-4$,

and the second principle monor $P{M}^2$$PM^2$ is:

For any matrix, the first principal minors are just the diagonal entries ofthe matrix.

$k$$k$th leading principle minor

The kth leading principle minor of an $n\times n$$n \times n$ matrix is the determinant of the $k\times k$$k \times k$ matrix obtained by deleting the last $n-k$$n-k$ rows and columns of the matrix.

We let $H_k(x_1,x_2,...x_n)$$H_k(x_1,x_2,...x_n)$ be the $k$$k$th leading principle minor of the Hessian matrix evaluated at the point $(x_1,x_2,,,x_n)$$(x_1,x_2,,,x_n)$ . Thus, if $f(x_1,x_2)=x_1^3+2x_1{x}_2+x_2^2$$f(x_1,x_2) = x_1^3 + 2x_1x_2 + x_2^2$, then, $H_1(x_1,x_2)=6x_1$$H_1(x_1,x_2) = 6x_1$,$H_2(x_1,x_2)=6x_1(2)-2(2)=12x_1-4$$H_2(x_1,x_2)=6x_1(2)-2(2) = 12x_1 -4$

Using principle minors to check Convexity and Concavity

Suppose $f(x_1,x_2,....x_n)$$f(x_1,x_2,....x_n)$ has continous second-order partial derivatives for each point $x=x(x_1,x_2,,,,x_n)\in S$$x=x(x_1,x_2,,,,x_n) \in S$. Then,

$f(x_1,x_2,...x_n)$$f(x_1,x_2,...x_n)$ is a convex function on S iff (if and only if) for each $x\in S$$x\in S$, all principal monors of H are non-negative ($\ge 0$$\ge 0$)

$f(x_1,x_2,..x_n)$$f(x_1,x_2,..x_n)$ is a concave function on S iff for each $x\in S$$x \in S$ and $k=1,2,...n$$k=1,2,...n$ all nonzero principal minors have the same sign as $(-1{)}^k$$(-1)^k$

($\text{or:}(P{M}_k)(-1{)}^k>0$$\text{or:} (PM_k)(-1)^k > 0$)

Expl. $f(x_1,x_2)=x_1^2+2x_1{x}_2+x^2$$f(x_1,x_2)=x_1^2 + 2x_1x_2 + x^2$ is a convex function on $S=R^2$$S=R^2$ .

The first principal minors (2 >=0 ), and the second principal minor is 4-4=0 >=0 .

So this is a convex function.

Expl. $f(x_1,x_2)=-x_1^2-x_1{x}_2-2x_2^2$$f(x_1,x_2)=-x_1^2 - x_1x_2 - 2x_2^2$ .

first order principal minors (-2, -4) are negative. so as $(-1{)}^1$$(-1)^1$ .

second order principal minor (7) is positive.

So, the function is a concave function.

Expl. $f(x_1,x_2)=x_1^2-3x_1{x}_2+2x_2^2$$f(x_1,x_2)= x_1^2 - 3x_1x_2 + 2x_2^2$

First order principal minors are positive (2,4)

Second PM = (8-9=-1) < 0. $(-1{)}^2$$(-1)^2$ > 0.

So this function is neither convex nor concave function.

Practice1: Check convexity or concavity for

(63420)

Practice2:

(Nota5200)

Inflaction Point, Saddle Point

For a single variable function, $x_{\ast }$$x_*$ is a inflaction point, if function’s second derivative $f^{″}(x_{\ast })$$f''(x_*)$ changes sign.

Such point is called saddle point in multi-dimensional function.

[End of 1207]