FE501 – 1130 Non-Linear Programming

Prerequisites (Statistical Content)

Random Variables and How to Describe Random Variables

Note: Moved to Here

Nonlinear Programming

For an LP, our goal was to maximize or minimize a linear function subject to a linear constraints. But in many interesting maximization and minimization problems, the objective function may not be a linear function or some of the constraints may not be linear constraints. Such an optimization problem is called a nonlinear programming problem (NLP).

NLP: (Either one or both of below satisfies)

• Objective function is nonlinear
• Any of the constraints is nonlinear

A general nonlinear programming problem (NLP) can be expressed as follows:

An NLP with no constraints is an unconstrained NLP

Notes:

Quadratic Programming

Quadratic Programming and Portfolio Selection

An investor who has fixed amount of money, wants to maximize the expected return (portfolio), while simultaneously ensuring that the risk is small (as measured by the variance).

General Problem Types:

1. Maximize expected return with respect to a limited variance.
2. Minimize portfolio risk (variance) with respect to a considerable expected return.

Portfolio Optimization Problem (680)

Example 1. Variance Minimization

Problem description: Total amount to invest 1000$ . Let $S_i$$S_i$ be the random variable representing the annual return on $1 invested in stock $i$$i$. We are given the following formations:

$E(S_1)=0.14$$E(S_1)=0.14$

$E(S_2)=0.11$$E(S_2)=0.11$

$E(S_3)=0.10$$E(S_3)=0.10$

$var{S}_1=0.20$$var \quad S_1=0.20$

$var{S}_2=0.08$$var \quad S_2=0.08$

$var{S}_3=0.18$$var \quad S_3=0.18$

$cov(S1,S_2)=0.05$$cov\ (S1,S_2)=0.05$

$cov(S1,S_3)=0.02$$cov\ (S1,S_3)=0.02$

$cov(S2,S_3)=0.03$$cov\ (S2,S_3)=0.03$

Question: Formulate a QPP that can be used to find the portfolio that attins an expected annual return of at least 12% and minimizes the variance of the annual dollar return on the portfolio.

Decision Variables:

Let $x_i$$x_i$ the amount of money that invested in $ith$$i\ th$ stock. Then the annual return can be calculated as:

Objective Function:

(to minimize the variance)

And also we have:

So that we have:

Formulating the QPP

Generalizing QPP Portfolio Optimization Problems

Generally there are two types of Portfolio Optimization problems in QP.

Either in the form of:

2. $$\begin{array}{}\text{(4)}& \end{array}$$

Profit Maximization Problem

It costs a company $c$$c$ dollars per unit to manufacture a product. Comsuper price for the product is $p$$p$ , customers demand is $D(p)$$D(p)$. Formulate an Optimization method to maximize the profit of the company so that a fair price of $p$$p$ can be determined.

Production Maximization

If K units of Capital and L units of Labor used, a company can produce KL units of product. Capital can be purchased at $ 4 / unit and labor at $ 1 / unit. A total of $ 8 is available to purchase capital and labor. Formulate an Optimization problem to maximize the quantity of the product that can be manufactored.

Decision variables:

The quantity of product = KL for given K and L.

The total cost = 4K + 1 L

So that we have:

Notes:

Three curves above are the isoprofit curve when z=1,z=2 and z=4. Colored region is the feasible region. The optimal solution to the problem is (1,4) occures where an isoprofit curve is tangent to the boundary of the feasible region.

Tangent of $x\cdot y$$x \cdot y$ at point B(1,4) is the line $4x+y=8$$4x+y=8$

Example 1

by definition this is a quadratic nonlinear problem

It is nonlinear cause the objective function is nonlinear, it is quadratic because the degree of x,y is 2.

Analysis:

We can also find the solution by drawing the isoprofit curve for z:

so the $(x^{\ast },y^{\ast })=(1,2)$$(x^*,y^*)=(1,2)$

Which is the optimal solution for the problem.

In Linear programming, the optimal solutions occur at the cornor points, however, on NLP, the optimal solutions can occur anywhere.

NLPs with only one decision variables

min $x^2$$x^2$

$x^{\ast }=0$$x^* = 0$

max $x^2$$x^2$

cause when $x\to +\mathrm{\infty }$$x \rightarrow +\infin$ we have $x^2\to +\mathrm{\infty }$$x^2 \rightarrow +\infin$ , so the problem is unbounded.

Types of NLPs

• Unconstrained:

  1. Singel var:

2. Multiple variable:

• Constrained:

Local Minimum(Maximum) (or local extremum) vs Optimal Minimum(Maximum)

Suppose that we want to minimize the f(x) drawn above.

for point $x_1$$x_1$ we have the following:

So that, we can conclude that $x_1$$x_1$ is a local minimum.

Similarly, $x_2$$x_2$ is also a local minimum.

But unfortunately none of local minimum points $x_1$$x_1$ or $x_2$$x_2$ is the global minimum ($x^{\ast }=a$$x^* = a$).

for gloabl minimum ($x^{\ast }$$x^*$) we have:

Convexity and Concavity

Facts:

1. For a convex function, a local minimum is always global minimum.
2. For a concave function, a local maximum is always a global maximum.
3. For a function neither convex nor concave, a local point may not be a global point.

solutions: gradient accent, gradient decent, section serach , newtons method are the numerical technicchs to find optional points.

Converting a NLP to LP

Suppose we have aproblem defined as following:

This is a Mixed Interger Nonlinear Programming Problems.

To solve this problem, we try to convert this to a LP:

for the values of u, x, y:

Let’s define a big positve number: $M$$M$ :

so that we can introduce new constraints as:

Suppose:

So that the original problem becomes:

In general if we have 1 binary and at maximum 1 continous variabls, it is possible to convert the problem to a LP.

Example:

Suppose in the previous problem y also is a binary variable:

Then we can change it to:

[End of 11.30]

References