How to debug a constrained optimization algorithm?

Question

I have implemented a saddle point optimization problem based on the algorithm by Prof. Nesterov, primal-dual[1]. Unfortunately, it doesn't work. It seems it is converging. But unfortunately, not to the optimal solution which I get with some out of the box solver. I am confident that out of the box solver's result is correct.

My question is, based on the arguments by paper, algorithm must work correctly. But somethings gets wrong. I want to check inequalities and conditions in proofs of the paper, But I don't know how to do this?especially because many of the inequalities involved unknown optimal solution ($x^*$). Is there any way to check inequalities in the paper, and understand what is wrong which cause my implementation doesn't work?

Note that I solved inner optimization problems in algorithm, using the same solver.

[1], Yurii Nesterov, Primal-dual subgradient methods for convex problems , Math. Program. 2009

Answer 1

You can use a Test Driven Development (TDD), the ideas behind are:

• before write code you write the test with the expected result;
• every line of code (almost all lines) is under test so when you modify a line you can check if there is the correct behavior or side effects.

With this methodology you can find and prevent some erros described by Dirk.

To write significative test from a math point of you follow the advice of Wolfgang Bangerth. You keep a simple case that you can do by hand and where you now the exact solution (in your case the optimal solution $x^*$). I this way you can put under tests the inequalities in the paper, and check the individual steps.

To keep you life easy try to use a unit-test framework (many languages have got it).

The advantages of using TDD emerge in subsequent amendments to the first draft, and you will save time in the future operations to your code.

Answer 2

Writing an optimization routine is like writing any other not too simple program and involves a fair amount of debugging. All things you mention in your question are good checks (i.e. taking care that all the things that theoretically should hold do indeed hold during iterations).

Some more general checks are:

• Are you sure that solutions are unique? If not, two solvers may return different optimal solutions.

• Primal values. See if the values of the primal objective values converge. If all primal values are finite (i.e. feasible) then the sequence of primal objectives should converge to the minimum of the sequence (not necessarily monotone). You can also compare the primal values of the outcome of your algorithm with the primal value of the black box solver.

• Similarly with dual values.

Some standard errors:

• Errors in the stepsizes. Some times a wrong stepsizes still leads to a convergent method but and in fact solving a different problem.

• Wrong order of updates.

• Signs, especially in front of data terms.

• All kinds of bugs, e. g. using the name of the iteration counter for some other purpose, accidentally overwriting somethings...

Answer 3

In addition to the things that @Dirk already states, run your algorithm on a problem that is simple enough that you can do each step of the algorithm exactly on a piece of paper. Then compare what your algorithm actually does.

For example, run it on a problem where you try to minimize a low-degree polynomial with linear constraints.