

# Convex optimization basics

Convex optimization is a field of study in which we seek to find the best solution to an optimization problem within a convex set. A convex set is a set where any two points can be connected by a line segment that lies entirely within the set. This property makes convex sets particularly useful for optimization problems because it guarantees that the optimal solution will be unique and well-defined.

One of the key concepts in convex optimization is the concept of a convex function. A function is convex if its second derivative is non-negative for all points in its domain. In other words, a convex function is one whose graph is a convex set.

Another important concept in convex optimization is the concept of a convex optimization problem. A convex optimization problem is a problem that consists of finding the minimum or maximum of a convex function over a convex set.

Consider the following convex optimization problem:

Minimize:

$$f(x) = x^2$$

Subject to:

$$-1 \le x \le 1$$

The optimal solution is $x = 0$ with a function value of $f(0) = 0$.

## Exercise
Find the optimal solution to the following convex optimization problem:

Minimize:

$$f(x) = x^3$$

Subject to:

$$-1 \le x \le 1$$

# Discrete optimization problems

Discrete optimization problems are a special class of convex optimization problems where the decision variables are discrete. These problems often arise in applications such as combinatorial optimization, integer programming, and machine learning.

One common approach to solving discrete optimization problems is to use linear programming, which is a method for finding the optimal solution to a linear optimization problem. Linear programming is based on the simplex algorithm, which is a powerful numerical method for solving linear programming problems.

Consider the following linear programming problem:

Minimize:

$$f(x) = 3x_1 + 2x_2$$

Subject to:

$$x_1 + x_2 \le 4$$
$$x_1 \ge 0$$
$$x_2 \ge 0$$

The optimal solution is $x_1 = 2$, $x_2 = 2$ with a function value of $f(2, 2) = 7$.

## Exercise
Solve the following linear programming problem:

Minimize:

$$f(x) = 4x_1 + 3x_2$$

Subject to:

$$x_1 + x_2 \le 5$$
$$x_1 \ge 0$$
$$x_2 \ge 0$$

# Linear programming and CVXPY

CVXPY is a Python library for convex optimization that allows you to solve convex optimization problems using a simple, high-level syntax. It provides a domain-specific language (DSL) for defining convex optimization problems and automatically translates these problems into a standard form that can be solved by numerical solvers.

One of the key features of CVXPY is its support for linear programming problems. You can define a linear programming problem in CVXPY by specifying the objective function, the decision variables, and the constraints.

Here's an example of how to define a linear programming problem in CVXPY:

```python
import cvxpy as cp

x = cp.Variable(2)
objective = cp.Minimize(3 * x[0] + 2 * x[1])
constraints = [x[0] + x[1] <= 4, x[0] >= 0, x[1] >= 0]
problem = cp.Problem(objective, constraints)
```

## Exercise
Define a linear programming problem in CVXPY that minimizes the following objective function:

$$f(x) = 4x_1 + 3x_2$$

Subject to the following constraints:

$$x_1 + x_2 \le 5$$
$$x_1 \ge 0$$
$$x_2 \ge 0$$

Solve the problem and find the optimal solution.

# Solving optimization problems with CVXPY

Once you've defined an optimization problem in CVXPY, you can solve it using a numerical solver. CVXPY supports a wide range of numerical solvers, including open-source solvers like ECOS and OSQP, as well as commercial solvers like Gurobi and MOSEK.

To solve an optimization problem with CVXPY, you first need to install a suitable solver. You can install a solver using pip, like this:

```
pip install cvxpy
pip install cvxpy_ecos
```

Once you've installed a solver, you can solve your optimization problem by invoking the `solve` method on the problem object:

```python
problem.solve()
```

## Exercise
Solve the linear programming problem defined in the previous exercise using CVXPY and the ECOS solver. Find the optimal solution and compare it to the solution found using the simplex algorithm.

# Examples of combinatorial optimization problems

Combinatorial optimization is a subfield of convex optimization that deals with optimization problems where the decision variables are discrete. Examples of combinatorial optimization problems include the traveling salesman problem, the knapsack problem, and the set cover problem.



## Exercise
Solve the following combinatorial optimization problem using CVXPY:

Minimize:

$$f(x) = \sum_{i=1}^{n} x_i$$

Subject to:

$$\sum_{i=1}^{n} a_i x_i \le b$$
$$x_i \in \{0, 1\}$$

Find the optimal solution and the optimal value of the objective function.

# Advanced topics in combinatorial optimization



Convex polytopes are a fundamental concept in convex optimization. A convex polytope is a convex set that is the intersection of a finite number of half-spaces.

Linear programming is a method for finding the optimal solution to a linear optimization problem. It is based on the simplex algorithm, which is a powerful numerical method for solving linear programming problems.

Integer programming is a method for finding the optimal solution to an optimization problem where the decision variables are required to be integers. It is a special case of convex optimization, and it can be solved using linear programming techniques.

## Exercise
Find the optimal solution to the following integer programming problem:

Minimize:

$$f(x) = \sum_{i=1}^{n} a_i x_i$$

Subject to:

$$\sum_{i=1}^{n} a_i x_i \le b$$
$$x_i \in \{0, 1\}$$

Find the optimal solution and the optimal value of the objective function.

# Applications of combinatorial optimization

Combinatorial optimization has a wide range of applications in various fields, including operations research, computer science, and economics.



## Exercise
Solve the following combinatorial optimization problem using CVXPY:

Minimize:

$$f(x) = \sum_{i=1}^{n} w_i x_i$$

Subject to:

$$\sum_{i=1}^{n} a_i x_i \le b$$
$$x_i \in \{0, 1\}$$

Find the optimal solution and the optimal value of the objective function.

# Implementing combinatorial optimization with CVXPY in Python



To implement a combinatorial optimization problem using CVXPY, you first need to define the objective function, the decision variables, and the constraints.

Once you've defined the problem, you can solve it using a numerical solver. CVXPY supports a wide range of numerical solvers, including open-source solvers like ECOS and OSQP, as well as commercial solvers like Gurobi and MOSEK.

## Exercise
Implement the following combinatorial optimization problem using CVXPY in Python:

Minimize:

$$f(x) = \sum_{i=1}^{n} w_i x_i$$

Subject to:

$$\sum_{i=1}^{n} a_i x_i \le b$$
$$x_i \in \{0, 1\}$$

Find the optimal solution and the optimal value of the objective function.

# Debugging and testing optimization code



Unit testing is a method for testing individual units of code to ensure that they work correctly. In the context of optimization code, unit testing can involve testing individual functions or components of the optimization problem.

Integration testing is a method for testing the interaction between different components of the optimization code. In the context of optimization code, integration testing can involve testing the interaction between the objective function, the decision variables, and the constraints.

Performance testing is a method for evaluating the performance of the optimization code. In the context of optimization code, performance testing can involve measuring the time taken to solve the optimization problem, the memory usage of the optimization code, and the accuracy of the solution.

## Exercise
Implement unit testing, integration testing, and performance testing for the combinatorial optimization problem implemented in the previous exercise.

# Best practices for combinatorial optimization in Python



One best practice is to use a consistent coding style. This includes using meaningful variable names, following a consistent indentation style, and using comments to explain complex code.

Another best practice is to write clear and concise code. This includes avoiding unnecessary complexity, using descriptive variable names, and breaking complex functions into smaller, more manageable functions.

Finally, it's important to thoroughly test your optimization code to ensure that it works correctly and efficiently. This includes unit testing, integration testing, and performance testing.

## Exercise
Implement the best practices discussed in this section when implementing the combinatorial optimization problem implemented in the previous exercise.

# Conclusion

In this textbook, we've covered the fundamentals of combinatorial optimization and how to implement optimization problems using CVXPY in Python. We've discussed various advanced topics in combinatorial optimization, including convex polytopes, linear programming, and integer programming. We've also discussed the applications of combinatorial optimization and the best practices for implementing optimization code in Python.

In the future, we plan to expand this textbook to cover additional topics in combinatorial optimization, including more advanced techniques for solving optimization problems and more applications of combinatorial optimization. We hope that this textbook has been a valuable resource for anyone interested in learning about combinatorial optimization and implementing optimization problems in Python using CVXPY.