attempting to do some geometry constraints on the solver and failing

[Brannon]

In the code below, if I don't add the "distanceMatch" constraints then the sx, sy, ex, ey constraints are used. However, when I add the distanceMatch constraints, those other four are ignored (or prioritized very low). Why is that? The code below is just attempting to put equally spaced points on a line (var[0] = x0, var[1] = y0, var[2] = x1, etc.) At a future point I want to add some more constraints that will make the result be nonlinear.

 

using System;
using System.Collections.Generic;
using Accord.Math.Optimization;
using AutoDiff;
namespace NewPlanner
{
 class AccordPlanner
 {
  public event Action<AccordPlanner, int> DrawProgress = delegate { };
  private const double Tolerance = 0.001;
  readonly NonlinearObjectiveFunction _f;
  readonly List<NonlinearConstraint> _constraints;
  public AccordPlanner(double startPointX, double startPointY, double startAngle, double endPointX, double endPointY, double endAngle)
  {
   var variables = new Variable[10];
   for(int i = 0; i < variables.Length; i++)
    variables[i] = new Variable();
   var distanceSum = BuildDistanceTerm(variables);
   _f = new NonlinearObjectiveFunction(variables.Length, ds => distanceSum.Evaluate(variables, ds), ds => distanceSum.Differentiate(variables, ds));
   var sx = new NonlinearConstraint(_f, ds => variables[0].Evaluate(variables, ds), ConstraintType.EqualTo, startPointX, ds => variables[0].Differentiate(variables, ds), Tolerance);
   var sy = new NonlinearConstraint(_f, ds => variables[1].Evaluate(variables, ds), ConstraintType.EqualTo, startPointY, ds => variables[1].Differentiate(variables, ds), Tolerance);
   var ex = new NonlinearConstraint(_f, ds => variables[variables.Length - 2].Evaluate(variables, ds), ConstraintType.EqualTo, endPointX, ds => variables[variables.Length - 2].Differentiate(variables, ds), Tolerance);
   var ey = new NonlinearConstraint(_f, ds => variables[variables.Length - 1].Evaluate(variables, ds), ConstraintType.EqualTo, endPointY, ds => variables[variables.Length - 1].Differentiate(variables, ds), Tolerance);
   _constraints = new List<NonlinearConstraint>{sx, sy, ex, ey};
   for (int i = 5; i < variables.Length; i += 2)
   {
    // one distance minus the other distance should be 0
    var distanceMatch = BuildDistanceMatch(variables, i);
    _constraints.Add(new NonlinearConstraint(_f, ds => distanceMatch.Evaluate(variables, ds), ConstraintType.EqualTo, 0.0, ds => distanceMatch.Differentiate(variables, ds), Tolerance));
   }
  }
  private Term BuildDistanceMatch(Variable[] vs, int i)
  {
   var ydi = vs[i - 0] - vs[i - 2];
   var xdi = vs[i - 1] - vs[i - 3];
   var yd1 = vs[i - 2] - vs[i - 4];
   var xd1 = vs[i - 3] - vs[i - 5];
   return TermBuilder.Power(xdi * xdi + ydi * ydi, 0.5) - TermBuilder.Power(xd1 * xd1 + yd1 * yd1, 0.5);
  }
  private Term BuildDistanceTerm(Variable[] vs)
  {
   var ret = TermBuilder.Constant(0.0);
   for (int i = 3; i < vs.Length; i += 2)
   {
    // add the distance between two points
    var xd = vs[i - 1] - vs[i - 3];
    var yd = vs[i] - vs[i - 2];
    ret += TermBuilder.Power(xd * xd + yd * yd, 0.5);
   }
   return ret;
  }
  public void Run()
  {
   var solver = new AugmentedLagrangianSolver(_f.NumberOfVariables, _constraints);
   var rand = new Random(42);
   for (int i = 0; i < solver.Solution.Length; i++)
   {
    solver.Solution[i] = rand.NextDouble() * 500;
   }
   // you can fill in the initial values of the Solution property
   var minimum = solver.Minimize(_f);
  }
 }
}

 

[César]

Hi Brannon,

I just wanted to let you know that I am trying to evaluate the problem here to see what is going on; please apologize for the delay in answering your question!

Best regards,

Cesar

[César]

Hi Brannon,

Most likely this could be an issue with the tolerances on each of the function parameters. If the variables have different operating scales, using a single Tolerance value for all of them might be problematic.

I have a possible fix in mind, but I would need to test your code to see if it actually solves the issue. Can you include the source for the Variable, Term and TermBuilder classes as well as the parameters you are using on your class constructor, so I could check if it indeed solves this issue?

Best regards,

Cesar

[César]

Hi Brannon,

I am producing a new set of the framework binaries addressing an issue I've found on the Augmented Lagrangian solver. Please let me know if this version works better (you might have to remove the previous .dlls - please keep a backup copy of them in case the older version works better). 

Best regards,

Cesar

[Brannon]

Cesar, thanks for looking into this. I tried your newer version, but could see no significant change in results. I modified the run method to look like this:

 

public event Action<IList<Point>> ResultAchieved = delegate { };

public void Run()
{
 var solver = new AugmentedLagrangianSolver(_f.NumberOfVariables, _constraints);
 var rand = new Random(42);
 for (int i = 0; i < solver.Solution.Length; i++)
 {
  solver.Solution[i] = rand.NextDouble() * 500;
 }
 // you can fill in the initial values of the Solution property
 var minimum = solver.Minimize(_f);

 var ret = new List<Point>(solver.Solution.Length / 2);
   
 for(int i = 1; i < solver.Solution.Length; i+= 2)
 {
  ret.Add(new Point(solver.Solution[i-1], solver.Solution[i]));
 }
 ResultAchieved.Invoke(ret);
}

 

I then added this test in a separate project:

 

using NUnit.Framework;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using NewPlanner;
using System.Windows;
namespace NewPlanner.Tests
{
 [TestFixture]
    class TestAccord
    {
  [Test]
  public void TestBasicLine()
  {
   var planner = new AccordPlanner(10.0, 10.0, 0.0, 50.0, 50.0, 0.0); // angles aren't used yet
   IList<Point> results = null;
   planner.ResultAchieved += list => results = list;
   planner.Run();
   var gap = (50.0 - 10.0) / results.Count;
   for (int i = 0; i < results.Count; i++)
   {
    Assert.AreEqual(10.0 + i * gap, results[i].X, 0.01);
    Assert.AreEqual(10.0 + i * gap, results[i].Y, 0.01);
   }
  }
    }
}

 

[César]

Thanks, this seems easier to test; but can you please include the source for the Variable, Term and TermBuilder classes as well? Otherwise I am afraid I still wouldn't be able to run the example.

Regards,

Cesar

[Brannon]

Those items all come from the AutoDiff package. Can you grab that with Nuget? See http://autodiff.codeplex.com/

[César]

Ah ok! I thought they were part of your project. I will download it. Thanks.

[César]

Hi Brannon,

Using that newer version, instead of 

   var solver = new AugmentedLagrangianSolver(_f.NumberOfVariables, _constraints);

Please try changing it to

    ResilientBackpropagation prop = new ResilientBackpropagation(_f.NumberOfVariables);
    var solver = new AugmentedLagrangianSolver(prop, _constraints);

It should produce much closer results, although still not the ones you specified. I will see how we can improve it further.

Best regards,

Cesar

[César]

Hi Brannon,

From the code, I can see you were expecting values like { 10, 18, 36, 48 } or similar (sorry, I couldn't not run the code right now to double-check). However, which values would you consider as valid outpout? If the code generated the values { 10, 20, 30, 40, 50 }, would you consider those values correct?

Best regards,

Cesar

[Brannon]

My test is not correct. {10, 20, 30, 40, 50 } are the correct values. My test should read

 

var gap = (50.0 - 10.0) / (results.Count - 1);

[César]

Hi Brannon,

If that is the case, then please let me know if this version works better. Just copy those two dlls over the others from my last post. You can create the solver directly like

var solver = new AugmentedLagrangianSolver(_f.NumberOfVariables, _constraints);

Best regards,

Cesar

[count...@gmail.com]

Cesar, can you confirm that this fixed AugmentedLagrangianSolver is in the 5 Jan 2014 build of Accord?

[César]

Hi there!

The fixed version I posted here is now in the 5 Jan 2014 build. However, a refactored version with more fixes will also be available in the next version. If you are still having trouble with the Augmented Lagrangian, I would suggest to try multiple inner solvers. Sometimes some of them works better than others. The point is that the next version of the framework is also bringing significant fixes to all other solvers, thus enhancing the augmented lagrangian.

Best regards,

Cesar