(6 intermediate revisions by the same user not shown)
Line 14: Line 14:
 
Automatic Control (AC)
 
Automatic Control (AC)
  
−
Question 3: Optimization   WORK IN PROGRESS
+
Question 3: Optimization
 
</font size>
 
</font size>
  
Line 21: Line 21:
 
----
 
----
 
----
 
----
−
:Student answers and discussions for [[QE2012_AC-3_ECE580-1|Part 1]],[[QE2012_AC-3_ECE580-2|2]],[[QE2012_AC-3_ECE580-2|3]],[[QE2012_AC-3_ECE580-4|4]],[[QE2012_AC-3_ECE580-5|5]]
+
: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'''  
 
'''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'''  
Line 27: Line 27:
 
<math> \alpha_{k} = arg\min_{\alpha \ge 0}f(x^{(k)} + \alpha d^{(k)}) .</math>
 
<math> \alpha_{k} = arg\min_{\alpha \ge 0}f(x^{(k)} + \alpha d^{(k)}) .</math>
 
<br>
 
<br>
−
Suppose that the function we wish to minimize is a standard quadratic of the form,
+
'''Suppose that the function we wish to minimize is a standard quadratic of the form,'''
 
<br>
 
<br>
 
<math> f(x) = \frac{1}{2} x^{T} Qx - x^{T}b+c, Q = Q^{T} > 0. </math>
 
<math> f(x) = \frac{1}{2} x^{T} Qx - x^{T}b+c, Q = Q^{T} > 0. </math>
−
<br>
+
<br><br>
−
'''(i)(10 pts) Find the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form'''
+
'''(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>'''
−
<math>  
+
−
\begin{align}
+
−
1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3},  
+
−
\end{align}
+
−
</math>  
+
−
 
+
−
'''where <span class="texhtml">''N'' − 1</span> is the number of steps performed in the uncertainty range reduction process. '''
+
−
 
+
 
<br>  
 
<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]]'''
 +
----
  
−
<br> '''(ii)(10 pts)''' It is known that the minimizer of a certain function f(x) is located in the interval[-5, 15]. What is the minimal number of iterations of the Fibonacci method required to box in the minimizer within the range 1.0? Assume that the last useful value of the factor reducing the uncertainty range is 2/3, that is
+
'''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.'''
  
−
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>
+
:'''Click [[QE2013_AC-3_ECE580-2|here]] to view [[QE2013_AC-3_ECE580-2|student answers and discussions]]'''
  
−
:'''Click [[QE2012_AC-3_ECE580-1|here]] to view [[QE2012_AC-3_ECE580-1|student answers and discussions]]'''
 
 
----
 
----
  
−
'''Problem 2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function'''  
+
'''Problem 3. (20 pts) [(i) (10 pts)] Convert the following optimization problem into a linear programming problem and solve it; '''
−
 
+
<br>
−
      <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
+
maximize  <math> -|x_1| -|x_2| -|x_3| </math>
−
      <math> =\frac{1}{2}x^T
+
<br>
−
\begin{bmatrix}
+
subject to
−
   1 & 1 \\
+
<br>
−
   1 & 2
+
<math>\begin{bmatrix}
−
  \end{bmatrix}x-x^T\begin{bmatrix}
+
   1 & 1 &-1  \\
 +
   0 & -1 & 0
 +
  \end{bmatrix} \begin{bmatrix}
 +
  x_1  \\
 +
  x_2 \\
 +
  x_3
 +
\end{bmatrix} = \begin{bmatrix}
 
   2  \\
 
   2  \\
 
   1
 
   1
−
  \end{bmatrix} + 3.</math>
+
  \end{bmatrix} .</math>  
 +
<br><br>
 +
'''[(ii) (10 pts)] Construct the dual program of the linear program above and solve it. '''
  
−
Where <span class="texhtml">''x''<sup>(0)</sup></span> is arbitrary.
+
:'''Click [[QE2013_AC-3_ECE580-3|here]] to view [[QE2013_AC-3_ECE580-3|student answers and discussions]]'''
−
 
+
----
−
:'''Click [[QE2012_AC-3_ECE580-2|here]] to view [[QE2012_AC-3_ECE580-2|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]]'''
 
----
 
----
  
−
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where '''
+
<br> '''Problem 5. (20pts) Find minimizers and maximizers of the function, '''
−
 
+
<br>
−
<math>A = \begin{bmatrix}
+
<math> f(x) = (a^Tx)(b^Tx), x \in R^3, </math>
−
  1 & 0 &-1  \\
+
<br>
−
  0 & 1 & 0  \\
+
'''subject to'''
−
  0 & -1& 0
+
<br>
−
\end{bmatrix}, b = \begin{bmatrix}
+
<math> x_1 + x_2 = 0 </math>
 +
<br>
 +
<math> x_2 + x_3 = 0, </math>
 +
<br>
 +
'''where'''
 +
<br>
 +
<math>a = \begin{bmatrix}
 
   0  \\
 
   0  \\
−
   2 \\
+
   1 \\
 +
  0
 +
\end{bmatrix}</math> and <math>b = \begin{bmatrix}
 +
  1  \\
 +
  0 \\
 
   1
 
   1
−
  \end{bmatrix}</math>  
+
  \end{bmatrix}</math>
−
 
+
−
 
+
−
 
+
−
'''Find the minimum length vector <math>x^{(\ast)}</math> that minimizes <math>\| Ax -b\|^{2}_2</math> '''
+
−
 
+
−
:'''Click [[QE2012_AC-3_ECE580-3|here]] to view [[QE2012_AC-3_ECE580-3|student answers and discussions]]'''
+
−
----
+
−
'''Problem 4. (20pts) Use any simplex method to solve the following linear program. '''
+
−
 
+
−
            <span class="texhtml">''Maximize''</span>'''    <span class="texhtml">''x''<sub>1</sub> + 2''x''<sub>2</sub></span>'''
+
−
        <span class="texhtml">''S'ubject to''</span>'''    <math>-2x_1+x_2 \le 2</math>'''
+
−
                        <math>x_1-x_2 \ge -3</math>
+
−
                        <math>x_1 \le -3</math>
+
−
                        <math>x_1 \ge 0, x_2 \ge 0.</math>
+
−
 
+
−
:'''Click [[QE2012_AC-3_ECE580-4|here]] to view [[QE2012_AC-3_ECE580-4|student answers and discussions]]'''
+
−
----
+
−
 
+
−
<br> '''Problem 5.(20pts) Solve the following problem:'''
+
−
 
+
−
            <span class="texhtml">''Minimize''</span>'''    <math>-x_1^2 + 2x_2</math>'''
+
−
        <span class="texhtml">''Subject to''</span>'''    <math>x_1^2+x_2^2 \le 1</math>'''
+
−
                        <math> x_1 \ge 0</math>
+
−
                        <math>x_2 \ge 0</math>
+
−
 
+
−
'''(i)(10pts) Find the points that satisfy the KKT condition.'''
+
−
 
+
−
 
+
−
 
+
−
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''
+
  
−
:'''Click [[QE2012_AC-3_ECE580-5|here]] to view [[QE2012_AC-3_ECE580-5|student answers and discussions]]'''
+
:'''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]]
 
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]

Latest revision as of 12: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

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett