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 edit

We define the objective function as:

 

and constraints of the problem as:

 

 

.

.

.

 

The Data edit

Suppose that  ,  , and   are given parameters where   and  . Moreover,   is an   vector of positive variables.

The Optimization Problem edit

The optimization problem is to minimize the objective function,   when the aforementioned linear constraints are satisfied.

The LMI: LMI for linear programming edit

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

 

Conclusion: edit

Solving this problem results in the values of variables   which minimize the objective function. It is also worthwhile to note that if  , the computational cost for solving this problem would be  .

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 edit

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

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

Related LMIs edit

LMI for Feasibility Problem

External Links edit

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


Return to Main Page edit

LMIs in Control/Tools