Automatic Control (AC)
Question 3: Optimization WORK IN PROGRESS
August 2013
1.(20 pts) In some of the optimization methods, when minimizing a given function f(x), we select an intial guess $ x^{(0)} $ and a real symmetric positive definite matrix $ H_{0} $. Then we computed $ d^{(k)} = -H_{k}g^{(k)} $, where $ g^{(k)} = \nabla f( x^{(k)} ) $, and $ x^{(k+1)} = x^{(k)} + \alpha_{k}d^{(k)} $, where
$ \alpha_{k} = arg\min_{\alpha \ge 0}f(x^{(k)} + \alpha d^{(k)}) . $
Suppose that the function we wish to minimize is a standard quadratic of the form,
$ f(x) = \frac{1}{2} x^{T} Qx - x^{T}b+c, Q = Q^{T} > 0. $
(i)(10 pts) Find a closed form expression for $ \alpha_k $ in terms of $ Q, H_k, g^{(k)}, and d^{(k)}; $
(ii)(10 pts) Give a sufficient condition on $ H_k $ for $ \alpha_k $ to be positive.
- Click here to view student answers and discussions
Problem 2. (20 pts) [(i) (10 pts)] Consider the one-point crossover of a chromosome in the schema
H = * 1 * 0 1 0 *
where the probability that a chromosome is chosen for crossover is $ p_c = 0.5. $ Find an upper bound on the probability that a chromosome from H will be destroyed by the one-point crossover.
[(ii) (10 pts)] Consider a chromosome in the schema
H = * 1 * 0 * * *
Find the probability that the mutation operation destroys the schema, where the probability of random change of each symbol of the chromosome is $ p_m = 0.1 $ independently.
- Click here to view student answers and discussions
Problem 3. (20 pts) [(i) (10 pts)] Convert the following optimization problem into a linear programming problem and solve it;
maximize $ -|x_1| -|x_2| -|x_3| $
subject to
$ \begin{bmatrix} 1 & 1 &-1 \\ 0 & -1 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} . $
[(ii) (10 pts)] Construct the dual program of the linear program above and solve it.
- Click here to view student answers and discussions
Problem 4. (20pts) Use any simplex method to solve the following linear program.
Maximize x1 + 2x2 S'ubject to $ -2x_1+x_2 \le 2 $ $ x_1-x_2 \ge -3 $ $ x_1 \le -3 $ $ x_1 \ge 0, x_2 \ge 0. $
- Click here to view student answers and discussions
Problem 5.(20pts) Solve the following problem:
Minimize $ -x_1^2 + 2x_2 $ Subject to $ x_1^2+x_2^2 \le 1 $ $ x_1 \ge 0 $ $ x_2 \ge 0 $
(i)(10pts) Find the points that satisfy the KKT condition.
(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.
- Click here to view student answers and discussions
