Abstract
Non-convex optimization problems belong to a class of classical nonlinear optimization problems, which are often difficult to solve. An optimization problem becomes non-convex due to the presence of non-convex functions in the objective function or constraints. A function is a convex function if its Hessian matrix is positive and semi-definite for all values; otherwise, it is a non-convex function. A Hessian matrix is called positive semi-definite when the eigenvalues of the matrix are non-negative. A non-convex function can be either a concave function or a function that is neither a concave nor a convex function. A concave function is always negative semi-definite, indicating that the eigenvalues of the matrix are non-positive. This chapter starts with a short introduction to non-convex problems, followed by a discussion on different non-convex problems arising in supply chain and finance. Thereafter, the authors discuss different algorithms used for solving non-convex problems. Finally, the chapter conclude with the limitations of different algorithms.
TopNon-Convex Function
A function is non-convex when the function does not act as a convex function. A function is a convex function if and only if its Hessian matrix is positive semi-definite for all values; otherwise, it is a non- convex function. A hessian matrix is called positive semi-definite if and only if all eigenvalues of the matrix are non-negative. For example, consider a function of n variables f(x) defined on a convex set D. f(x) is said to be a convex function when the following conditions hold.
- •
For any two points x1 and x2 and 
- •
The hessian matrix of f(x) is positive semi-definite for all values of x1,…,xn.
Figure 1a shows an example of convex functions. A non-convex function can be either a concave function or a function that is neither a concave nor a convex function. A function is a concave function if its hessian matrix is negative semi-definite, which happens only when all eigenvalues of the matrix are non-positive. For example, consider a concave function of n variables 𝜙(x) defined on a convex set D. 𝜙(x) is said to be concave when the following conditions hold.
- •
For any two points x1 and x2 and 0 ≤ λ ≤ 1, 
- •
The hessian matrix of f(x) is negative semi-definite for all values of x1,…,xn.
Figure 1. Different non-linear functions
An example of a non-convex function, which is neither concave nor convex, includes an inverse S-shaped function. An inverse S-shaped function is concave in nature initially up to a certain point above which the function changes its shape to convex. The point is often referred as a deflection point or economic point. In Figure 1.1b, we show an inverse S-shaped function. Historically, non-convex optimization problems have been of interest due to several real-world applications. Next, we briefly describe some of the non-convex application problems.
Key Terms in this Chapter
Negative Semi-definite: A matrix is negative semidefinite only if all its eigen values are non-positive.
Non-Convex Optimization: Non-convex optimization is a process of finding optimal solution for non-convex problems. Non-convexity may arise in a problem due the presence of non-convex function in the objective function or constraints. A non-convex function can be either concave function or a function, which is neither concave function nor convex function. A function is called convex function only if its hessian is positive semi-definite.
Global Optima: A global optima is optimal within all feasible solutions.
Positive Semi-definite: A matrix is positive semidefinite only if all its eigen values are non-negative.
Local Optima: A local optima is optimal within a neighboring set of candidate solutions.