

# Convex optimization basics



Consider the following convex optimization problem:

$$
\begin{aligned}
\text{Minimize } & \quad f(x) = x^2 \\
\text{Subject to } & \quad x \ge 0
\end{aligned}
$$

The objective function $f(x) = x^2$ is convex, and the feasible region is the non-negative real line. The optimal solution is $x^* = 0$ with an objective value of $f(0) = 0$.

## Exercise
Define a convex optimization problem with a non-convex objective function and a convex feasible region. State the problem and find its optimal solution.

# Duality theory and its applications



Consider the following linear programming problem:

$$
\begin{aligned}
\text{Minimize } & \quad c^T x \\
\text{Subject to } & \quad Ax \le b, x \ge 0
\end{aligned}
$$

The dual problem is:

$$
\begin{aligned}
\text{Maximize } & \quad b^T y \\
\text{Subject to } & \quad A^Ty \ge c, y \ge 0
\end{aligned}
$$

The optimal value of the primal problem is equal to the optimal value of the dual problem.

## Exercise
Formulate the dual problem of the following convex optimization problem:

$$
\begin{aligned}
\text{Minimize } & \quad x^2 + y^2 \\
\text{Subject to } & \quad x + y \le 1
\end{aligned}
$$

# The Numba library and its role in Python



Here's an example of using Numba to speed up a Python function:

```python
from numba import jit

@jit(nopython=True)
def add(a, b):
    return a + b

result = add(1, 2)
```

In this example, the `@jit(nopython=True)` decorator tells Numba to compile the `add` function with the highest optimization level. The `nopython=True` option ensures that Numba generates machine code without relying on the Python interpreter.

## Exercise
Write a Numba function that computes the square of a given number. Compare the execution time of the Numba function with the standard Python function.

# Efficient convex optimization using Numba



Here's an example of using Numba to implement the gradient descent algorithm:

```python
from numba import jit
import numpy as np

@jit(nopython=True)
def gradient_descent(f, grad_f, x0, alpha, max_iters):
    x = x0
    for _ in range(max_iters):
        x = x - alpha * grad_f(x)
    return x

# Example usage
f = lambda x: x**2
grad_f = lambda x: 2 * x
x0 = 1.0
alpha = 0.1
max_iters = 100

result = gradient_descent(f, grad_f, x0, alpha, max_iters)
```

In this example, we define the objective function $f(x) = x^2$ and its gradient $\nabla f(x) = 2x$. The `gradient_descent` function computes the optimal solution using the gradient descent algorithm.

## Exercise
Implement the Newton's method algorithm using Numba. Use the same example problem as in the previous exercise.

# Implementing duality theory using Numba



Here's an example of using Numba to compute the optimal value of the primal problem:

```python
from numba import jit

@jit(nopython=True)
def primal_value(c, A, b, x):
    return c.T @ x + 0.5 * x.T @ A @ x - b.T @ x

# Example usage
c = np.array([1.0, 1.0])
A = np.array([[1.0, 1.0], [1.0, -1.0]])
b = np.array([1.0, 0.0])
x = np.array([0.5, 0.5])

result = primal_value(c, A, b, x)
```

In this example, we define the primal problem with a linear objective function and a linear inequality constraint. The `primal_value` function computes the optimal value of the primal problem.

## Exercise
Implement the dual problem using Numba. Use the same example problem as in the previous exercise.

# Examples and case studies



Consider the following convex optimization problem:

$$
\begin{aligned}
\text{Minimize } & \quad \sum_{i=1}^{n} \frac{1}{2}x_i^2 + \sum_{i=1}^{n-1} x_i x_{i+1} \\
\text{Subject to } & \quad x_i \ge 0, \forall i
\end{aligned}
$$

This problem is a quadratic programming problem and can be solved using the Newton's method algorithm implemented with Numba.

## Exercise
Solve the following convex optimization problem using Numba:

$$
\begin{aligned}
\text{Minimize } & \quad \sum_{i=1}^{n} \frac{1}{2}x_i^2 + \sum_{i=1}^{n-1} x_i x_{i+1} \\
\text{Subject to } & \quad x_i \ge 0, \forall i
\end{aligned}
$$

# Optimization problems in real-world scenarios



Consider the following linear programming problem:

$$
\begin{aligned}
\text{Minimize } & \quad c^T x \\
\text{Subject to } & \quad Ax \le b, x \ge 0
\end{aligned}
$$

This problem can be used to model the allocation of resources in a production facility. The objective function represents the total cost of production, and the constraints represent the capacity and availability of resources.

## Exercise
Solve a real-world optimization problem using Numba. Discuss the challenges of solving the problem and the efficiency of using the Numba library.

# Conclusion and future developments

In this textbook, we have covered the basics of convex optimization, duality theory, the Numba library, and its application in solving convex optimization problems. We have presented several examples and case studies to illustrate the concepts learned in the text.

In conclusion, the Numba library provides a powerful tool for solving convex optimization problems efficiently. Future developments in this area will likely involve the integration of more advanced optimization algorithms and the extension of Numba to other domains beyond Python.

# Glossary and references

This section provides a glossary of key terms and concepts discussed in the textbook, as well as a list of references for further reading.

- Convex optimization: A subfield of optimization theory that deals with optimization problems where the objective function and the feasible region are convex.
- Duality theory: A fundamental concept in convex optimization that allows us to transform optimization problems into equivalent problems.
- Numba: A just-in-time (JIT) compiler for Python that allows us to write high-performance code using Python syntax.
- Gradient descent: An optimization algorithm that minimizes a differentiable function by iteratively moving in the direction of the negative gradient.
- Newton's method: An optimization algorithm that minimizes a twice continuously differentiable function by iteratively updating the current point using the inverse of the Hessian matrix.

## Exercise
Review the glossary and references. Discuss any additional terms or concepts that you would like to see included in the glossary.

# Course

Table Of Contents
1. Convex optimization basics
2. Duality theory and its applications
3. The Numba library and its role in Python
4. Efficient convex optimization using Numba
5. Implementing duality theory using Numba
6. Examples and case studies
7. Optimization problems in real-world scenarios
8. Conclusion and future developments
9. Glossary and references