(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
[[Category:ECE PhD Qualifying Exams]][[Category:ECE PhD Qualifying Exams]][[Category:ECE PhD Qualifying Exams]]
+
[[Category:ECE]]
 +
[[Category:QE]]
 +
[[Category:CNSIP]]
 +
[[Category:problem solving]]
 +
[[Category:automatic control]]
 +
[[Category:optimization]]
  
−
=QE2013_AC-3_ECE580=
+
<center>
 +
<font size= 4>
 +
[[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]]
 +
</font size>
  
 +
<font size= 4>
 +
Automatic Control (AC)
  
 +
Question 3: Optimization
 +
</font size>
  
−
Put your content here . . .
+
August 2013
 +
</center>
 +
----
 +
----
 +
:Student answers and discussions for [[QE2013_AC-3_ECE580-1|Part 1]],[[QE2013_AC-3_ECE580-2|2]],[[QE2013_AC-3_ECE580-3|3]],[[QE2013_AC-3_ECE580-4|4]],[[QE2013_AC-3_ECE580-5|5]]
 +
----
 +
'''1.(20 pts) In some of the optimization methods, when minimizing a given function f(x), we select an intial guess <math>x^{(0)}</math> and a real symmetric positive definite matrix <math>H_{0}</math>. Then we computed <math>d^{(k)} = -H_{k}g^{(k)}</math>, where <math>g^{(k)} = \nabla f( x^{(k)} )</math>, and <math>x^{(k+1)} = x^{(k)} + \alpha_{k}d^{(k)}</math>, where'''
 +
<br>
 +
<math> \alpha_{k} = arg\min_{\alpha \ge 0}f(x^{(k)} + \alpha d^{(k)}) .</math>
 +
<br>
 +
'''Suppose that the function we wish to minimize is a standard quadratic of the form,'''
 +
<br>
 +
<math> f(x) = \frac{1}{2} x^{T} Qx - x^{T}b+c, Q = Q^{T} > 0. </math>
 +
<br><br>
 +
'''(i)(10 pts) Find a closed form expression for <math>\alpha_k</math> in terms of <math>Q, H_k, g^{(k)}</math>, and  <math>d^{(k)}; </math>'''
 +
<br>
 +
'''(ii)(10 pts) Give a sufficient condition on <math>H_k</math> for <math>\alpha_k</math> to be positive.'''
  
 +
:'''Click [[QE2013_AC-3_ECE580-1|here]] to view [[QE2013_AC-3_ECE580-1|student answers and discussions]]'''
 +
----
  
 +
'''Problem 2. (20 pts) [(i) (10 pts)] Consider the one-point crossover of a chromosome in the schema'''
 +
<br>
 +
H = * 1 * 0 1 0 *
 +
<br>
 +
'''where the probability that a chromosome is chosen for crossover is <math>p_c = 0.5.</math>  Find an upper bound on the probability that a chromosome from H will be destroyed by the one-point crossover.'''
 +
<br><br>
 +
'''[(ii) (10 pts)] Consider a chromosome in the schema'''
 +
<br>
 +
H = * 1 * 0 * * *
 +
<br>
 +
'''Find the probability that the mutation operation destroys the schema, where the probability of random change of each symbol of the chromosome is <math>p_m = 0.1</math> independently.'''
  
 +
:'''Click [[QE2013_AC-3_ECE580-2|here]] to view [[QE2013_AC-3_ECE580-2|student answers and discussions]]'''
  
−
[[ ECE PhD Qualifying Exams|Back to ECE PhD Qualifying Exams]]
+
----
 +
 
 +
'''Problem 3. (20 pts) [(i) (10 pts)] Convert the following optimization problem into a linear programming problem and solve it; '''
 +
<br>
 +
maximize  <math> -|x_1| -|x_2| -|x_3| </math>
 +
<br>
 +
subject to
 +
<br>
 +
<math>\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} .</math>
 +
<br><br>
 +
'''[(ii) (10 pts)] Construct the dual program of the linear program above and solve it. '''
 +
 
 +
:'''Click [[QE2013_AC-3_ECE580-3|here]] to view [[QE2013_AC-3_ECE580-3|student answers and discussions]]'''
 +
----
 +
'''Problem 4. (20pts) Consider the following model of a discrete-time system, '''
 +
<br>
 +
<math> x(k+1) = x(k) + 2u(k), x(0) = 3, 0 \le k \le 2</math>
 +
<br>
 +
'''Use the Lagrange multiplier approach to calculate the optimal control sequence'''
 +
<br>
 +
{u(0), u(1), u(2)}
 +
<br>
 +
''' that transfers the initial state x(0) to x(3) = 9 while minimizing the performance index'''
 +
<br>
 +
<math> J = \frac{1}{2} \sum_{k=0}^2 u(k)^2 = \frac{1}{2}u^Tu. </math>
 +
<br>
 +
''' Hint: Use the system model to obtain a constraint of the form, <math>Au = b, A \in R^{1 \times 3}. </math>'''
 +
 
 +
:'''Click [[QE2013_AC-3_ECE580-4|here]] to view [[QE2013_AC-3_ECE580-4|student answers and discussions]]'''
 +
----
 +
 
 +
<br> '''Problem 5. (20pts) Find minimizers and maximizers of the function, '''
 +
<br>
 +
<math> f(x) = (a^Tx)(b^Tx), x \in R^3, </math>
 +
<br>
 +
'''subject to'''
 +
<br>
 +
<math> x_1 + x_2 = 0 </math>
 +
<br>
 +
<math> x_2 + x_3 = 0, </math>
 +
<br>
 +
'''where'''
 +
<br>
 +
<math>a = \begin{bmatrix}
 +
  0  \\
 +
  1 \\
 +
  0
 +
\end{bmatrix}</math> and <math>b = \begin{bmatrix}
 +
  1  \\
 +
  0 \\
 +
  1
 +
\end{bmatrix}</math>
 +
 
 +
:'''Click [[QE2013_AC-3_ECE580-5|here]] to view [[QE2013_AC-3_ECE580-5|student answers and discussions]]'''
 +
----
 +
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]

Latest revision as of 11:23, 25 March 2015


ECE Ph.D. Qualifying Exam

Automatic Control (AC)

Question 3: Optimization

August 2013

Student answers and discussions for Part 1,2,3,4,5

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

Back to ECE QE page

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=QE2013_AC-3_ECE580&oldid=69571"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood