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

# Exercise 1: Extending binary search

We learned how to generalize gradient descent and Newton's method to deal with more variables, but what about binary search? Well, let's discover it ourselves. Adapt the binary search method we saw in the first lesson of this section to solve a problem with two variables. Then, solve the following problem:

$$
\min_{x, y} x + y \\
s.t.: x + y > 1
$$


def f(x, y):
  return x + y

def constraint(x, y):
  return x + y > 1

def binary_search(a1, b1, a2, b2, f, cons, tol):
  '''
  Now we need two intervals, one for each variable.
  '''
  # Remove the following line and complete the code.
  pass


# Excercise 2: Maximizing

We stated that gradient descent and Newton's method can be easily adapted to solve maximization problems. But what are the restrictions that the problem should fulfill so we can maximize it with these algorithms? Change the methods and solve the following problem with both of them:

$$
\max_x -(x + 3)^2 + 5
$$

>**Note:** The intention is to change the method and not to change the problem to $\min_x (x + 3)^2 - 5$. But we can do both and compare the results.

>**Note:** The gradient of the function is $-2(x + 3)$

import numpy as np

# This would be a gradient ascent instead of a descent
def gradient_ascent(start, gradient, max_iter, learning_rate, tol=0.01):
  # Remove the following line and complete the code
  pass

# Exercise 3: Implementing linear regression

Linear regression is one of the most popular machine learning algorithms. Given a function and a set of inputs and outputs of that function, we want to approximate it with a linear function as accurately as we can.

We call $f$ the original function and $\hat{f}$ the approximation we're looking for. The input is a vector $\mathbf{x} = (x_1, x_2, ..., x_m)$. We're looking for a linear $\hat{f}$ of the form:

$$
\hat{f}(x_1, x_2, ..., x_N) = w_1x_1 + w_2x_2 + ... + w_mx_m
$$

If we write $\mathbf{w} = (w_1, w_2, ..., w_m)$, then we can write $\hat{f}$ as:

$$
\hat{f}(\mathbf{x}) = \mathbf{x}\mathbf{w}^\top
$$

We have $N$ examples of inputs $\mathbf{x}$ with their outputs $y = f(\mathbf{x})$. What we want is to find the vector $\mathbf{w}$ so that we minimize the mean squared error. That is:

$$
\min_\mathbf{w} \frac{1}{N} (\mathbf{y} - X\mathbf{w}^\top)^\top(\mathbf{y} - X\mathbf{w}^\top)
$$

Here, $\mathbf{y}$ is the vector of all the outputs and $X$ is the matrix with all the input vectors $\mathbf{x_1}, \mathbf{x_2}, ..., \mathbf{x_N}$.

Implement the linear regression algorithm using SciPy. Experiment with all the methods available in the documentation of the ```minimize``` function of ```scipy.optimize```.

Use the following template that has some hidden code and has what we need already defined. Add in the solution starting on **line 46**:

Test what we’ve learned about optimization algorithms, SciPy, vectors, and matrices.

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

Exercises

Exercise 1: Extending binary search

Excercise 2: Maximizing

Exercise 3: Implementing linear regression