A new fast method to compute saddle-points in constrained optimization and applications

Philippe Angot; Jean-Paul Caltagirone; Pierre Fabrie

hal-00626163, version 1

A new fast method to compute saddle-points in constrained optimization and applications

Philippe Angot ( Auteur à contacter de préférence ) ¹, Jean-Paul Caltagirone () ², Pierre Fabrie () ³

Applied Mathematics Letters 25, 3 (2012) 245-251

Résumé : The solution of the augmented Lagrangian related system $(A+r\,B^TB)\,\rv=f$ is a key ingredient of many iterative algorithms for the solution of saddle-point problems in constrained optimization with quasi-Newton methods. However, such problems are ill-conditioned when the penalty parameter $\eps=1/r>0$ tends to zero, whereas the error vanishes as $\cO(\eps)$. We present a new fast method based on a {\em splitting penalty scheme} to solve such problems with a judicious prediction-correction. We prove that, due to the {\em adapted right-hand side}, the solution of the correction step only requires the approximation of operators independent on $\eps$, when $\eps$ is taken sufficiently small. Hence, the proposed method is all the cheaper as $\eps$ tends to zero. We apply the two-step scheme to efficiently solve the saddle-point problem with a penalty method. Indeed, that fully justifies the interest of the {\em vector penalty-projection methods} recently proposed in \cite{ACF08} to solve the unsteady incompressible Navier-Stokes equations, for which we give the stability result and some quasi-optimal error estimates. Moreover, the numerical experiments confirm both the theoretical analysis and the efficiency of the proposed method which produces a fast splitting solution to augmented Lagrangian or penalty problems, possibly used as a suitable preconditioner to the fully coupled system.

1 : Laboratoire d'Analyse, Topologie, Probabilités (LATP)
CNRS : UMR6632 – Université de Provence - Aix-Marseille I – Université Paul Cézanne - Aix-Marseille III
2 : Transferts, écoulements, fluides, énergétique (TREFLE)
CNRS : UMR8508 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure de Chimie et de Physique de Bordeaux (ENSCPB) – Arts et Métiers ParisTech
3 : Institut de Mathématiques de Bordeaux (IMB)
CNRS : UMR5251 – Université Sciences et Technologies - Bordeaux I – Université Victor Segalen - Bordeaux II

hal-00626163, version 1
http://hal.archives-ouvertes.fr/hal-00626163
oai:hal.archives-ouvertes.fr:hal-00626163
Contributeur : Philippe Angot <>
Soumis le : Vendredi 23 Septembre 2011, 16:20:59
Dernière modification le : Vendredi 11 Novembre 2011, 14:43:37

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1016/j.aml.2011.08.015

Exporter

Bibtex EndNote TEI RefWorks

%% hal-00626163, version 1
%% http://hal.archives-ouvertes.fr/hal-00626163
@article{angot:hal-00626163,
    hal_id = {hal-00626163},
    url = {http://hal.archives-ouvertes.fr/hal-00626163},
    title = {{A new fast method to compute saddle-points in constrained optimization and applications}},
    author = {Angot, Philippe and Caltagirone, Jean-Paul and Fabrie, Pierre},
    abstract = {{The solution of the augmented Lagrangian related system $(A+r\,B^TB)\,\rv=f$ is a key ingredient of many iterative algorithms for the solution of saddle-point problems in constrained optimization with quasi-Newton methods. However, such problems are ill-conditioned when the penalty parameter $\eps=1/r>0$ tends to zero, whereas the error vanishes as $\cO(\eps)$. We present a new fast method based on a {\em splitting penalty scheme} to solve such problems with a judicious prediction-correction. We prove that, due to the {\em adapted right-hand side}, the solution of the correction step only requires the approximation of operators independent on $\eps$, when $\eps$ is taken sufficiently small. Hence, the proposed method is all the cheaper as $\eps$ tends to zero. We apply the two-step scheme to efficiently solve the saddle-point problem with a penalty method. Indeed, that fully justifies the interest of the {\em vector penalty-projection methods} recently proposed in \cite{ACF08} to solve the unsteady incompressible Navier-Stokes equations, for which we give the stability result and some quasi-optimal error estimates. Moreover, the numerical experiments confirm both the theoretical analysis and the efficiency of the proposed method which produces a fast splitting solution to augmented Lagrangian or penalty problems, possibly used as a suitable preconditioner to the fully coupled system.}},
    keywords = {Constrained optimization; Saddle-point problems; Augmented Lagrangian; Penalty method; Splitting prediction-correction scheme; Vector penalty-projection methods},
    language = {Anglais},
    affiliation = {Laboratoire d'Analyse, Topologie, Probabilit{\'e}s - LATP , Transferts, {\'e}coulements, fluides, {\'e}nerg{\'e}tique - TREFLE , Institut de Math{\'e}matiques de Bordeaux - IMB},
    pages = {245-251},
    journal = {Applied Mathematics Letters},
    volume = {25},
    number = {3 },
    audience = {internationale },
    doi = {10.1016/j.aml.2011.08.015 },
    year = {2012},
    pdf = {http://hal.archives-ouvertes.fr/hal-00626163/PDF/AML\_ACF11\_am.pdf},
}

%F hal-00626163, version 1
%0 Journal Article
%U http://hal.archives-ouvertes.fr/hal-00626163
%2 MATH:MATH_OC;MATH:MATH_NA;MATH:MATH_AP;PHYS:MECA:MEFL;SPI:MECA:MEFL;SPI:FLUID
%T A new fast method to compute saddle-points in constrained optimization and applications
%A Angot, Philippe
%A Caltagirone, Jean-Paul
%A Fabrie, Pierre
%+ Laboratoire d'Analyse, Topologie, Probabilités - LATP , Transferts, écoulements, fluides, énergétique - TREFLE , Institut de Mathématiques de Bordeaux - IMB
%X The solution of the augmented Lagrangian related system $(A+r\,B^TB)\,\rv=f$ is a key ingredient of many iterative algorithms for the solution of saddle-point problems in constrained optimization with quasi-Newton methods. However, such problems are ill-conditioned when the penalty parameter $\eps=1/r>0$ tends to zero, whereas the error vanishes as $\cO(\eps)$. We present a new fast method based on a {\em splitting penalty scheme} to solve such problems with a judicious prediction-correction. We prove that, due to the {\em adapted right-hand side}, the solution of the correction step only requires the approximation of operators independent on $\eps$, when $\eps$ is taken sufficiently small. Hence, the proposed method is all the cheaper as $\eps$ tends to zero. We apply the two-step scheme to efficiently solve the saddle-point problem with a penalty method. Indeed, that fully justifies the interest of the {\em vector penalty-projection methods} recently proposed in \cite{ACF08} to solve the unsteady incompressible Navier-Stokes equations, for which we give the stability result and some quasi-optimal error estimates. Moreover, the numerical experiments confirm both the theoretical analysis and the efficiency of the proposed method which produces a fast splitting solution to augmented Lagrangian or penalty problems, possibly used as a suitable preconditioner to the fully coupled system.
%G Anglais
%2 2011-01-01
%R 10.1016/j.aml.2011.08.015
%J Applied Mathematics Letters
%2 internationale
%8 2012-00-00
%2 2011-08-22
%V 25
%N 3
%P 245-251
%K Constrained optimization; Saddle-point problems; Augmented Lagrangian; Penalty method; Splitting prediction-correction scheme; Vector penalty-projection methods
%Z \MSC[2010] 49K35; 65F05; 65F08; 65F10; 65F35; 65K05; 65K10; 65K15; 65N22; 76D05; 76D07; 90C25; 90C26

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00626163"><analytic>
<author><persName><forename>Philippe</forename><surname>Angot</surname></persName>
<affiliation>
<orgName type="laboratory">LATP</orgName>
<orgName type="team">Laboratoire d'Analyse, Topologie, Probabilités</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6632</orgName>
<orgName type="institution">Université de Provence - Aix-Marseille I</orgName>
<orgName type="institution">Université Paul Cézanne - Aix-Marseille III</orgName>
</affiliation>
</author>
<author><persName><forename>Jean-Paul</forename><surname>Caltagirone</surname></persName>
<affiliation>
<orgName type="laboratory">TREFLE</orgName>
<orgName type="team">Transferts, écoulements, fluides, énergétique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8508</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure de Chimie et de Physique de Bordeaux (ENSCPB)</orgName>
<orgName type="institution">Arts et Métiers ParisTech</orgName>
</affiliation>
</author>
<author><persName><forename>Pierre</forename><surname>Fabrie</surname></persName>
<affiliation>
<orgName type="laboratory">IMB</orgName>
<orgName type="team">Institut de Mathématiques de Bordeaux</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5251</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<title type="main" level="a">A new fast method to compute saddle-points in constrained optimization and applications</title></analytic><monogr><title level="j" type="main">Applied Mathematics Letters</title><imprint><biblScope type="publicationDate">2012-00-00</biblScope><biblScope type="vol">25</biblScope><biblScope type="issue">3</biblScope><biblScope type="pp">245-251</biblScope></imprint></monogr><idno type="doi">10.1016/j.aml.2011.08.015</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00626163</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00626163/PDF/AML_ACF11_am.pdf</idno></biblStruct>
</listBibl>
</listBibl>