LMIs in Control/pages/LMI for Feasibility Problem

LMI for Feasibility Problem in Optimization

The feasibility problem is to find any feasible solutions for an optimization problem without regard to the objective value. This problem can be considered as a special case of an optimization problem where the objective value is the same for all the feasible solutions. Many optimization problems have to start from a feasible point in the range of all possible solutions. One way is to add a slack variable to the problem in order to relax the feasibility condition. By adding the slack variable the problem any start point would be a feasible solution. Then, the optimization problem is converted to find the minimum value for the slack variable until the feasibility is satisfied.

The System

Assume that we have two matrices as follows:

${\begin{aligned}A(x)=A_{0}+A_{1}x_{1}+...+A_{n}x_{n}\quad i=1,2,...,n\end{aligned}}$

${\begin{aligned}B(x)=B_{0}+B_{1}x_{1}+...+B_{n}x_{n}\quad i=1,2,...,n\end{aligned}}$

which are matrix functions of variables $x=[x_{1}\quad x_{2}\quad ...\quad x_{n}]^{\text{T}}\in \mathbb {R} ^{n}$.

The Data

Suppose that the matrices ${\begin{aligned}A_{0},A_{1},...,A_{n}\quad \end{aligned}}$ and ${\begin{aligned}B_{0},B_{1},...,B_{n}\quad \end{aligned}}$ are given.

The Optimization Problem

The optimization problem is to find variables ${\begin{aligned}x=[x_{1}\quad x_{2}...x_{n}]\end{aligned}}$ such that the following constraint is satisfied:

${\begin{aligned}A(x)<B(x)\end{aligned}}$

The LMI: LMI for Feasibility Problem

This optimization problem can be converted to a standard LMI problem by adding a slack variable, $t$.

The mathematical description for this problem is to minimize $t$ in the following form of the LMI formulation:

${\begin{aligned}&{\text{min}}\quad t\\&{\text{s.t.}}\quad A(x)<B(x)+tI\\\end{aligned}}$

Conclusion:

In this problem, $x$ and $t$ are decision variables of the LMI problem.

As a result, these variables are determined in the optimization problem such that the minimum value of $t$ is found while the inequality constraint is satisfied.

Implementation

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

https://github.com/asalimil/LMI-for-Feasibility-Problem-of-Convex-Optimization

Related LMIs

LMI for Linear Programming

External Links

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

Return to Main Page

LMIs in Control/Tools