QE2017 AC-3 ECE580 - Rhea

Automatic Control (AC)

Question 3: Optimization

August 2017

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

1.(20 pts) Considern the following linear program,

minimize

2x_{1} + x_{2}

,
subject to

x_{1} + 3x_{2} \geq 6

2x_{1} + x_{2} \geq 4

x_{1} + x_{2} \leq 3

x_{1} \geq 0

,

x_{2} \geq 0

.

Convert the above linear program into standard form and find an initial basix feasible solution for the program in standard form.

2.(20 pts)

(15 pts) FInd the largest range of the step-size, $\alpha$ , for which the fixed step gradient descent algorithm is guaranteed to convege to the minimizer of the quadratic function

f = \frac{1}{2} x^{T}Qx - b^{T}x

starting from an arbitary initial condition $x^{(0)} \in \mathbb{R}^{n}$ , where $x \in \mathbb{R}^{n}$ , and $Q = Q^{T} > 0$ .

(5 pts) Find the largest range of the step size, $\alpha$ , for which the fixed step gradient descent algorithm is guaranteed to converge to the minimizer of the quadratic function

f= 6x_{1}^{2}+2x_{2}^{2}-5

,

starting from an arbitrary initial condition $x^{(0)} \in \mathbb{R}^{n}$

3. (20 pts) Is the function

Alumni Liaison