1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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