# Quadratic Programming

- Mathematical optimization problems with quadratic functions
- Developed in the 1950s
- Widely used in
    - Optimization of financial portfolios,
    - Image and signal processing,
    - Regression,
    - Scheduling in chemical plants, etc.
- Solution methods
    - Interior point,
    - Augmented Lagrange,
    - Gradient-based,
    - Extensions of the simplex algortihm.
    
## Problem Formulation
Our objective is to find $\mathbf{x}\in\mathbb{R}^n$ in the following problem:

\begin{align}
\text{minimize}\  & \frac{1}{2}\mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T\mathbf{x}, \\
\text{subject to } & \\
& A\mathbf{x} \ \leq \mathbf{b}, \\
\end{align}
where
- $\mathbf{c} \in \mathbb{R}^n$,
- $Q \in \mathbb{R}^{n \times n}$,
- $A \in \mathbb{R}^{m \times n}$,
- $\mathbf{b} \in \mathbb{R}^{m}$.

## Coding in Python
The model:
\begin{align}
\text{minimize}\  & x^2 + 2y^2 + \frac{1}{2}z^2 , \\
\text{subject to } & \\
& x + 3y + 2z \geq 5, \\
& y + z \geq 2.5, \\
& x, y \geq 0, \\
& y \in \mathbb{Z} \\
& z \in \{0, 1\}
\end{align}
### Step 1: Import Package


```python
from gurobipy import *
```

### Step 2: Create a model


```python
quadratic_model = Model('quadratic')
```

### Step 3: Define decision variables


```python
x = quadratic_model.addVar(vtype=GRB.CONTINUOUS, lb = 0, name="x")
y = quadratic_model.addVar(vtype=GRB.INTEGER, lb = 0, name="y")
z = quadratic_model.addVar(vtype=GRB.BINARY, name="z")
```

### Step 4: Define the objective function


```python
obj_fn = x**2 + 2*y**2 + 0.5*z**2
quadratic_model.setObjective(obj_fn, GRB.MINIMIZE)
```

### Step 5: Add constraints


```python
# x + 3y + 2z >= 5
quadratic_model.addConstr(x + 3*y + 2*z >= 5)
# y + z >= 2.5
quadratic_model.addConstr(y + z >= 2.5)
```

### Step 6: Solve model and output the result


```python
quadratic_model.setParam('OutputFlag',False)
quadratic_model.optimize()

print('Optimization is done. Objective Function Value: %.2f' % quadratic_model.objVal)
# Get values of the decision variables
for v in quadratic_model.getVars():
    print('%s: %g' % (v.varName, v.x))
```

### Extras: Update the type of a decision variable

Let us change the requirement of integrality on the decision variable $y$:


```python
y.vType = GRB.CONTINUOUS

quadratic_model.optimize()

print('Optimization is done. Objective Function Value: %.2f' % quadratic_model.objVal)
# Get values of the decision variables
for v in quadratic_model.getVars():
    print('%s: %g' % (v.varName, v.x))
```

### Extras: Add a quadratic constraint

Let us add a quadratic constraint: $x^2 \geq y^2 + z^2$


```python
quadratic_model.addConstr(z**2 + y**2 <= x**2)

quadratic_model.optimize()

print('Optimization is done. Objective Function Value: %.2f' % quadratic_model.objVal)
# Get values of the decision variables
for v in quadratic_model.getVars():
    print('%s: %g' % (v.varName, v.x))
```

e5185c1ff992aa9fa9f87580ab2826a72c72733e
ipynb
Jupyter Notebook
mathematicalProgramming/Video05/Video05.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video05/Video05.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video05/Video05.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
2021-11-21T05:02:50.000Z
2022-02-17T04:44:57.000Z
Qwen/Qwen-72B
1. YES
2. YES