# What is an optimization problem?

A general mathematical formulation for **the optimization problems studied on this course** is
$$
\begin{align} \
\min \quad &f(x)\\
\text{s.t.} \quad & g_j(x) \geq 0\text{ for all }j=1,\ldots,J\\
& h_k(x) = 0\text{ for all }k=1,\ldots,K\\
&x\in \mathbb R^n.
\end{align}
$$

The above problem can be expressed as 
>Find an $x\in \mathbb R^n$ such that $g_j(x)\geq 0$ for all $j=1,\ldots,J$ and $h_k(x)=0$ for all $k=1,\ldots,K$, and there does not exist $x'\in \mathbb R^n$ such that $f(x')<f(x)$ and $g_j(x')\geq 0$ for all $j=1,\ldots,J$, $h_k(x')=0$ for all $k=1,\ldots,K$.

There are three main components to an optimization problem:
* the variables $x$ are called the **decision variables**,
* the equalities and inequalities $g_j(x)\geq 0$ and $h_k(x)=0$ are called the **constraints**,
* the funtion $f(x)$ is called the **objective function**.

Values of decision variables $x^*$ are called **solutions** and a solution is called
* **feasible** if $g_j(x^*)\geq 0$ for all $j=1,\ldots,J$, $h_k(x^*)=0$ for all $k=1,\ldots,K$,
* **locally optimal** if $x^*$ is feasible and there exists $r>0$ such that there does not exist a feasible solution $x'\in \operatorname{B}(x^*,r)$ such that $f(x')<f(x^*)$, and
* **optimal** if $x^*$ is feasible and there does not exist a feasible solution $x'$ such that $f(x')<f(x^*)$.

The problem is called
* **linear/nonlinear** if the objective function and the constraints of the problem are/are not affinely linear,
* **multi/unimodal** if the problem has/does not have more than one local optimum,
* **convex/nonconvex** if the objective and the constraints are that,
* **continuous/differentiable/twice-differentiable, etc** if the objective and the constraints are that.


## Why do we study optimization problems? 

Because optimization problems arise in various fields engineering, finance, medicine etc.

### Mixing problem
Refinery produces 3 types of gasoline by mixing 3 different grude oil. Each grude oil can be purchased maximum of 5000 barrels per day. Let us assume that octane values and lead concentrations behave linearly in mixing. Refining costs are 4\$ per barrel and the capacity of the refinery is 14000 barrels per day. Demand of gasoline can be increased by (demand grows 10 barrels per day for each \$ used for advertizing). The details of the gasolines and Grude oils can be found in the following tables:

| |Gasoline 1|Gasoline 2|Gasoline 3|
|---|---|---|---|
|Sale price|70|60|50|
|Lower limit for octane|10|8|6|
|Upper limit for lead|0.01|0.02|0.01|
|Demand|3000|2000|1000|
|Refining cost|4|4|4|

| |Grude oil 1|Grude oil 2|Grude oil 3|
|---|---|---|---|
|Purchase price|45|35|25|
|Octane value|12|6|8|
|Lead concentration|0.005|0.02|0.03|
|Availability|5000|5000|5000|


Determine the production quantities of each type of gasoline, mixing ratios of different grude oil and advertising budget so that the profit is maximized and the demand is met exactly.

#### Modelling mixing problem as an optimization problem:
* decision variables
    * $x_{ij}$ = amount of grude oil $i$ used for producing gasoline $j$
    * $y_j$ = the amount of money used for advertizing gasoline $j$
* constraints
    * gasoline 1 demand: $x_{1,1}+x_{2,1}+x_{3,1}=3000+10y_1$
    * gasoline 2 demand: $x_{1,2}+x_{2,2}+x_{3,2}=2000+10y_2$
    * gasoline 3 demand: $x_{1,3}+x_{2,3}+x_{3,3}=1000+10y_3$
    * grude oil 1 availability: $x_{1,1}+x_{1,2}+x_{1,3}\leq 5000$
    * grude oil 2 availability: $x_{2,1}+x_{2,2}+x_{2,3}\leq 5000$
    * grude oil 3 availability: $x_{3,1}+x_{3,2}+x_{3,3}\leq 5000$
    * gasoline 1 octave value: $\frac{12x_{1,1}+6x_{2,1}+8x_{3,1}}{x_{1,1}+x_{2,1}+x_{3,1}}\geq 10$
    * gasoline 2 octave value: $\frac{12x_{1,2}+6x_{2,2}+8x_{3,2}}{x_{1,2}+x_{2,2}+x_{3,2}}\geq 8$
    * gasoline 3 octave value: $\frac{12x_{1,3}+6x_{2,3}+8x_{3,3}}{x_{1,3}+x_{2,3}+x_{3,3}}\geq 6$
    * gasoline 1 lead value: $\frac{0.005x_{1,1}+0.02x_{2,1}+0.03x_{3,1}}{x_{1,1}+x_{2,1}+x_{3,1}}\leq 0.01$
    * gasoline 2 lead value: $\frac{0.005x_{1,2}+0.02x_{2,2}+0.03x_{3,2}}{x_{1,2}+x_{2,2}+x_{3,2}}\leq 0.02$
    * gasoline 3 lead value: $\frac{0.005x_{1,3}+0.02x_{2,3}+0.03x_{3,3}}{x_{1,3}+x_{2,3}+x_{3,3}}\leq 0.01$
* objective function:
$$
70(x_{1,1}+x_{2,1}+x_{3,1})+60(x_{1,2}+x_{2,2}+x_{3,2})+50(x_{1,3}+x_{2,3}+x_{3,3})-45(x_{1,1}+x_{1,2}+x_{1,3})-35(x_{2,1}+x_{2,2}+x_{2,3})-25(x_{3,1}+x_{3,2}+x_{3,3})
$$

# How to solve optimization problems?

## Iterative vs. non-iterative methods

Optimal solutions to some optimization problems can be found by defining an explicit formula for it. For example, if the objective function is twice continuously differentiable and there are no constraints, the optimal solution (if exists) can be found by calculating all the zero-points of the gradient and finding the best one of those. In this kind of cases, the optimization problem **can be solved using non-iterative methods.**

**In this course we concentrate on the iterative methods.** Iterative methods are needed, if the problem has constraints, or the problem is in some other way not-well behaved (to be defined later, depending on the context). In iterative methods, the solving the optimizaiton problem starts from a so-called starting solution and then tries to improve the solution iteratively. The optimization algorithm chooses how the solution is changed at each iteration.



## What kind of methods will you learn in this course?
Different optimization problems require different methods. In this course, we study optimization problems, which are
* non-linear
* not hugely multimodal

Often the methods cannot guarantee a (global) optimum, but instead **we need to satisfy ourselves with a local optimum**. In addition, it is usually not possible to find the actual optimal solution, but instead **an approximation of the optimal solution**. A feasible solution $x^*$ is called an approximation of a local optimum $x^{**}$ with quality $L>0$, when $\|x^*-x^{**}\|\leq L$.


# Line search

Let us study optimization problem $\min_{x\in[a,b]} f(x)$, where $a,b\in\mathbb R$. Let us try to find an approximation of a local optimum to this problem. 


```python
#Example objective function
def f(x):
    return 2+(1-x)**2
```


```python
print "The value of the objective function at 0 is " + str(f(0))
```

    The value of the objective function at 0 is 3


## Line search with fixed steps
**input:** the quality $L>0$ of the approximation of the local optimum.  
**output:** an approximation of the local optimum with quality $L$.
```
start with x as the start point of the interval
loop until stops:
    if the value of the objective is increasing for x+L from x
        stop, because the approximation of the locally optimal solution is x 
    increase x by L
```


```python
def fixed_steps_line_search(a,b,f,L):
    x = a
    while f(x)>f(x+L) and x+L<b:
        x=x+L
    return x
```


```python
%timeit fixed_steps_line_search(0.0,3.0,f,1e-3)
#x = fixed_steps_line_search(0,3,f,1e-3); print "optimum is "+str(x)
```

    1000 loops, best of 3: 587 µs per loop


## The method of bisection
**input:** the quality $L>0$ of the approximation of the local optimum.  
**output:** an approximation of the local optimum with quality $L$.
```
Set x as the start point of interval and y as the end point
while y-x<2*L:
    if the function is increasing at the mid point between x and y:
        set y as the midpoint between y and x, because a local optimum is before the midpoint
    otherwise:
        set x as the midpoint, because a local optimum is after the midpoint
return midpoint between x and y
```

The following function is to be completed in class as an exercise


```python
def bisection_line_search(a,b,f,L,epsilon):
    x = a
    y = b
    while y-x>2*L:
        if f((x+y)/2+epsilon)>f((x+y)/2-epsilon):
            y=(x+y)/2+epsilon
        else:
            x = (x+y)/2-epsilon
    return (x+y)/2
```

This is what we should end up. The following function is not shown on the slides.


```python
def bisection_line_search(a,b,f,L,epsilon):
    x = a
    y = b
    while y-x<2*L:
        if f((x+y)/2-epsilon)<f((x+y)/2+epsilon):
            y = (x+y)/2+epsilon
        else:
            x = (x+y)/2-epsilon
    return (x+y)/2
    
```


```python
%timeit bisection_line_search(0.0,3.0,f,1e-3,1e-4)
#x = bisection_line_search(0.0,3.0,f,0.01,1e-4); print "x="+str(x)
```

    100000 loops, best of 3: 9.61 µs per loop


## Golden section search

### Golden section

Let $a<c<b$ be such that $\frac{b-a}{c-a}=\frac{c-a}{b-c}$. Then it is said that the point $c$ devides interval $[a,b]$ in the ratio of golden section (from the left, mirror from the right). Note that $c=a+\frac{\sqrt{5}-1}2(b-a)\approx a+0.618(b-a)$.



There is a theorem that if $a<c<d<b$ and both points divide the interval $[a,b]$ in the ratio of golden section (from right and left), then the point $c$ divides the interval $[a,d]$ in the ratio of golder ration from the left.



### Golden section search algorithm


**input:** the quality $L>0$ of the approximation of the local optimum.  
**output:** an approximation of the local optimum with quality $L$.
```
Set x as the start point of interval and y as the end point
while y-x>2*L:
    Divide the interval [x,y] in the golden section from the letf and right and attain two division points
    If the greater of the division points has a greater function value 
        set y as the rightmost division point, because a local optimum is before that
    otherwise:
        set x as the leftmost division point, because a local optimum is after that
return midpoint between x and y
```

The following function is to be completed in class as an exercise


```python
import math
def golden_section_line_search(a,b,f,L):
    x = a
    y = b
    while y-x>2*L:
        if f(x+(math.sqrt(5.0)-1)/2.0*(y-x))<f(y-(math.sqrt(5.0)-1)/2.0*(y-x)):
            x = y-(math.sqrt(5.0)-1)/2.0*(y-x)
        else:
            y = x+(math.sqrt(5.0)-1)/2.0*(y-x)
    return (x+y)/2
```


```python
%timeit golden_section_line_search(0.0,3.0,f,1e-3)
#x = golden_section_line_search(0.0,3.0,f,0.01); print "x="+str(x)
```

    10000 loops, best of 3: 20.1 µs per loop


0f09094c09fc53fd9305e6a40a705ec5bf78c69a
ipynb
Jupyter Notebook
Lecture 2, What is an optimization problem and how to solve them and line search.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2019-04-26T12:46:14.000Z
2021-11-23T03:38:59.000Z
Lecture 2, What is an optimization problem and how to solve them and line search.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
Lecture 2, What is an optimization problem and how to solve them and line search.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2016-01-08T16:28:11.000Z
2021-04-10T05:18:10.000Z
Qwen/Qwen-72B
1. YES
2. YES