Search

The Matlab function Bdiffmin aims at computing the B-differential of the componentwise minimum of two affine vector functions. To realize this task, Bdiffmin calls the Matlab function Isf, which has been designed to determine the chambers of an arrangement of hyperplanes having a point in common. The sign vectors computed by the latter function can be used to solve a number of other enumeration problems such as determining the signed feasibility of strict inequality systems, listing the orthants encountered by the null space of a matrix, itemizing the pointed cones generated by a set of vectors and their inverses, giving the bipartitions of a finite set of points that can be separated by an affine hyperplane and many others.; La fonction Matlab Bdiffmin a pour but de calculer le B-différentiel du minimum par composante de deux fonctions vectorielles affines. Pour réaliser cette tâche, Bdiffmin fait appel à la fonction Matlab Isf, qui a été conçue pour déterminer les chambres d'un arrangement d'hyperplans ayant un point en commun. Les vecteurs de signes calculés par cette dernière fonction peuvent être utilisés pour résoudre un certain nombre d'autres problèmes d'énumération tels que la détermination de tous les sens des inégalités rendant un système d'inégalités strictes réalisable, établir la liste de tous les orthants rencontrés par le noyau d'une matrice, détailler tous les cônes pointus que l'on peut former au moyen d'un ensemble fini de vecteurs et de leurs inverses, donner les bipartitions d'un ensemble fini de points qui puissent être séparées par un hyperplan affine, ainsi que beaucoup d'autres problèmes.

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "bad kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved; the notion of regularity is associated with the algorithm and is analysed with care.; L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit être intérieur à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenus en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "mauvais plis" de la fonction minimum et d'agir en conséquence.De manière à éviter au si souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale vers des points régulier est démontrée; la notion de régularité est associée à l'algorithme et est analysée avec soin.

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "negative kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved.; L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit être intérieur à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenus en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "mauvais plis" de la fonction minimum et d'agir en conséquence.De manière à éviter au si souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale vers des points régulier est démontrée; la notion de régularité est associée à l'algorithme et est analysée avec soin.

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. These formulations are used to state some properties of the B-differential, like its symmetry, condition for its completeness, its connectivity, bounds on its cardinal, etc. The set to specify has a finite number of elements, which may grow exponentially with the range space dimension of the functions, so that its description is most often algorithmic. We present first an incremental-recursive approach avoiding to solve any optimization subproblem, which is based on the notion of matroid circuit and the related introduced concept of stem vector. Next, we propose modifications, adapted to the problem at stake, of an algorithm introduced by Rada and Černý in 2018 for determining the cells of an arrangement in the space of hyperplanes having a point in common. Measured in CPU time on the considered test-problems, the mean acceleration ratios of the proposed algorithms, with respect to the one of Rada and Černý, are in the range 7..15, and this speed-up can exceed 30, depending on the problem and the approach.; Cet article se concentre sur la description et le calcul du B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles. Ce problème se pose dans la reformulation du problème de complémentarité linéaire avec la C-fonction Min. Cette question a de nombreuses formulations équivalentes et nous en citons quelques-unes en algèbre linéaire, en analyse convexe et en géométrie discrète. Ces formulations sont utilisées pour établir certaines propriétés du B-différentiel, comme sa symétrie, une condition assurant sa complétude, sa connectivité, des bornes sur son cardinal, etc. L'ensemble à décrire comporte un nombre fini d'éléments, qui peut grandir exponentiellement avec la dimension de l'espace d'arrivée des fonctions, de sorte que sa description est le plus souvent algorithmique. Nous présentons d'abord une approche incrémentale-récursive, qui évite de résoudre des problèmes d'optimisation et qui est fondée sur la notion de circuit de matroïde et sur le concept introduit adjacent de vecteur-souche. Ensuite, nous proposons des modifications, adaptées au problème posé, d'un algorithme introduit par Rada et Černý en 2018 pour déterminer les cellules d'un arrangement dans l'espace d'hyperplans ayant un point commun. Mesurée en temps CPU sur les problèmes-tests considérés, les moyennes des quotients d'accélération des algorithmes proposés, par rapport à celui de Rada et Černý, sont de l'ordre de 7..15, et cette accélération peut dépasser 30, selon le problème et l'approche.

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. These formulations are used to state some properties of the B-differential, like its symmetry, condition for its completeness, its connectivity, bounds on its cardinal, etc. The set to specify has a finite number of elements, which may grow exponentially with the range space dimension of the functions, so that its description is most often algorithmic. We present first an incremental-recursive approach avoiding to solve any optimization subproblem, which is based on the notion of matroid circuit and the related introduced concept of stem vector. Next, we propose modifications, adapted to the problem at stake, of an algorithm introduced by Rada and Černý in 2018 for determining the cells of an arrangement in the space of hyperplanes having a point in common. Measured in CPU time on the considered test-problems, the mean acceleration ratios of the proposed algorithms, with respect to the one of Rada and Černý, are in the range 7..15, and this speed-up can exceed 30, depending on the problem and the approach.; Cet article se concentre sur la description et le calcul du B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles. Ce problème se pose dans la reformulation du problème de complémentarité linéaire avec la C-fonction Min. Cette question a de nombreuses formulations équivalentes et nous en citons quelques-unes en algèbre linéaire, en analyse convexe et en géométrie discrète. Ces formulations sont utilisées pour établir certaines propriétés du B-différentiel, comme sa symétrie, une condition assurant sa complétude, sa connectivité, des bornes sur son cardinal, etc. L'ensemble à décrire comporte un nombre fini d'éléments, qui peut grandir exponentiellement avec la dimension de l'espace d'arrivée des fonctions, de sorte que sa description est le plus souvent algorithmique. Nous présentons d'abord une approche incrémentale-récursive, qui évite de résoudre des problèmes d'optimisation et qui est fondée sur la notion de circuit de matroïde et sur le concept introduit adjacent de vecteur-souche. Ensuite, nous proposons des modifications, adaptées au problème posé, d'un algorithme introduit par Rada et Černý en 2018 pour déterminer les cellules d'un arrangement dans l'espace d'hyperplans ayant un point commun. Mesurée en temps CPU sur les problèmes-tests considérés, les moyennes des quotients d'accélération des algorithmes proposés, par rapport à celui de Rada et Černý, sont de l'ordre de 7..15, et cette accélération peut dépasser 30, selon le problème et l'approche.

This paper considers the balanced form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang and published in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that, when any rowwise convex combination of two square matrices is nonsingular, the $\ell_\infty$ norm of the inverse of these rowwise convex combinations is maximized by an extreme diagonal matrix.; Cet article considère la forme équilibrée du problème de complémentarité linéaire standard avec solution unique et présente une expression plus précise de la borne d'erreur supérieure découverte par Chen et Xiang et publiée en 2006. Cette expression a au moins deux avantages. Elle rend possible l'évaluation exacte du facteur de la borne d'erreur et elle permet d'obtenir une estimation supérieure de ce facteur en termes des longueurs en bits des données lorsque celles-ci s'expriment en nombres rationnels. En chemin, nous montrons que, lorsque les combinaisons convexes ligne par ligne de deux matrices carrées sont inversibles, la norme infinie de l'inverse de ces combinaisons convexes est maximale pour une matrice diagonale extrême.

Lecture Notes (in French) of optimization courses given at ENSTA (Paris, next Saclay), ENSAE (Paris) and at the universities Paris I, Paris VI and Paris Saclay (979 pages)., Syllabus d’enseignements délivrés à l’ENSTA (Paris, puis Saclay), à l’ENSAE (Paris) et aux universités Paris I, Paris VI et Paris Saclay (979 pages).

This paper considers a generalized form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that, when any rowwise convex combination of two square matrices is nonsingular, the ℓ∞ norm of the inverse of these rowwise convex combinations is maximized by an extreme diagonal matrix.; Cet article considère une forme généralisée du problème de complémentarité linéaire standard avec solution unique et présente une expression plus précise de la borne d'erreur supérieure découverte par Chen et Xiang en 2006. Cette expression a au moins deux avantages. Elle rend possible l'évaluation exacte du facteur de la borne d'erreur et elle permet d'obtenir une estimation supérieure de ce facteur en termes des longueurs en bits des données lorsque celles-ci s'expriment en nombres rationnels. En chemin, nous montrons que, lorsque les combinaisons convexes ligne par ligne de deux matrices carrées sont inversibles, la norme ℓ∞ de l'inverse de ces combinaisons convexes est maximale pour une matrice diagonale extrême.

This course starts with the presentation of the optimality conditions of an optimization problem described in a rather abstract manner, so that these can be useful for dealing with a large variety of problems. Next, the course describes and analyzes various advanced algorithms to solve optimization problems (nonsmooth methods, linearization methods, proximal and augmented Lagrangian methods, interior point methods) and shows how they can be used to solve a few classical optimization problems (linear optimization, convex quadratic optimization, semidefinite optimization (SDO), nonlinear optimization). Along the way, various tools from convex and nonsmooth analysis will be presented. Everything is conceptualized in finite dimension. The goal of the lectures is therefore to consolidate basic knowledge in optimization, on both theoretical and algorithmic aspects.

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "bad kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved; the notion of regularity is associated with the algorithm and is analysed with care.; L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit être intérieur à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenus en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "mauvais plis" de la fonction minimum et d'agir en conséquence.De manière à éviter au si souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale vers des points régulier est démontrée; la notion de régularité est associée à l'algorithme et est analysée avec soin.

International audience; The paper "An algorithmic characterization of P-matricity" (SIAM Journal on Matrix Analysis and Applications, 34:3 (2013) 904–916, by the same authors as here) implicitly assumes that the iterates generated by the Newton-min algorithm for solving a linear complementarity problem of dimension n, which reads 0 ⩽ x ⊥ (M x + q) ⩾ 0, are uniquely determined by some index subsets of [[1, n]]. Even if this is satisfied for a subset of vectors q that is dense in R^n, this assumption is improper, in particular in the statements where the vector q is not subject to restrictions. The goal of the present contribution is to show that, despite this blunder, the main result of that paper is preserved. This one claims that a nondegenerate matrix M is a P-matrix if and only if the Newton-min algorithm does not cycle between two distinct points, whatever is q. The proof is not more complex, requiring only some adjustments, which are essential however.; L'article "An algorithmic characterization of P-matricity" (SIAM Journal on Matrix Analysis and Applications, 34:3 (2013) 904–916, par les mêmes auteurs qu'ici) suppose implicitement que les itérés générés par l'algorithme de Newton-min pour résoudre le problème de complémentarité linéaire de dimension n, qui s'écrit 0 ⩽ x ⊥ (M x + q) ⩾ 0, sont déterminés de manière unique par des sous-ensembles d'indices de [[1, n]]. Même si cette hypothèse est vérifiée pour un sous-ensemble de vecteurs q qui est dense dans R^n, elle n'est pas appropriée, en particulier dans les énoncés où le vecteur q n'est pas soumis à des restrictions. Le but du la contribution présente est de montrer que, malgré cette bévue, le résultat principal de l'article est préservé. Celui-ci affirme qu'une matrice non dégénérée M est une P-matrice si, et seulement si, l'algorithme de Newton-min ne cycle pas entre deux points distincts, quel que soit q. La démonstration n'est pas plus complexe et ne requiert que quelques ajustements, qui sont cependant essentiels.

The plain Newton-min algorithm can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the linear complementarity problem (LCP) $"0 ≤ x ⊥ (Mx+q) ≥ 0"$. This algorithm converges, whatever is q, when M is an M-matrix, but not when it is a P-matrix. When convergence occurs, it is often very fast (in at most n iterations for an M-matrix, where n is the number of variables, but often much faster in practice). In 1990, Harker and Pang proposed to improve the convergence ability of this algorithm by introducing a stepsize along the Newton-min direction that results in a small jump over the first encountered kink of the min-function, in order to avoid its points of nondifferentiability. This paper shows that, for the Fathi problem (an LCP with a positive definite symmetric matrix M, hence a P-matrix), an algorithmic scheme, including the algorithm of Harker and Pang, may require n iterations to converge, depending on the starting point.; L'algorithme de Newton-min peut être vu comme une instance de la méthode de Newton semi-lisse agissant sur la formulation équationnelle min(x,Mx+q) = 0 du problème de complémentarité linéaire (PCL) $0 ≤ x ⊥ (Mx+q) ≥ 0$. Cet algorithme converge, quel que soit q, lorsque M est une M-matrice, mais pas lorsque M est une P-matrice. En cas de convergence, celle-ci est souvent très rapide (en moins de n itérations pour une M-matrice, où n est le nombre de variables, mais souvent bien plus rapidement en pratique). En 1990, Harker et Pang ont proposé d'améliorer la capacité de converger de cet algorithme en introduisant un pas le long de la direction de Newton-min qui se traduit par une petit saut au-dessus du premier pli de la fonction min rencontré, de manière à éviter ses points de non-différentiabilité. Cet article montre que, pour le problème de Fathi (un PCL avec une matrice M symétrique définie positive, donc une P-matrice), un schéma algorithmique, incluant l'algorithme de Harker et Pang, peut requérir n itérations pour converger.

This paper addresses two elementary subjects in linear algebra, intertwining concepts in real and complex numbers, which could be proposed as homework assignments to students learning complex linear algebra. First, given an $R$-linear system of equations with data in complex numbers, necessary and sufficient conditions are given ensuring that there exists a C-linear system of equations of the same size that has the same solution set whatever is the constant term of the original system. The motivation for searching for such an equivalence may be theoretical or based on a numerical efficiency wish. This first result rests on the second contribution of the paper, which claims that, being given an $R$-injective matrix $M\in\mathbb{C}^{m\times(2n)}$ - such a matrix must have more rows than half the number of its columns - one can find a matrix $H\in\mathbb{C}^{n\times m}$ such that $HM$ is also R-injective.; Cet article traite de deux sujets élémentaires d'algèbre linéaire, entrelaçant des concepts d'analyses réelle et complexe, qui pourraient très bien être proposés en projet de réflexion à des étudiants apprenant l'algèbre linéaire complexe. En premier lieu, étant donné un système d'équations $R$-linéaire, exprimé en nombres complexes, nous donnons des conditions nécessaires et suffisantes pour que l'on puisse trouver un système d'équations $C$-linéaire de même dimension, qui ait le même ensemble de solutions quel que soit le terme constant du système original. La motivation de la recherche d'une telle équivalence peut être théorique ou fondée sur un souhait d'efficacité numérique. Ce premier résultat repose sur la seconde contribution de cet article, qui affirme que, étant donné une matrice R-injective $M\in\mathbb{C}^{m\times(2n)}$ - une telle matrice doit avoir plus de lignes que la moitié de son nombre de colonnes - on peut trouver une matrice $H\in\mathbb{C}^{n\times m}$ telle que $HM$ soit R-injective.

Numerical optimization in complex numbers has drawn much less attention than in real numbers. A widespread opinion is that, since a complex number is a pair of real numbers, the best strategy to solve a complex optimization problem is to transform it into real numbers and to solve the latter by a real number solver. This paper defends another point of view and presents four arguments to convince the reader that skipping the transformation phase and using a complex number algorithm, if any, can sometimes have significant benefits. This is demonstrated for the particular case of a semidefinite optimization problem solved by a feasible corrector-predictor primal-dual interior-point method. In that case, the complex number formulation has the advantage (i) of having a smaller memory storage, (ii) of having a faster iteration, (iii) of requiring less iterations, and (iv) of having "smaller" feasible and solution sets. The computing time saving is rooted in the fact that some operations (like the matrix-matrix product) are much faster for complex operands than for their double size real counterparts, so that the conclusions of this paper could be valid for other problems in which these operations count a great deal in the computing time. The iteration number saving has its origin in the smaller (though complex) dimension of the problem in complex numbers. Numerical experiments show that all together these properties result in a code that can run up to four times faster. Finally, the feasible and solution sets are smaller since they are isometric to only a part of the feasible and solution sets of the problem in real numbers, which increases the chance of having a unique solution to the problem.; L'optimisation numérique en nombres complexes a attiré beaucoup moins l'attention qu'en nombres réels. Une opinion répandue est que, puisqu'un nombre complexe est un couple de nombres réels, la meilleure stratégie pour résoudre un problème d'optimisation en nombres complexes est de le transformer en nombres réels et de résoudre ce dernier par un solveur réel. Cet article défend un autre point de vue et présente quatre arguments pour convaincre le lecteur que se passer de la transformation et d'utiliser un algorithme en nombres complexes, lorsqu'un tel algorithme est disponible, peut parfois être beaucoup plus efficace. Ceci est mis en évidence pour le cas particulier des problèmes d'optimisation semi-définie positive résolus par une méthode de points-intérieurs primale-duale réalisable utilisant la technique des prédictions-corrections. Dans ce cas, la formulation en nombres complexes a l'avantage (i) de requérir moins d'espace-mémoire, (ii) d'avoir une itération plus rapide, (iii) de nécessiter moins d'itérations et (iv) d'avoir des ensembles admissible et de solutions plus petits. Le gain en temps de calcul vient du fait que certaines opérations (comme le produit de deux matrices) sont beaucoup plus rapides pour des opérandes complexes que pour leurs contreparties réelles de taille double, si bien que les conclusions de cet article pourraient aussi être valables pour d'autres problèmes dans lesquels ces opérations interviennent pour une bonne part dans le temps de calcul. Le gain en nombre d'itérations provient de la dimension plus petite (bien que complexe) du problème en nombres complexes. Une expérimentation numérique montre que toutes ces propriétés conduisent a un code qui s'exécute jusqu'à quatre fois plus rapidement. Finalement, les ensembles admissible et de solutions sont plus petits parce qu'ils sont isomorphes à une partie seulement des ensembles admissible et de solutions du problème en nombres réels, ce qui accroît la possibilité d'avoir une solution unique du problème.

Numerical optimization in complex numbers has drawn much less attention than in real numbers. A widespread opinion is that, since a complex number is a pair of real numbers, the best strategy to solve a complex optimization problem is to transform it into real numbers and to solve the latter by a real number solver. This paper defends another point of view and presents four arguments to convince the reader that skipping the transformation phase and using a complex number algorithm, if any, can sometimes have significant benefits. This is demonstrated for the particular case of a semidefinite optimization problem solved by a feasible corrector-predictor primal-dual interior-point method. In that case, the complex number formulation has the advantage (i) of having a smaller memory storage, (ii) of having a faster iteration, (iii) of requiring less iterations, and (iv) of having " smaller " feasible and solution sets. The computing time saving is rooted in the fact that some operations (like the matrix-matrix product) are much faster for complex operands than for their double size real counterparts, so that the conclusions of this paper could be valid for other problems in which these operations count a great deal in the computing time. The iteration number saving has its origin in the smaller (though complex) dimension of the problem in complex numbers. Numerical experiments show that all together these properties result in a code that can run up to four times faster. Finally, the feasible and solution sets are smaller since they are isometric to only a part of the feasible and solution sets of the problem in real numbers, which increases the chance of having a unique solution to the problem.; L'optimisation numérique en nombres complexes a attiré beaucoup moins l'attention qu'en nombres réels. Une opinion répandue est que, puisqu'un nombre complexe est un couple de nombres réels, la meilleure stratégie pour résoudre un problème d'optimisation en nombres complexes est de le transformer en nombres réels et de résoudre ce dernier par un solveur réel. Cet article défend un autre point de vue et présente quatre arguments pour convaincre le lecteur que se passer de la transformation et d'utiliser un algorithme en nombres complexes, lorsqu'un tel algorithme est disponible, peut parfois être beaucoup plus efficace. Ceci est mis en évidence pour le cas particulier des problèmes d'optimisation semi-définie positive résolus par une méthode de points-intérieurs primale-duale réalisable utilisant la technique des prédictions-corrections. Dans ce cas, la formulation en nombres complexes a l'avantage (i) de requérir moins d'espace-mémoire, (ii) d'avoir une itération plus rapide, (iii) de nécessiter moins d'itérations et (iv) d'avoir des ensembles admissible et de solutions plus petits. Le gain en temps de calcul vient du fait que certaines opérations (comme le produit de deux matrices) sont beaucoup plus rapides pour des opérandes complexes que pour leurs contreparties réelles de taille double, si bien que les conclusions de cet article pourraient aussi être valables pour d'autres problèmes dans lesquels ces opérations interviennent pour une bonne part dans le temps de calcul. Le gain en nombre d'itérations provient de la dimension plus petite (bien que complexe) du problème en nombres complexes. Une expérimentation numérique montre que toutes ces propriétés conduisent a un code qui s'exécute jusqu'à quatre fois plus rapidement. Finalement, les ensembles admissible et de solutions sont plus petits parce qu'ils sont isomorphes à une partie seulement des ensembles admissible et de solutions du problème en nombres réels, ce qui accroît la possibilité d'avoir une solution unique du problème.

International audience; This paper analyses the behavior of the augmented Lagrangian algorithm when it deals with an infeasible convex quadratic optimization problem. It is shown that the algorithm finds a point that, on the one hand, satisfies the constraints shifted by the smallest possible shift that makes them feasible and, on the other hand, minimizes the objective on the corresponding shifted constrained set. The speed of convergence to such a point is globally linear, with a rate that is inversely proportional to the augmentation parameter. This suggests us a rule for determining the augmentation parameter that aims at controlling the speed of convergence of the shifted constraint norm to zero; this rule has the advantage of generating bounded augmentation parameters even when the problem is infeasible.\addtext{ Implications on an SQP algorithm using the AL algorithm for solving its osculating quadratic problems are discussed; Cet article analyse le comportement de l'algorithme du lagrangien augmenté lorsqu'il cherche à résoudre un problème d'optimisation quadratique convexe non réalisable. Nous montrons que l'algorithme trouve un point qui, d'une part, réalise les contraintes translatées par la plus petite translation qui les rend compatibles et, d'autre part, minimise l'objectif sur l'ensemble admissible ainsi transformé. La vitesse de convergence vers un tel point est globalement linéaire, avec un taux inversement proportionnel au paramètre d'augmentation. Ceci suggère une règle de mise à jour de ce paramètre, de manière à obtenir une vitesse de convergence donnée des contraintes translatées vers zéro; cette règle a l'avantage de générer des paramètres d'augmentation bornés, même lorsque le problème n'est pas réalisable

When a solver of convex quadratic optimization problem (QP) is used within a nonlin-ear optimization code, implementing the SQP algorithm, it is important that it deals appropriately with the special QPs that can be generated by the nonlinear solver, those that are infeasible or unbounded. The goal of this paper is to highlight the po-tential of the augmented Lagrangian (AL) algorithm in that respect and to give an account on the efficiency of the implementation of this algorithm in the C++/Matlab codes Oqla/Qpalm. We show how these pieces of software compare with some fre-quently used QP solvers, which use active-set or interior-point methods, and demon-strate that they provide an appropriate response when they deal with the special QPs quoted above.

This report is the user's guide of the convex optimization problem solver OQLA.

This report describes the technical details of the implementation of the augmented Lagrangian algorithm used in Oqla and Qpalm, which are pieces of software designed to solve a convex quadratic optimization problem. The goal of the report is to make easier the reading and the understanding of the C++/Matlab functions defining the solvers. The Oqla and Qpalm user's guides can be found elsewhere.

When a solver of convex quadratic optimization problem (QP) is used within a nonlin-ear optimization code, implementing the SQP algorithm, it is important that it deals appropriately with the special QPs that can be generated by the nonlinear solver, those that are infeasible or unbounded. The goal of this paper is to highlight the po-tential of the augmented Lagrangian (AL) algorithm in that respect and to give an account on the efficiency of the implementation of this algorithm in the C++/Matlab codes Oqla/Qpalm. We show how these pieces of software compare with some fre-quently used QP solvers, which use active-set or interior-point methods, and demon-strate that they provide an appropriate response when they deal with the special QPs quoted above.

The module M1CG1 solves for x in Rn the linear system(LS) Ax=b,by a possibly preconditioned Fletcher-Reeves conjugate gradient (CG) algorithm. In this system, the n x n matrix A and the vector b in Rn are supposed to be known. It is assumed that the matrix A is symmetric. Therefore, solving the linear system is equivalent to finding a stationary point of the minimization problem(QP) infx (½)xT Ax-bT x.To be sure to be able to solve the linear system (LS) [resp. the minimization problem (QP)] for an arbitrary b in Rn, the matrix A must be nonsingular [resp. positive definite]. When A is positive definite, (LS) and (QP) are equivalent. If the CG algorithm encounters a quasi-negative curvature direction, which is a conjugate direction v satisfyingvT Av ≤ ν ∥ v ∥2,for some given threshold ν≥0, M1CG1 just stops. In this inequality, ∥ ∙ ∥ denotes the Euclidean norm.The way A is actually stored is irrelevant for M1CG1, since the algorithm requires only products Av of A times various vectors v and since this operation is supposed to be done in a user-supplied subroutine. This gives the possibility to use the code even when A is not known explicitly.M1CG1 has the nice feature of being able to build itself a preconditioning matrix while it solves the linear system (LS). This matrix is an approximation of A-1 and can then be used to precondition a subsequent linear system with the same matrix A or a matrix close to A, and a different right-hand side. The preconditioning matrix is formed by BFGS updates. It is also possible to form an l-BFGS preconditioning matrix, so that the solver is adapted to problems of very large dimension. M1CG1 can also improve a previously built preconditioner; this feature is however presently limited by the fact that the method used to improve the preconditioner (i.e., full BFGS updates or l-BFGS updates with a given selection procedure) must be the same as the one used to build the previous preconditioner.Another feature of M1CG1 is to be able to solve in parallel two linear systems: (LS) and(LS') Ax'=b',The latter system uses the same matrix A as in (LS), but another right-hand side b'. The second linear system (LS') is solved using the conjugate directions generated by the CG iterations for solving (LS). This means that the two systems are solved without increasing the number of matrix-vector products. This feature is useful for the truncated SQP algorithm in constrained optimization.

The name of the code, SQPlab, stands for Sequential Quadratic Programming (SQP) laboratory. It is written in Matlab. This piece of software is used by the author as a kind of laboratory for trying techniques related to the SQP algorithm, but it has been designed so that it can be useful to many. It is also aimed at accompanying the hanging chain project developped along part III of the book 'Numerical Optimization – Theoretical and Practical Aspects' (second edition), by J.F. Bonnans, J.Ch. Gilbert, C. Lemaréchal, C. Sagastizábal, during which it is shown how to implement step by step many aspects of the algorithm.

QPAL is a piece of software that aims at solving a convex quadratic optimization problem with linear equality and inequality constraints. The implemented algorithm uses an augmented Lagrangian approach, which relaxes the equality constraints and deals explicitely with the bound constraints on the original and slack variables. The generated quadratic functions are minimized on the activated faces by a truncated conjugate gradient algorithm, interspersed with gradient projection steps. When the optimal value is finite, convergence occurs at a linear speed that can be prescribed by the user. Matrices can be strored in dense or sparse structures; in addition, the Hessian of the quadratic objective function may have a direct of inverse $\ell$-BFGS form. QPAL is written in Fortran-2003.

SQPpro is a piece of software that aims at solving a nonlinear optimization problem with nonlinear equality and inequality constraints. The functions defining the problem must be at least once differentiable. The implemented algorithm uses an SQP approach, which is a workable version of the Newton and quasi-Newton methods. The quadratic optimization that has to be solved at each iteration uses the solver QPAL. The constraint Jacobian matrices can be strored in dense or sparse structures; in addition the Hessian of the Lagrangien can be approximated by the BFGS (dense) or $\ell$-BFGS (sparse) formula. SQPpro is written in Fortran-2003.

International audience; Problems of differentiable optimization arise when one tries to determine the optimal value of a finite number of parameters, optimality referring to the minimality of a given criteria. This article describes the principal algorithms for the resolution of these problems by précising their motivation. these resolution problems arise in numerous sectors of engineering as well as in science and economy. They are sometimes posed in infinite dimension; in that case, one tries to determine an optimal function. The current numerical methods of optimization stem from ever multiplying advances that enrich another.; Les problèmes d’optimisation différenciable se posent lorsque l’on cherche à déterminer la valeur optimale d’un nombre fini de paramètres, l’optimalité signifiant la minimalité d’un critère donné. Cet article décrit les principaux algorithmes de résolution de ces problèmes, en précisant leur motivation. Ces problèmes de résolution se présentent dans de nombreux domaines de l’ingénieur, mais aussi en science et en économie. Ils se posent parfois en dimension infinie, on cherche alors à déterminer une fonction optimale. Les méthodes numériques actuelles de l’optimisation sont la résultante d‘avancées qui ne cessent de se multiplier et de s’enrichir mutuellement.

This note describes how the optimization problems of the Modulopt collection are organized within the Libopt environment. It is aimed at being a guide for using and enriching this collection in this environment.

International audience

We consider an augmented Lagrangian algorithm for minimizing a convex quadratic function subject to linear inequality constraints. Linear optimization is an important particular instance of this problem. We show that, provided the augmentation parameter is large enough, the constraint value converges globally linearly to zero. This property is proven by establishing first a global radial Lipschitz property of the reciprocal of the dual function subgradient. It is also a consequence of the proximal interpretation of the method. No strict complementarity assumption is needed. The result is illustrated by numerical experiments and algorithmic implications are discussed.

International audience; Seismic reflection tomography is a method for the determination of a subsurface velocity model from the traveltimes of seismic waves reflecting on geological interfaces. From an optimization viewpoint, the problem consists in minimizing a nonlinear least-squares function measuring the mismatch between observed traveltimes and those calculated by raytracing in this model. The introduction of a priori information on the model is crucial to reduce the under-determination. The contribution of this paper is to introduce a technique able to take into account geological a priori information in the reflection tomography problem expressed as constraints in the optimization problem. This constrained optimization is based on a Gauss-Newton Sequential Quadratic Programming approach. At each Gauss-Newton step, a solution to a strictly convex quadratic optimization problem subject to linear constraints is computed thanks to an augmented Lagrangian relaxation method. Our choice for this optimization method is motivated and its original aspects are described. The efficiency of the method is shown on applications on a 2D OBC real data set and on a 3D real data set: the introduction of constraints coming both from well logs and from geological knowledge allows to reduce the under-determination of the 2 inverse problems. Introduction Reflection tomography allows to determine a velocity model from the traveltimes of seismic waves reflecting on geological interfaces. This inverse problem is formulated as a nonlinear least-squares function which measures the mismatch between observed traveltimes and traveltimes computed by ray tracing method. This method has been successfully applied to real data sets (Ehinger et al, 2001, Broto et al, 2003). Nevertheless, the under-determination of the inverse problem generally requires the introduction of additional information on the model to reduce the number of admissible models. Penalization terms modelling this information can be added to the seismic terms in the objective functions but the tuning of the penalization weights may be tricky. In this paper, we propose to handle the a priori information by the introduction of equality and inequality constraints in the optimization process. This approach allows to introduce lot of constraints of different types, provided we have at our disposal an adequate constrained optimization method. We developed an original method designed for the tomographic inverse problem which presents the following characteristics: it is a large scale problem (10000-50000 unknowns), the forward operator is nonlinear and its computation may be expensive (large number of source-receiver couples, up to 500000), the problem is ill-conditioned. In the first part of this paper, the chosen method is motivated and its original aspects are shortly described (for further details, refer to Delbos et al, 2004). Applications on a 2D PP/PS real data set and on a 3D PP real data set are presented in a second part.

We consider an augmented Lagrangian algorithm for minimizing a convex quadratic function subject to linear inequality constraints. Linear optimization is an important particular instance of this problem. We show that, provided the augmentation parameter is large enough, the constraint value converges globally linearly to zero. This property is proven by establishing first a global radial Lipschitz property of the reciprocal of the dual function subgradient. It is also a consequence of the proximal interpretation of the method. No strict complementarity assumption is needed. The result is illustrated by numerical experiments and algorithmic implications are discussed.

Projet PROMATH; A technique for maintaining the positive definiteness of the matrices in the quasi-Newton version of the SQP algorithm is proposed. In our algorithm, approximations of the Hessian of the augmented Lagrangian are updated. The positive definiteness of these matrices in the space tangent to the constraint manifold is ensured by a piecewise line-search technique, while their positive definiteness in a decoupled complementary subspace is obtained by setting the augmentation parameter. The combination of these two ideas makes the new approach more robust in our experiment with respect to existing approaches

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and $q$-superlinear convergenc- e is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds.