# General optimization problems

## General optimization problems

1. Linear Least squares Write down exact solution of the linear least squares problem:

\|Ax-b\|^2 \to \min_{x \in \mathbb{R}^n}, A \in \mathbb{R}^{m \times n}

Consider three cases:

1. m < n
2. m = n
3. m > n
2. To successfully write a test on optimization methods, a student must spend at least \mathrm{K} kilocalories. The evening before the test, he goes to the store to buy food for dinner. There are m items in the store, the unit price of each item is p_i, i = 1, \ldots , m. It is also known that each item’s i-th unit gives the student energy equal to k_i kilocalories. Formulate the problem of determining the contents of a minimum value basket for the successful writing of a test. Is this a convex problem? Why?

3. Give an explicit solution of the following LP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & Ax = b \end{split}

4. Give an explicit solution of the following LP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & a^\top x ≤ b, \end{split}

where a \neq 0

5. Give an explicit solution of the following LP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & l \preceq x \preceq u, \end{split}

where l \preceq u

6. Give an explicit solution of the following LP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & 1^\top x = 1, \\ & x \succeq 0 \end{split}

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

7. Give an explicit solution of the following LP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & 1^\top x = \alpha, \\ & 0 \preceq x \preceq 1, \end{split}

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?

8. Give an explicit solution of the following QP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & x^\top A x \leq 1, \end{split}

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 \lambda >0, \lambda=0, \lambda<0?

9. Give an explicit solution of the following QP.

\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & (x - x_c)^\top A (x - x_c) \leq 1, \end{split}

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

10. Give an explicit solution of the following QP.

\begin{split} & x^\top Bx \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & x^\top A x \leq 1, \end{split}

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

11. Consider the equality constrained least-squares problem

\begin{split} & \|Ax - b\|_2^2 \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & Cx = d, \end{split}

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^*.

12. Derive the KKT conditions for the problem

\begin{split} & \mathbf{tr \;}X - \log\text{det }X \to \min\limits_{X \in \mathbb{S}^n_{++} }\\ \text{s.t. } & Xs = y, \end{split}

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

X^* = I + yy^\top - \dfrac{1}{s^\top s}ss^\top

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

\begin{split} & f_0(x) \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & f_i(x) \leq 0, \quad i = [1,m] \end{split}

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

\begin{split} & \nabla_x L (x^*, \mu^*) = \nabla f_0(x^*) + \sum\limits_{i=1}^m\mu_i^*\nabla f_i(x^*) = 0 \\ & \mu^*_i \geq 0, \quad i = [1,m] \\ & \mu^*_i f_i(x^*) = 0, \quad i = [1,m]\\ & f_i(x^*) \leq 0, \quad i = [1,m] \end{split}

Show that

\nabla f_0(x^*)^\top (x - x^*) \geq 0

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^*.

14. Let X \in \mathbb{R}^{m \times n} with \text{rk} X = n, \Omega \in \mathbb{S}_{++}^n, and W \in \mathbb{R}^{k \times n}. Find matrix G \in \mathbb{R}^{k \times m}, which solves the following optimization problem:

f(G) = \text{tr} \left(G \Omega G^\top \right) \to \min\limits_{GX = W} 1.Consider the problem of projection some point y \in \mathbb{R}^n, y \notin \Delta^n onto the probability simplex \Delta^n. Find 2 ways to solve the problem numerically and compare them in terms of the total computational time, memory requirements and iteration number for n = 10, 100, 1000.

\begin{split} & \|x - y \|_2^2 \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & 1^\top x = 1, \\ & x \succeq 0 \end{split}