Automatic Control (AC)

Question 3: Optimization

August 2016

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 basic 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 converge 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

$f(x_{1}, x_{2})=\frac{1}{(x_{1}-2)^{2} + (x_{2}+1)^{2}+3}$

locally convex, concave, or neither in the neighborhood of the point $[2 -1]^{T}$? Justify your answer by giving all the details of your argument.

4. (20 pts) Solve the following optimization problem:

optimize $x_{1}x_{2}$

subject to $x_{1}+x_{2}+x_{3}=1$

$x_{1}+x_{2}-x_{3}=0$

5. (20 pts) Solve the following optimization problem:

maximize $14x_{1}-x_{1}^{2}+6x_{2}-x_{2}^{2}+7$

subject to $x_{1}+x_{2} \leq 2$

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