[Coin-ipopt] Mehrotra's predictor-corrector

Andreas Waechter andreasw at watson.ibm.com
Mon Feb 4 15:37:17 EST 2008

Hi Xiaoming,

> You mentioned in IPOPT 3.31:
> - an option 'mehrotra_algorithm' which can be used to solve LPs and
>   (convex) QPs.  It is an implementation of Mehrotra's predictor-corrector
>   algorithm.  However, there is no starting point heuristic.
> 1) Does this method support linear system dimension reduction? For 
> example, "reduction to m x m linear system from (n+m)x(n+m)linear system 
> (for many design variables n but few constraints m). Since solving the 
> linear system is very expensive for large design variables (few millions 
> design variables but few constraints), reducing the linear system 
> dimension is very helpful.

I assume that you are probably refering to a standard techique that is 
used in interior point methods for linear programming, where a matrix of 
the form

/ D  A^T \
\ A   0  /

is condensed into AD(A^T).  As far as I know, the LP codes do that since 
they want to use factorization methods for symmetric positive definite 
matrices (such as Cholesky).

In Ipopt, the D matrix is usually not a diagonal matrix (since it includes 
the Hessian of the Lagrangian function), so that the condensed linear 
system can be rather (undesiredly) dense.  Hence, Ipopt uses sparse linear 
solvers for symmtric indefinite matrices.  For linear problems with a 
diagonal D matrix, a good sparse linear solver will see that the D part of 
the matrix is only diagonal and it will essentially perform a reduction of 
the linear system automatically in some form, so that an explicit 
reduction into an m x m system should not be necessary.  (I hope I'm not 
lying here...)

> 2) Does IPOPT support convex programming efficiently compared other 
> convex-specialized software?

I don't know what "convex-specialized software" you are referring to, and 
don't know how to answer that question.



More information about the Coin-ipopt mailing list