Convex Optimization Problems

Convex optimization problems can be expressed in various standard forms, each with advantages and disadvantages depending on the specific problem. Here are some of the most common standard forms of convex optimization problems:

Linear programming (LP)

This is the simplest form of convex optimization problems, where the objective function and the inequality constraints are affineaffine. The general form of an LP problem is:

$$\begin{aligned} \min_{\bold x} \quad & \bold c^T\bold x\\ \textrm{s.t.} \quad & A\bold x \le \bold b \end{aligned}$$

Here, $\bold x$ is the optimization variable, $\bold c$ and $\bold b$ are vectors, and $A$ is a matrix.

Example of LP

Consider the objective to be maximized of an optimization problem as follows:

$$f(x,y) = x + y$$

The constraints are as follows:

$$\begin{aligned} 25x + 35y & <= 5000 \\ x &>= 50 \\ y &>= 60 \end{aligned}$$

The above problem can be reformulated as standard LP if $\bold x =\begin{bmatrix}x \\ y\end{bmatrix} ,\quad \bold c = \begin{bmatrix}-1 \\ -1\end{bmatrix},\quad A=\begin{bmatrix}25 & 35 \\ -1 & 0\\ 0 & -1\end{bmatrix}$ and $\bold b=\begin{bmatrix}5000 \\ -50 \\ -60\end{bmatrix}$. The following code solves this LP using cvxpy: