Chapter 5 Constrained Optimization



Chapter 5 Constrained OptimizationSafarzadehTable of ContentsTOC \o "1-2" \h \z \uCONSTRAINED OPTIMIZATION PAGEREF _Toc30328638 \h 1Lagrangian Function and Equality Constraints: PAGEREF _Toc30328639 \h 1Application in Finance PAGEREF _Toc30328640 \h 5Economic Interpretation of the Lagrangian Multiplier: PAGEREF _Toc30328641 \h 9Appendix: Concavity and Convexity of Functions PAGEREF _Toc30328642 \h 10CONSTRAINED OPTIMIZATIONThe optimizing problems of finance, business and economics are generally of a constrained nature. This is because every economic unit faces some constraints in optimizing objective. For example, a portfolio manager allocating funds among different assets may set the objective as minimizing risk of the portfolio subject to earning a return that is higher than return to risk free assets. Every consumer is constrained in buying goods and services by his/her budget or income constraint, and every producer faces cost or input constraints.Chapter 4 was concerned with the optimizing rules for functions with no constraints or restrictions attached. In such cases, the relative maximum or the relative minimum is the optimum solution. This chapter is concerned with the optimum solution of problems in which a function, called the objective function, is optimized subject to one or more constraints. With a constraint imposed on the variables, the solution of the constrained optimizing problem may differ from the unconstrained problem, even if the objective functions are the same.The problem of finding a constrained optimum in calculus assumes that the constraints hold with equality. The more general problem of maximizing or minimizing an objective function subject to inequality constraints is called mathematical programming. In both cases, however, the method of Lagrangian function can be used to solve constrained optimization problems.Lagrangian Function and Equality Constraints:Consider the following constrained maximization problem as an example of simple production function:Maximize: Q=90N-2N2Subject to: N≤20where the first equation is the objective function and the second inequality is the constraint. The problem is to maximize the output (Q) subject to the constraint that the business can not have more than 20 units of labor (N). To solve the constrained optimizing problem, we form the Lagrangianfunction. The Lagrangian function is formed by augmenting the constraint together with the Lagrange multiplier λ to the objective function.L = 90N-2N2 + λ(20-N)If the constraint is satisfied, no matter what value λ has, the second term in the right side of the Lagrangian equation will vanish and L = 90N-2N2. That is, maximizing L with respect to N is the same as maximizing Q, and achieving the objective. Therefore, the trick in solving a constrained optimizing problem is to incorporate the constraint into the problem and insure that the constraint is satisfied with equality.This is done by treating λ as an additional variable and assuming L is a function of N and λ. That is,L(N,λ) = 90N-2N2 + λ(20-N). Differentiating L with respect to N and λ results in the following two equations which have been set equal to zero to find the values of N and λ.LN = 90 - 4N - λ = 0 Lλ = 20-N = 0The solution to the second equation is N=20. By substituting the value of N in the first equation we have λ = 10. Note that, in this problem λ > 0. If λ > 0, the constraints is binding and the solution to the constrained optimization problem with the values N=20 and Q=1000 is final. If λ < 0, then the constraint is non-binding and it should not be considered in the solution to the problem. That is, the problem should be solved as unsonstrained optimization of maximizing Q=90-2N2 with N=22.5 and Q=1012.5. The following graph represents the distinction between binding and non-binding constraints.f <- function(N) 90*N - 2*N^2plot(f, 0, 40, ylab="Q", xlab="N", main="Binding and Non-Binding Constraints", col="black"); abline(v=20, col="green"); abline(v=30, col="red")points(22.5, f(22.5)); points(20, f(20)); points(30, f(30))From the graph of the production function, since N≤20 the producer can not achieve the maximum Q that happens at N=22.5 with a Q=1012.5. However, if the constraint were N≤30, the maximum Q would still be 1012.5 units with 10 units of labor redundant or going slack.Do More Practice: 1- Change the constraint in the problem above from 20 to 30, N≤30. Solve the problem to find the value of λ. What is the sign of λ? Why? 2- Change the constraint in the problem above from 20 to 22.5, N≤22.5. Solve the problem to find the value of λ. What is the sign of λ? Why?Example: For the function y=2500-20x+.05x2, minimize y subject to the constraint y≥180. The problem can be formulated as:Minimize: y=2500-20x+.05x2 Subject to: x≥180Form the Lagrangianfunction, (L) as:L=2500-20x+.05x2 +λ(180 - x)Differentiating L with respect to x and λ and setting them equal to zero results in: Lx = -20 +.10x - λ = 0 Lλ = 180-x = 0the solution to the two equations are x=200, λ=-2 and y=520. Since λ < 0, the problem should be solved as unconstrained optimization problem:y'=-20+.10x=0, or y=200 and y=500. The following grpah shows why the constarint should be dropped and the objective function should be optimized with no constraint.f <- function(x) 2500 - 20*x + .05*x^2 plot(f, 150, 250, ylab="Y", xlab="X", main="Binding and Non-Binding Constraints", col="black"); abline(v=180, col="red"); abline(v=200, col="green")points(180, f(180)); points(200, f(200))Example: Consumer Theory Maximize: U = U(X, Y)Subject to: PxX + PyY = Mwhere the first equation is the objective function in which U(X,Y) is the utility function, assumed to be differentiable, and PxX+PyY=M is the budget constraint. The problem is to maximize the utility subject to the budget constraint. To solve the constrained optimizing problem, we form the Lagrangian function.The Lagrangian function is formed by augmenting the constraint together with the Lagrange multiplier λ to the objective function.L = U(X,Y) + λ(M-PxX-PyY)If the constraint is satisfied, no matter what value λ has, the second term in the right side of the Lagrangian equation will vanish and L=U(X,Y). That is, maximizing L with respect to X and Y is the same as maximizing U(X,Y). Therefore, the trick in solving a constrained optimizing problem is to incorporate the constraint into the problem and insure that the constraint is satisfied with equality. This is done by treating λ as an additional variable and assuming L is a function of X, Y, and λ. That is, L(X,Y,λ) = U(X,Y) + λ(M-PxX-PyY)This function may be maximized with respect to the three unknown variables X, Y, and λ. The first order conditions are:Lx =Ux - λ*Px = 0Ly =Uy - λ*Py = 0Lλ =M-PxX-PyY = 0A point P(X*,Y*,λ*) that satisfies the three equations of the first-order condition is the extremum.Application in FinanceExample: An investor is allocating funds between to assets 1 and 2. The invetor is a risk averse investor, trying to minimize the variance of her portfolio. The variance-covariance of the two assets are σ12=.002, σ22=.002, and σ12=.002. Find the weights assigned to each asset in the portfolio and the minimum-variance.library('rootSolve')# The Vriance Function of the Portfolio is formulated as: f <- function(w) .002*w^2 + .003*(1-w)^2 - 2*w*(1-w)*.0004# To minimize the variance, differentiate f and solve it for its zeroes. F <- function(w) {}body(F) <- D (body(f), 'w')root <- multiroot(F, 0, maxiter = 1000)root$root # Minimum Varince Weight for asset 1.## [1] 0.5862069w2 <- 1 - root$root # Minimum Varince Weight for asset 2.w2## [1] 0.4137931f(root$root) # The Minimum variance## [1] 0.001006897# Plot of the variance function with respect to w.w <- seq(0, 1, .05)plot (f, w, xlab="W", ylab="Portfolio Variance", main="Minimum Variance Portfolio"); abline(v = root$root, col = "red")points(root$root, f(root$root), col='green')Example: An investor is allocating funds between to assets 1 and 2. The average monthly returns to assets 1 and 2 are 2.3% and 1.1%. The average monthly return to risk-free asset is .2%. The variance-covariance of the two assets are σ12=.0072, σ22=.0049, and σ12=.0023. Graph the efficient frontier and the capital allocation line. Find the global minimum-variance combination of the two assets.Solutio: The global minimum varinace the solution to unconstrained minimizing problem of minimizing the variance of the return to portfolio:# The Vriance Function of the Portfolio is formulated as: w1 <- seq(-.5, 1.5, .005)w2 <- 1-w1f <- function(w1, w2) .0072*w1^2 + .0049*w2^2 + 2*w1*w2*.0023r <- function(w1, w2) .023*w1 + .011*w2Risk <- sqrt(f(w1, w2))Return <- r(w1, w2)plot(Risk, Return, type='l', main='Global Minimum Variance')wp <- (.0049-.0023)/(.0072+.0049-2*.0023)Rp <- .023*wp + .011*(1 - wp)sigma <- sqrt(f(wp, (1-wp)))Rf <- .002Sharpe <- (Rp-Rf)/sigmaX <- seq(0, 1, .01)Y <- Rf + Sharpe*Xlines(X, Y)points(sigma, Rp, col='green')Example: An investor is allocating funds between to assets 1 and 2. The average monthly returns to assets 1 and 2 are .00669538 and .01106344. The average monthly return to risk-free asset is .00192717%. The variance-covariance of the two assets are σ12=.00297109, σ22=.00589258, and σ12=.00053632. The objective of the investor is to minimize the risk of the portfolio subject to a portfolio return higher than the return to risk free asset. Graph the efficient frontier and the capital allocation line. Find the tangency point solution to the fund allocation problem.#AAPL - WMT w1 <- seq(0 , 1, .005)w2 <- 1-w1# The Vriance and return Functions of the Portfolio is formulated as: f <- function(w1, w2) .00297109*w1^2 + .00589258*w2^2 + 2*w1*w2*.00053632r <- function(w1, w2) .00669538*w1 + .01106344*w2Risk <- sqrt(f(w1, w2))Return <- r(w1, w2)plot(Risk, Return, type='l', main='Tangency Point solution')#Finding the weights for each asset:w1 <- (.00589258*.00476821-.00053632*.00913627)/(.00297109+.00589258 -2*.00053632)w2 <- (.00297109*.00913627-.00053632*.00476821)/(.00297109+.00589258 -2*.00053632)#Normalizing the weights to add up to onewp <- w1/(w1+w2)#Finding the return and the risk to the tangency point portfolioRp <- .00669538*wp + .01106344*(1 - wp)Rp## [1] 0.008942955sigma <- sqrt(f(wp, (1-wp)))sigma## [1] 0.05028148Rf <- .00192717#Finding the Sharpe RatioSharpe <- (Rp-Rf)/sigma#Graphing the Capital Allocation LineX <- seq(0 , 1, .005)Y <- Rf + Sharpe*Xlines(X, Y)points(sigma, Rp, col='green')Economic Interpretation of the Lagrangian Multiplier:The Lagrange multiplier can be thought of as the rate of change of the objective variable with respect to the constraint. That is, it shows the marginal valuation, or the implicit price of the constraint. For example, in a utility maximizing problem subject to the budget constraint the objective variable is U and the constraint is M (Money or budget.) Therefore, λ=dUdM, which is the marginal utility of money (marginal valuation of money) or the implicit price of money for the consumer.For a utility maximizing problem, the first order conditions Ux=λPx, or λ=UxPx, and Uy=λPy, or λ=UyPy, imply that consumer is in equilibrium if the marginal utility received from spending one dollar on X or Y is equal to the marginal utility of that one dollar for the consumer. If the budget constraint is binding, i.e., if the consumer spends all of her money on X and Y, then λ is positive (λ>0), which implies that money has a positive marginal utility or implicit price for the consumer. In this case, the optimum solution will be somewhere on the budget constraint.If the budget constraint is non-binding, i.e.?the consumer’s budget is not a factor in her buying decision, then λ=0, which means that the consumer has so much money that the marginal valuation of money or the implicit price of money is zero for the consumer. In this case, the solution will be the same as the unconstrained maximization. That is, the consumer buys those quantities of X and Y which satiates the consumer.In general, if a resource is limited and its constraint is binding, that resource will have a positive implicit price, (λ>0). On the contrary, if a resource is abundant and its constraint is non-binding, then the implicit price of the resource will be zero, (λ>0).To prove that λ=dudM, totally differentiate the objective function U=U(x,y) and the constraint M=PxX+PyY to get dU=Uxdx+Uydy and dM=Pxdx+Pydy. Divide both sides of the two equations together to get dUdM=Uxdx+UydyPxX+PyY. Substitute for Ux and Uy from the first order condition, where Ux=λPx and Uy=λPy, to get dUdM=λPxdx+λPydyλPxdX+λPydY=λ.Example: For a constrained cost minimizing problem prove that the Lagrangian multiplier λ is the marginal cost of production.Solution: A cost minimizing problem can be formulated as Minimize C=wL+rK subject to Q(L,K)=Q0, where L and K are labor and capital inputs, w and r are wages and rental cost of capital and Q is the output. Marginal cost is defined as cost of additional unit of output ordCdQ. Totally differentiate the objective function and the constraint to get dC=wdL+rdK and dQ=QLdL+QKdK . Divide the two equations together and substitute for w and r from the first order condition (w=λQL and r=λQK), dCdQ=λQLdL+λQKdKQLdL+QKdK.Therefore, λ is the marginal cost of productiondCdQ=λ.Problem: 1. A consumer has a hypothetical utility function U=lnxy, where x and y are quantities of two goods sold at market prices of 2 dollars and 3 dollars, respectively. Given that consumer has an income of $60:Set up the mathematical programming problem of maximizing consumer’s utility subject to his budget constraint.Find the optimum levels of x and y.Test for the second order condition.Suppose that the objective of the consumer in problem 1 is to minimize expenditures subject to a fixed level of utility, Uo=150. Given that market prices are the same as in problem 1,set up the proper optimizing problem.find the optimum levels of x and y.test the second order conditions.Appendix: Concavity and Convexity of FunctionsA function f(x) is said to be convex over the interval(x1,x2) if for the two points x1 and x2 and for all, 0 < α < 1,f[αx2+(1-α)x1≤αf(x2)+(1-α)f(x1)]A function f(x) is said to be concave if -f(x) is convex. A function f(x) is said to be strictly convex if the equation above is a strict inequality.Graphically, a function f(x) is convex if a line segment joining any two points [x1,f(x1)], [x2,f(x2)], of f(x) lies on or above the surface of f(x) (see the graph below.)An easier way to show that a function is convex is to use the second order derivative of the function, if the function is twice differentiable. A univariate continuous function f(x) is convex in the neighborhood of x0 if and only if f″(x)>0. A multivariable continuous function f(x1,....,xn) is convex if and only if the Hessian determinant of f is positive definite.ExampleProve that y=f(x)=2x2+x+3 is a convex function.Solution: f'(x)=4x+1 and $f "(x) = 4$. Since $f "(x) > 0$, the function is convex over the entire real number. The graph of the function is shown below.library(rootSolve)f <- function(x) (2*x^2+x+3)F1 <- function(x) {}body(F1) <- D (body(f), 'x')body (F1) ## 2 * (2 * x) + 1F2 <- function(x) {}body(F2) <- D(body (F1), 'x')body (F2) # 4>0## 2 * 2#curve(f,-1000,1000) also works library(ggplot2)sigmoid <- function(x) (2*x^2+x+3)x<-seq(-1.5,1.5, by=0.01)y<-sigmoid(x)df<-data.frame(x, y)g <- ggplot(df, aes(x,y))g <- g + geom_line(col='red')g <- g + geom_hline(yintercept = 0.5) + geom_vline(xintercept = 0) + xlim(-2,2)+ylim(-3,6)g <- g + ggtitle("2x^2+x+3")g## Warning: Removed 50 rows containing missing values (geom_path).ExampleDiscuss the concavity or convexity of y=f(x)=x3-3x2+x+5. Solution: f'(x)=3x2-6x+1 and $f "(x) = 6x - 6. f "(x) = -6 + 6x$ is positive for all the values of x>1 and is negative for all the values of x<1. Therefore, f(x) will be convex for x>1 and concave for x<1. The graph of the function is shown below.library(rootSolve)f <- function(x) (x^3 - 3*x^2 + x + 5)F1 <- function(x) {}body(F1) <- D (body(f), 'x')body (F1) ## 3 * x^2 - 3 * (2 * x) + 1F2 <- function(x) {}body(F2) <- D(body (F1), 'x')body (F2)## 3 * (2 * x) - 3 * 2#curve(f,-1000,1000) also works library(ggplot2)sigmoid <- function(x) (x^3 - 3*x^2 + x + 5)y<-sigmoid(x)df<-data.frame(x, y)g <- ggplot(df, aes(x,y))g <- g + geom_line(col='red')g <- g + geom_hline(yintercept = 0.5) + geom_vline(xintercept = 0) + xlim(-3,3)+ylim(-3,8)g <- g + ggtitle("x^3 - 3*x^2 + x + 5")g## Warning: Removed 25 rows containing missing values (geom_path).ExampleDiscuss the convexity or concavity of the z=f(x,y)=2x2+y2. Solution: The partial derivative of z with respect to x and y are?z?x=4x and ?z?y=2y, respectively. The second derivatives results in the quadratic form the Hessian matrix of which isH=4002Since the determinants of the principal minors of H are all positive, H is positive definite and f(x,y) is convex over the entire Euclidean E2 space. The graph of the function is presented below.library(rootSolve)f <- function(x) (2*x^2 + y^2)F1 <- function(x) {}body(F1) <- D (body(f), 'x')body (F1)## 2 * (2 * x)F2 <- function(x) {}body(F2) <- D(body (F1), 'y')body (F2)## [1] 0g2 <- function(x1, x2){(2*x1^2 + x2^2)}x1 <- seq(-5,5)x2 <- seq(-5,5)z<- outer(x1,x2,g2) persp(x1, x2,z, main="2*x^2 + y^2", col="lightblue", theta=30, phi=20, r=40, d=0.1, expand=0.5,ltheta=80, lphi=30, shade=0.75, ticktype="detailed", nticks=5) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download