Using Accord optimization for geometric constraint solver.

[Brad Phelan]

Hi there,

I'm trying to use use Accord as a solver for a geometric constraint solver for this library https://github.com/bradphelan/SketchSolve.NET

The library was originally C++ and I have ported it to C#. I want to swap out the numerical solver for something more maintainable and was hoping to use the accord solver here. However my first try ended up with a runtime error that I'm not sure about. I have the following code snippet.

       public static Result solve (bool isFine, IEnumerable<Constraint> cons)
        {
            var constraints = cons.ToArray ();

            // Get the parameters that need solving
            Parameter[] x = constraints.SelectMany (p=>p)
                .Distinct ()
                .Where(p=>p.free==true)
                .ToArray ();

            var f = new NonlinearObjectiveFunction
                ( x.Length
                , args => {
                    int i = 0;
                    foreach (var arg in args) {
                        x[i].Value = arg;
                    }
                    return calc (constraints);
                });

            // Now we can start stating the constraints 
            var nlConstraints = x.Select (p =>
                new NonlinearConstraint(f,
                    // 1st contraint: x should be greater than or equal to 0
                    function: (args) => p.Value, 
                    shouldBe: ConstraintType.GreaterThanOrEqualTo, 
                    value: 0
                )).ToList ();

            // Finally, we create the non-linear programming solver 
            var solver = new AugmentedLagrangianSolver(x.Length, nlConstraints);

            // And attempt to solve the problem 
            double minValue = solver.Minimize(f);

            return Result.succsess;

        } 

I have a framework for building geometric constraints and a function called calc which returns the current

error on the constraints.  The above is a naive first attempt to wrap my framework to make it accord

compatibile. However when I run my tests they all fail with the same error

which seems to suggest I have not set the gradient of the objective function. However in the API the gradient is

optional and I thought the algorithm would try to estimate the gradient if it was missing. I cannot calculate it

manually because the function is not trivially differentiable as it is a function of many geometric constraints

that are put together interactively.

Perhapps I am doing something obviously wrong and somebody can point it out.

Regards

Brad

[Brad Phelan]

I guess I could use the FiniteDifferences utility to estimate the gradient?

https://code.google.com/p/accord/source/browse/trunk/Sources/Accord.Math/Differentiation/FiniteDifferences.cs

[Brad Phelan]

Ok I got it to work ( sort of ) with

        public static double solve (bool isFine, IEnumerable<Constraint> cons)

        {
            var constraints = cons.ToArray ();

            // Get the parameters that need solving
            Parameter[] x = constraints.SelectMany (p=>p)
                .Distinct ()
                .Where(p=>p.free==true)
                .ToArray ();

            Func<double[], double> objective = args => {

                int i = 0;
                foreach (var arg in args) {
                    x [i].Value = arg;
                }

                var error = calc (constraints);
                Console.WriteLine(error);
                return error;
            };

            var gradient 
                = new FiniteDifferences (x.Length, objective); 

            var f = new NonlinearObjectiveFunction
                ( x.Length

                , objective
                , args => gradient.Compute(args)

                );

            // Now we can start stating the constraints 
            var nlConstraints = x.Select (p =>
                new NonlinearConstraint(f,
                    // 1st contraint: x should be greater than or equal to 0
                    function: (args) => p.Value, 
                    shouldBe: ConstraintType.GreaterThanOrEqualTo, 
                    value: 0
                )).ToList ();

            // Finally, we create the non-linear programming solver 

            var solver = new AugmentedLagrangianSolver(x.Length, new List<NonlinearConstraint>());

            // And attempt to solve the problem 
            double minValue = solver.Minimize(f);

            return minValue;

        }

though I'm not sure about the results. Need to spend some time with it

[César]

Hi Brad,

There is a section in code written as

                int i = 0;
                foreach (var arg in args) {
                    x [i].Value = arg;
                }

shouldn't it be

                int i = 0;
                foreach (var arg in args) {

                    x [i++].Value = arg;
                }

so the "i" variable is incremented? As the code currently is, the x[i] will always evaluate to x[0].

Best regards,

Cesar

[Brad Phelan]

Hey thanks for the reply. I actually spotted that a while ago and fixed it. I'm now having more success but having issues with convergence of the solutions.

Sometimes my setups converge and sometimes they do not???

My solver code is as below. However I'm not really sure about how I'm handling the gradient of the objective and constraints. It might be

totally wrong.

namespace SketchSolve
{

    public static class Solver
    {
        public static double solve (bool isFine, params Constraint[] cons)
        {
            return solve (isFine, (IEnumerable<Constraint>)cons);

        }

        public static double solve (bool isFine, IEnumerable<Constraint> cons)
        {
            var constraints = cons.ToArray ();

            // Get the parameters that need solving
            Parameter[] x = constraints.SelectMany (p=>p)
                .Distinct ()
                .Where(p=>p.free==true)
                .ToArray ();

            Func<double[], double> objective = args => {

                int i = 0;
                foreach (var arg in args) {
                    x [i].Value = arg;

                    i++;
                }
                var error = Constraint.calc (constraints);

                Console.WriteLine ( "x[" +  String.Join (", ", x.Select(y=>y.Value) ) + "]");
                Console.WriteLine(error);
                Console.WriteLine ("");

                return error;
            };

            var gradient 
                = new FiniteDifferences (x.Length, objective); 

            var f = new NonlinearObjectiveFunction
                ( x.Length
                , objective

                 , args => { 
                    var g =  gradient.Compute(args);
                    Console.WriteLine ( "g[" +  String.Join (", ", g ) + "]");
                    return g;

                   }
                );

            // Now we can start stating the constraints 

            var nlConstraints = x.SelectMany ((p,i) =>{
                    Func<double[],double> cfn = args=>x[i].Value;
                    var gcfn_ = new FiniteDifferences(x.Length, cfn);
                    Func<double[],double[]> gcfn = args=>gcfn_.Compute(args);
                    return new[]{

                        new NonlinearConstraint(f,
                            // 1st contraint: x should be greater than or equal to 0

                            function: cfn, 
                            shouldBe: ConstraintType.GreaterThanOrEqualTo, 
                            value: p.Min,
                            gradient: gcfn
                        ),

                        new NonlinearConstraint(f,
                            // 1st contraint: x should be greater than or equal to 0

                            function: cfn, 
                            shouldBe: ConstraintType.LesserThanOrEqualTo, 
                            value: p.Max,
                            gradient: gcfn 
                        ),

                    };

                }).ToList ();

            // Finally, we create the non-linear programming solver 

            var solver = new AugmentedLagrangianSolver(x.Length,  nlConstraints);

            solver.SetPrivatePropertyValue ("Solution", x.Select (v=>v.Value).ToArray ());