binary quadratic optimization under linear constraints

Hi guys.

I have to find an optimal gradient and intercept of a straight to minimize the sum of squared deviations to fit a 2D data points set, with linear constraints.

So, i have to solve the binary quadratic optimization problem: minF(ki,bi)=min(sum(ki*xj+bi-yj))^2 where (xj,yj) are the coordinates of the j-th data set point.

i have also to define some constraints, such as:

ki<=Kmax;

Hmin <= ki*xj+bi-yj <= Hmax

i've tried to use fmincon and quadprog but i was not able to solve my problem. could someone give me some tips?

many thanks

Answer 1

[John D'Errico]

How is this not just a linear least squares estimation of the two unknown parameters? There is nothing binary about this, except that you have two unknowns. That is a misuse of the word, and will just confuse people.

As far as the quadratic optimization goes, again, you are trying define the problem in terms of flowery words, when a simple solution exists.

While you can use polyfit but for the constraints, those constraints make it a problem for lsqlin, which can trivially solve your problem. This is a simple linear least squares estimation problem, subject to linear inequality constaints.

[alessio morabito]

Many thanks John. You're right, but i didn't know that matlab could do this.

But now i've to implement another optimization in the algorithm:

i've to minimize (in the sense of least squares) the difference between Rj and Ri, with:

Ri=unknown variable;

Rj=[xj-(Si+Ri*A)]^2+[yj-(Zi+Ri*B)]^2]; (all terms are known, excluding Ri)

such that m<=Rj-Ri<=M

is now quadprog the best way to solve this problem?

Thanks in advance