[Coin-ipopt] IPOPT remains dual infeasible

[Peter Carbonetto]

THE SCENARIO: I have an optimization problem with about 60 variables
(later this will grow), a nonlinear objective, bound constraints (all
the variables must lie in the positive quadrant) and a sparse set of
linear constraints.

[My problem consists of solving inference in a Bayesian model using a
variational approximation.]

THE GOOD NEWS: IPOPT converges to a very reasonable solution after about 
80 iterations, and does so using a limited-memory quasi-Newton 
approximation to the Hessian (limited_memory_max_history = 5) because I 
haven't bothered to compute the second derivatives. I know the solution is 
reasonable because there is an existing algorithm tailored to my problem 
that comes up with the same answer.

THE BAD NEWS: IPOPT fails to converge to a point that is dual
feasible, or takes an extremely long time to do so. The output from
IPOPT looks something like this:

iter    objective    inf_pr   inf_du lg(mu)  ||d||
    0  9.4872744e+01 2.22e-16 4.89e+02   0.0 0.00e+00
    1  5.4935737e+01 2.22e-16 7.25e+00  -4.0 2.80e+01
    2  5.3405603e+01 1.11e-16 5.21e+00  -1.3 4.36e-02
    3  4.6288683e+01 0.00e+00 2.84e+00  -0.8 3.29e-01

                         . . .

   85  2.6698305e+01 2.22e-16 5.84e-02  -2.6 3.35e-02
   86  2.6698300e+01 2.22e-16 2.42e-02  -2.6 5.99e-02
   87  2.6658051e+01 2.22e-16 1.91e+00  -3.9 8.45e-03
   88  2.6669530e+01 2.22e-16 2.75e-01  -3.1 1.11e-02

Notice that the dual variables have failed to converge to the feasible
region. Currently, I workaround this problem by setting a high
tolerance for dual infeasibility (dual_inf_tol = 0.9).

I'm wondering if anyone may have some deeper understanding of
primal-dual methods than myself and may be able to explain why this is
going on. I suspect that the problem may have something to do with the 
quasi-Newton approximation, but I can't be sure since I haven't coded
the exact Hessian.

[By the way, Andreas, I've done all this using a MATLAB interface I've
developed. There were a few significant obstacles in getting IPOPT to
interface with MATLAB, but at this point it is working quite
nicely. More on that in the not-too-distant future.]

Thank you,

Peter Carbonetto
Dept. of Computer Science
University of British Columbia