<jupyter_start><jupyter_text>Seminar 20 Interior point method  Reminder- Projected gradient descent- Frank-Wolfe method  Convex optimization problem with equality constraints\begin{equation*}\begin{split}&\min f(x) \\ \text{s.t. } & Ax = b,\end{split}\end{equation*}where $f$ is convex and twice differentiable, $A \in \mathbb{R}^{p \times n}$ and $\mathrm{rank} \; A = p < n$  Dual problemRelation between dual and conjugate functions \begin{equation*}\begin{split}g(\mu) &  = -b^{\top}\mu + \inf_x(f(x) + \mu^{\top}Ax) \\& = -b^{\top}\mu - \sup_x((-A^{\top}\mu)^{\top}x -f(x)) \\& = -b^{\top}\mu - f^*(-A^{\top}\mu)\end{split}\end{equation*}Dual problem$$\max_\mu -b^{\top}\mu - f^*(-A^{\top}\mu)$$**Approach 1**: find conjugate function and solve unconstrained optimization problem **Issues**- it may be not so easy to find solution of the primal problem from the dual one- conjugate function $f^*$ has to be twice differentiable for fast solving of dual problem, but this is not always hold  Optimality conditions- $Ax^* = b$- $f'(x^*) + A^{\top}\mu^* = 0$or$$ \begin{bmatrix} f' & A^{\top} \\ A & 0 \end{bmatrix} \begin{bmatrix} x^{\\*} \\ \mu^{\\*} \end{bmatrix} = \begin{bmatrix} 0 \\ b \end{bmatrix} $$**Approach 2**: solve generally non-linear system with Newton method.**Q**: in what case the system becomes linear?  Newton method for convex optimization problem with equality constraints\begin{equation*}\begin{split}& \min_v f(x) + f'(x)^{\top}v + \frac{1}{2}v^{\top}f''(x)v\\\text{s.t. } & A(x + v) = b\end{split}\end{equation*}From the optimality condition follows $$ \begin{bmatrix} f''(x) & A^{\top} \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -f'(x) \\ 0 \end{bmatrix} $$**Newton direction $v$ is defined only for non-singular matrix!****Q:** how direction $w$ can be interpreted? **Exercise**. Estimate number of iterations required for convergence of Newton method for quadratic objective and linear equality constraints.  Linearization of optimality conditions- $A(x + v) = b \rightarrow Av = 0$- $f'(x + v) + A^{\top}w \approx f'(x) + f''(x)v + A^{\top}w = 0$or- $f''(x)v + A^{\top}w = -f'(x)$  Pseudocode**Important note:** initial point has to lie inside the feasible set!```pythondef NewtonEqualityFeasible(f, gradf, hessf, A, b,                                                       stop_crit, line_search, x0,                                                       tol):        x = x0        n = x.shape[0]        while True:                newton_matrix = [[hessf(x), A.T], [A, 0]]                rhs = [-gradf(x), 0]                w = solve_lin_sys(newton_matrix, rhs)                h = w[:n]                if stop_crit(x, h, gradf(x), **kwargs) < tol:                        break                    alpha = line_search(x, h, f, gradf(x), **kwargs)                x = x + alpha * h            return x```  Stopping criterionEstimate the following difference$$f(x) - \inf_v(\hat{f}(x + v) \; | \; A(x+v) = b),$$where $\hat{f}$ is quadratic approximation of function $f$.To do this multiply both side by $h^{\top}$ from the left $$\langle h^{\top} \rvert \cdot \quad f''(x)h + A^{\top}w = -f'(x)$$and use constraint $Ah = 0$$$h^{\top}f''(x)h = -f'(x)^{\top}h$$Then $$\inf_v(\hat{f}(x + v) \; | \; A(x+v) = b) = f(x) - \frac{1}{2}h^{\top}f''(x)h$$**Summary:** value of $h^{\top}f''(x)h$ is the most natural stopping criterion of Newton method.  Convergence theoremConvergence of the equality constrained Newton method is equivalent to convergence classical Newton method for unconstrained optimization problem.**Theorem**Assume the following conditions hold- level set $S = \{ x \; | \; x \in D(f), \; f(x) \leq f(x_0), \; Ax = b \}$ is closed and $x_0 \in D(f), \; Ax_0 = b$- for any $x \in S$ and $\tilde{x} \in S$ hessian $f''(x)$ is Lipschitz- in the set $S$ $\|f''(x)\|_2 \leq M $ and norm of the inverse matrix of the KKT system is bounded aboveThen, Newton method converges to the pair $(x^*, \mu^*)$ - linearly when iterands far from the solution- quadratically in sufficiently small neighbourhood of the solution  Infeasible starting point- Newton method requires that starting point is feasible- But what to do if this requirement is violated? Example of hard case is the problem in which domain of the objective function is not $\mathbb{R}^n$.- Assume starting point is infeasible, then KKT conditions can be written as$$\begin{bmatrix}f''(x) & A^{\top}\\A & 0\end{bmatrix}\begin{bmatrix}v\\w\end{bmatrix} = -\begin{bmatrix}f'(x)\\{\color{red}{Ax - b}}\end{bmatrix}$$- If $x$ is feasible, then the system is equivalent to the system for Newton method with feasible starting point  Primal-dual interpretation- Method is called *primal-dual*, if every iteration updates both primal and dual variables- In particular, re-write optimality condition in the following form$$r(x^*, \mu^*) = (r_p(x^*, \mu^*), r_d(x^*, \mu^*)) = 0,$$where $r_p(x, \mu) = Ax - b$ and $r_d(x, \mu) = f'(x) + A^{\top}\mu$- Solve system with Newton method:$$r(y + z) \approx r(y) + Dr(y)z = 0$$ - Primal-dual direction in Newton method is defined as the solution of the following system$$Dr(y)z = -r(y)$$or more detailed$$\begin{bmatrix}f''(x) & A^{\top}\\A & 0\end{bmatrix}\begin{bmatrix}z_p\\z_d\end{bmatrix} = -\begin{bmatrix}r_p(x, \mu)\\r_d(x, \mu)\end{bmatrix}= - \begin{bmatrix}f'(x) + A^{\top}\mu\\Ax - b\end{bmatrix}$$- Replace $z_d^+ = \mu + z_d$ and obtain$$\begin{bmatrix}f''(x) & A^{\top}\\A & 0\end{bmatrix}\begin{bmatrix}z_p\\z_d^+\end{bmatrix}= - \begin{bmatrix}f'(x)\\Ax - b\end{bmatrix}$$- This system is equivalent to the previous one in the following notation$$v = z_p \qquad w = z_d^+ = \mu + z_d $$- Newton method gives direction for update primal variable and updated value for dual variable  Pseudocode```pythondef NewtonEqualityInfeasible(f, grad, hessf, A, b,                                                           stop_crit, line_search, x0,                                                           mu0, tol):        x = x0        mu = mu0        n = x.shape[0]        while True:                z_p, z_d = ComputeNewtonStep(hessf(x), A, b)                if stop_crit(x, z_p, z_d, grad(x), **kwargs) < tol:                        break                    alpha = line_search(x, z_p, z_d,                                                         f, grad(x), **kwargs)                x = x + alpha * z_p                mu = mu + alpha * z_d            return x```  Stopping criterion and backtracking- Update $r_p$ after step $z_p$$$A(x + \alpha z_p) - b = [A(x + z_p) = b] = Ax + \alpha(b - Ax) - b = (1 - \alpha)(Ax - b)$$- Total update after $k$ steps$$r^{(k)} = \prod_{i=0}^{k-1}(1 - \alpha^{(i)})r^{(0)}$$- Stopping criterion: $Ax = b$ and $\|r(x, \mu)\|_2 \leq \varepsilon$ - Backtracking: $c \in (0, 1/2)$, $\beta = (0, 1)$```pythondef linesearch(r, x, mu, z_p, z_d, c, beta):    alpha = 1    while norm(r(x + alpha * z_p, mu + alpha * z_d)) >=     (1 - c * alpha) * norm(r(x, mu)):         alpha *= beta       return alpha```  Convergence theoremThe theorem result is similar to the case of feasible starting point**Theorem.** Assume that- sublevel set $S = \{(x, \mu) \; | \; x \in D(f), \; \| r(x, \mu) \|_2 \leq \| r(x_0, \mu_0)  \|_2 \}$ is closed- in the set $S$ norm of the inverse KKT matrix is bounded- hessian is Lipschitz in $S$.Then convergence is - linear far from the solution and- quadratic in the sufficiently small neighbourhood.  General convex optimization problem\begin{equation*}\begin{split}& \min_{x \in \mathbb{R}^n} f_0(x)\\\text{s.t. } & f_i (x) \leq 0 \qquad i=1,\ldots,m\\& Ax = b,\end{split}\end{equation*}where $f_i$ are convex and twice smoothly differentiable, $A \in \mathbb{R}^{p \times n}$ and $\mathrm{rank} \; A = p < n$. Assume that the problem is strictly feasible, i.e. Slater conditions are satisfied.  Optimality conditions- Primal feasibility$$Ax^* = b, \; f_i(x^*) \leq 0, \; i = 1,\ldots,m$$- Dual feasibility$$\lambda^* \geq 0$$- Lagrangian stationarity$$f'_0(x^*) + \sum_{i=1}^m \lambda^*_if'_i(x^*) + A^{\top}\mu^* = 0$$- Complementary slackness condition$$\lambda^*_i f_i(x^*) = 0, \qquad i = 1,\ldots, m$$  Idea- Reduce the problem with **inequality** constraints to sequence of **equality** constrained problems- Use methods for solving equality constrained problems \begin{equation*}\begin{split}& \min f_0(x) + \sum_{i=1}^m I_-(f_i(x))\\\text{s.t. } & Ax = b,\end{split}\end{equation*}where $I_-$ is an indicator function$$I_-(u) = \begin{cases}0, & u \leq 0\\\infty, & u > 0\end{cases}$$**Issue.** Now objective function **is not differentiable**.  Logarithmic barier**Idea.** Approximate function $I_-(u)$ with function$$\hat{I}_-(u) = -t\log(-u),$$where $t > 0$ is fixed parameter.- Functions $I_-(u)$ and $\hat{I}_-(u)$ are convex and non-decreasing- But $\hat{I}_-(u)$ is **differentiable** and approximates $I_-(u)$ while $t \to 0$<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt
plt.rc("text", usetex=True)
import numpy as np

x = np.linspace(-2, 0, 100000, endpoint=False)
plt.figure(figsize=(10, 6))
for t in [0.1, 0.5, 1, 1.5, 2]:
    plt.plot(x, -t * np.log(-x), label=r"$t = " + str(t) + "$")
plt.legend(fontsize=20)
plt.xticks(fontsize=20)
plt.yticks(fontsize=20)
_ = plt.xlabel("$u$", fontsize=26)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1836383207750269, 'fraction_numerical': 0.010441334768568353, 'mean_word_length': 3.131169408626056, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '591384', 'license': 'MIT', 'n_tokens_mistral': 3244, 'n_tokens_neox': 2993, 'n_words': 999, 'path': 'Spring2017-2019/20-InteriorPoint/Seminar20en.ipynb', 'repo_name': 'Jhomanik/MIPT-Opt', 'size': '9290'}