# Linear Programming

$$\mathbf{x} = arg\;\underset{\mathbf{x}}{min}\;c^T\mathbf{x}$$
subject to 
$$A\mathbf{x} = b$$
$$\mathbf{x} \succeq 0$$

**Programming**

$$(x, y)  = arg\;\underset{x,y}{max} \;5x + 3y$$
subject to
$$x + y \leq 10$$
$$2x + y \leq 16$$
$$x + 4y \leq 32$$
$$x,y \geq 0$$

The constraints can be re-written under formula: $Gx \preceq h$, where:
$$G=\begin{bmatrix}
1 & 1 \\
2 &  1 \\ 
1 & 4  \\ 
-1 & 0 \\ 
0 & -1 \\
\end{bmatrix}, \;h = \begin{bmatrix}
10 \\ 
16 \\ 
32 \\ 
0 \\ 
0
\end{bmatrix}$$

**CVXOPT Solution:**


```python
from cvxopt import matrix, solvers
c = matrix([-5., -3.])
G = matrix([[1., 2., 1., -1., 0.], [1., 1., 4., 0., -1.]])
h = matrix([10., 16., 32., 0., 0.])

solvers.options['show_progress'] = False
sol = solvers.lp(c, G, h)

print('Solution"')
print(sol['x'])
```

    Solution"
    [ 6.00e+00]
    [ 4.00e+00]
    


# Quadratic Programming (QP)

**General formula**

\begin{equation}
\mathbf{x} = arg \underset{\mathbf{x}}{min} \frac{1}{2}\mathbf{x}^T\mathbf{P}\mathbf{x}+\mathbf{q}^T\mathbf{x}+\mathbf{r}
\end{equation}
subject to
$$\mathbf{G}\mathbf{x} \preceq \mathbf{h}$$
$$\mathbf{A}\mathbf{x}=\mathbf{b}$$

where $P \in S_+^n$ (set of square matrices $\succeq 0$ with $n$ columns), $G \in \mathbb{R}^{m\times n}$, $A \in \mathbb{R}^{p\times n}$

### QP Example

$$(x, y) = arg \;\underset{x,y}{min} \;{(x-10)}^2 + {(y-10)}^2$$
subject to 
$$\begin{bmatrix}
1 & 1 \\
2 &  1 \\ 
1 & 4  \\ 
-1 & 0 \\ 
0 & -1 \\
\end{bmatrix}\begin{bmatrix}
x\\ 
y
\end{bmatrix}
\preceq \begin{bmatrix}
10\\ 
16\\ 
32\\ 
0\\ 
0
\end{bmatrix}$$

_Example of distance from a point to a polyhedron_



```python
from cvxopt import matrix, solvers
P = matrix([[1., 0.], [0., 1.]])
q = matrix([-10., -10.])
G = matrix([[1., 2., 1., -1., 0.], [1., 1., 4., 0., -1.]])
h = matrix([10., 16., 32., 0., 0])

solvers.options['show_progress'] = False
sol = solvers.qp(P, q, G, h)

print('Solution:')
print(sol['x'])
```

    Solution:
    [ 5.00e+00]
    [ 5.00e+00]
    


# Geometric Programming

$$x = arg\;\underset{x}{min}\;f_0(x)$$
subject to 
$$f_i(x)\leq1, \;i=1,2,...,m$$
$$h_j(x) = 1, \;j=1,2,...,p$$

where $f_0, f_1,.., f_m$ are posynomials and $h_1,...,h_p$ are monomials

**Monomial function**
$f:\Re^n \rightarrow \Re$ with definite set $dom\;f=\Re^n_{++}$ has formula:
$$f(x) = cx_1^{a_1}x_2^{a_2}...x_n^{a_n}$$
with $c > 0$ and $a_i\in\Re$


**Posynomial function**: sum of monomials
$$f(x) = \sum_{k=1}^{K}c_kx_1^{a_{1k}}x_2^{a_{2k}}...x_n^{a_{nk}}$$
with $c_k > 0$





```python
from cvxopt import matrix, solvers
from math import log, exp# gp
from numpy import array
import numpy as np

K = [4]
F = matrix([[-1., 1., 1., 0.],
            [-1., 1., 0., 1.],
            [-1., 0., 1., 1.]])
g = matrix([log(40.), log(2.), log(2.), log(2.)])
solvers.options['show_progress'] = False
sol = solvers.gp(K, F, g)

print('Solution:')
print(np.exp(np.array(sol['x'])))

print('\nchecking sol^5')
print(np.exp(np.array(sol['x']))**5)
```

    Solution:
    [[1.58489319]
     [1.58489319]
     [1.58489319]]
    
    checking sol^5
    [[9.9999998]
     [9.9999998]
     [9.9999998]]



```python

```

ede69f5c6e0faa09db4187f8c22e2da2fe97b70a
ipynb
Jupyter Notebook
svm/tutorial/convex-optim.ipynb
giangtranml/framgia-training
c7fb343bd43b1bceb241b447ff956febb99c94a8
MIT
2020-08-06T09:39:42.000Z
2020-08-06T09:39:42.000Z
svm/tutorial/convex-optim.ipynb
giangtranml/framgia-training
c7fb343bd43b1bceb241b447ff956febb99c94a8
MIT
svm/tutorial/convex-optim.ipynb
giangtranml/framgia-training
c7fb343bd43b1bceb241b447ff956febb99c94a8
MIT
Qwen/Qwen-72B
1. YES
2. YES