Ex1

Write down Newton’s formula for finding the minimum of \(f(x) = (3x^4 - 4x^3)/12\) in the range of [-10,10]. Then, implement it in R.

\(f(x) = (3x^4 - 4x^3)/12\)
\(f'(x) = (12x^3 - 12x^2)/12 = x^3-x^2\)
\(f''(x) = 3x^2-2x\)

Let’s take a look at the curve of f(x) and f’(x)

f <- function(x){
  (3*x^4 - 4*x^3)/(12)
}
f_prime <- function(x){
  (x^3 - x^2)
}
curve(f, col = 'blue', xlim=c(-2,2), ylim=c(-0.2,0.5))
curve(f_prime, col = 'red', xlim=c(-2,2), ylim=c(-0.2,0.5),add=TRUE)
abline(h=0)
abline(v=0)

Newton’s Formula:
\[X_{k+1} = X_k = \frac{p(X_k)}{p'(X_k)}\]

By applying Newton’s formula we get,

\(x_1 = x_0 - \frac{(x_0)^3 -(x_0)^2}{3(x_0)^2-2(x_0)}\)

f <- function(x) {
  x - (x^3 - x^2)/(3 * x^2 - 2*x)
}

get_values <- function(X_0) {
  val <- c()
  for(i in 1:10) {
    if(i==1) {
      val[[i]] <- f(X_0)
    } else {
      val[[i]] <- f(val[[i-1]])
    }
  }
  print(val)
}
get_values(1.5)
## [[1]]
## [1] 1.2
## 
## [[2]]
## [1] 1.05
## 
## [[3]]
## [1] 1.004348
## 
## [[4]]
## [1] 1.000037
## 
## [[5]]
## [1] 1
## 
## [[6]]
## [1] 1
## 
## [[7]]
## [1] 1
## 
## [[8]]
## [1] 1
## 
## [[9]]
## [1] 1
## 
## [[10]]
## [1] 1

Ex 2

Explore optimize() in R and try to solve the previous problem.

f <- function(x) {
  (3*x^4 -  4*x^3)/12
}

x_min <- optimize(f, c(-10, 10))
x_min
## $minimum
## [1] 0.9999986
## 
## $objective
## [1] -0.08333333

Here we can confirm the minimum is at 1 and the value of f(x) at the minimum is -0.0833

Ex3

Use any optimization algorithm to find the minimum of \(f(x,y)=(x-1)^2+100(y-x^2)^2\) in the domain \(-10 \le x,y \le 10\). Discuss any issues concerning the optimization process.

I will be using Newton’s method for higher dimension to answer this question.

\(x_{t+1} = x_t - H^{-1} \bigtriangledown f(x,y)\)
\(x_{0} = \begin{bmatrix}x \\y \end{bmatrix} =\begin{bmatrix}0 \\0 \end{bmatrix}\) Starting Value

\(\bigtriangledown f(x,y) = \begin{bmatrix}(x-1)^{2} \\100 (y - x^{2}) ^{2} \end{bmatrix}\)

Hessian matrix by finding second derivative and plugging in starting values

\(f_{xx} = 1200x^2+2-400y\)
\(f_{xy} = -400x\)
\(f_{yy} = 200\)
\(f_{yx} = -400x\)

\(H = \bigtriangledown^2 f(x,y) = \begin{bmatrix}2 & -0 \\-0 & 200 \end{bmatrix}\)

\(H^{-1} = \begin{bmatrix}0.5 & 0 \\0 & 0.005 \end{bmatrix}\)

with t=0, \(x_{1} = x_{0} - H^{-1}\bigtriangledown f(x,y)\)

\(x_{1} = \begin{bmatrix}0 \\0 \end{bmatrix} - \begin{bmatrix}0.5 & 0 \\0 & 0.005 \end{bmatrix}\begin{bmatrix}1 \\0 \end{bmatrix}\)

\(x_{1} = \begin{bmatrix}0 \\0 \end{bmatrix} - \begin{bmatrix}0.5 \\0 \end{bmatrix}\)

\(x_{1} = \begin{bmatrix}-0.5 \\0 \end{bmatrix}\)

From here f(x,y) will converge into a single point as you go through more values of t. The issues I faced was optimizing for a multivariate function. I ended up choosing this optimization algorithm as it was the only one I knew how to use.

Ex4

Explore the optimr package for R and try to solve the previous problem.

library(optimr)
fn <- function(x, y){
  (x - 1)^2 + 100 * (y - x^2)^2
}
optimr(c(-10,10), fn, method = "L-BFGS-B")
## Error in fn(par, ...) : argument "y" is missing, with no default
## $convergence
## [1] 9999
## 
## $par
## [1] NA NA
## 
## $counts
## [1] NA NA
## 
## $message
## [1] "optim method failure\n"

Resources:

Module 3 Lecture Notes and videos.
[https://bbhosted.cuny.edu/webapps/blackboard/content/listContent.jsp?course_id=_2010113_1&content_id=_58466313_1]

Optim package in R
[https://www.rdocumentation.org/packages/optimr/versions/2019-12.16/topics/optimr]