4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Could you clarify what are $A$, $b$, and their dimensions? Is $x$ assumed to be nonnegative? $\endgroup$
    – Mark
    Commented May 20, 2013 at 11:07
  • $\begingroup$ 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$. $\endgroup$
    – user21277
    Commented May 20, 2013 at 11:30
  • $\begingroup$ My first reaction was that this is related to the "maximum feasible subsystem" problem but then I noticed the unit vector constraint... $\endgroup$
    – Dirk
    Commented Aug 20, 2013 at 15:58

1 Answer 1

Reset to default
1
$\begingroup$

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 .

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .