📖 Unconstrained optimization

📖 Unconstrained optimization#

⏱ 21 min | 2104 words

A standard optimization problem#

Example

Consider a (monopolistic) firm that is facing a market demand for its products $D (p) = α + \frac{1}{4 α} p^{2} - p$ and the cost of production $C (q) = β q + δ q^{2}$ . As usual, $p$ and $q$ denote price and quantity of product, respectively.

To maximize its profit $π (p, q) = p q - C (q)$ , the firm solves the following optimization problem

\begin{array}{r} Π (α, β, δ) = max_{p, q} π (p, q) = max_{p, q} [p q - C (q)] \\ subject to \\ q = D (p) \\ q \geq 0 \\ p > 0 \end{array}

Plugging in the functions $D (p)$ and $C (q)$ we have an equivalent formulation

\begin{array}{r} Π (α, β, δ) = max_{p, q} [(p - β) q - δ q^{2}] \\ subject to \\ q = α + \frac{1}{4 α} p^{2} - p \\ q \geq 0 \\ p > 0 \end{array}

Components of the optimization problem#

Objective function: function to be maximized or minimized, also known as maximand
In the example above profit function $π (p, q) = p q - C (q)$ to be maximized
Decision/choice variables: the variables that the agent can control in order to optimize the objective function, also known as controls
In the example above price $p$ and quantity $q$ variables that the firm can choose to maximize its profit
Equality constraints: restrictions on the choice variables in the form of equalities
In the example above $q = α + \frac{1}{4 α} p^{2} - p$
Inequality constraints (weak and strict): restrictions on the choice variables in the form of inequalities
In the example above $q \geq 0$ and $p > 0$
Parameters: the variables that are not controlled by the agent, but affect the objective function and/or constraints
In the example above $α$ , $β$ and $δ$ are parameters of the problem
Value function: the “optimized” value of the objective function as a function of parameters
In the example above $Π (α, β, δ)$ is the value function

Definition

The general form of the optimization problem is

\begin{array}{r} V (θ) = max_{x} f (x, θ) \\ subject to \\ g_{i} (x, θ) = 0, i \in {1, \dots, I} \\ h_{j} (x, θ) \leq 0, j \in {1, \dots, J} \end{array}

where:

$f (x, θ) : R^{N} \times R^{K} \to R$ is an objective function
$x \in R^{N}$ are decision/choice variables
$θ \in R^{K}$ are parameters
$g_{i} (x, θ) = 0, i \in {1, \dots, I}$ where $g_{i} : R^{N} \times R^{K} \to R$ , are equality constraints
$h_{j} (x, θ) \leq 0, j \in {1, \dots, J}$ where $h_{j} : R^{N} \times R^{K} \to R$ , are inequality constraints
$V (θ) : R^{K} \to R$ is a value function

Definition

The set of admissible choices (admissible set) contains all the choices that satisfy the constraints of the optimization problem.

Note

Sometimes the equality constraints are dropped from the definition of the optimization problem, because they can always be represented as a pair of inequality constraints $g_{i} (x, θ) \leq 0$ and $- g_{j} (x, θ) \leq 0$

Note

Note that strict inequality constraints are not present in the definition above, although they may be present in the economic applications. You already know that this has to do with the intention to keep the set of admissible choices closed, such that the solution of the problem (has a better chance to) exist. Sometimes they are added to the definition.

A roadmap for formulating an optimization problem (in economics)

Determine which variables are choice variables and which are parameters according to what the economic agent has control over
Determine whether the optimization problem is a maximization or a minimization problem
Determine the objective function of the economic agent (and thus the optimization problem)
Determine the constraints of the optimization problem: equality and inequality, paying particular attention to whether inequalities should be strict or weak (the latter has huge implications for the existence of the solution)

Example

Consider a decision maker who is deciding how to divide the money they have between food and services, bank deposit and buying some crypto. Discuss and Write down the corresponding optimization problem. [class exercise]

Classes of the optimization problems#

Static optimization: finite number of choice variables

singe instance of choice
deterministic finite horizon dynamic choice models can be represented as static
our main focus in this course

Dynamic programming: some choice variables are infinite sequences, solved using similar techniques as static optimization

will touch upon in the end of the course

Deterministic optimal control: some “choice variables” are functions, completely new theory is needed
Stochastic optimal control: “choice variables” are functions, objective function is a stochastic process, yet more theory is needed

Review of one-dimensional optimization#

Let $f : [a, b] \to R$ be a differentiable function

$f$ takes $x \in [a, b] \subset R$ and returns number $f (x)$
derivative $f^{'} (x)$ exists for all $x$ with $a < x < b$

Differentiability implies that $f$ is continuous, and because the interval $[a, b]$ is closed and bounded, $f$ has a maximum and a minimum on $[a, b]$ by the Weierstrass extreme value theorem.

Reminder of definitions

A point $x^{*} \in [a, b]$ is called a

maximizer of $f$ on $[a, b]$ if $f (x^{*}) \geq f (x)$ for all $x \in [a, b]$
minimizer of $f$ on $[a, b]$ if $f (x^{*}) \leq f (x)$ for all $x \in [a, b]$

Point $x$ is called interior to $[a, b]$ if $a < x < b$

A stationary point of $f$ on $[a, b]$ is an interior point $x$ with $f^{'} (x) = 0$

_images/stationary.png — Fig. 73 Both $x^{*}$ and $x^{* *}$ are stationary#

Fact

If $f$ is differentiable and $x^{*}$ is either an interior minimizer or an interior maximizer of $f$ on $[a, b]$ , then $x^{*}$ is stationary

$\Rightarrow$ any interior maximizer stationary
$\Rightarrow$ set of interior maximizers $\subset$ set of stationary points
$\Rightarrow$ maximizers $\subset stationary points \cup {a} \cup {b}$

Algorithm for finding maximizers/minimizers:

Locate stationary points
Evaluate $y = f (x)$ for each stationary $x$ and for $a$ , $b$
Pick point giving largest $y$ value

First oder conditions (FOC)#

Necessary

In this lecture we focus on the unconstrained optimization problems of the form

\begin{array}{r} max_{x} f (x, θ) also written as f (x, θ) \to max, \\ min_{x} f (x, θ) also written as f (x, θ) \to min, \end{array}

where $f (x, θ) : R^{N} \to R$ and unless stated otherwise is assumed to be continuous and twice continuously differentiable everywhere on $R^{N}$ . Parameter $θ$ may or may not be present.

Note

Twice continuously differentiable functions are said to be $C^{2}$ .

Every point in the whole space $R^{N}$ is interior, therefore all maximizers/minimizers have to be stationary points
Assuming differentiability implies we can focus on derivative based conditions

Definition

Given a function $f : R^{N} \to R$ , a point $x \in R^{N}$ is called a stationary point of $f$ if $\nabla f (x) = 0$

Definition

Given a function $f : R^{N} \to R$ , a point $x^{⋆} \in R^{N}$ is called a local maximizer/minimizer of $f$ if $\exists ϵ$ such that $f (x) \leq f (x^{⋆})$ for all $x \in B_{ϵ} (x^{⋆})$

If the inequality is strict, then $x^{⋆}$ is called a strict local maximizer/minimizer of $f$

A maximizer/minimizer (global) must also be a local one, but the opposite is not necessarily true.

Fact (Necessary condition for optima)

Let $f (x, θ) : R^{N} \to R$ be a differentiable function and let $x^{⋆} \in R^{N}$ be a local maximizer/minimizer of $f$ .

Then $x^{⋆}$ is a stationary point of $f$ , that is $\nabla f (x^{⋆}) = 0$

Example

Consider quadratic form $f (x) = x^{'} A x$ where $A = (\begin{array}{rr} 1, & 0.5 \\ 0.5, & 2 \end{array})$

Solving the FOC

\nabla f (x) = 2 x^{'} A = 0 ⟹ x = 0

The point $(0, 0)$ should be an optimizer.

_images/6ef874230d5f955db21f8fc6cf8af740328eedf32326dd1d833206d8a3a78c01.png

_images/cd96216b562ed8bc908234e8403ff6325a31d2a2d685e9306a49d494fce14458.png

_images/a39efaa9e1f83fe5cfcd16f9f17e0ab693d8054dc2086e6cb88b84b435aa07e0.png

Example

Consider quadratic form $f (x) = x^{'} A x$ where $A = (\begin{array}{rr} 1, & 0.5 \\ 0.5, & - 2 \end{array})$

Solving the FOC

\nabla f (x) = 2 x^{'} A = 0 ⟹ x = 0

The point $(0, 0)$ should be an optimizer?

_images/475c3726000289cb39aa908cacc22ab632304e8e24dd27a8da668efd8e4e859a.png

_images/68f3db5fe0df66b3fbdc22761f59550be5b2be9c8208624eea7b920aaff6f3b6.png

_images/ec3947f919ca5344e1a583c9641f869eda187321e873c9c42c2b2a7ee448d7e5.png

This is an example of a saddle point where the FOC hold, yet the point is not a local maximizer/minimizer!
Similar to $x = 0$ in $f (x) = x^{3}$ : derivative is zero, yet the point is not an optimizer
How to distinguish saddle points from optima? Key insight: the function has different second order derivatives in different directions!

Second order conditions (SOC)#

allow to establish whether the stationary point is a local maximizer/minimizer or a saddle point
help to determine whether an optimizer is a maximizer or a minimizer
do not give definitive answer in all cases, unfortunately

Fact (necessary SOC)

Let $f (x) : R^{N} \to R$ be a twice continuously differentiable function and let $x^{⋆} \in R^{N}$ be a local maximizer/minimizer of $f$ . Then:

$f$ has a local maximum at $x^{⋆} ⟹ H f (x^{⋆})$ is negative semi-definite
$f$ has a local minimum at $x^{⋆} ⟹ H f (x^{⋆})$ is positive semi-definite

recall the definition of semi-definiteness

Fact (sufficient SOC)

Let $f (x) : R^{N} \to R$ be a twice continuously differentiable function. Then:

if for some $x^{⋆} \in R^{N}$ $\nabla f (x^{⋆}) = 0$ (FOC satisfied) and $H f (x^{⋆})$ is negative definite, then $x^{⋆}$ is a strict local maximum of $f$
if for some $x^{⋆} \in R^{N}$ $\nabla f (x^{⋆}) = 0$ (FOC satisfied) and $H f (x^{⋆})$ is positive definite, then $x^{⋆}$ is a strict local minimum of $f$

observe that SOC are only necessary in the “weak” form, but are sufficient in the “strong” form
this leaves room for ambiguity when we can not arrive at a conclusion — particular stationary point may be a local maximum or minimum
but we can rule out saddle points for sure, in this case neither semi-definiteness nor definiteness can be established, the Hessian is indefinite

Example

Consider a one dimensional function $f (x) = (x - 1)^{2}$ , $\nabla f (x) = 2 x - 2$ , $H f (x) = 2$ .

Point $x = 1$ is a stationary point where FOC is satisfied.

Treating $H f (x)$ as $1 \times 1$ matrix, we can see it is positive definite at $x = 1$ ( $y^{'} [2] y = 2 y^{2} > 0$ for all $y \neq 0$ ), therefore $x = 1$ is a strict local minimum of $f$ .

Example

Consider a one dimensional function $f (x) = x^{2} - 1$ , $\nabla f (x) = 2 x$ , $H f (x) = 2$ .

Point $x = 0$ is a stationary point where FOC is satisfied.

Treating $H f (x)$ as $1 \times 1$ matrix, we can see it is positive definite at $x = 0$ ( $y^{'} [2] y = 2 y^{2} > 0$ for all $y \neq 0$ ), therefore $x = 0$ is a strict local minimum of $f$ .

Example

Consider a one dimensional function $f (x) = (x - 1)^{4}$ , $\nabla f (x) = 4 (x - 1)^{3}$ , $H f (x) = 12 (x - 1)^{2}$ .

Point $x = 1$ is a stationary point where FOC is satisfied.

Treating $H f (x)$ as $1 \times 1$ matrix, we can see it is positive semi-definite (and negative semi-definite) at $x = 1$ ( $y^{'} [0] y = 0 \geq 0$ and $y^{'} [0] y = 0 \leq 0$ for all $y \in R$ ), therefore at $x = 1$ function $f$ may have a local minimum. But may have a local maximum as well. No definite conclusion! (In reality it is a local and global minimum)

Example

Consider a one dimensional function $f (x) = (x + 1)^{3}$ , $\nabla f (x) = 3 (x + 1)^{2}$ , $H f (x) = 6 (x + 1)$ .

Point $x = - 1$ is a stationary point where FOC is satisfied.

Treating $H f (x)$ as $1 \times 1$ matrix, we can see it is positive semi-definite (and negative semi-definite) at $x = - 1$ ( $y^{'} [0] y = 0 \geq 0$ and $y^{'} [0] y = 0 \leq 0$ for all $y \in R$ ), therefore at $x = 1$ function $f$ may have a local minimum. But may have a local maximum as well. No definite conclusion! (In reality it is neither local minimum nor maximum)

Establishing definiteness of Hessian in $R^{2}$ case#

Recall that a symmetric matrix $A$ is

positive definite $⟺$ all eigenvalues are strictly positive
negative definite $⟺$ all eigenvalues are strictly negative
nonpositive definite $⟺$ all eigenvalues are nonpositive
nonnegative definite $⟺$ all eigenvalues are nonnegative
indefinite $⟺$ there are both positive and negative eigenvalues

Let $H$ be a $2 \times 2$ matrix $\to$ eigenvalues are roots of a quadratic equation

\begin{array}{r} H = (\begin{array}{cc} a & b \\ c & d \end{array}) ⟹ H - λ I = (\begin{array}{cc} a - λ & b \\ c & d - λ \end{array}) \end{array}

\begin{array}{r} ⟹ det (H - λ I) = (a - λ) (d - λ) - b c \\ = λ^{2} - (a + d) λ + (a d - b c) \\ = λ^{2} - trace (H) λ + det (H) \end{array}

Hence the the two eigenvalues $λ_{1}$ and $λ_{2}$ of $H$ are given by the two roots of

λ^{2} - trace (H) λ + det (H) = 0

From the Viets’s formulas for a quadratic polynomial we have

\begin{array}{r} λ_{1} + λ_{2} = trace (H) \\ λ_{1} λ_{2} = \det (H) \end{array}

Applying this result to a Hessian of a function $f : R^{2} \to R$ we have

Fact

Given a twice continuously differentiable function $f : R^{2} \to R$ and a stationary point $x^{⋆} : \nabla f (x^{⋆}) = 0$ , the second order conditions provide:

if $\det (H f (x^{⋆})) > 0$ and $trace (H f (x^{⋆})) > 0$ $⟹$
- $λ_{1} > 0$ and $λ_{2} > 0$ ,
- $H f (x^{⋆})$ is positive definite,
- $f$ has a strict local minimum at $x^{⋆}$
if $\det (H f (x^{⋆})) > 0$ and $trace (H f (x^{⋆})) < 0$ $⟹$
- $λ_{1} < 0$ and $λ_{2} < 0$ ,
- $H f (x^{⋆})$ is negative definite,
- $f$ has a strict local maximum at $x^{⋆}$
if $\det (H f (x^{⋆})) = 0$ and $trace (H f (x^{⋆})) > 0$ $⟹$
- $λ_{1} = 0$ and $λ_{2} > 0$ ,
- $H f (x^{⋆})$ is positive semi-definite (nonnegative definite),
- $f$ may have a local minimum $x^{⋆}$
- undeceive!
if $\det (H f (x^{⋆})) = 0$ and $trace (H f (x^{⋆})) < 0$ $⟹$
- $λ_{1} = 0$ and $λ_{2} < 0$ ,
- $H f (x^{⋆})$ is negative semi-definite (nonpositive definite),
- $f$ may have a local maximum $x^{⋆}$
- undeceive!
if $\det (H f (x^{⋆})) < 0$
- $λ_{1}$ and $λ_{2}$ have different signs,
- $H f (x^{⋆})$ is indefinite,
- $x^{⋆}$ is a saddle point of $f$

Example

Consider a two dimensional function $f (x) = (x_{1} - 1)^{2} + x_{1} x_{2}^{2}$

\begin{array}{r} \nabla f (x) = (2 (x_{1} - 1) + x_{2}^{2}, 2 x_{1} x_{2}), H f (x) = (\begin{array}{ll} 2, & 2 x_{2} \\ 2 x_{2}, & 2 x_{1} \end{array}) \end{array}

Point $x_{1}^{⋆} = (1, 0)$ is a stationary point where FOC is satisfied.

\begin{array}{r} H f (x^{⋆}) = (\begin{array}{ll} 2, & 0 \\ 0, & 2 \end{array}), \det (H f (x^{⋆})) = 4 > 0, trace (H f (x^{⋆})) = 4 > 0 \end{array}

Therefore at $x_{1}^{⋆} = (1, 0)$ function $f$ has a strict local minimum.

Point $x_{2}^{⋆} = (1 + \frac{\sqrt{2}}{2}, - \sqrt{2})$ is also a stationary point where FOC is satisfied.

\begin{array}{r} H f (x^{⋆}) = (\begin{array}{ll} 2, & 2 \sqrt{2} \\ 2 \sqrt{2}, & 2 - \sqrt{2} \end{array}), \det (H f (x^{⋆})) = - 4 - 2 \sqrt{2} < 0 \end{array}

Therefore at $x_{2}^{⋆} = (1, 0)$ function $f$ has a saddle point.

Point $x_{3}^{⋆} = (1 - \frac{\sqrt{2}}{2}, \sqrt{2})$ is yet another stationary point where FOC is satisfied.

\begin{array}{r} H f (x^{⋆}) = (\begin{array}{ll} 2, & - 2 \sqrt{2} \\ - 2 \sqrt{2}, & 2 + \sqrt{2} \end{array}), \det (H f (x^{⋆})) = 2 \sqrt{2} - 4 < 0 \end{array}

Therefore again, at $x_{3}^{⋆} = (1, 0)$ function $f$ has a saddle point.

📖 Unconstrained optimization

Contents

📖 Unconstrained optimization#

A standard optimization problem#

Components of the optimization problem#

Classes of the optimization problems#

Review of one-dimensional optimization#

First oder conditions (FOC)#

Second order conditions (SOC)#

Establishing definiteness of Hessian in $R^{2}$ case#

References and reading#

📖 Unconstrained optimization

Contents

📖 Unconstrained optimization#

A standard optimization problem#

Components of the optimization problem#

Classes of the optimization problems#

Review of one-dimensional optimization#

First oder conditions (FOC)#

Second order conditions (SOC)#

Establishing definiteness of Hessian in R2 case#

References and reading#

Establishing definiteness of Hessian in $R^{2}$ case#