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  WORK IN PROGRESS
 +
</font size>
  
−
Put your content here . . .
+
August 2013
 +
</center>
 +
----
 +
----
 +
: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]]
 +
----
 +
'''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>
 +
'''(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'''
 +
<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>
  
  
−
[[ ECE PhD Qualifying Exams|Back to ECE PhD Qualifying Exams]]
+
<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
 +
 
 +
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>
 +
 
 +
:'''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'''
 +
 
 +
      <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
 +
      <math>  =\frac{1}{2}x^T
 +
\begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix}x-x^T\begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix} + 3.</math>
 +
 
 +
Where <span class="texhtml">''x''<sup>(0)</sup></span> is arbitrary.
 +
 
 +
:'''Click [[QE2012_AC-3_ECE580-2|here]] to view [[QE2012_AC-3_ECE580-2|student answers and discussions]]'''
 +
 
 +
----
 +
 
 +
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where '''
 +
 
 +
<math>A = \begin{bmatrix}
 +
  1 & 0 &-1  \\
 +
  0 & 1 & 0  \\
 +
  0 & -1& 0
 +
\end{bmatrix}, b = \begin{bmatrix}
 +
  0  \\
 +
  2 \\
 +
  1
 +
\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]]'''
 +
----
 +
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]

Revision as of 13:36, 23 January 2015


ECE Ph.D. Qualifying Exam

Automatic Control (AC)

Question 3: Optimization WORK IN PROGRESS

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 the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form $ \begin{align} 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, \end{align} $

where N − 1 is the number of steps performed in the uncertainty range reduction process.




(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

$ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $

Click here to view student answers and discussions

Problem 2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function 

      $ f = \frac{1}{2}x^TQx - x^Tb+c  $
     $   =\frac{1}{2}x^T  \begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix}x-x^T\begin{bmatrix}   2  \\   1  \end{bmatrix} + 3. $

Where x(0) is arbitrary.

Click here to view student answers and discussions

Problem 3. (20pts) For the system of linear equations,$ Ax=b $ where

$ A = \begin{bmatrix} 1 & 0 &-1 \\ 0 & 1 & 0 \\ 0 & -1& 0 \end{bmatrix}, b = \begin{bmatrix} 0 \\ 2 \\ 1 \end{bmatrix} $


Find the minimum length vector $ x^{(\ast)} $ that minimizes $ \| Ax -b\|^{2}_2 $

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

Back to ECE QE page

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

Alumni Liaison

Prof. Math. Ohio State and Associate Dean
Outstanding Alumnus Purdue Math 2008

Jeff McNeal