# First order sufficient condition for minimum

Suppose I have the problem of finding the minimum of some function $f(x,y)$ subject to three inequality constraints $g_1(x,y),g_2(x,y),g_3(x,y) \leq 0$. Further assume the functions $f,g_2,g_3$ to be convex on $\mathbf{R}^2$ ($g_1$ is not convex).

A theorem in my book says that if I find a KKT-point where $g_1$ is inactive (the corresponging Lagrange multiplier is zero), then I know this point to be a local minimum. (Under assumptions that $f,g_2,g_3$ are convex in the neighbourhood of this point).

A corollary to the same theorem says that if all of $f,g_1,g_2,g_3$ are convex, then the local minimum is in fact the global minimum.

Now to what confuses me: In the solution to the above described problem, the found KKT-point (with $g_1$ being inactive) is said to be the global minimum as a cause of the above theorem and corollary. Since $g_1$ is not convex, I cannot see how this works.

You really don't even need KKT. Let's consider two problems: the original, \begin{array}{lll} P_1: & \text{minimize} & f(x,y) \\ & \text{subject to} & g_1(x,y) \leq 0 \\ & & g_2(x,y) \leq 0 \\ & & g_3(x,y) \leq 0 \end{array} and the same model with $g_1$ completely removed: \begin{array}{lll} P_2: & \text{minimize} & f(x,y) \\ & \text{subject to} & g_2(x,y) \leq 0 \\ & & g_3(x,y) \leq 0 \end{array} Let $f_1^*$ and $f_2^*$ be the optimal values $P_1$ and $P_2$, respectively (including by convention $+\infty$ if a model is infeasible, and $-\infty$ if it is unbounded). Clearly, it must be true that $f_1^*\geq f_2^*$. After all, $P_2$ is a relaxation of $P_1$; it has fewer constraints. So $P_2$ is certainly going to have an objective that's less than or equal to that of $P_1$.
Now suppose $(x^*,y^*)$ is an optimal point for $P_2$. That means $$f(x^*,y^*)=f_2^*, \quad g_2(x^*,y^*)\leq 0, \quad g_3(x^*,y^*)\leq 0$$ Further suppose it happens to be the case that $g_1(x^*,y^*)\leq 0$. Then $(x^*,y^*)$ is a feasible point of $P_1$ as well! Therefore, $$f(x^*,y^*)\geq f_1^*.$$ But now we have $$f_1^*\geq f_2^* = f(x^*,y^*) \geq f_1^* \quad\Longrightarrow\quad f_1^*=f_2^*.$$ So if $g_1(x^*,y^*)\leq 0$, that means the optimal point of $P_2$ is also a globally optimal point of $P_1$.
Note that it doesn't matter if $g_1$ is convex. In fact, we haven't used convexity at all here. The above argument holds even if $f$, $g_2$, and $g_3$ are all non-convex. The general principle is this:
Let's bring KKT back into it---and this means we have to bring convexity into it. You said that you found a KKT point $(x,y)$ where $g_1$ is inactive---its Lagrange multiplier $\lambda_1$ is zero. That means you could remove the term $\lambda_1 g_1(x,y)$ from the Lagrangian altogether without modifying its value or the other KKT conditions. You're left with the Lagrangian for $P_2$, with its KKT conditions satisfied. This establishes that the point is a local minimum for $P_2$; and since that problem is convex, it is global as well.
The text passage discusses the conditions under which a KKT point can be considered a global minimum in an optimization problem with both convex and non-convex constraints. It explains why, even if one of the constraints is non-convex, a KKT point can still be a global minimum if that constraint is inactive.
no_question

the passage does not contain a mathematical question or a request for a calculation. it is an explanation of a concept in optimization theory.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# First order sufficient condition for minimum

Suppose I have the problem of finding the minimum of some function $f(x,y)$ subject to three inequality constraints $g_1(x,y),g_2(x,y),g_3(x,y) \leq 0$. Further assume the functions $f,g_2,g_3$ to be convex on $\mathbf{R}^2$ ($g_1$ is not convex).

A theorem in my book says that if I find a KKT-point where $g_1$ is inactive (the corresponging Lagrange multiplier is zero), then I know this point to be a local minimum. (Under assumptions that $f,g_2,g_3$ are convex in the neighbourhood of this point).

A corollary to the same theorem says that if all of $f,g_1,g_2,g_3$ are convex, then the local minimum is in fact the global minimum.

Now to what confuses me: In the solution to the above described problem, the found KKT-point (with $g_1$ being inactive) is said to be the global minimum as a cause of the above theorem and corollary. Since $g_1$ is not convex, I cannot see how this works.

You really don't even need KKT. Let's consider two problems: the original, \begin{array}{lll} P_1: & \text{minimize} & f(x,y) \\ & \text{subject to} & g_1(x,y) \leq 0 \\ & & g_2(x,y) \leq 0 \\ & & g_3(x,y) \leq 0 \end{array} and the same model with $g_1$ completely removed: \begin{array}{lll} P_2: & \text{minimize} & f(x,y) \\ & \text{subject to} & g_2(x,y) \leq 0 \\ & & g_3(x,y) \leq 0 \end{array} Let $f_1^*$ and $f_2^*$ be the optimal values $P_1$ and $P_2$, respectively (including by convention $+\infty$ if a model is infeasible, and $-\infty$ if it is unbounded). Clearly, it must be true that $f_1^*\geq f_2^*$. After all, $P_2$ is a relaxation of $P_1$; it has fewer constraints. So $P_2$ is certainly going to have an objective that's less than or equal to that of $P_1$.
Now suppose $(x^*,y^*)$ is an optimal point for $P_2$. That means $$f(x^*,y^*)=f_2^*, \quad g_2(x^*,y^*)\leq 0, \quad g_3(x^*,y^*)\leq 0$$ Further suppose it happens to be the case that $g_1(x^*,y^*)\leq 0$. Then $(x^*,y^*)$ is a feasible point of $P_1$ as well! Therefore, $$f(x^*,y^*)\geq f_1^*.$$ But now we have $$f_1^*\geq f_2^* = f(x^*,y^*) \geq f_1^* \quad\Longrightarrow\quad f_1^*=f_2^*.$$ So if $g_1(x^*,y^*)\leq 0$, that means the optimal point of $P_2$ is also a globally optimal point of $P_1$.
Note that it doesn't matter if $g_1$ is convex. In fact, we haven't used convexity at all here. The above argument holds even if $f$, $g_2$, and $g_3$ are all non-convex. The general principle is this:
Let's bring KKT back into it---and this means we have to bring convexity into it. You said that you found a KKT point $(x,y)$ where $g_1$ is inactive---its Lagrange multiplier $\lambda_1$ is zero. That means you could remove the term $\lambda_1 g_1(x,y)$ from the Lagrangian altogether without modifying its value or the other KKT conditions. You're left with the Lagrangian for $P_2$, with its KKT conditions satisfied. This establishes that the point is a local minimum for $P_2$; and since that problem is convex, it is global as well.
user
The text passage discusses the conditions under which a KKT point can be considered a global minimum in an optimization problem with both convex and non-convex constraints. It explains why, even if one of the constraints is non-convex, a KKT point can still be a global minimum if that constraint is inactive.

TYPE: NO_QUESTION

The passage does not contain a mathematical question or a request for a calculation. It is an explanation of a concept in optimization theory.