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

Hi all -- what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, where some constraints are non-linear (and non-differentiable), e.g. $0 \leq x_i \leq 1$, and $\sum_i x_i \mathbf{1}_{x_i>a} < b$ ?

I am thinking about $N \approx 100$. FWIW, Matlab is apparently using an "active set method, similar to that of Gill et al.", which has somewhat uneven performance.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

The real issue here is the constraint

$\sum_{i} x_{i}1_{x_{i}>a} < b $

whose left hand side has horrible discontinuities.

Rather than using a solver designed for problems with continuous variables, you should formulate this as 0-1 mixed integer nonlinear programming problem, with binary decision variables $z_{i}$ that are 0 when $x_{i} \leq a$ and 1 when $x_{i}>a$. You can then use branch and bound to solve the problem.

share|improve this answer
    
Thanks, this works :) –  laxxy May 24 '12 at 2:29
add comment

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.