# Background

## Extreme value (Weierstrass) theorem

Пусть $S \subset \mathbb{R}^n$ - компактное множество и пусть $f(x)$ непрерывная функция на $S$. Тогда точка глобального минимума функции $f (x)$ на $S$ существует.

## Lagrange multipliers

Consider simple yet practical case of equality constraints:

The basic idea of Lagrange method implies switch from conditional to unconditional optimization through increasing the dimensionality of the problem:

# General formulations and conditions

Будем говорить, что задача имеет решение, если множество таких $x^* \in S$, что в них достигается минимум или инфимум данной функции не пусто

## Unconstrained optimization

### General case

Let $f(x): \mathbb{R}^n \to \mathbb{R}$ be a twice differentiable function.

If $x^*$ - is a local minimum of $f(x)$, then:

If $f(x)$ at some point $x^*$ satisfies the following conditions:

then (if necessary condition is also satisfied) $x^*$ is a local minimum(maximum) of $f(x)$.

### Convex case

It should be mentioned, that in convex case (i.e., $f(x)$ is convex) necessary condition becomes sufficient. Moreover, we can generalize this result on the class of non-differentiable convex functions.

Let $f(x): \mathbb{R}^n \to \mathbb{R}$ - convex function, then the point $x^*$ is the solution of $\text{(UP)}$ if and only if:

One more important result for convex constrained case sounds as follows. If $f(x): S \to \mathbb{R}$ - convex function defined on the convex set $S$, then:

• Any local minima is the global one.
• The set of the local minimizers $S^*$ is convex.
• If $f(x)$ - strongly convex function, then $S^*$ contains only one single point $S^* = x^*$.

## Optimization with equality conditions

### Intuition

Things are pretty simple and intuitive in unconstrained problem. In this section we will add one equality constraint, i.e.

We will try to illustrate approach to solve this problem through the simple example with $f(x) = x_1 + x_2$ and $h(x) = x_1^2 + x_2^2 - 2$

Итого, имеем: чтобы двигаясь из $x_F$ по бюджетному множеству в сторону уменьшения функции, нам необходимо гарантировать два условия:

Пусть в процессе такого движения мы пришли в точку, где $\nabla f(x) = \lambda \nabla h(x)$

Тогда мы пришли в точку бюджетного множества, двигаясь из которой не получится уменьшить нашу функцию. Это и есть локальный минимум в ограниченной задаче:)

Так давайте определим функцию Лагранжа (исключительно для удобства):

Тогда точка $x^*$ - локальный минимум описанной выше задачи, тогда и только тогда, когда:

Сразу же заметим, что $L(x^*, \lambda^*) = f(x^*)$.

### General formulation

Solution

Пусть $f(x)$ и $h_i(x)$ дважды дифференцируемы в точке $x^*$ и непрерывно дифференцируемы в некоторой окрестности $x^*$. Условия локального минимума для $x \in \mathbb{R}^n, \lambda \in \mathbb{R}^m$ запишутся как

В заисимости от поведения гессиана критические точки могут иметь разный характер

## Optimization with inequality conditions

### Example

Таким образом, если ограничения типа неравенств неактивны в задаче БМ, то можно не парится и выписывать решение задачи БМ. Однако, так бывает не всегда:) Рассмотрим второй игрушечный пример $f(x) = (x_1 - 1.1)^2 + (x_2 - 1.1)^2 \;\;\;\; g(x) = x_1^2 + x_2^2 - 1$

Итого, мы имеем проблему:

И два возможных случая:

1. $% 0 \end{split} %]]>$

2. $% 0 \\ & \langle y , \nabla^2_{xx} L(x^*, \mu^*) y \rangle \geq 0, \;\;\; \forall y \in \mathbb{R}^n : \nabla g(x^*)^\top y = 0 \end{split} %]]>$

Объединяя два возможных случая, можно записать общие условия для задачи:

Определим функцию Лагранжа:

Тогда точка $x^*$ - локальный минимум описанной выше задачи, тогда и только тогда, когда:

Сразу же заметим, что $L(x^*, \mu^*) = f(x^*)$. Условия $\mu^* > 0 , (1), (4)$ при этом реализуют первый сценарий, а условия $\mu^* > 0 , (1), (3)$ - второй.

### General formulation

Данная формулировка представляет собой общую задачу математического программирования. С этого момента и далее мы рассматриваем только $\textbf{регулярные}$ задачи. Это очень важное с формальной точки зрения замечание. Желающих разобраться подробнее просим обратиться к гуглу.

Solution

# Karush-Kuhn-Tucker conditions

Пусть $x^*$ решение задачи математического программирования, и функции $f, h_j, g_i$ дифференцирумы. Тогда найдутся такие $\lambda^*$ и $\mu^*$, что выполнены следующие условия:

• $\nabla_x L(x^*, \lambda^*, \mu^*) = 0$
• $\nabla_\lambda L(x^*, \lambda^*, \mu^*) = 0$
• $\mu^*_j \geq 0$
• $\mu^*_j g_j(x^*) = 0$
• $g_j(x^*) \leq 0$

Эти условия являются достаточными, если задача регулярна, т. е. если: 1) данная задача есть задача выпуклой оптимизации (т. е. функции $f$ и $g_i$ выпуклые, $h_i$ - аффинные) и выполнено условие Слейтера; либо 2) выполнена сильная двойственность.