Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Could you clarify what are $A$, $b$, and their dimensions? Is $x$ assumed to be nonnegative? –  Mark May 20 '13 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 '13 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 '13 at 15:58

1 Answer 1

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 .

share|improve this answer
    
Edit. dummy i instead of j. –  Mark May 20 '13 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 '13 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 '13 at 7:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.