Non-Linear Programming

294. Non-Linear Programming

294.0.0.1. EOQ

Parameters

$𝐷$ : annual demand (units)
$𝐾$ : unit ordering cost ($)
$ℎ$ : unit holding cost per year ($)
$𝑝$ : unit purchasing cost ($)

Decision Variable

$𝑄$ : order quantity per order (units)

Objective

Minimize annual total cost

$\frac{𝑞}{2}$ : average inventory level
$ℎ \times \frac{𝑞}{2} = \frac{ℎ 𝑞}{2}$ : annual holding cost
$𝑝 𝐷$ : annual purchasing cost
$\frac{𝐷}{𝑞}$ : number of orders in a year
$𝐾 \times \frac{𝐷}{𝑞} = \frac{𝐾 𝐷}{𝑞}$ : annual ordering cost

Objective Function

min_{𝑞 \geq 0} \underset{\begin{matrix} Ordering \\ Cost \end{matrix}}{\underset{⏟}{\frac{𝐾 𝐷}{𝑞}}} + \underset{\begin{matrix} Purchasing \\ Cost \end{matrix}}{\underset{⏟}{𝑝 𝐷}} + \underset{\begin{matrix} Inventory \\ Cost \end{matrix}}{\underset{⏟}{\frac{ℎ 𝑞}{2}}}

$𝑝 𝐷$ is just a constant, so:

𝑇 𝐶 (𝑞) = \underset{\begin{matrix} Ordering \\ Cost \end{matrix}}{\underset{⏟}{\frac{𝐾 𝐷}{𝑞}}} + \underset{\begin{matrix} Inventory \\ Cost \end{matrix}}{\underset{⏟}{\frac{ℎ 𝑞}{2}}}

As $𝑞$ increases:
- Inventory costs increase
- Ordering cost decease
As $𝑞$ decreases:
- Inventory costs decrease
- Ordering cost increase

294.0.0.2. Portfolio Optimization

Objective

Invest $𝐵$ dollars in $𝑛$ stocks while managing risk and meeting required return

Notation

$𝐵$ : budget ($)
$𝑅$ : required minimum expected return
For each stock $𝑖 \in {1, \dots, 𝑛}$
- $𝑝_{𝑖}$ : current price
- $𝜇_{𝑖}$ : expected future price
- $𝜎_{𝑖}^{2}$ : variance of ruturn per share
- $𝜎_{𝑖 𝑗}$ : Covariance between assets $𝑖$ and $𝑗$
- $𝑥_{𝑖}$ : number of shares to buy (decision variable)

Model

\begin{aligned} min & \sum_{𝑖 = 1}^{𝑛} 𝜎_{𝑖}^{2} 𝑥_{𝑖}^{2} + 2 \sum_{𝑖 = 1}^{𝑛} \sum_{𝑗 = 𝑖 + 1}^{𝑛} 𝜎_{𝑖 𝑗} 𝑥_{𝑖} 𝑥_{𝑗} & (Total risk) \\ 𝑠 . 𝑡 . & \sum_{𝑖 = 1}^{𝑛} 𝑝_{𝑖} 𝑥_{𝑖} \leq 𝐵 & (Budget constraint) \\ \sum_{𝑖 = 1}^{𝑛} 𝜇_{𝑖} 𝑥_{𝑖} \geq 𝑅 & (Return constraint) \\ 𝑥_{𝑖} \geq 0 \forall 𝑖 = 1, \dots, 𝑛 & (No short-selling) \end{aligned}

294.0.1. Linearizing Maximum/Minimum Functions

When the maximum function is on the smaller side of inequality

General Form

𝑦 \geq max (𝑥_{1}, 𝑥_{2}) ⟺ 𝑦 \geq 𝑥_{1} \land 𝑦 \geq 𝑥_{2}

This rule holds regardless of whether $𝑥_{1}$ , $𝑥_{2}$ , $𝑦$ are variables, constants, or expressions
You’re ensuring that $𝑦$ is greater than or equal to all values in the maximum function, so it must be greater than or equal to each term individually

Generalized form with more than two elements

𝑦 \geq max (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}) ⟺ 𝑦 \geq 𝑥_{𝑖} \forall 𝑖 = 1, \dots, 𝑛

Example

𝑦 + 𝑥_{1} + 3 \geq max (𝑥_{1} - 𝑥_{3}, 2 𝑥_{2} + 4) ⟺ {\begin{cases} 𝑦 + 𝑥_{1} + 3 \geq 𝑥_{1} - 𝑥_{3} \\ 𝑦 + 𝑥_{1} + 3 \geq 2 𝑥_{2} + 4 \end{cases}

When the minimum function is on the larger side of inequality

General Form

𝑦 \leq min (𝑥_{1}, 𝑥_{2}) ⟺ 𝑦 \leq 𝑥_{1} \land 𝑦 \leq 𝑥_{2}

This rule holds regardless of whether $𝑥_{1}$ , $𝑥_{2}$ , $𝑦$ are variables, constants, or expressions
You’re ensuring that $𝑦$ is smaller than or equal to all values in the minimum function, so it must be smaller than or equal to each term individually

Generalized form with more than two elements

𝑦 \leq min (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}) ⟺ 𝑦 \leq 𝑥_{𝑖} \forall 𝑖 = 1, \dots, 𝑛

Example

𝑦 + 𝑥_{1} \leq min (𝑥_{1} - 𝑥_{3}, 2 𝑥_{2} + 4, 0) ⟺ {\begin{cases} 𝑦 + 𝑥_{1} \leq 𝑥_{1} - 𝑥_{3} \\ 𝑦 + 𝑥_{1} \leq 2 𝑥_{2} + 4 \\ 𝑦 + 𝑥_{1} \leq 0 \end{cases}

Cases Where Linearization Does Not Apply

$𝑦 \leq max (𝑥_{1}, 𝑥_{2}) ⇎ 𝑦 \leq 𝑥_{1} \land 𝑦 \leq 𝑥_{2}$
$𝑦 \geq max (𝑥_{1}, 𝑥_{2}) ⇎ 𝑦 \geq 𝑥_{1} \land 𝑦 \geq 𝑥_{2}$
Maximum or minimum function in an equality

𝑦 = max (𝑥_{1}, 𝑥_{2}) or 𝑦 = min (𝑥_{1}, 𝑥_{2})

294.0.2. Linearize Objective Function

Minimize a Maximum Function

min max (𝑥_{1}, 𝑥_{2})

⟺

\begin{aligned} min & 𝑤 \\ 𝑠 . 𝑡 . & 𝑤 \geq 𝑥_{1} \\ 𝑤 \geq 𝑥_{2} \end{aligned}

Maximize a Minimum Function

\begin{aligned} max & min (𝑥_{1}, 𝑥_{2}, 2 𝑥_{3} + 5) + 𝑥_{4} \\ 𝑠 . 𝑡 . & 2 𝑥_{1} + 𝑥_{2} - 𝑥_{4} \leq 𝑥_{3} \end{aligned}

⟺

\begin{aligned} max & 𝑤 + 𝑥_{4} \\ 𝑠 . 𝑡 . & 𝑤 \leq 𝑥_{1} \\ 𝑤 \leq 𝑥_{2} \\ 𝑤 \leq 2 𝑥_{3} + 5 \\ 2 𝑥_{1} + 𝑥_{2} - 𝑥_{4} \leq 𝑥_{3} \end{aligned}

Cases Where Linearization Does Not Apply

$max max (𝑥_{1}, 𝑥_{2})$
$min min (𝑥_{1}, 𝑥_{2})$

Absolute Function

The absolute value is equivalent to a maximum function:

| 𝑥 | = max (𝑥, - 𝑥)

Thus, it can be linearized when it appears on the smaller side of an inequality:

| 𝑥 | \leq 𝑦 ⟺ {\begin{cases} 𝑥 \leq 𝑦 \\ - 𝑥 \leq 𝑦 \end{cases}

Example

We want to allocate $1000 to 2 people in a fair way

Fairness criterion: Minimize the difference between the amounts each person receives.
Let $𝑥_{𝑖}$ be amount to allocate to person $𝑖$ for $𝑖 = 1, 2$

We write the problem as:

\begin{aligned} min & | 𝑥_{2} - 𝑥_{1} | \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} = 1000 \\ 𝑥_{𝑖} \geq 0 \forall 𝑖 = 1, 2 \end{aligned}

The absolute value makes the objective nonlinear

Linearizing the Problem

We now reformulate the problem to make it linear

Step 1.: Introduce a new variable

Let $𝑤$ be the absolute difference: $𝑤 = | 𝑥_{2} - 𝑥_{1} |$

\begin{aligned} min & 𝑤 \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} = 1000 \\ 𝑤 = | 𝑥_{2} - 𝑥_{1} | \\ 𝑥_{𝑖} \geq 0 \forall 𝑖 = 1, 2 \end{aligned}

Step 2. Relax the equality

We replace the equality with an inequality:

\begin{aligned} min & 𝑤 \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} = 1000 \\ 𝑤 \geq | 𝑥_{2} - 𝑥_{1} | \\ 𝑥_{𝑖} \geq 0 \forall 𝑖 = 1, 2 \end{aligned}

Step 3. Replace absolute value with maximum

Recall:

| 𝑥_{2} - 𝑥_{1} | = max (𝑥_{2} - 𝑥_{1}, 𝑥_{1} - 𝑥_{2})

Therefore:

𝑤 \geq | 𝑥_{2} - 𝑥_{1} | \Leftrightarrow 𝑤 \geq max (𝑥_{2} - 𝑥_{1}, 𝑥_{1} - 𝑥_{2}) \Leftrightarrow 𝑤 \geq 𝑥_{2} - 𝑥_{1} \land 𝑤 \geq 𝑥_{1} - 𝑥_{2}

Now the problem is fully linear:

\begin{aligned} min & 𝑤 \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} = 1000 \\ 𝑤 \geq 𝑥_{2} - 𝑥_{1} \\ 𝑤 \geq 𝑥_{1} - 𝑥_{2} \\ 𝑥_{𝑖} \geq 0 \forall 𝑖 = 1, 2 \end{aligned}

Reformulating in One Variable

using $𝑥_{2} = 1000 - 𝑥_{1}$ , we can express everything in terms of $𝑥_{1}$ :

\begin{aligned} min & 𝑤 \\ 𝑠 . 𝑡 . & 𝑤 \geq 1000 - 2 𝑥_{1} \\ 𝑤 \geq 2 𝑥_{1} - 1000 \\ 𝑥_{1} \geq 0 \end{aligned}

We are minimizing $𝑤$ , which represents the difference between the two allocations. The solution occurs when the two inequalities intersect — that is, when both are equal:

1000 - 2 𝑥_{1} = 2 𝑥_{1} - 1000 \Rightarrow 𝑥_{1} = 500

So:

$𝑥_{1} = 500$
$𝑥_{2} = 1000 - 𝑥_{1} = 500$
$𝑤 = | 500 - 500 | = 0$

This is the fair allocation: each person receives $500, and the difference between the two amounts is 0.

294.0.3. Linearizing Products of Decision Variables

Products of decision variables can be linearized if:

A binary and a continuous variable
Two binary variables

Cannot be linearized if:

Two continuous variables