Learn to solve optimization problems in Python using essential math tools, metaheuristic methods, and constrained optimization techniques. Master efficient solutions for real-world applications.

Optimization with Python from zero to hero.png

cvxpy.tar.gz

cvxpy

Optimization theory seeks the best solution, which is pivotal for machine learning, cost-cutting in manufacturing, refining logistics, and boosting finance profits.

This course provides a detailed description of different optimization problems and the techniques used to solve them. You’ll begin with the formal definition of an optimization problem and an overview of essential mathematical tools: derivatives, gradients, and Hessian. With this knowledge, you’ll implement solutions for several optimization problems. You’ll also learn approximate metaheuristic population methods like particle swarm optimization and genetic algorithms, and solve constrained optimization problems using techniques like penalty methods and constraint simplification. Finally, you’ll solve linear programs and integer programs. 

By the end of this course, you’ll become proficient in formulating different kinds of problems as optimization problems and become skilled in the Python tools that efficiently solve these problems.

Mastering Optimization with Python

Until now, we've had a broad theoretical background in optimization. We've understood some algorithms and the importance of derivatives, gradients, and Hessians. To better grasp all this knowledge, we've implemented all the algorithms we've seen so far. Implementing our version of the algorithms is a great exercise that allows us to develop a deeper understanding of all the different elements that are involved when solving a problem.

As we've seen when visiting gradient descent or Newton's method, there are advanced versions of these algorithms out there that can deal with saddle points and convergence in a better way. Explaining the details of those advanced algorithms is beyond the scope of this course, but that doesn't mean we can't use them. Once again, a Python library will allow us to do it: SciPy.

Our versions have been implemented in problems with just one variable. But real-life problems, like training machine learning models, can involve hundreds or thousands of variables. The versions provided by SciPy will handle multiple variables for us. Nevertheless, to effectively use SciPy, we need to know about the best ways to operate with so many variables. So let's dive into SciPy and its advanced algorithms.



# Multidimensional world

When we talk about problems with hundreds of variables, it's hard to even write them in mathematical form. How can we write a formula with hundreds of variables? In math, there's a way to do it compactly, using vectors and matrices. When we write a variable in lowercase and boldface, we're referring to vectors:

$$
\mathbf{x}, \mathbf{y}, \mathbf{z}
$$

A **vector** represents a point in the multidimensional world. The same way we said $(a, b, c)$, now we can say $\mathbf{x} = \begin{pmatrix} a & b & c \end{pmatrix}$.

A **matrix** is an ordered set of vectors of the same size. We saw what a matrix is when we learned the Hessian of a multidimensional function. We'll denote matrices with uppercase letters.

$$
A = \begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
$$

The **transpose** of a matrix is an operation that converts the rows into columns and columns into rows. When a vector is transposed, it becomes a column vector instead of a row vector. We denote transposition as $\mathbf{x}^\top$, $A^\top$. For example:

$$
\mathbf{x} = \begin{pmatrix}a & b & c\end{pmatrix} \\
\mathbf{x}^\top = \begin{pmatrix}a \\ b \\ c\end{pmatrix}
$$

And for matrix:

$$
A = \begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
\\
A^\top = \begin{pmatrix}
a & c \\
b & d
\end{pmatrix}
$$

>**Note:** In many courses, a vector is assumed to be a column vector, and its transpose to be a row vector. Here, we did it the other way round. But that's not important—as long as we remember it.

The laws of multiplication and addition of matrices and vectors are designed to make it easy for us to write formulas with them. For example, if $\mathbf{x} = \begin{pmatrix}x & y & z\end{pmatrix}$, then $x^2 + y^2 + z^2 = \mathbf{x}\mathbf{x}^\top$. Note that $\mathbf{x}$ can be arbitrarily large, but the sum of the squares of all its entries will always be $\mathbf{x}\mathbf{x}^\top$.

A system of linear equations can be expressed as:

$$
\mathbf{x}A = \mathbf{b}
$$

Here, $\mathbf{x}$ contains the variables, $A$ is the coefficients of each equation, and $\mathbf{b}$ contains the right part of each equation. Addition and subtraction in matrices and vectors are performed element-wise. That's why we can only perform them between matrices or vectors of the same size. For example:

$$
A = \begin{pmatrix}a_1 & a_2 \\
a_3 & a_4\end{pmatrix} \\

B = \begin{pmatrix}b_1 & b_2 \\
b_3 & b_4\end{pmatrix} \\

A + B = \begin{pmatrix}a_1 + b_1 & a_2 + b_2 \\
a_3 + b_3 & a_4 + b_4\end{pmatrix} \\
$$

Multiplying a vector or a matrix by a number is the same as multiplying each element by that number:

$$
\mathbf{x} = \begin{pmatrix}x & y & z\end{pmatrix} \\
a\mathbf{x} = \begin{pmatrix}ax & ay & az\end{pmatrix}
$$

Before the end of this section, let's look at how an expression can change when written in vector notation. The **mean squared error (MSE)** appears a lot in machine learning. We usually want to minimize this error as the target of model training. It measures the average error in a prediction, taking as an error the distance from the prediction to the actual value. The formula without vectors is:

$$
MSE = \frac{1}{N}\sum_{i = 1}^{i = N}(y_i - \hat{y_i})^2
$$

The sum symbol indicates that we should iterate for every prediction and evaluate its error. Written in vector notation, the formula is:

$$
MSE = \frac{1}{N} (\mathbf{y} - \hat{\mathbf{y}})(\mathbf{y} - \hat{\mathbf{y}})^\top
$$

We're just multiplying a vector with its transpose. Besides being a more compact notation, computers also take advantage of vectors and matrices because they can make the operations way faster than when considering each variable independent of the others. We're not going to learn how to perform those faster calculations but we'll learn how to use them to solve large optimization problems. 

Learn to apply gradient descent and Newton's method to problems with several variables.

Introduction

Derivatives and Gradients

First Optimization Algorithms

Population Methods

Adding Constraints

Solving Sudoku and the 8-Queens Puzzle as Constraint Satisfaction

Linear Constrained Optimization

Summary and Conclusion

Appendix

Maze Solver Using the Ant Colony Optimization Algorithm

Multiple Variables Using SciPy

Multidimensional world