General optimization problems

1. Give an explicit solution of the following LP.

2. Give an explicit solution of the following LP.

where $a \neq 0$

3. Give an explicit solution of the following LP.

where $l \preceq u$

4. Give an explicit solution of the following LP.

This problem can be considered as a simplest portfolio optimization problem.

5. Give an explicit solution of the following LP.

where $\alpha$ is an integer between $0$ and $n$. What happens if $\alpha$ is not an integer (but satisfies $0 \leq \alpha \leq n$)? What if we change the equality to an inequality $1^\top x \leq \alpha$?

6. Give an explicit solution of the following QP.

where $A \in \mathbb{S}^n_{++}, c \neq 0$. What is the solution if the problem is not convex $(A \notin \mathbb{S}^n_{++})$ (Hint: consider eigendecomposition of the matrix: $A = Q \mathbf{diag}(\lambda)Q^\top = \sum\limits_{i=1}^n \lambda_i q_i q_i^\top$) and different cases of $% 0, \lambda=0, \lambda<0 %]]>$?

7. Give an explicit solution of the following QP.

where $A \in \mathbb{S}^n_{++}, c \neq 0, x_c \in \mathbb{R}^n$.

8. Give an explicit solution of the following QP.

where $A \in \mathbb{S}^n_{++}, B \in \mathbb{S}^n_{+}$.

9. Consider the equality constrained least-squares problem

where $A \in \mathbb{R}^{m \times n}$ with $\mathbf{rank }A = n$, and $C \in \mathbb{C}^{k \times n}$ with $\mathbf{rank }C = k$. Give the KKT conditions, and derive expressions for the primal solution $x^*$ and the dual solution $\lambda^*$.

10. Derive the KKT conditions for the problem

where $y \in \mathbb{R}^n$ and $s \in \mathbb{R}^n$ are given with $y^\top s = 1$. Verify that the optimal solution is given by

11. Supporting hyperplane interpretation of KKT conditions. Consider a convex problem with no equality constraints

Assume, that $\exists x^* \in \mathbb{R}^n, \mu^* \in \mathbb{R}^m$ satisfy the KKT conditions

Show that

for all feasible $x$. In other words the KKT conditions imply the simple optimality criterion or $\nabla f_0(x^*)$ defines a supporting hyperplane to the feasible set at $x^*$.