A function is concave when a line segment joining two points lies entirely below or on the graph of a function.
There are two ways to test the concavity of a function: by using an inequality identity or through the use of a Hessian matrix.
The necessary condition for a function to be concave is that the determinant of the Hessian matrix of the function should be greater than zero.
The Hessian matrix can be used to determine the concavity and convexity of a function
In order for an engineering system to provide more outputs from the inputs available, optimization is necessary. The goal of optimization is to produce the maximum output, efficiency, profit, and performance from an engineering system.
So, how does one go about optimizing an engineering system? Usually, mathematical models are developed to optimize engineering systems. When mathematical relationships are derived between the objective function, constraints, and decision values, the mathematical functions formulated can be convex or non-convex.
In the case of a convex function, there is a feasible solution and a globally optimal solution. It is harder to obtain optimized solutions for non-convex functions, as there are multiple feasible points, saddle points, and local minima for a given function. It is important to identify the nature of the function to conclude whether the solution obtained is the global optimum or not.
To determine whether a function is convex or concave, the Hessian matrix can be used. In this article, we will take a look at concave functions and explore how concavity can be determined using the Hessian matrix.
All About Concave Functions
A function is concave when a line segment joining two points lies entirely below or on the graph of the function. When plotting a concave function, its local maximum is also a global maximum. A function is considered strictly concave if the line segment condition is satisfied.
In optimization, functions can either be convex or concave. There is a relationship between a convex function and a concave function; the negative of a convex function is a concave function, and vice versa. The other common property of convex and concave functions is that the sum of convex functions is a convex function and the sum of concave functions is a concave function.
How to Test Concavity
There are two ways to test the concavity of a function:
- By using an inequality identity.
- By using a Hessian matrix.
Inequality Identity Concavity Test
In the first method of testing, the function is tested for convexity. If the inequality identity is not satisfied, the function is concave.
The inequality to be satisfied for the convex function is:
Note that x1 and x2 are the two points on the function plot. If the inequality holds, the function is convex. If the opposite of the inequality is obeyed by the function, it is considered a concave function.
Hessian Matrix Concavity Test
A function is convex if the Hessian matrix of that function is positive semi-definite. When the Hessian matrix is positive definite, the function is strictly convex. To test the concavity of a function, compute the Hessian matrix and prove it is negative semi-definite. The function is strictly concave when the Hessian matrix is negative definite. In any optimization problem in engineering, concavity and convexity are of great importance, as testing the concavity or convexity helps determine whether the solutions are global or local.
Checking Concave Up or Concave Down at a Given Point
The concavity and the determinant of the Hessian matrix are related. If the determinant of the Hessian matrix at a given point is less than zero, the concavity of the function is inconsistent at that point.
For example, consider a two-variable function f(x). Compute the determinant of the Hessian matrix of the function f(x) at (xo, yo). If the determinant is less than zero, the concavity of the function is inconsistent at point (xo, yo). The necessary condition for a function to be concave is that the determinant of the Hessian matrix of the function should be greater than zero. The nature of the concavity can be identified from the elements of the matrix.
The Hessian matrix can be written as follows:
If the determinant of the Hessian matrix is greater than zero at (xo, yo) and
If fxx (xo, yo) > 0, the function f is concave up at (xo, yo).
If fxx (xo, yo) < 0, the function f is concave down at (xo, yo).
How the Hessian Matrix Supports the Optimization Process in Engineering Systems
In the optimization and approximation process, the knowledge of concavity is important, as it indicates the rate of change (derivative) of a function. In most engineering optimization problems, determining the feasible solution involves identifying the nature of the derivative function. For example, in local linear approximation, second derivative information can be utilized to improve the approximation.
Consider a function f of two variables x and y. When computing the Hessian matrix, we obtain a 2×2 matrix with four second-order derivatives. Calculating the Hessian matrix determinant and using it to check concavity requires additional information on some second-order derivatives.
There is often confusion regarding which derivative to use to measure concavity. Calculating the Eigenvalues of the Hessian matrix can help determine whether the function is concave up or down at a given point. Concave up means the function derivative is increasing and concave down means the function derivative is decreasing. Knowing this helps engineers determine whether the solution obtained is the local minimum or maximum.
Optimize Your System With Cadence Tools
Hessian matrices are invaluable during the optimization process of an engineering system. Luckily, Cadence’s suite of CFD tools can assist you in solving optimization problems in highly complex engineering systems.