given a system of inequalities expressed in the following way: A x &gt; k _ where A ∈ M n , m ( R ) , with n&gt;m, and k _ = ( k , k , … , k ) ∈ R n In general, the system might or might not admit solutions. I would like to find a solution x ∈ R m that minimizes the number of violated inequalities.

Question

given a system of inequalities expressed in the following way:  A  x  &amp;gt;      k    _  where   A  ∈        M          n      ,      m      (          R      )      , with n&amp;gt;m, and       k    _    =  (  k  ,  k  ,  …  ,  k  )  ∈        R    n  In general, the system might or might not admit solutions. I would like to find a solution   x  ∈        R    m   that minimizes the number of violated inequalities.

garcialdariamcy4q · Accepted Answer

A  x  &amp;gt;  k is a difficult concept in optimization. Usually we deal with   A  x  ≥  k. (If needed you can add a small number   ε  &amp;gt;  0 to   k; note also that solvers typically employ a feasibility tolerance, so ε should be larger than that).So, assume we have   A  x  ≥  k. Next we can do                    min                                              ∑          i                          δ          i                                                            ∑          j                          a                      i            ,            j                                    x          j                ≥        k        −                  δ          i                M                                            δ          i                ∈        {        0        ,        1        }            Here   M is a large enough number.

llunallenaipg5r · Accepted Answer

Thanks a lot for your answer, it is very very helpful!

given a system of inequalities expressed in the following way: A x > <munder>

Answered question

Answer & Explanation

New Questions in Algebra I