MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn moreOpportunities for recent engineering grads.

Apply Today
Asked by GFX on 22 Mar 2013

Dear all,

Hi, I'm new to Matlab and also to optimization problems. I need help on an optimization problem. The problem is as follows:

find x=(est_pos_1, ... est_pos_n) minimizing the sum of squared difference between elements in matrix A and B where: a_ij = 1 if Euclidean distance between est_pos_i and est_pos_j is less than constant R and 0 otherwise, 0 < i, j < m + n, m is number of points with known position, n of points with unknown positions to be estimated, b_ij = 1 if Euclidean distance between actual_pos_i and actual_pos_j is less than R and 0 otherwise. Matrix B is given.

I tried solving it using Particle Swarm Optimization with poor success, i.e. the error between the estimated and actual positions is high.

*No products are associated with this question.*

Answer by Matt J on 29 Mar 2013

Edited by Matt J on 29 Mar 2013

Accepted answer

No, you can't use the Optimization Toolbox. The solvers in the Toolbox are smooth algorithms (except for bintprog) and therefore apply to differentiable functions.

However, your matrix A, and therefore the objective function overall, is a piecewise constant, non-differentiable, function of x. The piecewise constant behavior will also mean that the objective function is flat almost everywhere, making almost every point a local minimum where the optimization can get stuck.

Show 1 older comment

GFX on 29 Mar 2013

For example, how do I easily and quickly determine if such a problem is say linear, convex, or non linear? I know about the standard forms of LP, convex programs and such, but for eg. in my original question, how do you determine them?

Matt J on 29 Mar 2013

Well, I don't think there's always an easy way. Certainly optimization textbooks will always give examples of functions that are convex etc... and you build your analysis skills from that.

However, in your case, the A matrix can only take on values 0 or 1. Discrete-valued functions like that have to be piecewise constant.

## 5 Comments

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/68186#comment_138170

Should the references to a_ij and b_ij be instead references to A_ij and B_ij ?

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/68186#comment_138176

Hi there, a_ij are elements of matrix A and b_ij are elements of matrix B, i, j are index for row and column of the matrix. Sorry for the inclarity. Thank you again.

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/68186#comment_138183

The two matrices A and B appear to be different sizes, as B only goes as far as the known positions but A extends to estimated positions. I am not sure what the sum of the squared difference would mean for different sized matrices?

If the values are all 0's and 1's, then squared difference would be the same as absolute difference, right? And in turn would be the same as "not equal" ?

What does it mean to estimate position (i,j) for points whose actual position is known?

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/68186#comment_139703

Hi, the size of A an B are of the same size. However, instead of determine all m+n points, we are to decide only on the position of n unknown points, since the m points we already known their position from prior knowledge. We are to determine positions of est_pos_i (estimated positions of unknown points i, n of these) given some connectivity constrains, given by B. So, we are trying to recreate the position of all points based on connectivity readings. In actual, B can be obtained for e.g. say the points know who their neighboring points are. However, for simulation, B can simply be calculated by determining if the distances between the actual positions between any pair of points. In simulation, we also have the exact positions of all points. I hope I am clear. Thank you.

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/68186#comment_139704

And the objective here is to recreate the configuration (positioning) of points that resembles the exact configuration. Hence the sum of square difference objective.

Thank you.