# [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

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.

Regards,

Andreas

```