[Coin-ipopt] Constraint Qualifications and IPOPT

[Peter Carbonetto]

Greetings IPOPT folks,

    I have a rather technical (and long-winded!) question regarding 
constraint qualifications and IPOPT. I would welcome any comments or 
thoughts from people that have experience or expertise on the matter.

    I'm working on a problem which I've framed as a constrained, nonlinear 
optimization problem. Naturally, I'm using IPOPT to solve it.

    My problem instances are generated randomly, and in some instances 
IPOPT either fails to converge to a solution, or has a great deal of 
difficulty doing so. I hypothesize that the reason IPOPT is having 
difficulty is that on these occasions the problem does not satisfy the 
linear independence constraint qualifications (LICQ), nor the 
Mangasarian-Fromovitz constraint qualifications (MFCQ). The only 
constraints other than bound constraints are nonlinear equality 
constraints. The randomly-generated problem instances are too large to 
verify by hand. However, I've come up with a very small example which 
could conceivably arise, in which the rows of the Jacobian are linearly 
dependent for every feasible point. A subblock of the Jacobian looks 
something like this:

    |  a/n  -b/n   c/m  -d/m  |
    | -a/n   b/n  -c/m   d/m  |
    |   0     0     0     0   |
    |   0     0     0     0   |

where a, b, c, d, n and m are all positive numbers. It is plain to see 
that the first row is always a multiple of the second row, regardless of 
what values one chooses.

    For this particular example, IPOPT has rather erratic behaviour: 
sometimes it converges quickly to the solution, sometimes it converges 
very very slowly, and occasionally it gives up.

    I decided to investigate the behaviour of IPOPT in the absence of LICQ 
a little further, and see how it does on some other small optimization 
problems that are known not to satisfy standard constraint qualifications. 
I examined 5 optimization problems: two from Forsgren, Gill and Wright 
[1], two from Izmailov and Solodov [2], and exercise 12.13 from the book 
of Nocedal and Wright (2nd edition). IPOPT failed---or converged with much 
difficulty---for 2 of the 5 problems. In both failures, neither LICQ nor 
MFCQ were satisfied at the solution.

    Now, here is my question: is there any hope that IPOPT could work with 
strategies for dealing with problems without constraint qualifications? Do 
any of you know whether the strategies of Izmailov & Solodov [2], or 
Wright [3] feasible and realistic to implement for large optimization 
problems? Has anyone had success using IPOPT to solve problems that did 
not satisfy LICQ? Or should I give up such hopes, and instead peruse the 
literature for ideas on how to modify my undesirable equality constraints?

    Any suggestions would be welcome.

Peter Carbonetto
Ph.D. Candidate
Dept. of Computer Science
University of British Columbia

REFERENCES

[1] Forsgren, Gill and Wright. (2002) Interior Methods for Nonlinear
Optimization. SIAM Review 44: 525-597.

[2] Izmailov and Solodov. (2004) Newton-Type Methods for Optimization
Problems without Constraint Qualifications. SIAM Journal on
Optimization 15: 210-228.

[3] Wright. (2005) An algorithm for degenerate nonlinear programming
with rapid local convergence. SIAM Journal on Optimization 15:
673-696.