Can I solve this with Matlab Optimization Toolbox?

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.

[Walter Roberson]

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

[GFX]

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.

[Walter Roberson]

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]

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]

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.

Answer 1

[Matt J]

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.

[GFX]

Hi there,

Thanks for the swift and informative reply. As you probably know, I'm pretty new to optimizations and stuffs. You were able to see right away, that the objective function is piece wise constant, and non-differentiation function of x. I've attempt to read some books on optimization, but their objective are given as functions of x directly, unlike here where it is further defined difference of matrix elements and the elements of matrix defined piecewisely.

Is there trick on identifying that easily? Is there any reference that you can recommend me to read?

Thank you.

[GFX]

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]

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]

Thanks Matt J, thanks all. :-)