RN-Nonlinear Optimization:Basics

1 Extremum Point of Multivariate Function

For a second order differentiable univariate function $f(x)$, the conditions for the existence of extremum points are,

• Necessary Condition
  $$f^{\prime }(x)=0$$
• Sufficient Condition
  $$\begin{gathered} f^{\prime \prime }(x)>0\text{(local minima)} \\ {f}^{\prime \prime }(x)<0\text{(local maxima)} \end{gathered}$$

Similarly, for a second order differentiable multivariate function $f(\mathbf{x})$, the conditions for the existence of extremum points are,

• Necessary Condition
  $$\nabla f(\mathbf{x})=0$$
• Sufficient Condition
  $$\begin{gathered} {\nabla }^{2}f(\mathbf{x})\succ 0\text{local minima} \\ {\nabla }^{2}f(\mathbf{x})\prec 0\text{local maxima} \end{gathered}$$

In summary, for a second order differentiable function $f(\mathbf{x})$, the conditions for the existence of local minima(maxima) are the gradient $\nabla f(\mathbf{x})$ equals to $0$ and the Hessian matrix ${\nabla }^{2}f(\mathbf{x})$ is positive(negative) definite.

2 Convex Function

In addition to using the definition to determine whether a function is convex, we can also use the following two necessary and sufficient conditions:

• First Order Condition: Assume ${\mathbb{R}}_c$ is a open convex set on Euclidean space $E_n$, and $f(\mathbf{x})$ is differentiable. For any two points ${\mathbf{x}}_1\in {\mathbb{R}}_c$ and ${\mathbf{x}}_2\in {\mathbb{R}}_c$
  $$f({\mathbf{x}}_2)\ge f({\mathbf{x}}_1)+\nabla f({\mathbf{x}}_1{)}^T({\mathbf{x}}_2-{\mathbf{x}}_1)$$
  Then $f(\mathbf{x})$ is a convex function. And if
  $$f({\mathbf{x}}_2)>f({\mathbf{x}}_1)+\nabla f({\mathbf{x}}_1{)}^T({\mathbf{x}}_2-{\mathbf{x}}_1)$$
  Then $f(\mathbf{x})$ is a strictly convex function.

• Second Order Condition: Assume ${\mathbb{R}}_c$ is a open convex set on Euclidean space $E_n$, and $f(\mathbf{x})$ is second order differentiable, if its Hessian matrix is semi positive definite
  $${\nabla }^{2}f(\mathbf{x})⪰0$$
  then $f(\mathbf{x})$ is a convex function. And if
  $${\nabla }^{2}f(\mathbf{x})\succ 0$$
  then $f(\mathbf{x})$ is a strictly convex function.

3 Karush-Kuhn-Tucker Conditions

Consider the following nonlinear optimization problem,
$$\begin{array}{rl}\text{(NLP)}\min & f(\mathbf{x})\\ s.t.& g_i(\mathbf{x})\le 0,\forall i=1,...,m\\ & h_j(\mathbf{x})=0,\forall i=1,...,p\end{array}$$
in which $f(\mathbf{x}),g(\mathbf{x})$ and $h(\mathbf{x})$ are differentiable, the functions $g(\mathbf{x})$ and $h(\mathbf{x})$ are assumed to satisfy certain regularity conditions also known as constraint qualifications (e.g. the functions $g(\mathbf{x})$ and $h(\mathbf{x})$ should be affine functions).

The Lagrange function is,
$$\mathcal{L}(\mathbf{x},\mathbf{\lambda },\mathbf{\mu })=f(\mathbf{x})+{\mathbf{\lambda }}^{T}g(\mathbf{x})+{\mathbf{\mu }}^{T}h(\mathbf{x})$$

The Lagrangian dual function is,
$$d(\mathbf{\lambda },\mathbf{\mu })=\underset{\mathbf{x}}{\inf }\mathcal{L}(\mathbf{x},\mathbf{\lambda },\mathbf{\mu })$$

The the Lagrangian dual problem is,
$$\underset{\mathbf{\lambda },\mathbf{\mu }}{\max }d(\mathbf{\lambda },\mathbf{\mu })$$

The Karush-Kuhn-Tucker conditions can be described as:

• Stationarity
  $$\nabla f(\mathbf{x})+{\mathbf{\lambda }}^{T}g(\mathbf{x})+{\mathbf{\mu }}^{T}h(\mathbf{x})=0$$
• Primal Feasibility
  $$g(\mathbf{x})\le 0,h(\mathbf{x})=0$$
• Dual Feasibility
  $$\mathbf{\lambda }\ge 0$$
• Complementary Slackness
  $${\mathbf{\lambda }}^{T}g(\mathbf{x})=0$$

KKT conditions are necessary conditions for optimality. If $f(\mathbf{x})$ is a convex function, and constraint functions $g(\mathbf{x})$ and $h(\mathbf{x})$ satisfies Slater’s condition, then strong duality holds, KKT conditions are sufficient and necessary.

4 Conclusion

For unconstrained convex minimization problem, in a few special cases, we can find a solution through analytically solving the optimality equation($\nabla f(\mathbf{x})=0$), but usually the problem must be solved by an iterative algorithm, such as Newton’s method, gradient descent method, steepest descent method.

For solving constrained convex minimization problem, one famous interior point method is barrier method. Interior point methods solve the KKT conditions by applying Newton’s method to a sequence of equality constrained problems, or to a sequence of modified versions of the KKT conditions.

The following paragraph is from Prof. Boyd’s book, Convex Optimization,

We can view interior-point methods as another level in the hierarchy of convex optimization algorithms.

• Linear equality constrained quadratic problems are the simplest. For these problems the KKT conditions are a set of linear equations, which can be solved analytically.
• Newton’s method is the next level in the hierarchy. We can think of Newton’s method as a technique for solving a linear equality constrained optimization problem, with twice differentiable objective, by reducing it to a sequence of linear equality constrained quadratic problems.
• Interior-point methods form the next level in the hierarchy: They solve an optimization problem with linear equality and inequality constraints by reducing it to a sequence of linear equality constrained problems.

References

[1] Boyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.