# LMIs in Control/pages/LMI for Linear Programming

LMI for Linear Programming

Linear programming has been known as a technique for the optimization of a linear objective function subject to linear equality or inequality constraints. The feasible region for this problem is a convex polytope. This region is defined as a set of the intersection of many finite half-spaces which are created by the inequality constraints. The solution for this problem is to find a point in the polytope of existing solutions where the objective function has its extremum (minimum or maximum) value.

## The System

We define the objective function as:

${\displaystyle c_{1}x_{1}+c_{2}x_{2}+...c_{n}x_{n}}$

and constraints of the problem as:

${\displaystyle a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}

${\displaystyle a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}

.

.

.

${\displaystyle a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}

## The Data

Suppose that ${\displaystyle c_{j}\in \mathbb {R} ^{n}}$, ${\displaystyle a_{ij}\in \mathbb {R} ^{n}}$, and ${\displaystyle b_{i}\in \mathbb {R} ^{m}}$ are given parameters where ${\displaystyle i=1,2,...,m}$ and ${\displaystyle j=1,2,...,n}$. Moreover, ${\displaystyle x=[x_{1}\quad x_{2}\quad ...\quad x_{n}]^{\text{T}}}$ is an ${\displaystyle n\times 1}$ vector of positive variables.

## The Optimization Problem

The optimization problem is to minimize the objective function, ${\displaystyle c^{\text{T}}x}$ when the aforementioned linear constraints are satisfied.

## The LMI: LMI for linear programming

The mathematical description of the optimization problem can be readily written in the following LMI formulation:

{\displaystyle {\begin{aligned}&{\text{min}}\quad c^{\text{T}}x&\\&{\text{s.t.}}\quad a_{i}^{\text{T}}x\leq b_{i}x\\\end{aligned}}}

## Conclusion:

Solving this problem results in the values of variables ${\displaystyle x}$ which minimize the objective function. It is also worthwhile to note that if ${\displaystyle m\geq n}$, the computational cost for solving this problem would be ${\displaystyle mn^{2}}$.

There does not exist an analytical formulation to solve a general linear programming problem. Nonetheless, there are some efficient algorithms, like the Simplex algorithm, for solving a linear programming problem.

## Implementation

A link to Matlab codes for this problem in the Github repository: