Support Vector Machines — Lecture series — Addressing optimisation problems with constraints

In the previous post, we learnt about optimisation problems and how they relate to the geometric margin. In this post, we shall be talking about how to tackle optimisation problems with constraint.

Learning objective:

Understand the concept of constraints in relation to optimisation problems.

Main question:

When given some function f(x), how can we find the value of x that generates the minimum or the maximum value of that function, provided that we can only select the value of x from a stated set of values?

Let’s assume that we are trying to minimise the function f(x), which is represented by the graph in Fig 1 below:

Fig. 1

However, the only values of x that we can choose to minimise f(x) are the values of x that satisfy the function x — 2=0, which is the equation of the line also represented in Fig. 1.

We can conclude from the above scenario that, the lowest value of f(x) that can be generated by a value of x that also satisfies x-2=0 is 4 and the value of x that satisfies this optimisation problem is 2.

Problems of this nature, where we will have to figure out the maximum or minimum value of a quadratic function subject to some constraints, are referred to as quadratic optimisation problems.

In the next post, we will look at optimisation problems with regards to support vector machines.