{
"cells": [
{
"cell_type": "markdown",
"id": "5adde2e4",
"metadata": {},
"source": [
"# Optimization\n",
"\n",
"**Prerequisites**\n",
"\n",
"- [Introduction to Numpy](https://datascience.quantecon.org/numpy_arrays.html) \n",
"- [Applied Linear Algebra](https://datascience.quantecon.org/applied_linalg.html) \n",
"\n",
"\n",
"**Outcomes**\n",
"\n",
"- Perform optimization by hand using derivatives \n",
"- Understand ideas from gradient descent "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5ac6039f",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Uncomment following line to install on colab\n",
"#! pip install "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "caa0acdd",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# imports for later\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"id": "4964d3ad",
"metadata": {},
"source": [
"## What is Optimization?\n",
"\n",
"Optimization is the branch of mathematics focused on finding extreme values (max or min) of\n",
"functions.\n",
"\n",
"Optimization tools will appear in many places throughout this course, including:\n",
"\n",
"- Building economic models in which individuals make decisions that maximize their utility. \n",
"- Building statistical models and maximizing the fit of these models by optimizing certain fit\n",
" functions. \n",
"\n",
"\n",
"In this lecture, we will focus mostly on the first to limit the moving pieces, but in other lectures, we’ll discuss the second in detail."
]
},
{
"cell_type": "markdown",
"id": "c6e96464",
"metadata": {},
"source": [
"### Derivatives and Optima\n",
"\n",
"Here, we revisit some of the theory that you have already learned in your calculus class.\n",
"\n",
"Consider function $ f(x) $ which maps a number into another number. We can say that any point\n",
"where $ f'(x) = 0 $ is a local extremum of $ f $.\n",
"\n",
"Let’s work through an example. Consider the function\n",
"\n",
"$$\n",
"f(x) = x^4 - 3 x^2\n",
"$$\n",
"\n",
"Its derivative is given by\n",
"\n",
"$$\n",
"\\frac{\\partial f}{\\partial x} = 4 x^3 - 6 x\n",
"$$\n",
"\n",
"Let’s plot the function and its derivative to pick out the local extremum by hand."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c0650e1a",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def f(x):\n",
" return x**4 - 3*x**2\n",
"\n",
"\n",
"def fp(x):\n",
" return 4*x**3 - 6*x\n",
"\n",
"# Create 100 evenly spaced points between -2 and 2\n",
"x = np.linspace(-2., 2., 100)\n",
"\n",
"# Evaluate the functions at x values\n",
"fx = f(x)\n",
"fpx = fp(x)\n",
"\n",
"# Create plot\n",
"fig, ax = plt.subplots(1, 2)\n",
"\n",
"ax[0].plot(x, fx)\n",
"ax[0].set_title(\"Function\")\n",
"\n",
"ax[1].plot(x, fpx)\n",
"ax[1].hlines(0.0, -2.5, 2.5, color=\"k\", linestyle=\"--\")\n",
"ax[1].set_title(\"Derivative\")\n",
"\n",
"for _ax in ax:\n",
" _ax.spines[\"right\"].set_visible(False)\n",
" _ax.spines[\"top\"].set_visible(False)"
]
},
{
"cell_type": "markdown",
"id": "121fb34c",
"metadata": {},
"source": [
"If you stare at this picture, you can probably determine the the local maximum is at\n",
"$ x = 0 $ and the local minima at $ x \\approx -1 $ and $ x \\approx 1 $.\n",
"\n",
"To properly determine the minima and maxima, we find the solutions to $ f'(x) = 0 $ below:\n",
"\n",
"$$\n",
"f'(x) = 4 x^3 - 6 x = 0\n",
"$$\n",
"\n",
"$$\n",
"\\rightarrow x = \\left\\{0, \\frac{\\sqrt{6}}{2}, \\frac{-\\sqrt{6}}{2} \\right\\}\n",
"$$\n",
"\n",
"Let’s check whether we can get the same answers with Python! To do this, we import a new\n",
"package that we haven’t seen yet."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9385444b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import scipy.optimize as opt"
]
},
{
"cell_type": "markdown",
"id": "42f22f2a",
"metadata": {},
"source": [
"Then using the function definitions from earlier, we search for the minimum and maximum values."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f4e8e51e",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# For a scalar problem, we give it the function and the bounds between\n",
"# which we want to search\n",
"neg_min = opt.minimize_scalar(f, [-2, -0.5])\n",
"pos_min = opt.minimize_scalar(f, [0.5, 2.0])\n",
"print(\"The negative minimum is: \\n\", neg_min)\n",
"print(\"The positive minimum is: \\n\", pos_min)"
]
},
{
"cell_type": "markdown",
"id": "1c0f680f",
"metadata": {},
"source": [
"The scipy optimize package only has functions that find minimums… You might be wondering, then, how we\n",
"will verify our maximum value.\n",
"\n",
"It turns out that finding the maximum is equivalent to simply finding the minimum of the negative function."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "667c8560",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Create a function that evaluates to negative f\n",
"def neg_f(x):\n",
" return -f(x)\n",
"\n",
"max_out = opt.minimize_scalar(neg_f, [-0.35, 0.35])\n",
"print(\"The maximum is: \\n\", max_out)"
]
},
{
"cell_type": "markdown",
"id": "83c3ce63",
"metadata": {},
"source": [
"We won’t dive into the details of optimization algorithms in this lecture, but we’ll impart some brief\n",
"intuition to help you understand the types of problems these algorithms are good at solving and\n",
"the types of problems they will struggle with:\n",
"\n",
"The general intuition is that when you’re finding a maximum, an algorithm takes a step\n",
"in the direction of the derivative… (Conversely, to find a minimum, the algorithm takes a step opposite the direction of the derivative.)\n",
"This requires the function to be relatively smooth and continuous. The algorithm also has an easier time if there is only one (or very few) extremum to be found…\n",
"\n",
"For minimization, you can imagine the algorithm as a marble in a bowl.\n",
"\n",
"The marble will keep rolling down the slope of the bowl until it finds the bottom.\n",
"\n",
"It may overshoot, but once it hits the slope on the other side, it will continue to roll back\n",
"and forth until it comes to rest.\n",
"\n",
"Thus, when deciding whether numerical optimization is an effective method for a\n",
"particular problem, you could try visualizing the function to determine whether a marble\n",
"would be able to come to rest at the extreme values you are looking for."
]
},
{
"cell_type": "markdown",
"id": "6eac2037",
"metadata": {},
"source": [
"### Application: Consumer Theory\n",
"\n",
"A common use of maximization in economics is to model\n",
"optimal consumption decisions [https://en.wikipedia.org/wiki/Consumer_choice](https://en.wikipedia.org/wiki/Consumer_choice)."
]
},
{
"cell_type": "markdown",
"id": "078ee65b",
"metadata": {},
"source": [
"#### Preferences and Utility Functions\n",
"\n",
"To summarize introductory economics, take a set of\n",
"[preferences](https://en.wikipedia.org/wiki/Preference_%28economics%29) of consumers over “bundles”\n",
"of goods (e.g. 2 apples and 3 oranges is preferred to 3 apples and 2 oranges, or a 100% chance to\n",
"win $ 1 $ dollar is preferred to a 50% chance to win $ 2.10 $ dollars).\n",
"\n",
"Under certain assumptions, you rationalize the preferences as a utility function over the different\n",
"goods (always remembering that the utility is simply a tool to order preferences and the numbers are\n",
"usually not meaningful themselves).\n",
"\n",
"For example, consider a utility function over bundles of bananas (B) and apples (A)\n",
"\n",
"$$\n",
"U(B, A) = B^{\\alpha}A^{1-\\alpha}\n",
"$$\n",
"\n",
"Where $ \\alpha \\in [0,1] $.\n",
"\n",
"First, let’s take a look at this particular utility function."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c33392dd",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def U(A, B, alpha=1/3):\n",
" return B**alpha * A**(1-alpha)\n",
"\n",
"fig, ax = plt.subplots()\n",
"B = 1.5\n",
"A = np.linspace(1, 10, 100)\n",
"ax.plot(A, U(A, B))\n",
"ax.set_xlabel(\"A\")\n",
"ax.set_ylabel(\"U(B=1.5, A)\")"
]
},
{
"cell_type": "markdown",
"id": "c0de350f",
"metadata": {},
"source": [
"We note that\n",
"\n",
"- $ U(B,1) $ is always higher with more B, hence, consuming more bananas has a\n",
" : positive marginal utility i.e. $ \\frac{d U(B,1)}{d B} > 0 $. \n",
"- The more bananas we consume, the smaller the change in marginal utility, i.e.\n",
" $ \\frac{d^2 U(B,1)}{d B^2} < 0 $. \n",
"\n",
"\n",
"If we plot both the $ B $ and the $ A $, we can see how the utility changes with different\n",
"bundles."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "624c829c",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"B = np.linspace(1, 20, 100).reshape((100, 1))\n",
"contours = ax.contourf(A, B.flatten(), U(A, B))\n",
"fig.colorbar(contours)\n",
"ax.set_xlabel(\"A\")\n",
"ax.set_ylabel(\"B\")\n",
"ax.set_title(\"U(A,B)\")"
]
},
{
"cell_type": "markdown",
"id": "d9a8d2ac",
"metadata": {},
"source": [
"We can find the bundles between which the consumer would be indifferent by fixing a\n",
"utility $ \\bar{U} $ and by determining all combinations of $ A $ and $ B $ where\n",
"$ \\bar{U} = U(B, A) $.\n",
"\n",
"In this example, we can implement this calculation by letting $ B $ be the variable on the\n",
"x-axis and solving for $ A(\\bar{U}, B) $\n",
"\n",
"$$\n",
"A(B, \\bar{U}) = U^{\\frac{1}{1-\\alpha}}B^{\\frac{-\\alpha}{1-\\alpha}}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8757bfa8",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def A_indifference(B, ubar, alpha=1/3):\n",
" return ubar**(1/(1-alpha)) * B**(-alpha/(1-alpha))\n",
"\n",
"def plot_indifference_curves(ax, alpha=1/3):\n",
" ubar = np.arange(1, 11, 2)\n",
" ax.plot(B, A_indifference(B, ubar, alpha))\n",
" ax.legend([r\"$\\bar{U}$\" + \" = {}\".format(i) for i in ubar])\n",
" ax.set_xlabel(\"B\")\n",
" ax.set_ylabel(r\"$A(B, \\bar{U}$)\")\n",
"\n",
"fig, ax = plt.subplots()\n",
"plot_indifference_curves(ax)"
]
},
{
"cell_type": "markdown",
"id": "f54cd766",
"metadata": {},
"source": [
"Note that in every case, if you increase either the number of apples or bananas (holding the other\n",
"fixed), you reach a higher indifference curve.\n",
"\n",
"Consequently, in a world without scarcity or budgets, consumers would consume\n",
"an arbitrarily high number of both to maximize their utility."
]
},
{
"cell_type": "markdown",
"id": "9fe2771b",
"metadata": {},
"source": [
"#### Budget Constraints\n",
"\n",
"While the above example plots consumer preferences, it says nothing about what the consumers can afford.\n",
"\n",
"The simplest sort of constraint is a budget constraint where bananas and apples both have a price\n",
"and the consumer has a limited amount of funds.\n",
"\n",
"If the prices per banana and per apple are identical, no matter how many you consume, then the\n",
"affordable bundles are simply all pairs of apples and bananas below the line.\n",
"$ p_a A + p_b B \\leq W $.\n",
"\n",
"For example, if consumer has a budget of $ W $, the price of apples is $ p_A = 2 $ dollars per\n",
"apple, and the price of bananas is normalized to be $ p_B = 1 $ dollar per banana, then the consumer\n",
"can afford anything below the line.\n",
"\n",
"$$\n",
"2 A + B \\leq W\n",
"$$\n",
"\n",
"Or, letting $ W = 20 $ and plotting"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "176b1fb7",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def A_bc(B, W=20, pa=2):\n",
" \"Given B, W, and pa return the max amount of A our consumer can afford\"\n",
" return (W - B) / pa\n",
"\n",
"def plot_budget_constraint(ax, W=20, pa=2):\n",
" B_bc = np.array([0, W])\n",
" A = A_bc(B_bc, W, pa)\n",
" ax.plot(B_bc, A)\n",
" ax.fill_between(B_bc, 0, A, alpha=0.2)\n",
" ax.set_xlabel(\"B\")\n",
" ax.set_ylabel(\"A\")\n",
" return ax\n",
"\n",
"fig, ax = plt.subplots()\n",
"plot_budget_constraint(ax, 20, 2)"
]
},
{
"cell_type": "markdown",
"id": "3cbe8c83",
"metadata": {},
"source": [
"While the consumer can afford any of the bundles in that area, most will not be optimal."
]
},
{
"cell_type": "markdown",
"id": "815d576b",
"metadata": {},
"source": [
"#### Optimal Choice\n",
"\n",
"Putting the budget constraints and the utility functions together lets us visualize the optimal\n",
"decision of a consumer. Choose the bundle with the highest possible indifference curve within its\n",
"budget set."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "feef4d30",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"plot_indifference_curves(ax)\n",
"plot_budget_constraint(ax)"
]
},
{
"cell_type": "markdown",
"id": "16e647c0",
"metadata": {},
"source": [
"We have several ways to find the particular point $ A, B $ of maximum utility, such as\n",
"finding the point where the indifference curve and the budget constraint have the same slope, but a\n",
"simple approach is to just solve the direct maximization problem.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\max_{A, B} & B^{\\alpha}A^{1-\\alpha}\\\\\n",
"\\text{s.t. } & p_A A + B \\leq W\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Solving this problem directly requires solving a multi-dimensional constrained optimization problem,\n",
"where scipy [https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html#constrained-minimization-of-multivariate-scalar-functions-minimize](https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html#constrained-minimization-of-multivariate-scalar-functions-minimize)\n",
"has several options.\n",
"\n",
"For this particular problem, we notice two things: (1) The utility function is increasing in both\n",
"$ A $ and $ B $, and (2) there are only 2 goods.\n",
"\n",
"This allows us 1) to assume that the budget constraint holds at equality, $ p_a A + B = W $, 2) to\n",
"form a new function $ A(B) = (W - B) / p_a $ by rearranging the budget constraint at equality, and\n",
"3) to substitute that function directly to form:\n",
"\n",
"$$\n",
"\\max_{B} B^{\\alpha}A(B)^{1-\\alpha}\n",
"$$\n",
"\n",
"Compared to before, this problem has been turned into an unconstrained univariate optimization\n",
"problem.\n",
"\n",
"To implement this in code, notice that the $ A(B) $ function is what we defined before\n",
"as `A_bc`.\n",
"\n",
"We will solve this by using the function `scipy.optimize.minimize_scalar`, which takes a function\n",
"`f(x)` and returns the value of `x` that minimizes `f`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bd6ad4e5",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"from scipy.optimize import minimize_scalar\n",
"\n",
"def objective(B, W=20, pa=2):\n",
" \"\"\"\n",
" Return value of -U for a given B, when we consume as much A as possible\n",
"\n",
" Note that we return -U because scipy wants to minimize functions,\n",
" and the value of B that minimizes -U will maximize U\n",
" \"\"\"\n",
" A = A_bc(B, W, pa)\n",
" return -U(A, B)\n",
"\n",
"result = minimize_scalar(objective)\n",
"optimal_B = result.x\n",
"optimal_A = A_bc(optimal_B, 20, 2)\n",
"optimal_U = U(optimal_A, optimal_B)\n",
"\n",
"print(\"The optimal U is \", optimal_U)\n",
"print(\"and was found at (A,B) =\", (optimal_A, optimal_B))"
]
},
{
"cell_type": "markdown",
"id": "00001e95",
"metadata": {},
"source": [
"This allows us to do experiments, such as examining how consumption patterns change as prices or\n",
"wealth levels change."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2255c0f4",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Create various prices\n",
"n_pa = 50\n",
"prices_A = np.linspace(0.5, 5.0, n_pa)\n",
"W = 20\n",
"\n",
"# Create lists to store the results of the optimal A and B calculation\n",
"optimal_As = []\n",
"optimal_Bs = []\n",
"for pa in prices_A:\n",
" result = minimize_scalar(objective, args=(W, pa))\n",
" opt_B_val = result.x\n",
"\n",
" optimal_Bs.append(opt_B_val)\n",
" optimal_As.append(A_bc(opt_B_val, W, pa))\n",
"\n",
"fig, ax = plt.subplots()\n",
"\n",
"ax.plot(prices_A, optimal_As, label=\"Purchased Apples\")\n",
"ax.plot(prices_A, optimal_Bs, label=\"Purchased Bananas\")\n",
"ax.set_xlabel(\"Price of Apples\")\n",
"ax.legend()"
]
},
{
"cell_type": "markdown",
"id": "7f7fb768",
"metadata": {},
"source": [
"#### Exercise\n",
"\n",
"See exercise 1 in the [exercise list](#ex3-5)."
]
},
{
"cell_type": "markdown",
"id": "c795e0b1",
"metadata": {},
"source": [
"#### Satiation Point\n",
"\n",
"The above example is a particular utility function where consumers prefer to “eat” as much as\n",
"possible of every good available, but that may not be the case for all preferences.\n",
"\n",
"When an optimum exists for the unconstrained problem (e.g. with an infinite budget), it is called a\n",
"bliss point, or satiation.\n",
"\n",
"Instead of bananas and apples, consider a utility function for potato chips (`P`) and chocolate\n",
"bars (`C`).\n",
"\n",
"$$\n",
"U(P, C) = -(P - 20)^2 - 2 * (C - 1)^2\n",
"$$\n",
"\n",
"To numerically calculate the maximum (which you can probably see through inspection), one must directly solve the constrained maximization problem."
]
},
{
"cell_type": "markdown",
"id": "07e8dcc3",
"metadata": {},
"source": [
"#### Exercise\n",
"\n",
"See exercise 2 in the [exercise list](#ex3-5).\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "2b043755",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "markdown",
"id": "23c2f1ef",
"metadata": {},
"source": [
"### Exercise 1\n",
"\n",
"Try solving the constrained maximization problem by hand via the Lagrangian method.\n",
"\n",
"Is it surprising that the demand for bananas is unaffected by the change in apple prices?\n",
"\n",
"Why might this be?\n",
"\n",
"([back to text](#dir3-5-1))"
]
},
{
"cell_type": "markdown",
"id": "204828da",
"metadata": {},
"source": [
"### Exercise 2\n",
"\n",
"Using a similar approach to that of the apples/bananas example above, solve for the optimal\n",
"basket of potato chips and chocolate bars when `W = 10`, `p_P = 1`, and `p_C = 2`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0715a88b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"W = 10\n",
"p_P = 1\n",
"p_C = 2\n",
"\n",
"# Your code here"
]
},
{
"cell_type": "markdown",
"id": "438428b0",
"metadata": {},
"source": [
"What is the optimal basket if we expand the budget constraint to have `W = 50`?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ad333190",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Your code here"
]
},
{
"cell_type": "markdown",
"id": "42675be0",
"metadata": {},
"source": [
"What is the optimal basket if we expand the budget constraint to have `W = 150`?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a359f819",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Your code here"
]
},
{
"cell_type": "markdown",
"id": "87634e45",
"metadata": {},
"source": [
"You can no longer assume that the `A_bc` function is always binding, as we did before, and will need to check results more carefully.\n",
"\n",
"While not required, you can take this opportunity to play around with other scipy functions such as Scipy optimize [https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html](https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html).\n",
"\n",
"([back to text](#dir3-5-2))"
]
}
],
"metadata": {
"date": 1668050880.323638,
"filename": "optimization.md",
"kernelspec": {
"display_name": "Python",
"language": "python3",
"name": "python3"
},
"title": "Optimization"
},
"nbformat": 4,
"nbformat_minor": 5
}