The optimization problem

Optimization

Much of machine learning is built around the idea of loss functions and optimizing for them. In fact, if you can formulate the loss as a good optimization problem, you can build a strong predictive model.

In this article, we will introduce the general idea behind the formulation and nature of optimization problems.

Prerequisites

To understand this article, we recommend familiarity with the concepts in

Follow the above links to first get acquainted with the corresponding concepts.

Problem statement

Optimization is an approach to minimize or maximize a function of variables. For example,

\begin{aligned} \min_{\vx} \text{ }& f(\vx) \\ \text{ subject to } &\\ & g(\vx) = \va \\ & h(\vx) \ge \mathbf{b} \\ \end{aligned}

The objective function

The above statement describes the task of finding a value of a variable \( \vx \) where the function \( f(\vx) \) attains a minimium value. The function being minimized, \(f: \real^n \to \real \), is known as the objective function.

Note that \( \max_{\vx} f(\vx) \) has the same solution as minimizing the negated objective function \( \min_{\vx} -f(\vx) \). So, it is common practice in optimization to standardize a problem as a minimization problem.

In our articles, we will use optimization to mean minimization, unless otherwise explicitly specified.

Constraints

The statements involving \( g(\vx) \) and \( h(\vx) \) require the variable \( \vx \) to satisfy certain conditions. These statements are known as constraints. A problem devoid of constraints is unconstrained, otherwise it is a constrained optimization problem.

Specifically, the constraints \( g(\vx) = \va \) are known as the equality constraints.

The constraints \( h(\vx) \ge \vb \) are known as inequality constraints.

The set of all input values \( \vx \) that satisfy the constraints is known as the feasible set. Note that in unconstrained optimization problems, the feasible set is unbounded.

So, the goal of optimization is to discover the least value of the objective function attainable using the elements of the feasible set as input.

Solution

The element of the feasible set that attains the minimum value of the function is known as the solution. It is usually denoted as \( \star{\vx} \) . Consequently, the minimum of the objective function is denoted as \( f(\star{\vx}) \).

In some problem settings, we are interested in \( \star{\vx} \), in others we actually care about \( f(\star{\vx}) \).

For example, when fitting machine learning models to data by minimizing the loss, we do not actually care about the value of the loss at the end of the optimization process. Instead, we are interested in the value of the parameters that lead to minimum loss.

Global vs local minimizers

If the function value is lowest among all elements of the feasible set, then the solution is a global minimizer. If it is lower than all the elements of the feasible set that lie within a neighborhood of \( \star{\vx} \), then the solution is a local minimizer.

It is desirable that an optimization approach discover the global minimizer. In fact, avoiding locally optimal solutions and providing guarantees for rapidly discovering the global solution is an important challenge in optimization research.

Where to next?

Expand your knowledge of optimization approaches with our detailed interactive articles on this subject.

To brush up on calculus, explore our articles on topics in calculus and multivariate calculus. Or start with strong mathematical foundations.

Already an optimization expert? Check out comprehensive courses on machine learning or deep learning.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Let's connect

Please share your comments, questions, encouragement, and feedback.