Incluant une Journée industrielle de l'optimisation
HEC Montréal, 7  9 mai 2012
JOPT2012
HEC Montréal, 7 — 9 mai 2012
WB8 Dégénérescence en optimisation lisse / Degeneracy in Smooth Optimization
9 mai 2012 11h00 – 12h15
Salle: Transat
Présidée par Dominique Orban
3 présentations

11h00  11h25
Customizing the Solution Process of COINOR's Linear Solvers with Python
We introduce CyLP, an opensource application to model and solve linear and mixedinteger linear programs in Python. CyLP wraps around solvers from COINORa repository of opensource optimization software. In addition to a mere interface, CyLP allows modification of the solution process via python scripts. In linear programming, users can easily define customized pivot rules. In MIPs, CyLP allows users to customize the branchandcut tree transversal method. We illustrate these features by implementing the positive edge pivot rule, an efficient pivot rule for degenerate linear programs.

11h25  11h50
Superlinear Convergence of PrimalDual InteriorPoint Methods in the Absence of Strict Complementarity
In the absence of strict complementarity, the powerful interiorpoint methods exhibit, in the best case, a linear convergence rate on nonlinear problems. In this talk, we propose a cheap and
efficient dual update strategy to recover the Qsuperlinear convergence of the iterates. We present numerical results on a test set of non strictly complementary problems. 
11h50  12h15
The Bitter Truth About InteriorPoint Methods
Interiorpoint methods feature prominently in the solution of constrained optimization problems, and involve the need to solve a sequence of 3x3 block indefinite system which become increasingly illconditioned throughout the iteration. To solve these systems, it is common practice to perform a block Gaussian elimination, and then either solve the resulting reduced 2x2 block indefinite system that has a typical saddlepoint form, or further reduce the system to the normal equations and apply a symmetric positivedefinite solver. We explore whether the step of reducing the system from 3x3 block form to a 2x2 block form necessarily pays off. We use energy estimates to obtain bounds on the eigenvalues of the matrices in question, which indicate that in fact at least in terms of spectral structure, it may be better to keep the system in its original unreduced form rather than perform a partial elimination.