Automatic Control (AC)

Question 3: Optimization

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) Consider the following model of a discrete-time system, **

$ x(k+1) = x(k) + 2u(k), x(0) = 3, 0 \le k \le 2 $

**Use the Lagrange multiplier approach to calculate the optimal control sequence**

{u(0), u(1), u(2)}

** that transfers the initial state x(0) to x(3) = 9 while minimizing the performance index**

$ J = \frac{1}{2} \sum_{k=0}^2 u(k)^2 = \frac{1}{2}u^Tu. $

** Hint: Use the system model to obtain a constraint of the form, $ Au = b, A \in R^{1 \times 3}. $**

**Click here to view student answers and discussions**

**Problem 5. (20pts) Find minimizers and maximizers of the function, **

$ f(x) = (a^Tx)(b^Tx), x \in R^3, $

**subject to**

$ x_1 + x_2 = 0 $

$ x_2 + x_3 = 0, $

**where**

$ a = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} $ and $ b = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} $

**Click here to view student answers and discussions**