Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
ISE 530 Optimization Methods
2Problem 1
Find the roots of the polynomial p(x) = 5x4 − 20x+ 2 in the interval [0, 1] using binary
search.
Problem 2
Consider the function f(x) = 1
4
x4 − x2 + 2x − 1. We want to minimize this function
using Newton’s method. Verify that starting at a point close to 0 or 1 and using Newton’s
method, one would opbtain iterates alternating between close neighborhoods of 0 and 1,
and never converge. Apply Newton’s method to this problem with the Armijo-Goldstein
condition, and backtracking, starting from point 0. Use µ = 0.5 and a backtracking ratio of
0.9. Experiment with other values of µ ∈ (0, 1) and the backtrcking ratio.
Problem 3
One of the most fundamental techniques of statistical analysis is the method of maxi-
mum likelihood estimation. Given a sample set of independently drawn observations from
a parametric distribution, the estimation problem is to determine the values of the distri-
bution parameters that maximize the probability that the observed sample set comes from
this distribution.
Consider, for example, the observations x1 = −0.24, x2 = 0.31, x3 = 0.23, x4 = −1.1,
sampled from a normal distribution. If the mean of the distribution is known to be 0, what is
the maximum likelihood estimate for the standard deviation σ? Construct the log-likelihood
function and maximize it using the golden section search.
2
3Problem 4
Consider the problem:
P: min z = f(x)
such that
gi(x) ≤ 0, i = 1, . . . ,m
where x ∈ Rn, and f(x) is convex and the feasibility region is convex.
The Sequential Unconstrained Minimization Technique is as follows:
Step 0 Disregarding the constraints of P, find a minimal point of the unconstrained problem.
Is this point feasible? If yes, stop. Else, got to step 1.
Step 1 Start with an initial interior feasible point x0 and set k = 1.
Step 2 Use an unconstrained optimization method to find the minimum of the barrier function
B(x, rk) = f(x)− rk
m∑
i=1
1
gi(x)
where, for instance, rk = 10
1−k. Start the minimization process from the point xk−1
and denote the the resulting optimal point by xk.
Step 3 Does the current solution satisfy some stop criterion? If yes, stop. Else, set k := k+1
and go to step 2.
Assuming tha the requirements for applying the above method are all satisfied, carry out
3 iterations to solve the problem:
P: min z = 3x21 − 2x1x2 + 2x22 − 26x1 − 8x2
such that
x1 + 2x2 ≤ 6
x1 − x2 ≥ 1
x1, x2 ≥ 0
3