# Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint

I am wondering what is known about optimization problems of the following type.

Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities $$Az≥b,$$ and we would like to select $x$ so that when substituted in place of $z$ the largest number of such inequalities is satisfied.

I can think of a brute force way of solving the problem, which is to consider every possible subset of the inequalities, and solve the optimization problem of finding the nearest point to the origin. Is there something better?

Any ideas or references to literature would be appreciated. I would also be interested in dual problems, and would like to know if this sort of problem has an official name or can be converted to a standard one.

-
Could you clarify what are $A$, $b$, and their dimensions? Is $x$ assumed to be nonnegative? –  Mark May 20 at 11:07
If it helps, we can assume that $x$ is nonnegative. These are some $m$ linear inequalities of the form $$a_{i1} z_1+a_{i2} z_2 +\ldots+a_{in} z_n \geq b_i$$ with $i=1,2,\ldots,m$. These are organized into an $m \times n$ matrix $A$. No assumptions are made about $b$. –  user21277 May 20 at 11:30
My first reaction was that this is related to the "maximum feasible subsystem" problem but then I noticed the unit vector constraint... –  Dirk Aug 20 at 15:58

Your problem can be formulated as a nonlinear programming problem in such way. Let $$f_i(x):= \text{piecewise} \left(\sum_{j=1}^{j=n} a_{i,j}x_j- b_i <0,0,1 \right).$$ Then we find $$\max f(x)= \sum_{i=1}^{i=m}f_i(x)$$ under the constraint $$\sum_{j=1}^{j=n} x_j^2 =1.$$ This can be solved by global optimizers. I use the DirectSearch in Maple (See http://www.maplesoft.com/applications/view.aspx?SID=101333 .).

See an example in an *.mw file from http://rapidshare.com/files/1627770637/NP.mw .

-
Edit. dummy i instead of j. –  Mark May 20 at 12:55
Mark: In reply to your comment on the answer I'm deleting: oops! I totally missed the unit vector part. –  Noah Stein May 20 at 13:43
This example for $n=20$ and $m=25$ can be downloaded as a *.pdf file from rapidshare.com/files/2904066844/NP.pdf . –  Mark May 21 at 7:56