Discover MakerZone

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

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Can I solve this with Matlab Optimization Toolbox?

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.

5 Comments

Walter Roberson on 22 Mar 2013

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?

GFX on 29 Mar 2013

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.

GFX on 29 Mar 2013

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.

GFX

Products

No products are associated with this question.

1 Answer

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.

4 Comments

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.

GFX on 31 Mar 2013

Thanks Matt J, thanks all. :-)

Matt J

Contact us