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:

$c_1{x}_1+c_2{x}_2+...c_n{x}_n$

and constraints of the problem as:

$a_{11}{x}_1+a_{12}{x}_2+...+a_{1n}{x}_n<b_1$

$a_{21}{x}_1+a_{22}{x}_2+...+a_{2n}{x}_n<b_2$

.

.

.

$a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mn}{x}_n<b_m$

The Data

Suppose that $c_j\in {ℝ}^n$, $a_{ij}\in {ℝ}^n$, and $b_i\in {ℝ}^m$ are given parameters where $i=1,2,...,m$ and $j=1,2,...,n$. Moreover, $x=[x_1{x}_2...x_n{]}^{\text{T}}$ is an $n\times 1$ vector of positive variables.

The Optimization Problem

The optimization problem is to minimize the objective function, $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:

$\begin{array}{ccc}& \text{min}{c}^{\text{T}}x& \\ & \text{s.t.}{a}_i^{\text{T}}x\le b_{i}x\\ \end{array}$

Conclusion:

Solving this problem results in the values of variables $x$ which minimize the objective function. It is also worthwhile to note that if $m\ge n$, the computational cost for solving this problem would be $m{n}^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:

https://github.com/asalimil/LMI-for-Linear-Programming

Related LMIs

LMI for Feasibility Problem

External Links

• [1] - LMI in Control Systems Analysis, Design and Applications

Return to Main Page

LMIs in Control/Tools