[Ipopt] [Coin-ipopt] FW: IPOPT efficiency

[Andreas Waechter]

Hello,

> Thank you very much for taking time to answer my questions. It is
> really helpful. Now, I have other questions.
>
> 1) Our objective and constraints are separable functions. Thus, the
>    W_k in Equations (11) and (13) in your paper is a diagonal
>    matrix. Does it guarantee the matrix in the top left block in the
>    matrix in (13) is a diagonal matrix for all cases ( I am not quite
>    sure about Sigma_k)? I believe that IPOPT solves the Eq(13) instead
>    Eq(11) due to the filter line-search step.

Yes, since Sigma_k is always a diagonal matrix, the upper left matrix
in (13) is always diagonal if your W_k is diagonal.  And, yes, Ipopt
solved system (13), but this has not much to do with the fact that
Ipopt is a filter method; it has to do with the fact that we need to
generate descent directions (we would have to do so also if Ipopt uses
a penalty function), and with the fact that we might choose \delta_c
to be non-zero if A_k is rank-deficient, since otherwise we could not
factorize the (then singular) matrix.

> > 2) Looking at Eq(13), the lower right block in the matrix (n+m)*(n+m)
>    is diagonal. Right?.

Yes, but \delta_c is usually zero.  It is only nonzero if Ipopt thinks
that A is rank-deficient, or if Ipopt is in the restoration phase.

> If it true and A_k does have full rank (in our
>    case, I expect many engineering cases), then, we can have
>    d_k(lamda) in terms of d_k(x).

I guess what you mean would only work if \delta_c is nonzero, and as I
said, this is usually not the case.  Or maybe you mean it like this:

If we have the linear system

/  W   A \ / x \     / a \
|        ||    | = - |   |
\ A^T  0 / \ y /     \ b /

with A full rank and W positive definite (is it in your application?),
you could solve it as

[A^T W^{-1} A] y = b - A^T W^{-1} a      to get y, and then

x = -W^{-1} a - W^{-1} A y

(modulo sign errors I might just have made).  You would have to form
[A^T W^{-1} A] and factorize it.

>  Finally (inserting the first row in
>    Eq 13), we can reduce the system (n+m)*(n+m) to a smaller system
>    n*n. If M>>n (many constraints but less design variables). The
>    reduced linear system is much easy to be solved. Or, do you think a
>    good sparse linear solver can take care of that diagonal lower
>    right block efficiently (so it is not necessary to reduce the
>    linear system) ? Am I wrong here ?

Yes, it is my understanding that a good sparse linear solver would do a 
good job here, if it uses a good BLAS/LAPACK implementation.  But if your 
A is really dense, it might be better to use a different data structure to 
store all matrices and to use LAPACK directly to do the above arithmetic. 
Again, this assumes that W is positive definite, or at least invertible 
and known to be positive definite if projected onto the null space of A^T.

The problem is that such a change would require knowledge of quite a 
number of details of the Ipopt implementation.  I don't have any plans to 
do something like this.  If you wanted to do that yourself,

> 3) Active set strategy.
>
> We define a constraint to be active when the constraint is violated or
> close the bound. As you know, the active set strategy is used in many
> SQP algorithms. Is it possible to apply the active set strategy to
> IPOPT? There are two reasons for that.
>
> (a) We usually have a huge number of constraints in engineering
> applications. However, majority of the constraints are far from the
> bound.
>
> (b) For engineering problems, the Jacobian matrix is often 100%
> dense. It is very hard to hold the Jacobian matrix for large problems
> (due to limited computer memory. For example, we have 1 million
> variables and 1 million constraints).
>
> Applying the active set strategy in IPOPT, I think we have active
> constraints only in Eq. (11) or (13) (A_k and W_k_ computation), then
> we have the search direction by solving the reduced system (only
> holding the active constraints). Well, the active constraints may
> switch in next iterations. The search direction may not be as good
> (robust) as the one with full constraint set. However, with the line
> search steps, I think we can solve many problems at least in more
> efficient way (due to a smaller linear system) with less computer
> memory requirement. This active set strategy may take more iterations
> to converge or even not converge. However, it does provide us a
> practical way to solve very large engineering problems from engineer's
> point of view. How do you think?

The art in an active set method is to decide what are the active
constraints.  Active set SQP methods solve a QP by an active set
method in each iteration, and the active inequalities in this QP
solution are what is usually called to be the active set.  There are
also SLP-EQP methods that solve an LP first to determine the active
set, and then use this active set to solve the linear system you
describe only for the active constraints.  But in both cases, one
needs to solve a QP or an LP first in order to determine the active
set, and both LP and QP need to know about the gradients of all
constraints, at least they have to be generated if the QP/LP solver
wants to test this constraint.

In other words, I don't see a simple solution here.  Ipopt has been
designed as an interior point method, and trying to make an active set
method out of it will be awkward since all data structures and
algorithmic details are set up for the interior point approach.  It
would then make more sense to write a new solver.

I agree with you that it would be great to have a good open source active 
set NLP solver.  I don't know of one, but I would be very happy to learn 
about such codes!

Regards

Andreas