Quadratic Programming is a combination of multiple mathematical concepts. Quadratic approximation (Taylor Series), Constrained function as well cost/loss optimization. Combined, it creates a convex optimization problem. Meaning that the problem can only be solved if and only if the problem can be represented as a convex problem. Additionally, the solution will only be within the convex region of the problem.
Quadratic Programming is formulated as the following:
The formula states that, find that will yield the smallest number, and minimize , while satisfying the constrained linear equation . Where stands for subjected to.
The function with the min is the loss function that states how good the value is. It is used as for expressing what the optimization should attempt to optimize as well if going in the right direction.
Finally, the is the quadratic approximation function that describes the optimization itself. Quadratic Programming is just a special case of using Quadratic Approximation and can be expressed as Polynomial Programming for generalizing.
Taylor Series – Approximation
The Quadratic approximation is derived from the Taylor Series, which is a definition of how a function can be re-expressed as the sum of an infinite sequence of derivative functions at a particular point. See the following definition:
For instance, a sine function, , can be expressed as an infinite polynomial expression.
However, it should be noted that working with infinite sequences is very much restricted when solving purely as a mathematical problem. Whereas applied mathematics in the real-world problem may not be able to make use of infinite sequence since it would require infinite function.
Instead, since this is done in the real world and an infinite sequence is impossible, instead an approximate version can be opted for and computed. Where the amount of error will be proportional to what degree of the Taylor Series is used as well as the distance from the sampled point and the point that the approximate function is based on.
See the following Taylor Series definition:
For a linear approximation, it will essentially become the tangent line. Since it will have the shape of a linear function. Additionally, it can for any given dimension, which effectively makes it a hyperplane. Though a linear approximation is limited by that it is only good for the problems that have a linear relationship.
The Linear Approximation is derived from the Taylor Series, see the following.
The Taylor can be reduced into a condensed Algebraic equation, that is the same shape as the linear equation:
The Quadratic approximation is the next level from the linear approximation one. It approximates the function around a certain point with a higher-level approximation.
It has the shape of a quadratic equation, see the following:
Deriving the Quadratic Approximation from the Taylor series gives the following.
The Quadratic approximation in linear-algebraic form can be expressed as follows:
The expression First order Partial derivative in respect for all the variables of . It will have the shape of a vector.
The expression is the Hessian Matrix, which contains all possible combinations of partial derivatives as a square matrix.
Partial Differential is rather straightforward to calculate. The first-order ordinary derivative is calculated for each of the variables individually. Resulting in a vector/list of derivatives equal to the number of variables.
For instance, given the following function with two variables.
Thus computing the individual variable’s derivatives gives the following set of functions:
Finally, it can be generalized as the following:
Hessian Matrix is the second-order ordinary partial differential, expressed as a matrix that contains all the combinations of second-order partial differential. See the following for a two variables example function as a Hessian Matrix:
Since Hessian Matrix is a square matrix, when multiplied by the vector, it produces a vector.
Constraints are additional conditions that a mathematical problem much satisfy. It is commonly expressed as subject to or s.t. See the following for an example:
The constraints can be expressed as either equality or inequality constraint. For simplicity, let us only consider linear constraints. See the following for the linear constraint expression:
When having a set of multiple constraints it can be expressed as a matrix equation. See the following statement. Where A is the constraint, V is the vector that is to be determined if in the
The constraints combined can create a geometric shape a convex shape, which is one of the required properties for Quadratic Programming.
Given linear constraints, it can be used as a hyperplane, which is a plan for any given vector space dimension. For 2D space, is a line, in 3D space is a plane and etc. That is to say a linear expression. This allows taking advantage of many properties of *Linear Algebra*. See the following expression of Hyperplane in linear-algebraic form.
Additionally, the hyperplane can be viewed as dividing the existing vector space into two sub-vector spaces. When computing a vector as a point with the hyperplane equation it will give a value. Where the sign determines on which side of the plane it is located.
Quadratic Programming Optimization Problem – Loss Function
Finally, the *loss function* is the function that will be the guiding expression on how well the optimization is going.
However, the question is what and how should it be expressed in our to guide the algorithm to optimize the problem in the way that is desired, alignment problem.
The more simple loss function is the MSE (Mean Square error), which computes the distance between values as the absolute value in order to determine how much error/loss.
Quadratic Programming in Programming
The QP programming as present above can not really be solved for any arbitrary problem with computer hardware. Rather it has to solve computational in order to find the best solution. It becomes related more to sequential quadratic programming (SQP). Where the idea is that similar to gradient descent a point within the convex vector space region walks in steps in till it finds the point with the lowest loss value. That is to say in till it finds the lowest valley. How it is implemented is a completely different problem. Fortunately, there exist many libraries in many various programming languages that have solved that problem. Thus, the problem becomes how to express our problem as a quadratic programming problem.
Free/Open software developer, Linux user, Graphic C/C++ software developer, network & hardware enthusiast.