## Optimization problem to be studied

We will start studying functions of multiple variables by studying unconstrained optimization problems
$$
\begin{align}
\min \quad &f(x)\\
\text{s.t.}\quad &x\in \mathbb R^n
\end{align}  
$$

As an example, we study the optimization problem
$$
\begin{align}
\min \quad & (x_1-10)^2+(x_2+5)^2+x_1^2\\
\text{s.t.}\quad &x_1,x_2\in\mathbb R
\end{align}  
$$
This problem is unconstrained, because there are no constraints.

Now we need to define a function in Python that evaluates that function. That is, we define a two-variable function 
$$f:(x_1,x_2)\to (x_1-10)^2+(x_2+5)^2+x_1^2$$


```python
def f_simple(x):
    return (x[0] - 10.0)**2 + (x[1] + 5.0)**2+x[0]**2
```

Now we can call that function


```python
print "At point (5,-5) the value of the function is ",f_simple([5,-5])
```

    At point (5,-5) the value of the function is  50.0


We can also plot that function


```python
%matplotlib
import numpy as np
from pylab import meshgrid
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def plot_2d_function(lb1,lb2,ub1,ub2,f):
    x = np.arange(lb1,ub1,0.1)
    y = np.arange(lb2,ub2,0.1)
    X,Y = meshgrid(x, y) # grid of point
    Z = [f([x,y]) for (x,y) in zip (X,Y)] # evaluation of the function on the grid
    fig = plt.figure()
    ax = fig.gca(projection='3d')
    surf = ax.plot_surface(X, Y, Z)
    return plt
```

    Using matplotlib backend: Qt4Agg



```python
plot_2d_function(3,-7,7,-3,f_simple)
```

    /usr/lib64/python2.7/site-packages/matplotlib/collections.py:590: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison
      if self._edgecolors == str('face'):





    <module 'matplotlib.pyplot' from '/usr/lib64/python2.7/site-packages/matplotlib/pyplot.pyc'>



# Direct search methods

Direct search methods (also called pattern search methods) just rely on the function values to find a (local) optimum. Direct search methods consist of a set of  
1. exploratory moves that acquire information about the function $f$ in th eneighbourhood of the current solution, and
2. pattern moves that attempt to speed up the search using the information acquired in the exploratory moves.

## Hooke&Jeeves

**input:** a minimum step length $L>0$, initial step length $\epsilon_0$, constant $0<\delta<1$ for reducing the step length, exploratory step multiplier $\gamma>1$, and starting solution $x_0$  
**output:** an approximation of a local optimum (no guarantees of quality in general cases)  
```
set epsilon as the initial step length epsilon0
set x as the starting solution
while epsilon is greater than L:
    for each coordinate direction i:
        find the smallest of function values by incrementing and reducing the variable value in that coordinate by epsilon, let this value be xi*
    if x is the same as (x1*,...,xn*):
        reduce epsilon to delta*epsilon
    else:
        if the value of f at (x1*,...,xn*) is smaller than at x+gamma*((x1*,...,xn*)-x):
            set x as (x1*,...xn*)
        else:
            set x as x+gamma*((x1*,...,xn*)-x)
return x
        
```
Thus, the exploratory step of Hooke&Jeeves is performed by incrementing and reducing the variable to each coordinate direction and the pattern move is just a multiplication of the exploratory move.





```python
import copy #Copying vectors
import numpy as np #Import vector calculus and much more!
def hookejeeves(L,epsilon0,delta,gamma,x0,f):
    epsilon = epsilon0
    x = np.array(x0)
    while epsilon>L:
        xtest = np.zeros(len(x))
        for coordinate in range(len(x)):
            exp_points = [copy.copy(x) for _ in range(3)] #points to be explored
            exp_points[0][coordinate]-=epsilon
            exp_points[1][coordinate]+=epsilon
            f_exp_points = [f(exp_point) for exp_point in exp_points]
            min_value = min(f_exp_points)
            xtest[coordinate] = exp_points[f_exp_points.index(min_value)][coordinate] #The coordinate value is the one where the minimum is attained
        if all(xtest==x):
            epsilon = delta*epsilon
        else:
            if f(xtest)<f(x+gamma*(xtest-x)):
                x = xtest
            else:
                x = x+gamma*(xtest-x)
    return x
```


```python
%timeit hookejeeves(0.001,1,0.1,2,[0,0],f_simple)
```

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


## Powell's method

Powell's method is similar to Hooke&Jeeves, but the first step in exploratory moves is taken to the direction of the last pattern move. This speeds up the convergence in most cases.



```python
import copy
import numpy as np
def powell(L,epsilon0,delta,gamma,x0,f):
    epsilon = epsilon0
    exp_direction = np.array([0,1])
    x = np.array(x0)
    while epsilon>L:
        xtest = np.zeros(len(x))
        exp_direction2 = np.array([exp_direction[1],-exp_direction[0]]) #Only works in 2d!!
        exp_points = [x,x+exp_direction,x-exp_direction,x+exp_direction2,x-exp_direction2]
        f_exp_points = [f(exp_point) for exp_point in exp_points]
        min_value = min(f_exp_points)
        xtest = exp_points[f_exp_points.index(min_value)] #Comparing among all exploratory points
        if all(xtest==x):
            epsilon = delta*epsilon
        else:
            if f(xtest)<f(x+gamma*(xtest-x)):
                x = xtest
            else:
                x = x+gamma*(xtest-x)
                exp_direction = (xtest-x)/np.linalg.norm(xtest-x)
    return x
```


```python
%timeit powell(0.001,1,0.1,2,[0,0],f_simple)
```

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


9bc23271355d7df39938be62394d687036c8c061
ipynb
Jupyter Notebook
Lecture 3, Direct search methods; Hooke&Jeeves and Powell's method.ipynb
AwelEshetu/edxCourses
2fb072d8e45d203080d40ca383de14257a1fcbd2
CC-BY-3.0
2016-07-18T12:49:18.000Z
2017-02-21T12:58:16.000Z
Lecture 3, Direct search methods; Hooke&Jeeves and Powell's method.ipynb
AwelEshetu/edxCourses
2fb072d8e45d203080d40ca383de14257a1fcbd2
CC-BY-3.0
Lecture 3, Direct search methods; Hooke&Jeeves and Powell's method.ipynb
AwelEshetu/edxCourses
2fb072d8e45d203080d40ca383de14257a1fcbd2
CC-BY-3.0
Qwen/Qwen-72B
1. YES
2. YES