This article simply introduced strategies for finding the stationary points of the objective function subject to one or more equality or inequality constraints.
Consider a standard form of continuous optimization problem,
in which
And are all continuous differentable.
We divided the problem into two cases: or . For the former we introduced The Method of Lagrange Multipliers as the solving strategy, and simply introduced KKT Conditions for the other one when it suits some Regularity Conditions.
Notice that it was easy to treat a maximization problem by negating the objective function, we only use the maximization problem as a general example.
The Method of Lagrange Multipliers
Consider the optimization problem
To transfer the constrained problem into an unconstrained one, we define the Lagrange Function,
In which . Then we have the necessary conditions for the optimal solution, which is
$$
\left{\right.
$$
called Stationary Equation and Constraints separately. Then solving the simultaneous equations, and the solution $({\bf x^},\overrightarrow{\lambda}!^)$ are stationary points and corresponding coefficients.
Cause we could get stationary point through Lagrange Multipliers directly, the minimization/maximization problems are treated in same way.
Maximize subject to .
Form the Lagrange Function
Then calculate gradient of the function and set it to .
We could get the solution
$$
\left{\right.
f_{\rm max}(x,y,z)=\dfrac{8\sqrt{3}}{9}abc
$$
KKT Conditions
For convinience, we consider the case without equality constraint but with a single inequality constraint first,
Then define the feasible regionMissing or unrecognized delimiter for \left and assuming that ${\bf x}^g{\bf x}^\mathbb{K}$ or not, we can divide the problem into two cases and discuss them separately.
${\bf C{\scriptsize ASE}; 1}.;; g({\bf x}^) <0.$ The best solution is inside . At this time we call ${\bf x}^$ as the interior solution. Obviously, at this time, an infinitesimal displacement of the point towards any direction will not against the constraint, so we call that the constraint condition is inactive.
${\bf C{\scriptsize ASE};2}.;;g({\bf x}^)=0.$ The best solution is on the border of . At this time we call ${\bf x}^$ as the boundary solution. Correspondingly, now we call that the constraint condition is active.
Likely, defining the Lagrangian Function
According to is active or inactive, the necessary condition for us to get the best solution are different.
Cause the constraint condition has no influence on getting the best solution, we could make directly. Now the task is equivalent to unconstrained optimization, and only is needed.
Now the constraint condition is equivalent to
Notice that for every points , there is orthogonal to . Likely, it is obvious to find that $\bigtriangledown f({\bf x}^)g\bigtriangledown f \in {\rm span}(\bigtriangledown g){\bf x}^\lambda\lambda \geq 0f\bigtriangledown f({\bf x}^*)\mathbb{K}\bigtriangledown g\mathbb{K}\lambda0$, which is called dual feasibility. Likely, if we want to maximize , we should keep .
Obviously, there will always be either or equal to , so it always holds that , which is called complementary slackness.
Thus we can summarize all necessary conditions mentioned above as KKT Conditions,
Similarly, we can also extend the conclusion to the general continuous optimization problem. The corresponding Lagrangian Function is defined as
And it’s also convinient to write down the corresponding KKT Conditions
In order for existing a point fitting the KKT Conditions, The primal question should satisfy some regular conditions, which has been listed on Wikipedia.
Minimize subject to and , in which .
The corresponding Langrangian Function is
According to KKT Condition, there must be
$$
\left {
\right.
\left {
\right.
$$
Now we can divide the problem into 2 cases according to whether or not.
It is easy to verify that satisfies all KKT Conditions above, so when , takes minimum value .
There is satisfies all KKT Conditions above only, so when and, takes minimum value .