Keywords:

pour assurer la convergence. Les sous problèmes qui en résultent peuvent être résolus efficacement en utilisant la structure clairsemée.

I would also like to express my gratitude and appreciation to my origin laboratories, Laboratory of Mathematics and their Applications of Pau, and Laboratoy of Mathematics and their Applications of Kenitra, for the great working conditions, the numerous activities and the different training which it provides. I address my gratitude to all the teaching and administrative staff of the Faculty of Sciences of Kenitra, in particular, Prof. Benkirane Abdelmoujib for their discussions and their encouragements.

My acknowledgments go also to the director of the Laboratory of Mathematics and their Applications of Pau Prof. Gilles Carbou, and Jacques Giacomoni, for accepting me into his laboratory and for the great working conditions as well as for the numerous activities and training provided. My thanks also to all the teaching staff of the laboratory, in particular, Prof. Davide Trujillo for his time trying to fix with me a computer bug. I would like also to thank all the administrative staff of the laboratory, in particular Mr. Bruno Demoisy, Mrs. Sylvie Berton and Mrs. Chantal Blanchard.

vi My thanks and appreciation for the doctoral schools of exact sciences of Pau University and of sciences and techniques of Ibn Tofail University, which have significantly contributed in my scientific training through numerous training programs during my thesis.

I am grateful, too, to Prof. María Cruz López de Silanes and Enrique Artal for having welcomed me, for a research internship of six months, in his institute "Instituto de Matemáticas y statisticas de la Universidad de Zaragoza". I am very thankful for him for giving me the opportunity to work in agreeable conditions and for his valuable time and help.

I would also like to thank the National Center of Scientific and Technical Research of Morocco, Campus France, and in particular the Laboratory of Mathematics and their Applications of Pau as well as the Erasmus+ program for the funding of my thesis.

I acknowledge all my professors, from the primary level up to now, who taught and educated me to arrive here, in particular, the teaching staff of Mathematics Department of Sciences and Techniques Faculties of Errachidia and of Fes. My special thanks go to my former professors in Fes, notably, Abdelmoujib Benkirane, Elhoussine Azroul, Jaouad BENNOUNA, Rachid Benkirane.

A very special thanks to all my family. Firstly, to my mother Aziza, my father Elmaarouf, my brother Abdelhak, my sisters Hafida, Latifa and Touria with their husbands Abdellah, Brahim and their children walid, mouad, Salma, Yahya and mohammed. Secondly, to all my uncles, aunts and cousins with their small families. I am very happy to have them by my sides and I am very grateful to each one of them.

Last but not least, I am grateful too, to all my lab mates and my friends PhD students at Ibn Tofail University and at Pau University. Firstly, for the former PhDs. I would like to thank my friends with whom I had a good time. Dears friends, your list is very long that I cannot cite you all, I wish you all happiness and full success in your personal and professional life. vii Résumé La méthode des asymptotes mobiles (MMA) est largement utilisée pour minimiser une fonction continue f de plusieurs variables. À chaque itération de cette méthode, la fonction objective et les contraintes du problème d'optimisation sont approchés par une fonction rationnelle convexe. Pour assurer la convergence de la méthode MMA, le sous problème de chaque itération doit être résolu à son optimum global unique. Cette méthode formule de façon itérative des sous problèmes non linéaires séparables et strictement convexes. Des asymptotes inférieures et supérieures sont introduites pour tronquer la région réalisable. En raison de sa structure spéciale, les sous problèmes qui en résultent peuvent être résolus par de nombreuses méthodes efficaces d'optimisation non linéaire, par exemple les méthodes de points intérieurs (IPM) et la programmation séquentielle convexe (SCP).

La version originale de la méthode des asymptotes mobiles (MMA) n'est pas garantie à l'intérieur de la région réalisable correspondante décrite par les contraintes. Par conséquent, il n'est pas en mesure de résoudre les problèmes d'optimisation lorsque la région réalisable est définie par les contraintes de faisabilité.

Nous proposons dans cette thèse des nouvelles approximations et de nouveaux algorithmes d'optimisation sans et avec contraintes, faciles à mettre en oeuvre sur la base de la méthode des asymptotes mobiles, ont les mêmes avantages que la version originale du MMA et du SCP, et plus d'avantages de convergence globale, et nous ne devons pas résoudre les sous problèmes générés par une autre méthode classique grâce à leur solution explicite. Pour montrer l'efficacité de notre algorithme, on a les compare avec des méthodes connues comme la méthode de Newton.

Une extension de la MMA en utilisant les paramètres spectraux au lieu de l'information de second ordre est présentée, ces paramètres gardent la séquence générée commodément conservatrice par rapport aux fonctions originales et donnent une information sur la courbure, préservant la propriété de convergence globale. En ce qui concerne la fonction objective, des approximations conservatrices assurent des valeurs monotones décroissantes. La convexité stricte et la séparabilité des fonctions du modèle sont conservées afin que les sous problèmes générés aient une solution unique. Le but de l'utilisation de ces paramètres est de réduire l'effort total de calcul de l'algorithme et la possibilité de l'appliquer à des problèmes d'optimisation à grande échelle.

Dans une autre partie, nous proposons une modification de ces derniers algorithmes pour l'optimisation avec contraintes qui assure la faisabilité par rapport à un ensemble donné de contraintes inégalités. La procédure étend les sous problèmes résultants par des contraintes non linéaires supplémentaires, qui sont transmises directement au sous problème pour assurer leur faisabilité à chaque étape d'itération. Comme technique globale, une procédure de recherche de lignes est utilisée List of Tables 2.1 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method. Here w(x) = (1 + |x|) 1/2 exp(-2 |x|). . . . . . . . . . . . . . . . 2.2 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present paper. Here w(x) = (1 + |x|) -4 exp(-10 |x| 0.5 ) * log(e + |x|) 10 . . . . . . . [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method. Here w(x) = (1 + |x|) 1/2 exp(-2 |x|) and α(k) = 2 1 + 1 4 c(k) .

Numerical comparison of the

3.2 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present paper. Here w(x) = (1 + |x|) -4 exp(-10 |x| 0.5 ) log(e + |x|) 10 and α(k) = 3 1 + 1 10 c(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method. Here w(x) = (1+|x|) 1/2 exp(-2 |x|) and α(k) = 2 1 + 1 4γ

(k) 1 , 4 + 1 3γ (k) 2
. 60 3.4 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method. Here w(x) = (1+|x|) 1/2 exp(-2 |x|) and α(k

) = 2 1 + 1 5γ (k) 1 , 3 + 1 10γ (k) 2
. 61 3.5 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method in three dimension. Here w(x) = (1 + |x|) number of equality constraints , c j (x), j = m e + 1, m c number of equality and inequality constraints , c j (x), j = m e + 1, • • • , m c inequality constraints , e j (x), j = 1, . . . , m f feasibility constraints, F feasible set given by the feasibility constraints e j (x),

iteration index, d (k) moving asymptotes, σ (k) ∈ (0, 1) stepsize to yield a descent in the merit function, y ∈ R m c +m f stepsize to yield a descent in the merit function, F feasible region, J(x) set of active constraints, L(x, y)

Lagrangian function, y ∈ R m c +m f dualvariables, y c ∈ R m c dual variables with respect to c j (x) j = 1, ..., m c , y e ∈ R m f dual variables with respect to e j (x) j = 1, ..., m f , LICQ linear independence constraint qualification, KKT Karush-Kuhn-Tucker first order optimality conditions, z (k) ∈ R n primal solution of the subproblem in iteration k, v (k) ∈ R m c +m f dual solution of the subproblem in iteration k, r ∈ (0, [START_REF] Andersen | Implementation of interior point methods for large scale linear programming[END_REF] positive parameter used in Armijo condition, U j j = 1, ..., n upper asymptote for primal variable x j j = 1, ..., n, L j j = 1, ..., n lower asymptote for primal variable x j j = 1, ..., n,

I (k) +
index set of nonnegative partial derivatives of objective,

I (k) - index set of negative partial derivatives of objective, f (k) (x), f (k) (x)
approximations of the objective function f in iteration k, Φ ρ (x, y) augmented Lagrangian merit function,

Introduction "version française"

La méthode des asymptotes mobiles (MMA) est introduite, sans une analyse globale de convergence, par Svanberg [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF] en 1987. Cette méthode peut être considérée comme une généralisation de la méthode de linéarisation convexe (CONLIN); voire [START_REF] Boyd | Convex Optimization[END_REF][START_REF] Fleury | Efficient approximation concepts using second order information[END_REF][START_REF] Fleury | First and second order convex approximation strategies in structural optimization[END_REF][START_REF] Fleury | Structural optimization methods for large scale problems: status and limitations[END_REF][START_REF] Ni | A globally convergent method of moving asymptotes with trust region technique[END_REF][START_REF] Svanberg | The method of moving asymptotes-modelling aspects and solution schemes[END_REF][START_REF] Svanberg | Mma and gcmma, versions september[END_REF][START_REF] Wang | A new method of moving asymptotes for large-scale unconstrained optimization[END_REF][START_REF] Zhang | A modification of convex approximation methods for structural optimization[END_REF][START_REF] Zillober | Global convergence of a nonlinear programming method using convex approximations[END_REF]. Plus tard, Svanberg [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] à proposer une nouvelle version de la méthode qui converge globalement mais qui fait appel toujours à des méthodes classiques pour résoudre les sous-problèmes résultant des approximations de la méthode. Depuis lors, de nombreuses versions ont été suggérées.

Svanberg a proposé ce type spécial d'approximation convexe pour résoudre numériquement des problèmes d'optimisation structurels, ces méthodes d'optimisation structurelle doivent être flexible de résoudre non seulement les dimensions des éléments en tant que variables de conception" mais aussi, par exemple, les variables de forme et les angles d'orientation des matériaux. Il devrait être capable de traiter toutes sortes de contraintes, à condition que seules les dérivées des fonctions de contraintes par rapport aux variables de conception puissent être calculées. Ainsi, la méthode devrait être capable de traiter des problèmes généraux de programmation non linéaire. En outre il doit tenir compte des caractéristiques des problèmes d'optimisation structurels, par exemple des évaluations de fonctions généralement très coûteuses, mais toujours la possibilité de calculer des gradients. De plus, la méthode devrait être stable et générer une séquence de solutions améliorées faisables du problème considéré. En effet, les approximations utilisées par Svanberg sont:

f (k) i (x) = r (k) i + n ∑ j=1 p (k) i j U (k) j -x j + q (k) i j x j -L (k) j (1) où p (k)
i j =    U (k) j -x (k) j 2 ∂ f i /∂ x j , if ∂ f i /∂ x j > 0 0, if ∂ f i /∂ x j ⩽ 0 (2) q (k) i j =    0, if ∂ f i /∂ x j ⩾ 0 -x (k) j -L (k) j 2 ∂ f i /∂ x j , if ∂ f i /∂ x j < 0 (3) r (k) i = f i x (k) - n ∑ j=1 p (k) i j U (k) j -x (k) j + q (k) i j x (k) j -L (k) j (4)
Introduction "version française" où toutes les dérivées ∂ f i /∂ x j pour i = 1, ..., m et j = 1, ..., n sont évaluées au x = x (k) . Ainsi sous les conditions p (k) i j ⩾ 0 et q (k) i j ⩾ 0, f (k) i est une fonction convexe, et donc chaque sousproblème a un unique optimum global.

Par cette technique, la forme de chaque fonction d'approximation est spécifiée par deux valeurs sélectionnées de paramètres L (k)

j et U (k)
j , qui sont choisis en fonction de la MMA spécifique démarche. Plusieurs règles de sélection de ces valeurs sont expliquées en détail dans [START_REF] Bruyneel | A family of mma approximations for structural optimization[END_REF][START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF]. Svanberg aussi montre comment ces deux paramètres peuvent être utilisés pour contrôler la convergence du processus. A chaque itération les asymptotes supérieure et inférieure U (k)

j et L (k)
j doivent être adaptées, les règles de mise à jour de ces paramètres selon Svanberg

• Si le processus a tendance à osciller, il doit être stabilisé. Cette stabilisation peut être réalisée en rapprochant les asymptotes du point d'itération courant.

• Si, au contraire, le processus est monotone et lent, il doit être " détendu ". Ceci peut être réalisé en éloignant les asymptotes du point d'itération courant.

Et donc une mise en oeuvre simple de ces règles est la suivante

Pour k = 0 et k = 1 L (k) j = x (k) j -( x j -x j ) et U (k) j = x (k) j + x j -x j . (5)
Pour k ≥ 2 1. Si les signes de x

(k) j -x (k-1) j et x (k-1) j -x (k-2) j
sont opposées, indiquant une oscillation du processus itératif, et les valeurs de asymptotes sont données par

L (k) j = x (k) -s x (k-1) j -L (k-1) j U (k) j = x (k) j + s U (k-1) j -x (k-1) (6)
2. Si les signes de x

(k) j -x (k-1) j et x (k-1) j -x (k-2) j
sont égaux, indiquant que le processus de convergence est lent, et donc

L (k) j = x (k) j -x (k-1) j -L (k-1) j /s U (k) j = x (k) j + U (k-1) j -x (k-1) j /s (7)
Plusieurs règles heuristiques ont également été données pour un processus d'adaptation pour l'ajustement automatique de ces asymptotes à chaque itération; voire [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF][START_REF] Svanberg | A globally convergent version of mma without linesearch[END_REF] On peut résumer les caractéristiques les plus importantes de la MMA comme suit • La MMA est une approximation de premier ordre au point itératif x (k) , i.e.,

f (k) x (k) = f x (k) ∇ f (k) x (k) = ∇ f x (k) (8)
• C'est une fonction rationnelle explicite, strictement convexe pour tout x tel que L (k) j < x j < U (k) j avec pôles, et c'est monotone (croissante si

∂ f ∂ x j x (k) > 0 et décroissante si ∂ f ∂ x j x (k) < 0).
• Les approximations sont séparables, ce qui signifie que la fonction d'approximation F : R d → R peut être exprimé sous la forme d'une somme des fonctions des variables individuelles, c'est-àdire, il existe des fonctions réelles F1, F2, ..., Fd telles que

F(x) = F 1 (x 1 ) + F 2 (x 2 ) + . . . + F d (x d ) (9)
Une telle propriété est cruciale dans la pratique parce que les matrices Hessianes des approximations seront diagonales, ce qui nous permet d'aborder des problèmes à grande échelle.

• Ce sont des fonctions lisses, les fonctions f (k) sont deux fois continûment différentiable sur les intervalles L (k) j < x j < U (k) j .

• A chaque itération externe, étant donné le point x (k) actuel, un sous-problème est généré et résolu, et sa solution définit l'itération suivante x (k+1) , donc une seule itération interne est effectuée.

Toutefois, il convient de mentionner que cette méthode ne donne pas de bons résultats dans certains cas. peut même échouer lorsque la courbure de l'approximation n'est pas correctement affectée [START_REF] Smaoui | Advances in dual algorithms and convex approximation methods[END_REF]. En effet, il est important de comprendre que toutes les approximations convexes, y compris le MMA, qui sont fondées sur les valeurs des approximations de premier ordre, ne fournissent aucune information sur la courbure. La deuxième est contenue dans la matrice Hessiane de la fonction objective H f , dont la composante (i, j) est ∂ 2 f ∂ x i ∂ x j (x). La mise à jour des asymptotes mobiles reste une tâche difficile. Une approche possible est d'utiliser la deuxième dérivée diagonale de la fonction objective pour définir les valeurs idéales de ces paramètres dans le MMA.

En fait, le MMA a été étendu afin d'inclure les dérivées de premier et de second ordre de la fonction objective. Un exemple simple de la MMA qui utilise un ordre de second ordre à l'itération Introduction "version française"

x (k) a été proposée par Fleury [START_REF] Fleury | Mathematical programming methods for constrained optimization: dual methods[END_REF]

f (k) (x) = f x (k) + d ∑ j=1 1 x (k) j -a (k) j - 1 x j -a (k) j x (k) j -a (k) j 2 ∂ f ∂ x j x (k) (10)
où, pour chaque j = 1, ..., n, les asymptotes a (k) j sont déterminés en fonction des dérivées partielles du premier et de deuxième ordre par [START_REF] Boyd | Convex Optimization[END_REF] et par [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] f (k) (x) =b (k) + c (k) xx (k) + d (k) 1 2

a (k) j = x (k) j + 2 ∂ f ∂ x j x (k) ∂ 2 f ∂ x 2 j x (k)
x (k) -a (k) 3 x -a (k) + 1 2 x (k) -a (k) x -2x (k) + a (k) (12)
a (k) =    L (k) si f ′ x (k) < 0 et L (k) < x (k) U (k) si f ′ x (k) > 0 et U (k) > x (k) (13)
Plusieurs versions ont été suggérées dans la littérature récente pour obtenir une mise en oeuvre pratique du MMA qui tire pleinement parti de l'information de second ordre, par exemple [START_REF] Bletzinger | Extended method of moving asymptotes based on second-order information[END_REF][START_REF] Chickermane | Structural optimization using a new local approximation method[END_REF][START_REF] Smaoui | Advances in dual algorithms and convex approximation methods[END_REF], et les articles qui y sont cités fournissent des lectures supplémentaires sur ce sujet. Les limites de la méthode d'analyse asymptote pour les approximations convexes du premier ordre sont examinées par Smaoui et al [START_REF] Smaoui | Advances in dual algorithms and convex approximation methods[END_REF], où l'on compare une approximation basée sur l'information du second ordre à une autre basée uniquement sur le premier ordre. L'approximation du second ordre permet d'obtenir le meilleur compromis entre robustesse et précision.

Contrairement à l'approche traditionnelle, nos méthodes remplacent le problème implicite (1.14) par une séquence de sous problèmes explicites convexes ayant une forme algébrique simple qui peut être résolue explicitement. Plus précisément, dans nos méthodes, une itération externe commence à partir de l'itération courante x (k) et se termine par une nouvelle itération x (k+1) . A chaque itération interne, à l'intérieur d'une itération externe explicite, un sous-problème convexe est généré et résolu. Dans ce sous-problème, la fonction objective originale est remplacée par une fonction linéaire plus une fonction rationnelle qui se rapproche des fonctions originales autour de x (k) . La solution optimale du sous-problème devient x (k+1) , et l'itération externe est terminée. Comme pour le MMA, nous montrerons que nos schémas d'approximation partagent toutes les caractéristiques énumérées ci-dessus.

De plus, notre méthode d'itération explicite est extrêmement simple à mettre en oeuvre et facile à utiliser. De plus, le MMA est très pratique à utiliser dans la pratique, mais ses propriétés théoriques de convergence n'ont pas été étudiées de manière exhaustive. Le présent document présente une étude détaillée des propriétés de convergence de la méthode proposée.

La principale motivation de ce manuscrit était de proposer des schémas d'approximation qui, comme nous le verrons, répond à toutes les propriétés bien connues de convexité et de séparabilité de la MMA. En particulier, le régime que nous proposons présente les principaux avantages suivants :

1. Un aspect important de notre schéma d'approximation est que tous les sous-problèmes associés ont des solutions explicites.

2. Il génère une séquence d'itérations qui est limitée et converge vers un point fixe de la fonction objective.

3. Convergence globale de la suite générée par les sous-problèmes de la méthode.

Dans cette thèse, un ensemble d'algorithmes de programmation séquentiels convexe strictement réalisable est présenté. Le but est de générer une séquence d'itération qui est strictement réalisable pour une classe particulière de contraintes, appelées contraintes réalisables, tandis que d'autres contraintes peuvent être violées au cours du processus d'itération. L'algorithme est motivé par des résultats numériques sur des fonctions de Benchmark, où certaines contraintes et la fonction objective ne peuvent être évaluées que si certaines contraintes de faisabilité sont satisfaites. Autres caractéristiques typiques sont des racines carrées ou des fonctions logarithmes d'expressions analytiques. Nous procédons à partir de la formulation du problème suivante

min x f (x) x ∈ R n s.t. c j (x) = 0, j = 1, . . . , m e c j (x) ≤ 0, j = m e + 1, . . . , m c e j (x) ≤ 0, j = 1, . . . , m f (14)
où les contraintes e j (x), j = 1, ..., m f , sont au moins deux fois continûment différentiables sur IR n . On suppose que certaines contraintes c j (x), j = 1, ..., m e , et la fonction objective f (x) peuvent seulement être évaluer sur l'ensemble faisable

F := x ∈ R n |e j (x) ≤ 0, j = 1, . . . , m f (15)
De plus, les contraintes régulières c j (x), j = 1, ..., m c et la fonction objective f (x), sont au moins deux fois différentiables et continues sur F. De plus, des contraintes de boîte peuvent être ajoutées au Introduction "version française" problème d'optimisation (1.14), ce qui est généralement le cas dans la pratique.

Le développement de la méthode des asymptotes mobiles (MMA) est motivé par des résultats numériques et des comparaisons des algorithmes démontrés avec d'autres algorithmes bien connus, ces algorithmes sont appliqués en optimisation des matériaux libres et en optimisation topologique voir Bendsøe et al [START_REF] Bendsoe | An analytical model to predict optimal material properties in the context of optimal structural design[END_REF]. Ces méthodes peuvent considérer comme une extension des méthodes SCP et de la méthode des asymptotes mobiles, voir Bendsøe et Sigmund [START_REF] Sigmund | Topology optimization-theory, methods, and applications[END_REF]. Dans un espace de conception donné, l'optimisation numérique trouve une approximation de l'optimum exacte du problème 1.14. La discrétisation par par élément fini est utilisée pour décider dans chaque élément s'il faut utiliser un matériau ou non. La rigidité de la structure est définie par la fonction dite de compliance, qui mesure le déplacement de la structure sous charge. Plus la conformité est faible, plus la structure résultante est rigide. De plus, la quantité totale de matériel est limitée. Pour éviter les instabilités numériques, c'est-à-dire les phénomènes en damier ou les zones grises, un filtre peut être utilisé, voir Ni, Zillober et Schittkowski [START_REF] Ni | Sequential convex programming methods for solving large topology optimization problems: implementation and computational results[END_REF]. Les problèmes d'optimisation en topologie sont des programmes non linéaires à grande échelle, qui peuvent être résolus efficacement par des algorithmes appropriés, par exemple la méthode de déplacement des asymptotes, voire Svanberg [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF].

Les algorithmes proposés dans cette thèse sont une extension des méthodes de programmation convexe séquentielles (SCP), de programmation convexe strictement réalisable (SCPF), qui est fréquemment utilisée en génie mécanique, la première méthode ne garantit pas la faisabilité des itérations, c'est-à-dire m f = 0, et la seconde nécessite une méthode par points intérieurs (IPM) pour obtenir une solution des sous problèmes produits. L'algorithme se rapproche de la solution optimale en résolvant une séquence de sous problèmes convexes et séparables, où une procédure de recherche de ligne par rapport à la fonction Lagrangienne augmentée est utilisée pour garantir la convergence globale, où la solution approximative satisfait toutes les contraintes du problème (1.14). MMA et SCP ont été conçus à l'origine pour résoudre des problèmes d'optimisation mécanique structurelle et sont souvent appliqués dans le domaine de l'optimisation topologique [START_REF] Sigmund | A 99 line topology optimization code written in matlab[END_REF][START_REF] Ling | Topology optimization of constrained layer damping on plates using method of moving asymptote (mma) approach[END_REF][START_REF] Bruyneel | Note on topology optimization of continuum structures including self-weight[END_REF][START_REF] Bruns | Topology optimization of non-linear elastic structures and compliant mechanisms[END_REF] . Étant donné que dans certains cas particuliers, les contraintes structurelles typiques deviennent linéaires dans les variables inverses, une substitution appropriée est appliquée, qui devrait linéariser ces fonctions dans un certain sens, voire [START_REF] Zillober | Very large scale optimization by sequential convex programming[END_REF]. Les méthodes MMA sont dérivées de la méthode d'optimisation CONLIN (CONvex LINearization), voire [START_REF] Fleury | Structural optimization: a new dual method using mixed variables[END_REF][START_REF] Fleury | Conlin: an efficient dual optimizer based on convex approximation concepts[END_REF]. L'algorithme formule des sous-problèmes convexes et séparables en linéarisant les fonctions des problèmes par rapport à deux asymptotes flexibles, une inférieure et une supérieure, si la dérivée partielle est négative dans l'itération courante, alors nous utilisons l'asymptote inférieure. Sinon, il est linéarisé dans le sens original. Comme le succès du MMA et du SCP dépend du point de départ et de la méthode utilisée pour résoudre les sous problèmes générés, le processus peut se terminer en oscillation si l'un d'eux n'est pas bien choisi.

Les méthodes proposées incluent une nouvelle approximation de la fonction objective, et des contraintes et une procédure de recherche de ligne, car aucune preuve de convergence ne peut être donnée pour la version originale du MMA. Les itérations sont évaluées par rapport à une fonction de mérite, qui combine la descente de la fonction objective et la faisabilité d'une manière appropriée. Le pas est réduit jusqu'à l'obtention d'une descente dans la fonction de mérite, par exemple, la fonction de Lagrange augmentée. Une stratégie active peut être appliquée pour réduire la taille du sous problème, économisant ainsi l'effort de calcul [START_REF] Bartlett | Active set vs. interior point strategies for model predictive control[END_REF]. Le programme SCPIP30.f est une implémentation de SCP, où la structure clairsemée des gradients et du Hessian est prise en compte. Quelques tests numériques comparatifs de SCP, de programmation quadratique séquentielle (SQP) et d'autres codes de programmation non linéaire sont disponibles pour des problèmes de tests d'optimisation structurels mécaniques, voire [START_REF] Schittkowski | Numerical comparison of nonlinear programming algorithms for structural optimization[END_REF]. Une convergence globale de la méthode SCP est proposée par Zillober [START_REF] Zillober | A globally convergent version of the method of moving asymptotes[END_REF][START_REF] Schittkowski | Nonlinear programming: algorithms, software, and applications[END_REF].

Bien qu'aucune preuve de convergence ne puisse être donnée pour la version originale du MMA, l'algorithme donne de bons résultats dans la pratique. En 1995, [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] à présenter une extension qui est globalement convergente mais dans la plupart des cas pas aussi efficaces que le MMA d'origine. Par la suite, une nouvelle méthode de convergence globale appelée GCMMA a été mise au point, ce qui a donné de bons résultats dans la pratique. Elle ne s'applique qu'aux contraintes d'inégalité, c.-à-d. m e = 0. Partant d'un point de départ réalisable x (0) ∈ F, l'algorithme génère une séquence de points d'itération réalisables, c'est-à-dire m c = 0, m f ̸ = 0. [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] à proposer des itérations internes supplémentaires garantissant f z (k,p) ≤ f (k,p) z (k,p) e j z (k,p) ≤ e (k,p) j z (k,p) , j = 1, . . . , m f [START_REF] Chen | Extended admm and bcd for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights[END_REF] où f (k,p) (x) est l'approximation strictement convexe de f (x) et e (k,p) j (x) est l'approximation convexe de e j (x), j = 1, ...., m f , à l'iteration externe k et l'iteration interne p. De plus, z (k,p) ∈ R n est la solution optimale du sous problème. Si la première ou la deuxième inégalité de (1.16) est violée pour au moins une contrainte ou la fonction objective, un sous problème plus conservateur est formulé à partir de l'approximation MMA. On peut montrer que la boucle d'itération interne se termine dans un nombre fini d'itérations. Notez que les fonctions doivent être évaluées à des points infaisables.

De nombreuses méthodes d'optimisation, par exemple SQP, appliquent des techniques de région de confiance pour montrer la convergence globale. Une nouvelle version du MMA est introduite par Ni [START_REF] Ni | A globally convergent method of moving asymptotes with trust region technique[END_REF], où les sous problèmes convexes sont limités par une région de confiance. Contrairement au MMA et au SCP, il ne s'applique qu'aux contraintes de boîte, alors que les contraintes d'égalité et d'inégalité ne peuvent être traitées, c'est-à-dire m e = m c = m f = 0.

Une combinaison de la méthode de déplacement des asymptotes avec l'approche par filtre est proposée par Fletcher et Leyffer [START_REF] Fletcher | Nonlinear programming without a penalty function[END_REF], est donnée par Ertel [START_REF] Ertel | Sequential convex programming methods for free material optimization[END_REF]. Un itéré est accepté, si une descente de la fonction objective ou une réduction de la violation des contraintes est obtenue. Sinon, le point est rejeté et un nouveau sous problème est généré en réduisant la distance entre les asymptotes. Les méthodes de filtrage induisent une séquence d'itération non monotone. Pour plus d'informations sur la méthode du filtre SQP et la preuve de convergence de l'algorithme, voire [START_REF] Fletcher | On the global convergence of a filter-sqp algorithm[END_REF]. Une extension de la méthode SCP proposée par [START_REF] Stingl | A sequential convex semidefinite programming algorithm with an application to multiple-load free material optimization[END_REF] pour les programmes semi-définis appelés PENSCP. Ils considèrent le problème suivant

min z f (Z) Z ∈ S n s.t. c j (Z) ≤ 0, j = 1, . . . , m c Z -Z ⪰ 0 Z -Z ⪰ 0 ( 17
)
où S n désigne l'espace des matrices symétriques de taille n. L'algorithme crée une séquence d'approximations convexes séparables par blocs du premier ordre. Contrairement au MMA et au SCP, la méthode utilise des asymptotes constantes. De plus, une procédure de recherche de ligne est appliquée pour assurer une descente suffisante de la fonction objective. Le sous problème semi-défini qui en résulte peut-être résolu efficacement grâce à sa structure spécifique par des solutions appropriées, par exemple PENNON, voire [START_REF] Stingl | A generalized augmented lagrangian method for semidefinite programming[END_REF]. La convergence globale de l'algorithme résultant peut être montrée, voire [START_REF] Stingl | A sequential convex semidefinite programming algorithm with an application to multiple-load free material optimization[END_REF]. Comme GCMMA on obtient de bons résultats pour les problèmes d'optimisation de topologie, il doit être appliqué à l'optimisation des matériaux libres [START_REF] Sigmund | Topology optimization approaches[END_REF][START_REF] Rojas-Labanda | Benchmarking optimization solvers for structural topology optimization[END_REF][START_REF] Kiyono | A new multi-p-norm formulation approach for stress-based topology optimization design[END_REF].

Certaines fonctions propres aux problèmes de FMO ne sont définies qu'à l'intérieur de la région réalisable, compte tenu des contraintes de faisabilité e j (x), j = 1, ...., m f . La méthode GCMMA proposée par Svanberg [START_REF] Svanberg | Mma and gcmma, versions september[END_REF] n'assure pas la faisabilité des itérations pendant le processus de solution.

Par conséquent, nous devons étendre la méthode de telle sorte que la stricte faisabilité soumise à un ensemble de contraintes particulières soit garantie à chaque étape de l'itération. Les contraintes de faisabilité convexes sont transmises directement au sous-problème tandis que la fonction objective ainsi que les contraintes restantes sont approximées sur la base du schéma d'approximation proposé dans [START_REF] Guessab | A globally convergent modified multivariate version of mma[END_REF][START_REF] Guessab | A globally convergent modified version of the method of moving asymptotes[END_REF]. Une stratégie d'ensemble actif n'est appliquée que pour les contraintes restantes, afin d'assurer la faisabilité chaque fois que des fonctions ou des gradients doivent être évaluées. En outre, les contraintes que l'on s'attend à trouver dans la solution optimale sont toujours incluses dans le réglage actif de la structure clairsemée des gradients et de la matrice Hessienne. Une recherche de ligne est effectuée pour assurer la convergence globale.

Les méthodes d'optimisation réalisables calculent une séquence d'itérations réalisables, c'est-àdire que seules les contraintes de faisabilité e j (x), j = 1, ..., m f , sont considérées, et donc m e = m c = 0. Dans la littérature, plusieurs méthodes d'optimisation réalisables peuvent être trouvées. Dans de nombreuses applications du monde réel, les problèmes d'optimisation sont de grande envergure et l'évaluation du gradient de fonction peut prendre du temps. En utilisant des techniques d'optimisation réalisables, le processus d'optimisation peut être interrompu à chaque itération, ce qui donne une solution réalisable, mais non optimale. Les méthodes d'optimisation réalisables les plus connues sont les méthodes de points intérieurs réalisables, les méthodes de projection et les méthodes de direction réalisables.

En général, les méthodes de points intérieurs (IPM) calculent à chaque itération une direction de descente de Newton en résolvant un système linéaire d'équations. L'orientation de la recherche qui en résultera pourrait ne pas être réalisable. Par conséquent, un deuxième système linéaire est formulé où le côté droit est perturbé assurant une direction réalisable. Certaines des méthodes FDIP résolvent un troisième système linéaire pour assurer une convergence super linéaire près d'un point fixe. Analogue aux méthodes SQP réalisables, une recherche de ligne le long de l'arc de recherche est effectuée pour assurer à la fois la faisabilité et une descente de la fonction objective. Un certain nombre de méthodes réalisables de point intérieur sont données dans la littérature [START_REF] Bakhtiari | A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent[END_REF][START_REF] Herskovits | A two-stage feasible directions algorithm for nonlinear constrained optimization[END_REF][START_REF] Herskovits | Feasible direction interior-point technique for nonlinear optimization[END_REF][START_REF] Panier | A qp-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization[END_REF][START_REF] Zhu | An efficient sequential quadratic programming algorithm for nonlinear programming[END_REF][START_REF] Papadrakakis | Large scale structural optimization: computational methods and optimization algorithms[END_REF].

Les méthodes de point intérieur réalisable partent de l'intérieur de la région réalisable et calculent une séquence d'itération qui s'approche de la limite. Une sous-classe est une méthode de barrière, où un paramètre de barrière combine les contraintes et la fonction objectif. Cela revient à ce qu'on appelle la fonction de barrière qui doit être minimisée, par exemple, par la méthode de Newton. Généralement, la fonction de barrière n'est définie que sur la région réalisable et tend vers l'infini à la limite. Une fonction de barrière populaire est la fonction de barrière logarithmique

f (x) + µ m f ∑ i=1 ln (-e j (x)) (18)
où µ ∈ R + est le paramètre barrière. En commençant par un gros µ, il est réduit itérativement de telle sorte que des solutions proches de la frontière peuvent être obtenues. Ces méthodes sont particulièrement efficaces pour les problèmes d'optimisation convexe, voire [START_REF] Potra | Interior-point methods[END_REF][START_REF] Gondzio | Interior point methods 25 years later[END_REF][START_REF] Pólik | Interior point methods for nonlinear optimization[END_REF][START_REF] Andersen | Implementation of interior point methods for large scale linear programming[END_REF]. Une autre classe de méthodes d'optimisation réalisables sont les méthodes de projection. Dans chaque itération k, les algorithmes calculent une direction de recherche

d (k) ∈ R n et projeter le point résultant x (k) + d (k)
à la limite de la région réalisable, si nécessaire. Le point projeté sur la frontière est noté x (k) P ∈ R n . La direction de recherche projetée d (k) P ∈ R n se compose de deux composants. À l'intérieur de la région réalisable, la direction de recherche projetée est donnée par d (k) . La deuxième partie est décrite par le segment de la limite entre le point d'intersection de d (k) avec la limite et le point de projection x (k) P . Une recherche de ligne est effectuée le long de la direction de recherche projetée d (k) P . Pour assurer la faisabilité, les problèmes doivent être convexes. L'effort de calcul de la projection dépend de l'algorithme et des contraintes du problème d'optimisation. Quelques méthodes de projection populaires sont présentées par Rosen [START_REF] Rosen | The gradient projection method for nonlinear programming. part i. linear constraints[END_REF][START_REF] Rosen | The gradient projection method for nonlinear programming. part ii. nonlinear constraints[END_REF] et par Grippo and al [START_REF] Grippo | A globally convergent version of the polak-ribiere conjugate gradient method[END_REF]. Les méthodes de projection sont souvent combinées avec d'autres méthodes efficaces d'optimisation non linéaire pour calculer la direction de descente d (k) . Jian, Zhang et Xue [START_REF] Jinbao | A superlinearly and quadratically convergent sqp type feasible method for constrained optimization[END_REF]ont combiné une méthode SQP avec des méthodes de projection pour obtenir une méthode SQP réalisable. Le sous problème quadratique est résolu pour obtenir une direction de descente. De plus, par une projection de l'itération x (k) sur la frontière on

Introduction "version française"

obtient un nouvel itéré.

Les méthodes de direction réalisables calculent une direction faisable d (k) , ce qui assure l'existence de θ (k) ∈ R + , tel que x (k) + σ (k) d (k) est faisable pour tout σ (k) ≤ θ (k) , où σ (k) ∈ R est la taille du pas. De nombreuses méthodes d'orientation réalisables peuvent être trouvées dans la littérature [START_REF] Zoutendijk | Methods of feasible directions: a study in linear and non-linear programming[END_REF]. Le premier algorithme de direction réalisable est proposé par Zoutendijk en 1960, voire [START_REF] Vanderplaats | Structural optimization by methods of feasible directions[END_REF]. Dans chaque itération k, une direction de recherche réalisable améliorée est déterminée et une recherche de ligne étendue est effectuée, donnant une descente suffisante de la fonction objectif et satisfaisant les contraintes e j (x) ≤ 0, j = 1, ..., m f . Commençons par un point de conception faisable x (0) , et calculons une direction de recherche d (k) à l'itération k satisfait une direction de descente par rapport à la fonction objectif et les ε-contraintes actives J (k)

ε := j = 1, . . . , m f |e j x (k) ≥ -ε , ε ∈ R + , i.e., ∇ f x (k) T d (k) ≤ 0 ∇e J x (k) T d (k) ≤ 0, j ∈ J (k) ε (19)
A chaque itération, un sous-problème linéaire est formulé, qui maximise la descente minimale, voir [START_REF] Topkis | On the convergence of some feasible direction algorithms for nonlinear programming[END_REF][START_REF] Kojima | An iteration potential reduction algorithm for linear complementarity problems[END_REF]. Nous dénotons la solution de min

δ ,d δ d ∈ R n , δ ∈ R s.t. ∇ f x (k) T d ≤ δ ∇e j x (k) T d ≤ δ , j ∈ J (k) ε ∥d∥ ∞ ≤ 1 (20)
par d (k) , δ (k) . Si ε est adapté correctement, on peut montrer que δ (k) ≤ 0, pour tout k = 0, 1, .... La taille de ε est très importante pour la convergence de l'algorithme. Si ε devient trop petit, on observe un comportement oscillant typique de l'algorithme. En 1961, Zoutendijk [START_REF] Vanderplaats | Structural optimization by methods of feasible directions[END_REF], a développé un algorithme plus robuste que le premier, et ε n'a pas besoin d'être adapté. En résolvant le problème min

δ ,d δ d ∈ R n , δ ∈ R s.t. ∇ f x (k) T d ≤ δ e j x (k) + ∇e j x (k) T d ≤ δ , j ∈ J (k) ε ∥d∥ ∞ ≤ 1 , (21)
on obtient une solution

d (k) , δ (k) , avec J (k) ε := j = 1, . . . , m f |e J x (k) ≥ -ε .
Une preuve de convergence pour les deux méthodes peut être donnée pour les contraintes convexes e j , j = 1, ..., m f , voire [START_REF] Bertsekas | Convex optimization algorithms[END_REF].Pour ces deux dernières versions des méthodes de direction de recherche, seule la convergence linéaire peut être représentée. Par conséquent, les sous problèmes sont étendus de sorte que les informations du deuxième ordre sont incluses. Une possibilité est de calculer une direction de descente d (k) 0 ∈ R n en résolvant un sous problème quadratique (QP), c'est-à-dire une fonction objective quadratique et des contraintes linéaires, selon les méthodes SQP, voir Schittkowski et Yuan [START_REF] Gill | Sequential quadratic programming methods[END_REF] min

d 1 2 d T H x (k) , y (k) d + ∇ f x (k) T d d ∈ R n s.t. e J x (k) + ∇e j x (k) T d ≤ 0, j = 1, . . . , m f (22)
où H x (k) , y (k) ∈ R n×n est la matrice hessienne de la fonction lagrangienne par rapport à x ou une approximation appropriée. De plus y (k) ∈ R; m f est la variable double. La direction de recherche résultante d

(k) 0 peut ne pas être réalisable, comme pour les contraintes actives ∇e j x (k) T d

(k) 0 = 0 est autorisée, ce qui donne une direction tangentielle à la région réalisable [START_REF] Panier | On combining feasibility, descent and superlinear convergence in inequality constrained optimization[END_REF]. Par conséquent, une correction est déterminée en inclinant la direction d'origine vers la région réalisable. Pour assurer une convergence rapide à proximité d'une solution, une direction de recherche supplémentaire est calculée par pliage. Une recherche de ligne étendue est effectuée le long de l'arc de recherche composé des trois directions, de sorte que la faisabilité et une descente suffisante de la fonction objectif sont garanties. La complexité de calcul par itération des méthodes SQP réalisables est significativement plus élevée par rapport aux méthodes SQP habituelles. Dans les méthodes les plus modernes, la complexité des calculs a été réduite.

Cette thèse traite des approximations basées sur la méthode des asymptotes mobiles. L'objectif principal est de proposer une nouvelle approche et des algorithmes faciles à mettre en oeuvre pour résoudre un problème d'optimisation non linéaire non convexe sans et avec un type particulier de contraintes et de comparer les résultats avec des méthodes connues. Au chapitre 2 publié dans le journal "Applicable Analysis and Discrete Mathematics", [START_REF] Guessab | A globally convergent modified version of the method of moving asymptotes[END_REF], présente le premier travail de cette thèse, une nouvelle méthode modifiée d'asymptotes mobiles est présentée. À chaque étape du processus itératif, un sous problème approximatif strictement convexe est généré et explicitement résolu, et ce faisant, nous proposons une stratégie pour incorporer une information de second ordre modifiée pour la localisation des asymptotes en mouvement. Cela réduit considérablement le coût de calcul de notre méthode d'optimisation et peut à la fois stabiliser et accélérer la convergence du processus général. Sous des hypothèses naturelles, nous prouvons la convergence géométrique de l'algorithme d'optimisation associé. De plus, les résultats expérimentaux révèlent que la méthode actuelle est significativement plus rapide que la méthode [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF], la méthode de Newton et la méthode BFGS, et qu'elle réussira lorsque ces dernières divergent simultanément.

Au chapitre 3, publié dans Applicable Analysis and Discrete Mathematics [START_REF] Guessab | A globally convergent modified multivariate version of mma[END_REF], nous présentons une extension de notre article précédent dans un cadre multivarié. La version multivariée proposée est un résultat globalement convergent pour une nouvelle méthode, qui consiste itérativement en la solution d'une version modifiée de la méthode de déplacement des asymptotes. Il est montré que l'algorithme généré possède certaines propriétés souhaitables. Nous indiquons les conditions dans lesquelles la convergence géométrique de la méthode actuelle est garantie. Tous nos résultats expérimentaux montrent que l'algorithme obtenu est significativement plus rapide que la méthode [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF], la méthode de Newton et la méthode CG-BFGS, et il réussira là où ces dernières divergent simultanément.

Dans le chapitre 4, nous présentons une nouvelle approche de la Méthode de Déplacement des Asymptotes utilisant des paramètres de projection spectrale pour l'optimisation par contrainte liée, ce nouvel algorithme combine les deux avantages de la convexité et de la séparabilité du MMA et l'accélération de la convergence de la méthode du gradient projeté. L'avantage de ce nouvel algorithme est qu'il est très facile à mettre en oeuvre et très efficace pour les problèmes à grande échelle et garder la faisabilité de l'itérer.

Chapter 1 Introduction

The method of moving asymptotes (MMA) was introduced, without a global convergence analysis, by Svanberg [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF] in 1987. This method can be considered as a generalization of the convex linearization method (CONLIN); see [11, 25, 26, 28, 48, 71-73, 76, 80, 84], Later, Svanberg [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] proposed a new version of the method that converges globally but still uses classical methods to solve the subproblems resulting from method approximations. Since then, many versions have been suggested.

Svanberg proposed this special type of convex approximation to solve structural optimization problems numerically, these structural optimization methods must be flexible to solve not only the dimensions of the elements as design variables, but also, for example, shape variables and material orientation angles. It should be able to handle all kinds of constraints, provided that only derivatives of the constraint functions in relation to the design variables can be calculated. Thus, the method should be able to deal with general nonlinear programming problems. In addition, it must take into account the characteristics of structural optimization problems, for example, evaluations of functions that are generally very expensive, but always the possibility of calculating gradients. In addition, the method should be stable and generate a sequence of feasible, improved solutions to the problem under consideration. Indeed, the approximations used by Svanberg are:

f (k) i (x) = r (k) i + n ∑ j=1 p (k) i j U (k) j -x j + q (k) i j x j -L (k) j (1.1)
where

p (k) i j =    U (k) j -x (k) j 2 ∂ f i /∂ x j , if ∂ f i /∂ x j > 0 0, if ∂ f i /∂ x j ⩽ 0 (1.2) q (k) i j =    0, if ∂ f i /∂ x j ⩾ 0 -x (k) j -L (k) j 2 ∂ f i /∂ x j , if ∂ f i /∂ x j < 0 (1.3) Introduction r (k) i = f i x (k) - n ∑ j=1 p (k) i j U (k) j -x (k) j + q (k) i j x (k) j -L (k) j (1.4)
where all derivatives ∂ f i /∂ x j pouri = 1, ..., met j = 1, ..., n are valued at x = x (k) . Thus under the conditions |p (k) i j ⩾ 0 and q (k)

i j ⩾ 0, f (k) i
is a convex function, and therefore each subproblem has a unique global optimum. By this technique, the shape of each approximation function is specified by two selected parameter values L (k) j and U (k) j , which are chosen according to the specific MMA approach. Several rules for selecting these values are explained in detail in [START_REF] Bruyneel | A family of mma approximations for structural optimization[END_REF][START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF]. Svanberg also shows how these two parameters can be used to control process convergence. At each iteration the upper and lower asymptotes U (k) j and L (k) j must be adapted, the rules for updating these parameters according to Svanberg

• If the process tends to oscillate, it must be stabilized. This stabilization can be achieved by bringing the asymptotes closer to the current iteration point.

• If, on the other hand, the process is monotonous and slow, it must be "relaxed". This can be achieved by moving the asymptotes away from the current iteration point.

And so a simple implementation of these rules is as follows for k = 0 and k = 1

L (k) j = x (k) j -( x j -x j ) and U (k) j = x (k) j + x j -x j . (1.5) For k ≥ 2 1. If the signs of x (k) j -x (k-1) j and x (k-1) j -x (k-2) j
are opposite, indicating an oscillation of the iterative process, and the asymptomatic values are given by

L (k) j = x (k) -s x (k-1) j -L (k-1) j U (k) j = x (k) j + s U (k-1) j -x (k-1) (1.6) 2. If the signs of x (k) j -x (k-1) j and x (k-1) j -x (k-2) j
are equal, indicating that the convergence process is slow, and therefore

L (k) j = x (k) j -x (k-1) j -L (k-1) j /s U (k) j = x (k) j + U (k-1) j -x (k-1) j /s (1.7)
Several heuristic rules have also been given for an adaptation process for the automatic adjustment of these asymptotes to each iteration; see [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF][START_REF] Svanberg | A globally convergent version of mma without linesearch[END_REF] The most important characteristics of MMA can be summarized as follows

• The MMA is a first-order approximation at the iterative point x (k) , i.e.,

f (k) x (k) = f x (k) ∇ f (k) x (k) = ∇ f x (k) (1.8)
• It is an explicit rational function, strictly convex for all x such that L (k) j < x j < U (k) j with poles, and it's monotonous. (increasing if

∂ f ∂ x j x (k) > 0 and decreasing if ∂ f ∂ x j x (k) < 0).
• The approximations are separable, which means that the approximation function F : R d → R can be expressed as a sum of the functions of the individual variables, i. e. there are real functions F1, F2, ..., Fd such that

F(x) = F 1 (x 1 ) + F 2 (x 2 ) + . . . + F d (x d ) (1.9)
Such a property is crucial in practice because the Hessian matrices of the approximations will be diagonal, allowing us to address problems on a large scale.

• These are smooth functions, the functions f (k) are twice continuously differentiable over the intervals

L (k) j < x j < U (k) j .
• For each external iteration, given the current point x (k) , a subproblem is generated and solved, and its solution defines the next iteration x(k+1) , so only one internal iteration is performed.

However, it should be mentioned that this method does not give good results in some cases. May even fails when the curvature of the approximation is not correctly affected [START_REF] Smaoui | Advances in dual algorithms and convex approximation methods[END_REF]. Indeed, it is important to understand that all convex approximations, including MMA, which are based on the values of first order approximations, do not provide any information on curvature. The second is contained in the Hessian matrix of the objective function

H f , whose component (i, j) is ∂ 2 f ∂ x i x j (x).
Updating moving asymptotes remains a difficult task. One possible approach is to use the second diagonal derivative of the objective to define the ideal values of these parameters in the MMA. In fact, the MMA has been extended to include first-and second-order derivatives of the objective function. For example, a simple example of MMA using a second order at iteration x (k) was proposed by Fleury [START_REF] Fleury | Mathematical programming methods for constrained optimization: dual methods[END_REF]

f (k) (x) = f x (k) + d ∑ j=1 1 x (k) j -a (k) j - 1 x j -a (k) j x (k) j -a (k) j 2 ∂ f ∂ x j x (k)
(1.10)

Introduction

, where, for each j = 1, ..., n, the asymptotes a (k) j are determined as a function of the first and second order partial derivatives by

a (k) j = x (k) j + 2 ∂ f ∂ x j x (k) ∂ 2 f ∂ x 2 j x (k) (1.11)
, and by [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]

f (k) (x) =b (k) + c (k) x -x (k) + d (k) 1 2 x (k) -a (k) 3 x -a (k) + 1 2 x (k) -a (k) x -2x (k) + a (k)
(1.12)

a (k) =    L (k) if f ′ x (k) < 0 and L (k) < x (k) U (k) if f ′ x (k) > 0 and U (k) > x (k) (1.13)
Several versions have been suggested in the recent literature to achieve a practical implementation of the MMA that takes full advantage of second-order information, for example, [START_REF] Bletzinger | Extended method of moving asymptotes based on second-order information[END_REF][START_REF] Chickermane | Structural optimization using a new local approximation method[END_REF][START_REF] Smaoui | Advances in dual algorithms and convex approximation methods[END_REF], and the articles cited therein to provide additional reading on this subject. The limitations of the asymptote analysis method for first-order convex approximations are examined by Smaoui et al [START_REF] Smaoui | Advances in dual algorithms and convex approximation methods[END_REF], where an approximation based on second-order information is compared to an approximation based only on the first order. The second-order approximation makes it possible to obtain the best compromise between robustness and precision.

Unlike the traditional approach, our methods replace the implicit problem (4.1) with a sequence of explicit convex subproblems with a simple algebraic form that can be solved explicitly. More precisely, in our methods, an external iteration starts from the current iteration x (k) and ends with a new iteration x (k+1) . At each internal iteration, within an explicit external iteration, a convex sub-problem is generated and solved. In this sub-problem, the original objective function is replaced by a linear function plus a rational function that approximates the original functions around x (k) . The optimal solution of the subproblem becomes x (k+1) , and the external iteration is complete. As with MMA, we will show that our approximation schemes share all the characteristics listed above. In addition, our explicit iteration method is extremely simple to implement and easy to use. In addition, MMA is very practical to use in practice, but its theoretical properties of convergence have not been studied in an exhaustive way. This document presents a detailed study of the convergence properties of the proposed method.

The main purpose of this manuscript was to propose approximation schemes which, as we will see, meet all the well-known properties of convexity and separability of MMA. In particular, the regime we propose has the following main advantages:

1. An important aspect of our approximation scheme is that all associated sub-problems have explicit solutions.

2. It generates an iteration sequence that is limited and converges to a fixed point of the objective function.

3. Global convergence of the sequence generated by the method's subproblems.

In this thesis, a set of strictly feasible convex sequential programming algorithms is presented. The goal is to generate an iteration sequence that is strictly feasible for a particular class of constraints, called feasible constraints, while other constraints may be violated during the iteration process. The algorithm is motivated by numerical results on Benchmark functions, where certain constraints, and the objective function can only be evaluated if certain feasibility constraints are met. Other typical characteristics are square roots or logarithmic functions of analytical expressions. We proceed from the following problem formulation

min x f (x) x ∈ R n s.t. c j (x) = 0, j = 1, . . . , m e c j (x) ≤ 0, j = m e + 1, . . . , m c e j (x) ≤ 0, j = 1, . . . , m f (1.14)
where the constraints e j (x), j = 1, ..., m f , are at least twice continuously differentiable on IR n . It is assumed that some constraints c j (x), j = 1, ..., m e , and the objective function f (x) can only be evaluated on the feasible set

F := x ∈ R n |e j (x) ≤ 0, j = 1, . . . , m f (1.15)
In addition, the regular constraints c j (x), j = 1, ..., m c and the objective function f (x), are at least twice continuously differentiable on F. In addition, box constraints can be added to the optimization problem 1, which is usually the case in practice.

The development of the Method of Moving Asymptotes(MMA) is motivated by numerical results and comparisons of demonstrated algorithms with other well-known algorithms, these algorithms are applied in free material optimization and topological optimization [START_REF] Bendsoe | An analytical model to predict optimal material properties in the context of optimal structural design[END_REF]. These methods can be considered as an extension of the SCP methods and the Method of Moving Asymptotes, see [START_REF] Sigmund | Topology optimization-theory, methods, and applications[END_REF]. In a given design space, numerical optimization finds an approximation of the exact optimum of the problem 1.14. Finite element discretization is used to decide in each element whether or not to use a material. The rigidity of the structure is defined by the so-called compliance function, which measures the displacement of the structure under load. The lower the compliance, the more rigid the resulting structure. In addition, the total amount of material is limited. To avoid numerical instabilities, i. e. checkered phenomena or grey areas, a filter can be used, see Ni, Zillober and Schittkowski [START_REF] Ni | Sequential convex programming methods for solving large topology optimization problems: implementation and computational results[END_REF].

Introduction

Topology optimization problems are large-scale, non-linear programs that can be solved effectively. by appropriate algorithms, such as the method of moving asymptotes, see [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF].

The algorithms proposed in this thesis are also an extension of the sequential convex programming (SCP), the strict feasible convex programming (SCPF) methods, which is frequently used in mechanical engineering, the first method does not ensure the feasibility of the iterates, i.e., m f = 0, and the second need an interior point method (IPM) to get a solution of the subproblems generated. The algorithm approximates the optimal solution by solving a sequence of convex and separable subproblems, where a line search procedure with respect to the augmented Lagrangian merit function is used for guaranteeing global convergence, where the approximate solution satisfies all the constraints of the problem (1.14). MMA and SCP were originally designed for solving structural mechanical optimization problems and it is often applied in the field of topology optimization [START_REF] Sigmund | A 99 line topology optimization code written in matlab[END_REF][START_REF] Ling | Topology optimization of constrained layer damping on plates using method of moving asymptote (mma) approach[END_REF][START_REF] Bruyneel | Note on topology optimization of continuum structures including self-weight[END_REF][START_REF] Bruns | Topology optimization of non-linear elastic structures and compliant mechanisms[END_REF] . Due to the fact that in some special cases, typical structural constraints become linear in the inverse variables, a suitable substitution is applied, which is expected to linearize these functions in some sense, see [START_REF] Zillober | Very large scale optimization by sequential convex programming[END_REF] MMA methods are derived from the optimization method CONLIN (CONvex LINearization), see [START_REF] Fleury | Structural optimization: a new dual method using mixed variables[END_REF][START_REF] Fleury | Conlin: an efficient dual optimizer based on convex approximation concepts[END_REF]. The algorithm formulates convex and separable subproblems by linearizing the problem's functions with respect to two flexible asymptotes, a lower and an upper one, if the partial derivative is negative in the current iterate, then we use the lower asymptote. Otherwise, it is linearized in the original sense. As the success of MMA and SCP is dependent on the starting point and the method used to solve the sub-problems generated, and the process might end in oscillation if one of them is not well chosen.

The methods proposed, including a new approximations of the objective function and constraints, and a line search procedure, as no convergence proof can be given to the original version of MMA. The iterates are valuated with respect to a merit function, which combines the descent of the objective function and the feasibility in a suitable way. The stepsize is reduced until a descent in the merit function,e.g, the augmented Lagrangian function, is obtained. An active strategy can be applied to reduce the size of the subproblem, saving computational effort [START_REF] Bartlett | Active set vs. interior point strategies for model predictive control[END_REF]. The program SCPIP30.f is an implementation of SCP, where the sparse structure of the gradients and the Hessian is taken into account. Some comparative numerical tests of SCP, sequential quadratic programming (SQP) and some other nonlinear programming codes are available for tests problems from mechanical structural optimization, see [START_REF] Schittkowski | Numerical comparison of nonlinear programming algorithms for structural optimization[END_REF]. Zillober in [START_REF] Schittkowski | Nonlinear programming: algorithms, software, and applications[END_REF][START_REF] Zillober | A globally convergent version of the method of moving asymptotes[END_REF] show the global convergence of the SCP.

Although no convergence proof for the original version of MMA can be given, the algorithm yields good results in practice. In 1995, [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] presented an extension which is globally convergent but in most cases not as efficient as the original MMA version. Later on, a new globally convergent method called GCMMA (globally convergent method of moving asymptotes) was developed, yielding good results in practice. It is only applicable for inequality constraints, i.e., m e = 0. Proceeding from a feasible starting point x (0) ∈ F, the algorithm creates a sequence of feasible iterates, i.e., m c = 0, m f ̸ = 0. [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] proposed additional inner iterations ensuring f z (k,p) ≤ f (k,p) z (k,p) e j z (k,p) ≤ e (k,p) j z (k,p) , j = 1, . . . , m f (1.16) where f (k,p) (x) is the strictly convex approximation of f (x) and e (k,p) j (x) is the convex approximation of e j (x), j = 1, ..., m f , in outer iteration k and the inner iteration p. Moreover, z (k,p) ∈ R n is the optimal solution of the subproblem. If the first or the second inequality of (1.16) is violated for at least one constraint or the objective function, a more conservative subproblem is formulated based on the MMA approximation. It can be shown that the inner iteration loop terminates within a finite number of iterations. Note that the functions have to evaluated at infeasible points.

Many optimization methods, for example SQP, apply trust region techniques to show global convergence. A new version of MMA is introduced by Ni [START_REF] Ni | A globally convergent method of moving asymptotes with trust region technique[END_REF], where the convex subproblems are restricted by a trust region. In contrast to MMA and SCP, it is only applicable for the box constraints, while equality and inequality constraints cannot be handled, i.e., m e = m c = m f = 0.

A combination of the method of moving asymptotes with the filter approach proposed by Fletcher and Leyffer [START_REF] Fletcher | Nonlinear programming without a penalty function[END_REF], is given by Ertel [START_REF] Ertel | Sequential convex programming methods for free material optimization[END_REF]. An iteration is accepted, if a descent in the objective function or a reduction of the constraint violation is obtained. Otherwise, the point is rejected and a new subproblem is generated by reducing the distance between the asymptotes. Filter methods induce a non-monotone iteration sequence. For more information about the SQP-filter method and the proof convergence of the algorithm, see [START_REF] Fletcher | On the global convergence of a filter-sqp algorithm[END_REF]. An extension of the SCP method proposed by [START_REF] Stingl | A sequential convex semidefinite programming algorithm with an application to multiple-load free material optimization[END_REF] for semidefinite programs called PENSCP. They consider the following problem

min z f (Z) Z ∈ S n s.t. c j (Z) ≤ 0, j = 1, . . . , m c Z -Z ⪰ 0 Z -Z ⪰ 0 (1.17)
where S n denotes the space of symmetric matrices of size n. The algorithm creates a sequence of first-order block-separable convex approximations. In contrast to MMA and SCP, the method uses constant asymptotes. Moreover, a line search procedure is applied to ensure a sufficient descent in the objective function. The resulting semidefinite subproblem can be solved efficiently due to its specific structure by appropriate solvers, e.g., PENNON, see [START_REF] Stingl | A generalized augmented lagrangian method for semidefinite programming[END_REF]. Global convergence of the resulting algorithm can be shown, see [START_REF] Stingl | A sequential convex semidefinite programming algorithm with an application to multiple-load free material optimization[END_REF]. As GCMMA achieves good results for topology optimization problems, it is to be applied to free material optimization [START_REF] Kiyono | A new multi-p-norm formulation approach for stress-based topology optimization design[END_REF][START_REF] Rojas-Labanda | Benchmarking optimization solvers for structural topology optimization[END_REF][START_REF] Sigmund | Topology optimization approaches[END_REF]. Some of the problem specific functions of FMO are only defined within the feasible region given by feasibility constraints e j (x), j = 1, ..., m f . The GCMMA method proposed by Svanberg [START_REF] Svanberg | Mma and gcmma, versions september[END_REF] is not ensuring feasibility of the Introduction iterates during the solution process. Therefore, we need to extend the method such that strict feasibility subject to a special set of constraints is guaranteed in each iteration step. The convex feasibility constraints are passed to the subproblem directly while the objective function, as well as the remaining constraints are approximated based on the approximation's scheme proposed in [START_REF] Guessab | A globally convergent modified multivariate version of mma[END_REF][START_REF] Guessab | A globally convergent modified version of the method of moving asymptotes[END_REF]. An active set strategy is applied to the remaining constraints only, to ensure feasibility whenever functions or gradients are to be evaluated. In addition, constraints that are expected to be active in the optimal solution are always included in the active setting the sparse structure of the gradients and Hessian. A line search is performed to ensure global convergence.

Feasible optimization methods compute a sequence of feasible iterates,i.e., only feasibility constraints e j (x), j = 1, ..., m f , are considered, i.e, m e = m c = 0. In the literature, several feasible optimization methods can be found. In many real-world applications, the optimization problems are of large scale dimension and the function gradient evaluations might be time-consuming. Using feasible optimization techniques, the optimization process can be aborted at each iterate yielding a feasible, although not optimal solution. The most known feasible optimization methods are feasible interior-point methods, projection methods, and feasible direction methods.

In general, interior-point methods (IPM) compute in each iteration a Newton descent direction by solving a linear system of equations. The resulting search direction might not be a feasible direction. Therefore, a second linear system is formulated where the right-hand side is perturbed ensuring a feasible direction. Some of the FDIP methods solve a third linear system to ensure superlinear convergence near a stationary point. Analog to feasible SQP methods, a line search along the search arc is performed to ensure both feasibility and a descent in the objective function. Several feasible direction interior methods are given in the literature [START_REF] Bakhtiari | A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent[END_REF][START_REF] Herskovits | A two-stage feasible directions algorithm for nonlinear constrained optimization[END_REF][START_REF] Herskovits | Feasible direction interior-point technique for nonlinear optimization[END_REF][START_REF] Panier | A qp-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization[END_REF][START_REF] Zhu | An efficient sequential quadratic programming algorithm for nonlinear programming[END_REF][START_REF] Papadrakakis | Large scale structural optimization: computational methods and optimization algorithms[END_REF].

Feasible interior point methods start from the interior of the feasible region and compute an iteration sequence that approaches the boundary. A subclass is a barrier method, where a barrier parameter combines the constraints and the objective function. This yields the so-called barrier function which is to be minimized, e.g., by Newton's method. Typically the barrier function is only defined on the feasible region and tends to infinity at the boundary. A popular barrier function is the logarithmic barrier function

f (x) + µ m f ∑ i=1 ln (-e j (x)) (1.18)
where µ ∈ R + is the barrier parameter. Starting with a large µ, it is reduced iteratively, such that solutions near the boundary can be obtained. These methods are especially successful for convex optimization problems, see [START_REF] Potra | Interior-point methods[END_REF][START_REF] Gondzio | Interior point methods 25 years later[END_REF][START_REF] Pólik | Interior point methods for nonlinear optimization[END_REF][START_REF] Andersen | Implementation of interior point methods for large scale linear programming[END_REF].

Another class of feasible optimization methods is projection methods. In each iteration k, the algorithms compute a search direction d (k) ∈ R n and project the resulting point x (k) + d (k) on the boundary of the feasible region, if necessary. The projected point on the boundary is denoted x

(k) P ∈ R n . The projected search direction d (k)
P ∈ R n consists of two components. Inside the interior of the feasible region, the projected search direction is given by d (k) . The second part is described by the segment of the boundary between the intersection point of d (k) with the boundary and the projection point x The effort to compute the projection depends on the algorithm and on the constraints of the optimization problem. Some popular projection methods are presented by Rosen [START_REF] Rosen | The gradient projection method for nonlinear programming. part i. linear constraints[END_REF][START_REF] Rosen | The gradient projection method for nonlinear programming. part ii. nonlinear constraints[END_REF], and by Grippo and al [START_REF] Grippo | A globally convergent version of the polak-ribiere conjugate gradient method[END_REF]. Projection methods are often combined with other efficient nonlinear optimization methods to compute the descent direction d (k) . Jian, Zhang and Xue [START_REF] Jinbao | A superlinearly and quadratically convergent sqp type feasible method for constrained optimization[END_REF] combined an SQP method with projection methods to get feasible SQP methods. The quadratic subproblem is solved to obtain a decent direction. Moreover, By a projection of the iterate x (k) on the boundary we get a new iteration.

Feasible direction methods compute a feasible direction d (k) , which ensures the existence of

θ (k) ∈ R + , such that x (k) + σ (k) d (k) is feasible for all σ (k) ≤ θ (k)
, where σ (k) ∈ R is the stepsize. Many different feasible direction methods can be found in the literature [START_REF] Zoutendijk | Methods of feasible directions: a study in linear and non-linear programming[END_REF]. The first feasible direction algorithm is proposed by Zoutendijk in 1960, see [START_REF] Vanderplaats | Structural optimization by methods of feasible directions[END_REF]. In each iteration k, an improving feasible search direction is determined and an extended line search is performed, yielding a sufficient descent in the objective function and satisfying the constraints e j (x) ≤ 0, j = 1, ..., m f . Let us start from a feasible design point x (0) , and compute a search direction d (k) at the iteration k satisfies a descent direction with respect to the objective function and the ε active constraints

J (k) ε := j = 1, . . . , m f |e j x (k) ≥ -ε , ε ∈ R + , i.e., ∇ f x (k) T d (k) ≤ 0 ∇e J x (k) T d (k) ≤ 0, j ∈ J (k) ε (1.19)
A each iteration, a linear subproblem is formulated, which maximizes the minimal descent, see [START_REF] Topkis | On the convergence of some feasible direction algorithms for nonlinear programming[END_REF][START_REF] Kojima | An iteration potential reduction algorithm for linear complementarity problems[END_REF]. We denote the solution of min k) . If ε is adapted adequately, it can be shown that δ (k) ≤ 0,for all k = 0, 1, .... The size of ε is very important for the convergence of the algorithm. If ε becomes too small, we observe a Introduction typical oscillating behavior of the algorithm. In 1961, Zoutendijk [START_REF] Vanderplaats | Structural optimization by methods of feasible directions[END_REF], developed an algorithm more robust than the first, and ε need not be adapted. By solving the problem min

δ ,d δ d ∈ R n , δ ∈ R s.t. ∇ f x (k) T d ≤ δ ∇e j x (k) T d ≤ δ , j ∈ J (k) ε ∥d∥ ∞ ≤ 1 (1.20) by d (k) , δ (
δ ,d δ d ∈ R n , δ ∈ R s.t. ∇ f x (k) T d ≤ δ e j x (k) + ∇e j x (k) T d ≤ δ , j ∈ J (k) ε ∥d∥ ∞ ≤ 1 , (1.21)
we get a solution

d (k) , δ (k) , with J (k) ε := j = 1, . . . , m f |e J x (k) ≥ -ε .
A convergence proof for both methods can be given for convex constraints e j , j = 1, ..., m f , see [START_REF] Bertsekas | Convex optimization algorithms[END_REF]. For these two last versions of the search direction methods, only linear convergence can be shown. Therefore, the subproblems are extended such that second-order information is included. One possibility is to compute a descent direction d (k) 0 ∈ R n by solving a quadratic subproblem (QP), i.e., a quadratic objective function and linear constraints, according to SQP methods, see [START_REF] Gill | Sequential quadratic programming methods[END_REF] min

d 1 2 d T H x (k) , y (k) d + ∇ f x (k) T d d ∈ R n s.t. e J x (k) + ∇e j x (k) T d ≤ 0, j = 1, . . . , m f (1.22)
where H x (k) , y (k) ∈ R n×n is the Hessian of the Lagrangian function with respect to x or an appropriate approximation. Moreover y (k) ∈ R m f is the dual variable. The resulting search direction

d (k)
0 may not be feasible, as for active constraints ∇e j x (k) T d

(k) 0 = 0 is allowed, which yields to a search direction tangential to the feasible region [START_REF] Panier | On combining feasibility, descent and superlinear convergence in inequality constrained optimization[END_REF]. Therefore, a correction is determined by tilting the original direction towards the feasible region. To ensure fast convergence near a solution an additional search direction is computed by bending. An extended line search is performed along the search arc consisting of all three directions, such that the feasibility and a sufficient descent in the objective function are guaranteed. The computational complexity per iteration of the feasible SQP methods is significantly higher compared to the usual SQP methods. In state-of-the-art methods, the computational complexity has been reduced. This thesis deals with approximations based on the method of moving asymptotes. The main objective is to propose a new approach and algorithms easy to implement for solving a non-convex nonlinear optimization problem without and with a special kind of constraint and compare the results with a known method.

In Chapter 2 published in "Applicable Analysis and Discrete Mathematics" [START_REF] Guessab | A globally convergent modified version of the method of moving asymptotes[END_REF], presents the first work during my thesis, A new modified moving asymptotes method is presented. At each step of the iterative process, a strictly convex approximating subproblem is generated and explicitly solved, and in doing so, we propose a strategy to incorporate modified second-order information for the moving asymptotes location. This considerably reduces the computational cost of our optimization method and may both stabilize and speed up the convergence of the general process. Under natural assumptions, we prove the geometric convergence of the associated optimization algorithm. In addition, experimental results reveal that the present method is significantly faster compared to the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, and the BFGS Method, and it will succeed where this latter diverges simultaneously.

In Chapter 3, published in Applicable Analysis and Discrete Mathematics [START_REF] Guessab | A globally convergent modified multivariate version of mma[END_REF], we introduce an extension of our previous paper [START_REF] Guessab | A globally convergent modified version of the method of moving asymptotes[END_REF] in a multivariate setting. The proposed multivariate version is a globally convergent result of a new method, which consists iteratively of the solution of a modified version of the method of moving asymptotes. It is shown that the algorithm generated has some desirable properties. We state the conditions under which the present method is guaranteed to converge geometrically. All our experimental results show that the resulting algorithm is significantly faster compared to the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, and the CG-BFGS Method, and it will succeed where this latter diverge simultaneously.

In Chapter 4, we present a new approach of the Method of Moving Asymptotes using a spectral projected parameter for bound constrained optimization, this new algorithm combines both advantages of convexity and separability of MMA and the speed up the convergence of the projected gradient method. The advantage of this new algorithm is that it is quite easy to implement and very effective for large scale problems and keep the feasibility of the iteration.

In Chapter 5, an extension of the new approach of the method of moving asymptotes presented in chapter 4 for constrained optimization problems is proposed, based on the sequential convex programming methods as proposed by [START_REF] Zillober | Very large scale optimization by sequential convex programming[END_REF]. The idea is to include the second-order information provided by this parameter into the model functions that define the rational approximations to the objective function and the nonlinear constraints, at the expense of additional gradient evaluations per inner iteration. The spectral parameter keeps the generated sequence conveniently conservative with respect to the original functions, preserving the global convergence property. As far as the objective function, conservative approximations ensure monotonically decreasing values, whereas, for the constraints, feasibility for an augmented problem is guaranteed. Strict convexity and separability of the model are kept so that the subproblems have a unique solution. Finally, Chapter 6 gives the conclusions of this thesis and some suggestions for future works.

Chapter 2 A GLOBALLY CONVERGENT MODIFIED UNIVARIATE VERSION OF THE METHOD OF MOVING ASYMPTOTES 2.1 Motivation and theoretical justification

Consider the unconstrained optimization problem: Find x * ∈ Ω such that

f (x * ) = min x∈Ω f (x) , (2.1)
where Ω is an open subset of R and f : R → R is a given non-linear real-valued objective function, typically twice continuously differentiable, which could be non-convex. In order to evaluate the merit of using second order information an extension of the method of moving asymptotes, that accounts for the curvatures, was proposed in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]. Let us first briefly recall its main idea. Throughout, we assume that f ′ does not vanish at a given suitable initial point x (0) ∈ Ω, that is f ′ (x (0) ) ̸ = 0, since if this is not the case we have nothing to solve. Starting from the initial design point x (0) the iterates x (k) are computed successively by solving sub-problems of the form: Find x (k+1) such that

f (k) (x (k+1) ) = min x∈Ω f (k) (x), (2.2)

A GLOBALLY CONVERGENT MODIFIED UNIVARIATE VERSION OF THE METHOD OF MOVING ASYMPTOTES

where the approximating function f (k) of the objective function f at the k-th iteration has the following form:

f (k) (x) = a (k) + b (k) (x -x (k) ) + (2.3) c(k) 1 2 (x (k) -d (k) ) 3 x -d (k) + 1 2 (x (k) -d (k) )(x -2x (k) + d (k) ) , with
d (k) = L (k) if f ′ (x (k) ) < 0, and L (k) < x (k) U (k) if f ′ (x (k) ) > 0, and U (k) > x (k) , (2.4)
here, the asymptotes U (k) and L (k) are adjusted heuristically during the iterations, or guided by a proposed given function where the first and second derivative are evaluated at the current iteration point x (k) . In contrast with the classical Newton method, here the approximation functions f (k) are of the form of a linear function plus a rational function. For each iteration, the approximate parameters

a (k) , b (k) and c (k) used in equation (2.
3) are determined in such a way that the following set of interpolation conditions are satisfied:

f (k) (x (k) ) = f (x (k) ), (2.5)
( f (k) ) ′ (x (k) ) = f ′ (x (k) ), (2.6)
( f (k) ) ′′ (x (k) ) = f ′′ (x (k) ).
(2.7)

It follows from the above identities that a (k) , b (k) , and c (k) are given by

a (k) = f (x (k) ), b (k) = f ′ (x (k) ), c (k) = f ′′ (x (k) ). (2.8)
In order to apply this method, it is necessary that the objective function should fulfill for each iteration k the following condition:

f ′′ (x (k) ) > 0, (2.9)
which is typically an important weakness to this approach. Hence, this method is very restrictive and also has the following disadvantage :

• It needs good initial solution x * close to the exact solution.

• It converges slowly, in many cases, to the optimum x * .

• It does not always converge.

• Its performance degrades when it applied to nonconvex functions.

A modified moving asymptotes method 29

It is the intention of this contribution to extend the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method to a more general context, by removing the restrictive condition (2.9) on the objective functions making the present approach more efficient. It is shown, as will be proved below, that the new method converges geometrically. Comparative numerical studies also show the success of the proposed extensions for various kinds of different test functions. Moreover, in almost all the problems we consider, the method of the present paper works better than the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method or the BFGS method itself. This chapter is organized as follows. In Section 2.2, we discuss a modified moving asymptotes method.

The general convergence theory for the new moving asymptotes method. In section 2.4, various numerical experiments conduct to confirm our theoretical finding.

A modified moving asymptotes method

Throughout this chapter we assume that w is a function satisfying the following conditions:

w is a real-valued function, defined and continuous on R, (2.10)

lim |x|→+∞ w(x) = 0. (2.11)
Our general modification of moving asymptotes method that we examine herein may be described as follows: Given the iteration point x(k) (at iteration k).

• The objective function f is iteratively approximated at the k-th iteration by the approximating function f (k) w where:

f (k) w (x) = ã(k) + b(k) (x -x(k) ) + c(k) 1 2 ( x(k) -d(k) ) 3 x -d(k) + 1 2 ( x(k) -d(k) )(x -2 x(k) + d(k) ) .
(2.12)

• The approximating function f (k) w is first order approximations of the original function f at the current iteration point x(k) , i.e.,

f (k) w ( x(k) ) = f ( x(k) ), (2.13)
( f (k) w ) ′ ( x(k) ) = f ′ ( x(k) ). (2.14)
In addition to the above conditions (2.13) and (2.14), the approximating function should satisfy the more general condition (2.15) instead of (2.7):

( f (k) w ) ′′ ( x(k) ) = f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) ) . (2.15)
Consequently, in the present situation, the approximate parameters ã(k) , b(k) and c(k) are here determined for each iteration such that:

ã(k) = f ( x(k) ), (2.16) b(k) = f ′ ( x(k) ), (2.17)
c(k) = f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) ) . (2.18)
Furthermore, in order to fully determine an explicit expression for the approximating function

f (k) w , the parameter d(k) is chosen such that d(k) = x(k) + 2 α(k) f ′ ( x(k) ) c(k) , (2.19)
where

{ α(k) } k is a sequence of real numbers with α(k) > 1, (k ∈ N). (2.20)
Different rules for how to choose these values (and possible weight functions in (2.15)) will be discussed later. We note that our method does not use the interpolation condition (2.7), but instead we have incorporated a first-and second-order information, as given in (2.18). Moreover, in particular, if you take w = 0 and at each iteration condition (2.9) is fulfilled, then our iterative scheme obviously reduces to the one introduced in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]. Hence, subsequent iterations of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method are similar, except that in the proposed approximating function f (k) w the parameters c (k) and d (k) are replaced by those computed in (2.18) and (2.19) respectively. It starts at an initial point x(0) and generates successive iterates by

f ( x(k+1) ) ← f (k) w ( x(k+1) ) = min x∈Ω f (k) w (x) . (2.21)
For simplicity, we have removed the index w in x(k) w .

We prefer to work with (2.18) instead of (2.7) for several reasons. First, as mentioned above, this allows us to to apply our method to a large class of objective functions. There is also a significant difference from a numerical point of view: many experimental results reveal that the iterative scheme based on our modification (2.18) can yield significantly fewer iterations than the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method or the BFGS Method itself. In contrast to these three approaches, our method converges even if the starting point is very far from the true solution. In addition, as we will see, the key features of the present method are:

• It does not require us to build a good initial solution close to the exact solution.

• It converges geometrically for a large class of functions w that satisfy condition (2.11).

• It will succeed where the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method and the BFGS Method break down.

Convergence Analysis

31

We have not succeeded in proving that the method can be extended to multiple dimensions, but in practice, we have found it to work in two dimensions.

Convergence Analysis

We start this section with a result concerning an explicit expression for the iterative sequence x(k) k generated by the approximating function f (k) w . Here, we continue to denote by c(k) , d(k) and α(k) the coefficients given by (2.18), (2.19) and (2.20) respectively. For brevity, in the following we use the notation: . Then, for each k > 0 the approximating function defined by (2.12) is a strictly convex function on I k . In addition, the function f (k) w has a unique minimum at

I k =      d(k) , +∞ if f ′ ( x(k) ) < 0, -∞, d(k) if f ′ ( x(k) ) > 0. , (2.22
x(k+1) ← x(k) * = d(k) + ( x(k) -d(k) ) s(k) (2.23)
where

s(k) = α(k) α(k) -1 . ( 2

.24)

Proof 1 The proof for this theorem follows by arguments essentially identical to those given in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF].

The main ingredient here is a suitable application of the condition (2.20) imposed on the coefficient d(k) . Next, let us make the following observation. We have tacitly assumed that the denominator of (2.24) cannot have the value zero, since if it is the case then by (2. [START_REF] Fletcher | An exact penalty function for nonlinear programming with inequalities[END_REF]) and (2.20) we immediately get f ′ ( x(k) ) = 0, and we have nothing to show. We first start by showing that the approximating function f (k) w is strictly convex in I k . To this end we prove that (

f (k) w ) ′′ is nonnegative in I k . Indeed, a simple calculation reveals that f (k) w ′′ (x) = c(k) x(k) -d(k) x -d(k) 3 . (2.25)
In view of (2.25), it remains to show that the term on the right-hand side of (2.

f ′ x(k) + 1 2 c(k) x(k) -d(k) 1 - x(k) -d(k) 2 x -d(k) 2 = 0, (2.26)
which, after trivial calculations, implies

x(k) -d(k) x -d(k) 2 = 1 + 2 f ′ x(k) c(k) x(k) -d(k) .
(2.27)

Now using (2.19), we can write

2 f ′ x(k) c(k) x(k) -d(k) = - 1 α(k) .
(2.28)

Therefore, after some simplification, equation (2.27) becomes

x(k) -d(k) x -d(k) 2 = 1 - 1 α(k) .
(2.29)

Finally, the required identity (2.23) immediately follows from (2.29) and the above mentioned fact that x k -d(k) and x -d(k) have the same sign in the interval I k . This completes the proof of the theorem.

Let us now define the notion of feasibility for a sequence of asymptotes r(k) := r(k) k , which we will often use in the sequel.

Definition 2.3.2 Let's w a function, satisfies (2.10) and (2.11). A sequence of asymptotes r(k) is said feasible, if for all k ≥ 0, there exist two real numbers L (k) and U (k) satisfying the following:

r(k) =          L (k) if f ′ x(k) < 0, and L (k) < x(k) + 2 f ′ x(k) | f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) )| , U (k) if f ′ x(k) > 0, and U (k) > x(k) + 2 f ′ x(k) | f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) )| .
(2.30)

It is clear from the above definition that every feasible sequence of asymptotes r(k) also satisfies the constraints of type (2.4).

The following proposition, which is easily obtained by a simple algebraic manipulation, shows that the lower bound of the difference between the asymptotes and the current iterate x(k) , can be estimated as in (2.31).

2 f ′ ( x(k) ) f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) ) < x(k) -d(k) . (2.31)
By defining the suitable index set

I (k) =    d(k) , +∞ if f ′ ( x(k) ) < 0, -∞, d(k) if f ′ ( x(k) ) > 0,    . (2.32)
Remark 2.3.4 If we take w = 0, so the null function is continuous and satisfied (2.11), then the interpolation condition:

( f (k) w ) ′′ ( x(k) ) = | f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) )|. become ( f (k) w ) ′′ ( x(k) ) = | f ′′ ( x(k) )|.
and if we assume that f ′′ ( x(k) ) > 0 ∀k ≥ 0 then

f (k) w = f (k)
where f (k) is the approximated function defined by

f (k) (x) = a (k) + b (k) (x -x(k) ) + (2.33) c(k) 1 2 ( x(k) -d(k) ) 3 x -d(k) + 1 2 ( x(k) -d(k) )(x -2 x(k) + d(k) ) a (k) = f ( x(k) ), b (k) = f ′ ( x(k) ), c(k) = f ′′ ( x(k) ).
(2.34)

and if we take α k = α > 1, we get

d(k) = x(k) + 2α f ′ ( x(k) ) f " ( x(k) ) , with α > 1 (2.35)
We can rewrite d(k) as

d(k) =          L k < x(k) + 2 f ′ x(k) f ′′ x(k) i f f ′ x(k) < 0, U k > x(k) + 2 f ′ x(k) f ′′ x(k) i f f ′ x(k) > 0.
(2.36)

So this method can be seen as an extension of the method of moving asymptotes with explicit solutions. MOVING ASYMPTOTES

We have built a strictly convex approximation function of the objective function f at x(k) , which is minimum at x(k) * ∈ I k . We have now to verify that the sequence { x(k) } k≥0 defined by x(k+1) = x(k) * converges to the solution x * of the initial problem.

Convergence study

In this Section, we give the main result of this chapter, that is sufficient conditions on the data (the point x(0) , the function f ′ in a neighborhood of x(0) , the family f ′′ x(k) , k ≥ 0), which guarantee that first derivative of f vanishes in a neighborhood of x * , first, and secondly, the convergence of the method to this zero.

To establish our convergence results, we need the following assumptions. We assume that there exist positive constants r, M, C and ξ < 1 such that the following assumptions hold:

Assumption 1 B r := x ∈ R : x -x(0) ≤ r ⊂ Ω. Assumption 2 sup k≥0 x(k) -d(k) ≤ C. Assumption 3 C M ≤ c(k) 2 x(k) -d(k) -f ′ x(k) . Assumption 4 sup k≥0 sup x∈B f ′′ (x) - f ′ x (k-1) x (k-1) -x(k) ≤ ξ M . Assumption 5 0 < f ′ x(0) ≤ r M (1 -ξ ) .
Assumption 2 enforces the quite natural conditions that are: at each iteration k, the distance between x(k) and the the interval boundary d(k) is bounded. Furthermore, Assumption 4 tells us that the coefficient c(k) does not change too much in a neighborhood of x(0) , and finally for any k the functions c(k) and 1 c(k) have not to change too much in a neighborhood of x(0) , and c(k) being sufficiently near c (0) where c

(0) = f ′′ ( x(0) ) + w( x(0) ) f ′ ( x(0)
) . Finally, Assumption 5 only says that f ′ x(0) is small enough and that f ′ x(0) is non zero. Throughout this subsection, we suppose that Assumptions 1-5 hold. The constants r, M, C and ξ < 1 that appear in the subsequent analysis are always the constants from Assumptions 1-5. Our aim is to show that the sequence x(k) k≥0 defined by (2.37) converges geometrically to a point x * in the sense that x(k)x * ≤ ξ k 1ξ

x (1)x (0) . given by

Convergence

x(k+1) = d(k) + ( x(k) -d(k) ) s(k) (2.37)
is completely contained in the interval B r , and converges to the unique zero of f ′ in B r .

Before we embark on the proof of Theorem 2.3.5, we first prove some technical lemmas.

Lemma 2.3.6 Let Assumption 2 and 3 be satisfied and let the sequence x(k) k≥0 be as defined in Theorem 2.3.5. Then, for any positive integer k the following inequality holds.

x(k) -x(k-1) ≤ M f ′ ( x(k-1) ) .
(2.38)

Proof 2 Let us fix a positive integer k. Using (2.37) we may write

x(k) -x(k-1) = d(k-1) + ( x(k-1) -d(k-1) ) s(k-1) -x(k-1) = ( x(k-1) -d(k-1) ) s(k-1) -1 (2.39)
Now, from (2.20) we have

s(k-1) > 1, (k > 1), (2.40)
we then immediately deduce

s(k-1) < s(k-1) .
Therefore, by (2.39), we arrive at

x(k) -x(k-1) ≤ x(k-1) -d(k-1) s(k-1) -1 , (2.41)
this, after some manipulations, leads

x(k) -x(k-1) ≤ x(k-1) -d(k-1) f ′ (x (k-1) ) c(k-1) 2 x(k-1) -d(k-1) -f ′ ( x(k-1) )
.

Finally, by Assumptions 2 and 3 we get the required inequality in (2.38).

In order to prove that the sequence x(k)

k≥0
converges geometrically, we need some further preparatory results.

Lemma 2.3.7 Let Assumption 4 be satisfied and let the sequence x(k) k≥0 be defined as in Theorem 2.3.5. Then, for any positive k the following inequality holds.

f ′ ( x(k) ) ≤ ξ M x(k) -x(k-1) . (2.

42) MOVING ASYMPTOTES

Proof 3 Fix a positive integer k. Let us define t(k-1) by

t(k-1) := c(k-1) 2 ( x(k-1) -d(k-1) ) -f ′ x(k-1) , (2.43)
and the auxiliary function ϕ : B → R as follows:

ϕ(x) := f ′ (x) - f ′ ( x(k-1) ) 1 2 c (k-1) ( x(k) -x(k-1) ) h(x), where h(x) := -f ′ x(k-1) - c(k-1) 2 x -x(k) + x(k-1) -d(k-1) -t(k-1) .
Using (2.43), it is easily checked that ϕ satisfies

ϕ( x(k-1) ) = 0, ϕ( x(k) ) = f ′ ( x(k) ).
Then, from the mean-value theorem and Assumption 4 we get

f ′ x(k) ≤ sup x∈B r f ′′ (x) - f ′ x(k-1) x(k-1) -x(k) x(k) -x(k-1) ≤ ξ M x(k) -x(k-1) . (2.44)
This shows that the required inequality (2.42) holds true for any positive integer k.

The next result shows that for all k the iterate x(k) remains in the interval B r .

Lemma 2.3.8 Let Assumption 2-4 be satisfied and let the sequence x(k) k≥0 be as defined in Theorem 2.3.5. Assume that the starting point x0 belongs to the interval B r , where r is defined in Assumption 1. Then, all terms of the sequence x(k) k≥0 lie inside the interval B r .

Proof 4 Indeed, combining inequalities (2.38) and (2.42) of Lemmas 2.3.6 and 2.3.7 respectively, we immediately obtain

x(k) -x(k-1) ≤ ξ x(k-1) -x(k-2) ≤ . . . ≤ ξ k-1 x(1) -x(0) , (2.45)
and therefore we have

x(k) -x(0) ≤ k ∑ l=1 x(l) -x(l-1) ≤ k ∑ l=1 ξ l-1 x(1) -x(0) ≤ x(1) -x(0) 1 -ξ . (2.46)
Finally, applying inequality (2.38) for k = 1 and using Assumption 5 we immediately get

x(k) -x(0) ≤ M 1 -ξ f ′ x(0) ≤ r, (2.47)
which shows that each x(k) belongs to B r .

As a consequence of the previous three lemmas, we are now in a position to prove Theorem 2.3.5.

Proof of Theorem 2.3.5 Since the entire sequence x(k) k≥0 remains in the (closed) interval B r by Lemma 2.3.8, every limit point of this sequence belongs to this set, too. Hence, it remains to show that the sequence x(k) k≥0 converges. To this end, we first note that, for k ≥ 0 and l ≥ 0, we have

x(k+l) -x(k) ≤ l-1 ∑ v=0 x(k+v+1) -x(k+v) ≤ ξ k l-1 ∑ v=0 ξ v x(1) -x(0) ≤ ξ k 1 -ξ x(1) -x(0) , (2.48)
then the sequence x(k) k≥0 is a Cauchy sequence. Being Cauchy in B r (closed interval in R), it has a limit, x * , in B r . Now, thanks to the continuity of f ′ on B r , (2.42) the continuity of f ′ on B and the convergence the sequence x(k)

k≥0 imply f ′ ( x * ) = lim k→+∞ f ′ x(k) ≤ ξ M lim k→+∞ x(k) -x(k-1) = 0, (2.49)
and then f ′ ( x * ) = 0. Passing to the limit for l tending to ∞ in (2.48), we deduce that

x(k) -x * ≤ ξ k 1 -ξ x(1) -x(0) , (2.50)
which shows the geometric convergence of the sequence x(k) k≥0 to x * .

We are now in a position to prove that f ′ has a unique zero in B r . To this end, we proceed by contradiction, assuming that f ′ has another zero ỹ * ∈ B. Let us introduce the auxiliary function

λ (x) = x(1) -x(0) f ′ ( x(0) ) f ′ (x) - f ′ ( x(0) ) x(0) -x(1) (x -x * ) , MOVING ASYMPTOTES
which satisfies λ ( x * ) = 0 and λ ( ỹ * ) = ỹ *x * . Therefore, applying (2.38) for k = 1, it follows from the mean value theorem and Lemma 2.3.6, inequality (2.38)

for k = 1, | x * -ỹ * | ≤ x(1) -x(0) f ′ ( x0 ) sup x∈B f ′′ (x) - f ′ ( x0 ) x0 -x(1) | x * -ỹ * | ≤ M ξ M | x * -ỹ * | ≤ ξ | x * -ỹ * | .
(2.51)

This yields x * = ỹ * since ξ < 1. Thus, the theorem is proved.

Description of algorithm

The results of the previous section may be used to construct the following algorithm.

Algorithm 1 Modified Method of Moving Asymptotes

1: Data: x(0) , w, αn > 1, ε 2: k = 0 3: REPEAT 4: c(k) = f ′′ ( x(k) ) + w( x(k) ) f ′ ( x(k) ) , 5: d(k) = x(k) + 2 α(k) f ′ ( x(k) ) c(k) , 6: s(k) = x(k) -d(k) 3 x(k) -d(k) - 2| f ′ ( x(k) )| c(k) , 7: x(k+1) = d(k) + sign( x(k) -d(k) ) s(k) , 8: while f ′ ( x(k) ) > ε.

Numerical examples

We employ the present method (designated as present) to solve some nonlinear, non-convex optimization problems and compare it with the [3] method, Newton's method and the BFGS method using two kinds of weight functions and four test functions:

f 1 (x) = 1 3 (sin 3 x -x 3 ) + x, f 2 (x) = 1 2 exp(x 2 ) + 1 2 (x - 1 2 sin(2x)) + 3 sin x + 5x, f 3 (x) = -( 1 3 x 3 + 5 2 x 2 + 3x -exp(x)), f 4 (x) = (x -1) 4 4 -2x + 1.
Numerical results are summarized in Tables 2.1 and 2.2, where for each weight function w, we present the objective functions, the starting points, the methods used, the number of iterations N to obtain the objective value of the obtained optimal solution x (N) and f (x) at x (N) . We use the following stopping criteria for computer programs: f ′ ( x(N) ) < ε, (the absolute value of the derivative of the function is less than or equal to the tolerance). For numerical illustrations we used different values of ε. Therefore, when the stopping criterion is satisfied, x * = x(N) is taken as the optimal solution. In Tables 2.1 and 2.2 div. means that the stopping criteria is not satisfied. Let k be the iteration index, then we choose the moving asymptotes as follows:

The test results in Tables 2.1 and 2.2 show that for all of the functions we tested, the present method is better than the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method and the BFGS Method. It always converges even if the starting point is very far from the true solution, and it never requires more iterations than the other three methods. In addition, as we can see, it may converge when these latter div.erge simultaneously. These characteristics give a strong advantage over these other methods. Chapter 3

Function Method N x N f (x N ) ≃ min f (x) ε f 1 (x) . . . . x(0) = 10 -
(x) = (1 + |x|) 1/2 exp(-2 |x|). Function f (x 0 ) Method N x N f (x N ) ≃ min f (x) f 1 (x) . . . . . x(0) = -62 *

A GLOBALLY CONVERGENT MULTIVARIATE VERSION OF THE METHOD OF MOVING ASYMPTOTES 3.1 Motivation and theoretical justification

We consider some new iterative methods for solving the unconstrained optimization problem: Find

x * ∈ Ω such that f (x * ) = min x∈Ω f (x) , (3.1)
where Ω is an open subset of R n and f : R n → R is a given non-linear real-valued objective function, typically twice continuously differentiable, which could be non-convex. In order to evaluate the merit of using second order information an extension of the method of moving asymptotes, that accounts for the curvatures, was proposed in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]. Let us put these things a bit more precisely. Throughout, we assume that ∇ f does not vanish at a given suitable initial point

x (0) ∈ Ω, that is ∇ f (x (0) ) ̸ = 0 R n , since
if this is not the case we have nothing to solve. Starting from the initial design point x (0) the iterates x (k) are computed successively by solving sub-problems of the form: Find x (k+1) such that

f (k) (x (k+1) ) = min x∈Ω f (k) (x), (3.2)
where the approximating function f (k) of the objective function f at the k-th iteration has the following form:

f (k) (x) = n ∑ j=1 α (k) - x j -L (k) j + α (k) + U (k) j -x j (3.3) + β (k) -, x -L (k) + β (k) + ,U (k) -x + γ (k) ,
The coefficients β

(k) -, β (k)
+ , L (k) and U (k) are some chosen parameters given by

β (k) - = (β (k) -) 1 , (β (k) -) 2 , . . . , (β (k) -) n , β (k) + = (β (k) + ) 1 , (β (k) + ) 2 , . . . , (β (k) + ) n , L (k) = L (k) 1 , L (k) 2 , . . . , L (k) n , U (k) = U (k) 1 ,U (k) 2 , . . . ,U (k) n
, and γ (k) ∈ R. They represent the unknown parameters that need to be computed based on the available information. In contrast with the classical Newton method, here the approximation functions f (k) are of the form of a linear function plus a rational function. For each iteration, the approximate parameters α

(k) -, α (k) + , β (k) -, β (k)
+ and γ (k) used in equation (3.3) are determined in such a way that the following set of interpolation conditions are satisfied:

f (k) (x (k) ) = f (x (k) ), (3.4)
f (k) , j (x (k) ) = f , j (x (k) ), j = 1, . . . , n. (3.5) f (k) ,, j j (x (k) ) = f ,, j j (x (k) ), (3.6)
In order to ensure that the functions f (k) have suitable proprieties discussed in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF], the author have assumed that the following conditions are satisfied for all k:

α (k) - j = β (k) - j = 0 i f f , j (x (k) ) > 0, α (k) + j = β (k) + j = 0 i f f , j (x (k) ) < 0, j = 1, . . . , n. (3.7)
It follows from the above identities that α

(k) -, α (k) + , β (k) -, β (k)
+ and γ (k) are given by

α (k) - j =    1 2 S (k) j j x (k) j -L (k) j 3 i f f , j x (k) < 0 0 otherwise (3.8)
3.1 Motivation and theoretical justification 45

α (k) + j =    1 2 S (k) j j U (k) j -x (k) j 3 i f f , j x (k) > 0 0 otherwise (3.9) β (k) - j =          f , j x (k) + α (k) - j x (k) j -L (k) j 2 i f f , j x (k) < 0 0 otherwise (3.10) β (k) + j =          f , j x (k) - α (k) + j U (k) j -x (k) j 2 i f f , j x (k) > 0 0 otherwise, (3.11)
and hence γ (k) is given by

γ (k) = f x (k) - n ∑ j=1    α (k) - j x (k) j -L (k) j + α (k) + j U (k) j -x (k) j    -β (k) -, x (k) -L (k) -β (k) + ,U (k) -x (k) . (3.12)
In (3.8) and (3.9), the coefficients S (k) j j were simply chosen such that S (k)

j j := e (k) x (k) -x (k-1) 2 ≈ f ,, j j x (k) , (3.13)
where

e (k) := ⟨∇ f (x (k) ) -∇ f (x (k-1) ), x (k) -x (k-1) ⟩. (3.14)
The authors have also assumed in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] that the objective function should fulfill for each iteration k the following conditions: f ,, j j (x (k) ) > 0, j = 1, . . . , n.

This is a real weakness of this approach, which drastically limits its application. Hence, this method is very restrictive and also has the following disadvantages :

• It needs good initial solution x * close to the exact solution.

• It converges slowly, in many cases, to the optimum x * .

• It does not always converge.

• Its performance degrades when it applied to non convex functions.

• Incapable of handling non-separability.

The purpose of this chapter is three-fold. First, we develop an extension of our previous paper [START_REF] Guessab | A globally convergent modified version of the method of moving asymptotes[END_REF] in a multivariate setting. Second, we propose a modified version of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method by removing the restrictive condition (3.15) on the objective functions. We will concentrate on the method of moving asymptotes since it is considered to belong to the most efficient methods. We believe that similar ideas can be developed for the other members of of several methods for solving minimization problems. Third, we show how the proposed algorithm can be modified in order that the technique can be applied to a fairly large class of objective functions. Moreover, it is shown, as will be proved below, that the new method converges geometrically. Comparative numerical simulations are conducted to show the success of the proposed extension for various kinds of different test functions. The results suggest that this latter is significantly faster compared to the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method or the BFGS method on all test functions and it can succeed where these latter diverge simultaneously. It also has the advantage that, under appropriate conditions, global convergence of the algorithm is guaranteed.

The remainder of this chapter is organized as follows. In Section 3.2, we develop a modified moving asymptotes method. Section 3.3 contains all technical results that are essential to show that our method is guaranteed to converge geometrically. In Section 3.4, we will concentrate on how our algorithm can be extended to the general setting where the objective function is nonconvex and non-separable. The point is not to give a definite answer to this problem but, rather, to clarify and understand how our algorithm can be used for this general situation. The test problems are Wood's, Powell's and Branin's functions. They are all documented in [START_REF] Laboratory | DRVOCR: A FORTRAN Implementation of Davidon's Optimally Conditioned Method[END_REF]. In section 3.5, various numerical experiments conduct to confirm our theoretical finding. In addition, the comparison with the models considered is also made and we conclude in Section 3.6.

A special modified multivariate version of moving asymptotes method

Throughout this section we assume that w is a function satisfying the following conditions:

w is a real-valued function, defined and continuous on R n , (

)

lim |x|→+∞ w(x) = 0. ( 3.17)
The general modification of moving asymptotes method that we examine herein may be described as follows: Given the iteration point x(k) (at iteration k).

• Our approach is to iteratively approximate at the k-th iteration the objective function by the approximating function f (k) w where:

f (x) ≈ f (k) w (x) = n ∑ j=1 c(k) j x j - d(k) j + b(k) , x - d(k) + ã(k) (3.18)
and the coefficients b(k) , c(k) , d(k) are some chosen parameters given by b

(k) = b(k) 1 , . . . , b(k) n , c(k) = c(k) 1 , . . . , c(k) n , d(k) = d(k) 1 , . . . , d (k)
( f (k) w ) , j (x) = b(k) j - c(k) j (x j - d(k) j ) 2 , j = 1, . . . , n, (3.19)
( f (k) w ) ,, j j (x) = 2 c(k) j (x j - d(k) j ) 3 , j = 1, . . . , n, (3.20)
and since the function f (k) w is separable, therefore if i ̸ = j, we have:

( f (k) w ) ,,i j = 0, i, j = 1, . . . , n. (3.21)
• The approximating function f (k) w is first order approximations of the original function f at the current iteration point x(k) , i.e.,

f (k) w (x (k) ) = f (x (k) ), (3.22)
( f (k) w ) , j (x (k) ) = f , j (x (k) ), j = 1, . . . , n. (3.23)
In addition to the above conditions (3.22) and (3.23), the approximating function should satisfy the following more general condition (3.24) instead of (3.6):

( f (k) w ) ,, j j (x (k) ) = f ,, j j (x (k) ) + w(x (k) ) f , j (x (k) ) . (3.24)
Consequently, in the present situation, the approximate parameters ã(k) , b(k) and c(k) can be expressed in the following forms:

ã(k) = f (x (k) ) - n ∑ j=1 x(k) j c(k) j - d(k) j - b(k) , x(k) - d(k) , (3.25) b(k)
j = f , j (x (k) ) + c(k) j ( x(k) j - d(k) j ) 2 , (3.26) c(k) j = f ,, j j (x (k) ) + w(x (k) ) f , j (x (k) ) 2 x(k) j - d(k) j 3 . (3.27)
Furthermore, in order to fully determine an explicit expression for the approximating function

f (k) w , the parameter d(k) is chosen such that d(k) j = x(k) j + 2 α(k) j f , j (x (k) ) f ,, j j (x (k) ) + w(x (k) ) f , j (x (k) ) , (3.28)
for simplicity, we put

γ (k) j = f ,, j j (x (k) ) + w(x (k) ) f , j (x (k) ) > 0. (3.29) So we can rewrite d(k) j = x(k) j + 2 α(k) j f , j (x (k) ) γ (k) j , (3.30)
where

{ α(k) } k := ( α(k) 1 , . . . , α(k) n ) k is a sequence of R n with α(k) j > 1, k ∈ N and j = 1, . . . , n. (3.31)
Different rules for how to choose these values (and possible weight functions in (3.24)) will be provided later. We note that our method does not use the interpolation condition (3.6), but instead we have incorporated a first-and second-order information, as given in (3.27). Moreover, in particular, if you take w = 0 and at each iteration condition (3.15) is fulfilled, then our iterative scheme obviously reduces to the one introduced in [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]. Hence, subsequent iterations of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method are essentially the same as the approximating function (3.18), except that in the proposed approximating function f (k) w the parameters c (k) and d (k) are replaced by those given in (3.27) and (3.30) respectively. Thus our scheme starts with some guess point x(0) and generates successive iterates by

f (x (k+1) ) ← f (k) w (x (k+1) ) = min x∈Ω f (k) w (x) . (3.32)
For the sake of notation simplicity, we have removed the index w in the iterative sequence x(k) w .

One of the key ingredient of the proposed approach is to work with (3.27) instead of (3.6). This modification will play an important role in the analysis of the proposed modified algorithm. Indeed, there are several good reasons for this choice. First, as mentioned above, the main reason is that this allows us to apply our method to a large class of objective functions. Second, there are also important advantages from the numerical point of view: many experimental results will confirm that the iterative scheme based on our modification version (3.27) can yield significantly fewer iterations than the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method or the BFGS method. Furthermore, in contrast to these three approaches, our method converges even if the starting point is very far from the true solution. In addition, as we will see, the key features of the present method are:

• It does not require us to build a good initial solution close to the exact solution.

• It converges geometrically for a large class of functions w that satisfy conditions (3.16) and (3.17).

• It will succeed where the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method and the BFGS Method break down.

Newton's method and the BFGS Method have a well-studied convergence theory that guarantees the convergence to a solution under a standard set of assumptions. For these and other their variants, the interested reader should consult one of the many excellent books on this subject [15, pp. 48-75] and [34, pp. 75-89]. We refer the readers to [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] and the references therein for the method of moving asymptotes.

Convergence Analysis

We start this section with a result concerning an explicit expression for the iterative sequence x(k) k generated by the approximating function f (k) w , as given in (3.18). Here, we continue to denote by c(k) , d(k) and α(k)

the coefficients given by (3.27), (3.30) and (3.31) respectively. Note that condition (3.31), imposed on the parameters α(k) , is crucial since it will guarantee strict convexity of the approximating function f (k) w . For brevity, in the following we use the notation:

I (k) = I (k) 1 × . . . × I (k) n , (3.33)
with

I (k) i = -∞, d(k) i ∪ d(k) i , +∞ , i = 1, . . . , n. (3.34)
Now we are in position to state the first main result. Then, for each k > 0 the approximating function f (k) w defined by (3.18) is a strictly convex function on I (k) . In addition, it has an unique minimum at

x(k+1) ← x(k) * = d(k) + G (k) (3.35)
where

G (k) = G (k) 1 , . . . , G (k) n with G (k) j = ( x(k) j - d(k) j ) s(k) j (3.36) s(k) j = α(k) j α(k) j -1 . (3.37) Proof 5
The main ingredient here is a suitable application of the condition (3.31) imposed on the coefficient d(k) . We first start by showing that the approximating function f (k) w is well defined and strictly convex in I (k) . To this end we prove that ∇ 2 f (k)

w is positive semidefinite in I (k) . Indeed, a simple calculation reveals that

∇ 2 f (k) w (x) =                γ (k) 1 x(k) 1 - d(k) 1 x 1 - d(k) 1 3 0 • • • 0 0 γ (k) 2 x(k) 2 - d(k) 2 x 2 - d(k) 2 3 . . . . . . . . . . . . . . . 0 0 • • • 0 γ (k) n x(k) n - d(k) n x n - d(k) n 3                (3.38)
In view of (3.38), it remains to show that the Hessian matrix on the right-hand side of (3.38) is positive semidefinite for all x ∈ I (k) . Since γ (k) is nonnegative (as can be seen in (3.29)), and the two terms

x(k) j - d (k)
I (k) , x T ∇ 2 f (k) w (x)x ≥ 0 then f (k)
w is a convex function on I (k) . Furthermore, the function f (k) w being well definite and continuous in I (k) , this implies the existence of a minimum, which by convexity is the unique critical point

x(k) * . Now, looking for ∇ f (k) w (x) = 0 R n we conclude that the optimum x(k) * is one solution of the system                         f ,1 x(k) + 1 2 γ (k) 1 x(k) 1 - d(k) 1   1 - x(k) 1 - d(k) 1 2 x 1 - d(k) 1 2    . . . f , j x(k) + 1 2 γ (k) j x(k) j - d(k) j   1 - x(k) j - d(k) j 2 x j - d(k) j 2    . . . f ,n x(k) + 1 2 γ (k) n x(k) n - d(k) n   1 - x(k) n - d(k) n 2 x n - d(k) n 2                            =          0 . . . 0 . . . 0          , (3.39)
or, equivalently,

f , j x(k) + 1 2 γ (k) j x(k) j - d(k) j   1 - x(k) j - d(k) j 2 x j - d(k) j 2    = 0, j = 1, . . . , n, (3.40)
which, after trivial calculations, implies

  x(k) j - d(k) j x j - d(k) j   2 = 1 + 2 f , j x(k) γ (k) j x(k) j - d(k) j .
(3.41)

Now using (3.30), we can write 2 f , j x(k)

γ (k) j x(k) j - d(k) j = - 1 α(k) j . (3.42)
Therefore, after some simplification, equation

(3.41) becomes   x(k) j - d(k) j x j - d(k) j   2 = 1 - 1 α(k) j . (3.43)
By condition (3.31) imposed on the parameter α (k) , it can be deduced from (3.43) that the solvability of our subproblem can always be guaranteed. Indeed, under this condition, the required identity (3.35) immediately follows from (3.43) and the above mentioned fact that xk j -d(k) j and x j -d(k) j have the same sign in the interval I (k) j . This completes the proof of the theorem.

Convergence study

In this Section, we give our second main result of this chapter, that is sufficient conditions on the data (the point x(0) , the gradient ∇ f in a neighborhood of x(0) , the family diag(H f x(k) ), k ≥ 0), which guarantee that first derivative of f vanishes in a neighborhood of x * , first, and secondly, the convergence of the method to this zero.

To establish our convergence results, we need the following assumptions. We assume that there exist positive constants r, M and ξ < 1 such that the following assumptions hold: Here where ∥.∥ is the standard Euclidean norm on R n .

Assumption 6 B r := x ∈ R n : x -x(0) ≤ r ⊂ Ω. Assumption 7 0 < α(k) j α(k) j -1 ≤ M 2 γ k j , (k > 0), j = 1, . . . , n.
Assumption 8

sup k>0 sup x∈B ∇ f , j (x) - f , j (x (k-1) ) x (k-1) j -x (k) j e ( j) ≤ ξ M ,
where e ( j) is the vector of R n with j-th component equal to 1 and all other components equal to 0.

Assumption 9 0 < f , j x(0) ≤ r M √ n (1 -ξ ) .
Assumption 7 enforces the quite natural conditions (3.31). Indeed, if condition 7 holds, then (3.31) is also satisfied. Furthermore, Assumption 8 tells us that the coefficient ∇ f , j (x (k) ) does not change too much in a neighborhood of x(0) , and finally for any k the functions ∇ f , j (x (k) ) and

f , j x (k-1)
x (k-1)x(k) have not to change too much in a neighborhood of x(k) . Assumption 9 only says that f , j

x(0) is small enough and that f , j x(0) is non zero.

Throughout this subsection, we assume that Assumptions 6-9 hold. The constants r, M and ξ < 1 that appear in the subsequent analysis are always the constants from Assumptions 6-9. Our aim is to show that the sequence x(k) k≥0 defined in Theorem 3.3.1 converges geometrically to a point x * in the sense that

x(k) -x * ≤ ξ k 1 -ξ x (1) -x (0) .
Theorem 3.3.2 Assume Assumptions 6-9 hold. Let the assumptions of theorem 4.4.3 be valid and let G (k) be defined by (3.36). Then the sequence x(k)

k≥0
given by

x(k+1) = d(k) + G (k) (3.44)
is completely contained in the ball B r , and converges to the unique zero of ∇ f in B r .

We first state some auxiliary lemmas, which will be needed in our investigation. Then, for any positive integer k the following inequality holds.

x(k) -x(k-1) ≤ M ∇ f (x (k-1) ) . ( 3
x(k) j - x(k-1) j = d(k-1) j + ( x(k-1) j - d(k-1) j ) s(k-1) j - x(k-1) j = ( x(k-1) j - d(k-1) j ) s(k-1) j -1 (3.46)
Now, from (3.31) we have s(k-1)

j > 1, j = 1, . . . , n, (k ≥ 1), (3.47)
we then immediately deduce

s(k-1) j < s(k-1) j .
Therefore, by (3.30), (3.37) and (3.46), we arrive at

x(k) j - x(k-1) j ≤ x(k-1) j - d(k-1) j s(k-1) j -1 , (3.48)
≤ 2 α(k-1) j ( α(k-1) j -1)γ (k-1) j f , j (x (k-1) ) . (3.49)
Finally, combing Assumption 7 and this last inequality, we get the required inequality (3.45).

In order to prove that the sequence x(k)

k≥0
converges geometrically, we need some further preparatory results.

Lemma 3.3.4 Let Assumption 8 be satisfied and let the sequence x(k) k≥0 be defined as in Theorem 3.3.2.

Then, for any positive k the following inequality holds.

f , j (x (k) ) ≤ ξ M x(k) j - x(k-1) j , j = 1, . . . , n. (3.50)
Proof 7 Fix a positive integer k. Let us define t(k-1)

j by t(k-1) j := γ (k-1) j 2 ( x(k-1) j - d(k-1) j ) -f , j x(k-1) , (3.51)
and the auxiliary function ϕ : B → R as follows:

ϕ(x) := f , j (x) - f , j (x (k-1) ) 1 2 γ (k-1) j ( x(k) j - x(k-1) j ) h j (x),
where

h j (x) := -f , j x(k-1) + γ (k-1) j 2 x j - x(k) j + x(k-1) j - d(k-1) j - t(k-1) j .
Using (3.51), it is easily checked that ϕ satisfies

ϕ(x (k-1) ) = 0, ϕ(x (k) ) = f , j (x (k) ).

Convergence Analysis 53

Also it is easy to see that

∇ϕ(x) = ∇ f , j (x) - f , j (x (k-1) ) x(k-1) j - x(k) j e ( j) . (3.52)
Then, from the mean-value theorem and Assumption 8 we get

f , j x(k) = ϕ(x (k) ) -ϕ(x (k-1) ) ≤ sup x∈B r ||∇ϕ(x)|| x(k) -x(k-1) ≤ sup x∈B r ∇ f , j (x) - f , j (x (k-1) )
x(k-1)

j - x(k) j e ( j) x(k) -x(k-1) ≤ ξ M x(k) -x(k-1) . (3.53)
This shows that the required inequality (3.50) holds true for any positive integer k.

The next result shows that for all k the iterate x(k) remains in the interval B r .

x(k) -x(k-1) ≤ ξ x(k-1) -x(k-2) ≤ . . . ≤ ξ k-1 x(1) -x(0) , (3.54)
and therefore we have

x(k) -x(0) ≤ k ∑ l=1 x(l) -x(l-1) ≤ k ∑ l=1 ξ l-1 x(1) -x(0) ≤ x(1) -x(0) 1 -ξ . (3.55)
Finally, applying inequality (4.4a) for k = 1 and using Assumption 9 we immediately get

x(k) -x(0) ≤ r, (3.56)
which shows that each x(k) belongs to B r .

As a consequence of the previous three lemmas, we are now in a position to prove Theorem 3.3.2.

Proof of Theorem 3.3.2. Since the entire sequence x(k) k≥0 remains in the (closed) ball B r by Lemma 3.3.5, every limit point of this sequence belongs to this set, too. Hence, it remains to show that the sequence x(k) k≥0 converges. To this end, we first note that, for k ≥ 0 and l ≥ 0, we have

x(k+l) -x(k) = l-1 ∑ v=0 (x (k+v+1) -x(k+v) ) ≤ l-1 ∑ v=0 x(k+v+1) -x(k+v) ≤ ξ k l-1 ∑ v=0 ξ v x(1) -x(0) ≤ ξ k 1 -ξ x(1) -x(0) , (3.57)
then the sequence x(k) k≥0 is a Cauchy sequence. Being Cauchy in B r , it has a limit, x * , in B r . Now, thanks to the continuity of f , j on B r and the convergence of the sequence x(k)

k≥0 imply f , j (x * ) = lim k→+∞ f , j x(k) ≤ ξ M lim k→+∞ x(k) j - x(k-1) j = 0, j = 1, . . . , n, (3.58)
and then ∇ f ( x * ) = 0. Passing to the limit for l tending to ∞ in (3.57), we deduce that

x(k) -x * ≤ ξ k 1 -ξ x(1) -x(0) , (3.59)
which shows the geometric convergence of the sequence x(k) k≥0 to x * .

We are now in a position to prove that ∇ f has an unique zero in B r . To this end, we proceed by contradiction, assuming that ∇ f has another zero ỹ * ∈ B r . Let us introduce the auxiliary function

λ j (x) = x(1) j - x(0) j f , j (x (0) j )   f , j (x) - f , j (x (0) j ) x(0) j - x(1) j x j -x * j   ,
which satisfies λ j (x * ) = 0 and λ j (ỹ * ) = ỹ * jx * j . Therefore, applying (3.45) for k = 1, it follows from the mean value theorem and Lemma 3.3.3, inequality (3.45)

for k = 1, x * j -ỹ * j = λ j (x * ) -λ j (ỹ * ) ≤ sup x∈B r ∇λ j (x) ||x * -ỹ * || ≤ x(1) j - x(0) j f , j x0 sup x∈B ∇ f , j (x) - f , j (x 0 ) x0 j - x(1) j e ( j) ||x * -ỹ * || ≤ M ξ M ||x * -ỹ * || = ξ ||x * -ỹ * || . (3.60)
This yields x * = ỹ * since ξ < 1. Thus, the theorem is proved.

Choice of the parameters α(k)

Here we give certain details, for the choice of the moving asymptotes d(k) , which are in general updated in each iteration. The introduction of the terms α(k) in the moving asymptote d(k) , as defined in (3.30) and (3.31)

Minimizing Non-convex Non-Separable Functions

55

respectively, is the basic difference between the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method and its variant presented here. These coefficients are essentially tuning parameters for global convergence for the present method, and of course their choices are a crucial point for the behaviour of the algorithms discussed in this chapter. To establish our convergence theorem, we have imposed that the parameter α(k) must satisfy Assumption 7. By this latter, after some manipulation, it can be deduced that

α(k) j ≥ 1 + 2 Mγ (k) j , j = 1, . . . , n, (3.61)
then we can choose the parameters α(k)

j ∈   1 + 2 Mγ (k) j
, +∞   , j = 1, . . . , n. Note that this choice obviously guarantees that α(k) > 1, which is one important assumption in Theorems 3.3.1 and 3.3.2 for the solvability of the subproblems. Although this is not an explicit choice, it was found to work well in practice by taking a suitable value for the parameter M.

Description of algorithm

The results of the previous section may be used to construct the following algorithm.

Algorithm 2 Modified Method of Moving Asymptotes 1: Input: x(0) ∈ R n , w, M 1 , M 2 ≥ 1, (and an optional error tolerance ε > 0). 2: k = 0 3: REPEAT 4: For j = 0, 1, . . . , n 5: γ

(k) j = f ,, j j (x (k) ) + w(x (k) ) f , j (x (k) ) , 6: α(k) j = M 1 1 + 2 M 2 γ (k) j , 7: d(k) j = x(k) j + 2 α(k) j f , j (x (k) ) γ (k) j , 8: s(k) j = α(k) j α(k) j -1 , 9:
x(k+1)

j = d(k) j + ( x(k) j - d(k) j ) s(k) j , 10: while ∇ f (x (k) ) > ε. 11: k ←-k + 1

Minimizing Non-convex Non-Separable Functions

The separability is a measure of difficulty of different objective functions. In general the separable functions are relatively easy to solve, when compared with their inseparable counterpart, because each variable of a separable function is independent of the other variables. If all the parameters or variables are independent, then a sequence of n independent optimization processes can be performed. As a result, each design variable or parameter can be optimized independently, and if the objective function f is separable, then, for x = (x 1 , x 2 , . . . ,

x n ) ∈ R n arg min x f (x) = arg min x 1 ,x 2 ,...,x n f (x 1 , x 2 , . . . , x n ) (3.62) = arg min x 1 ,x 2 ,...,x n n ∑ i=1 f i (x i ) (3.63) = n ∑ i=1 arg min x i f i (x i ) (3.64)
where

f (x) = n ∑ i=1 f i (x i ).
On the other hand, a function is called non separable, if its variables show inter-relation among themselves or are not independent. If the objective function variables are independent of each other, then the objective functions can be decomposed into sub-objective functions. Then, each of these sub-objectives involves only one decision variable, and Algorithm 2 solves the problem (3.1) for each variable independently of others, and then is like we minimize n functions of dimension 1. According to [START_REF] Jamil | A literature survey of benchmark functions for global optimisation problems[END_REF][START_REF] Salomon | Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. a survey of some theoretical and practical aspects of genetic algorithms[END_REF], the general condition of separability to see if the function is easy to optimize or not is given as

∂ f ∂ x i (x) = g(x i )h(x). (3.65)
The dimensionality is one of the difficulty for solving the problem (3.1), this difficulty increases with the problem's dimension. According to [START_REF] Whitley | Evaluating evolutionary algorithms[END_REF][START_REF] Winston | Artificial Intelligence[END_REF][START_REF] Chen | Extended admm and bcd for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights[END_REF][START_REF] Yao | Fast evolution strategies[END_REF] the search space increases exponentially with the number of parameters or dimension. For highly nonlinear problems, this dimensionality may be a significant barrier for almost all optimization algorithms. In this section, we extend Algorithm 2 for the non separable non convex optimization problem, which consists of a cyclic update of the variables x i , let's consider the problem (3.1), where here the objective function is non separable: we can formulate this problem as: At each iteration of this method, the function is minimized with respect to a single of variables while the rest of the variables are held fixed. More specifically, at iteration k of the algorithm, the variable x i is updated by solving the following subproblems

                               x (k+1) σ (1)
:= arg min

x σ (1) f (x σ (1) , x (k) σ (2) , . . . , x (k)
σ (i) , . . . , x (k) σ (n) ) x (k+1) σ (2) := arg min x σ (2) f (x (k) σ (1) , x σ (2) , . . . , x (k) σ (i) , . . . , x (k) σ (n) ) . . . x (k+1) σ (i) := arg min x σ (i) f (x (k+1) σ (1) , x (k+1) σ (2) , . . . , x (k+1) σ (i-1) , x σ (i) , . . . , x (k) σ (n) ) . . . x (k+1) σ (n) := arg min x σ (n) f (x (k+1) σ (1) , x (k+1) σ (2) , . . . , x (k+1) σ (i) , . . . , x (k+1) σ (n-1) , x σ (n) ), (3.66)
where σ is a uniformly random permutation of {1, . . . , n}. Let us use x (k) to denote the sequence of iterates generated by this algorithm, where

x (k) ≜ (x (k) σ (1) , x (k) σ (2) , . . . , x (k) σ (n) )
at iteration k, the selected variable (say variable i) is computed by solving the n following subproblems

arg min f σ (i) (x σ (i) ) s.t x σ (i) ∈ R (3.67)

Numerical examples

57

where

f σ (i) (x σ (i) ) := f (x (k+1) σ (1) , x (k+1) σ (2) , . . . , x (k+1)
σ (i-1) , x σ (i) , . . . , x (k) σ (n)
) is an approximation of the original objective function at the point x (k-1) . Algorithm 3 summarizes the process of solving a non convex optimization problem for a non separable objective function:

f i (x i ) s.t x i ∈ R i = 1, . . . , n 7: x (k+1) = arg min x 1 f 1 (x 1 ), . . . , arg min x n f n (x n ) 8:
Until some convergence criterion is met

Note that Algorithm 3 reduces to Algorithm 2 for the case where condition of separability (3.65) is valid, and then all of the variables are independent of each other.

Numerical examples

We employ the present method (designated as present) to solve some nonlinear, non-convex optimization problems and compare it with the [3] method, Newton's method and the BFGS method using two kinds of weight functions and four test functions:

f 1 (x) = -( 1 3 x 3 + 5 2 x 2 + 3x -exp(x)), f 2 (x, y) = 1 4 x 4 + (y -1) 4 + 4 3 x 3 -15 x + 2 15 y + 3, f 3 (x, y) = -exp(x) + exp(2y) + (x 3 + y 3 ) 3 -(x 2 + y 2 + 3(x + y) + 12) . f 4 (x, y, z) = 1 2 exp(x 2 ) + 2 exp(y) + 1 2 (z -3) 4 + 3 sin(x) - 1 6 sin(2x) - 1 3 y 3 + 5 2 y 2 + 3(y + z) -6
It is assumed that all methods use the finite difference method to compute first and second derivatives. Numerical results are summarized in Tables 3.1 -3.5, where for each weight function w, we present the objective functions, the starting points, the methods used, the number of iterations N to obtain the objective value of the obtained optimal solution x (N) and f (x) at x (N) . We use the following stopping criteria ∇ f ( x(N) ) ≤ ε, (the absolute value of the derivative of the function is less than or equal to the tolerance). For numerical illustrations we used different values of ε. Therefore, when the stopping criterion is satisfied, x * = x(N) is taken as the optimal solution. In Tables 3.1 -3.5 div. means that the stopping criteria is not satisfied. The test results in Tables 3.1 and 3.2 show that for all of the functions we tested, the present method is better than the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method and the BFGS Method. It always converges even if the starting point is very far from the true solution, and it never requires more iterations than the other three methods. Finally we must mention that in many other test cases in some examples the present method may converge when these latter diverge simultaneously. Many of them have been shown in this section. These characteristics give a strong advantage over these other methods. we consider the function:

f 1 : R -→ R x -→ -( 1 3 x 3 + 5 2 x 2 + 3x -exp(x)), Initial point Method N x N f (x N ) ≃ min f (x) ε x(0) = -2.
) = 2 1 + 1 4 c(k) . Initial point f (x 0 ) Method N x N f (x N ) ≃ min f (x) ε x(0) = -
Initial point Method N x N f (x N ) ≃ min f (x) ε x(0) = (1,
) = 2 1 + 1 4γ (k) 1 , 4 1 + 1 3γ (k) 2
.

f 3 : R × R -→ R (x, y) -→ -exp(x) + exp(2y) + (x 3 + y 3 ) 3 -(x 2 + y 2 + 3(x + y) + 12) , Initial point Method N X N = (x N , y N ) f (X N ) ≃ min f (x) ε x(0) = (
) = 2 1 + 1 5γ (k) 1 , 3 1 + 1 10γ (k) 2
. . . Table 3.5 Numerical comparisons of the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method in three dimension.

f 4 : R 3 -→ R (x, y, z) -→ 1 2 exp(x 2 ) + 2 exp(y) + 1 2 (z -3) 4 + 3 sin(x) - 1 6 sin(2x) - 1 3 y 3 + 5 2 y 2 + 3(y + z) -6 Initial point Method N X N = (x N , y N , z N ) f (X N ) ≃ min f (x) ε x(0) = (
Here w(x) = (1 + |x|) 1/4 exp(-20 |x|) and α(k

) = 5 1 + 1 7γ (k) 1 , 2 1 + 1 4γ (k) 2 , 4 1 + 1 3γ (k) 3
.

The process described in section 3.4 has been implemented in Matlab. The algorithm was terminated when the norm of the gradient of f ∇ f (x (k) ) was less than a specified tolerance ε. For all of test functions, the tolerance ε was taken to be very close to 0, in order to find the most exact solution. For Wood's and Powell's functions, the ε was set 10 -25 and for Branin's function ε = 10 -20 . For all the test functions in the table 3.6, the results include the number of variable of the objective function, respectively the number of iterations and evaluations functions N iter and N eval required to achieve convergence and the final function value, and the CPU time (s) of the program for each test problem.

Functions

Number

Conclusion

The proposed modified method of moving asymptotes has been computationally shown that it needs only a small number of iterations to converge to the exact solution up to the specified error tolerance. The algorithm is easy to use since all tuning parameters are automatically chosen. Furthermore, test examples on nonconvex and non-separable functions confirm that the algorithm is expected to be more efficient than the [START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method and the BFGS method. It also has the advantage that, under appropriate conditions, global convergence of the algorithm is guaranteed.

Chapter 4

NEW APPROACH OF MOVING ASYMPTOTES METHOD USING A SPECTRAL PARAMETERS FOR BOUND CONSTRAINED OPTIMIZATION 4.1 Introduction

In this chapter we present a new extension of the method of moving asymptotes for solving nonlinear non convex optimization problems, that use information from the current and previous iteration and an asymptotes serves to accelerate and stabilize the process convergence in the neighbourhood of the exact solution of the initial problem. We consider the bound constrained optimization problem

min f (x) s.t. x ∈ Ω = {x ∈ R n |l ≤ x ≤ u} (4.1)
where l = l 1 , l 2 , . . . , l n T , u = u 1 , u 2 , . . . , u n T with -∞ ≤ l i < u i ≤ +∞ for i = 1, 2, . . . , n. We denote by g(x) = g 1 (x), g 2 (x), . . . , g n (x) T the gradient of f at x.

We say that a vector x ∈ Ω is a stationary point of problem 4.1 if it satisfies

     x i = l i ⇒ g i > 0 l i < x i < u i ⇒ g i = 0 x i = u i ⇒ g i < 0 (4.2)
Problem (4.1) is very important in practical optimization, and many practical problems can be converted into (4.1). In addition, problem (4.1) is often a subproblem of augmented Lagrangian or penalty schemes for general constrained optimization. Hence it has received much attention in recent decades, and many numerical algorithms have been developed. A popular one among these methods is the method of moving asymptotes which was originally proposed in [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF] and extended in [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF][START_REF] Svanberg | A globally convergent version of mma without linesearch[END_REF][START_REF] Svanberg | The method of moving asymptotes-modelling aspects and solution schemes[END_REF][START_REF] Svanberg | Mma and gcmma, versions september[END_REF]. the advantage of this method is that it is quite easy to implement, very effective for large scale problems and converge to the exact solution from any start point. and a second important advantage is keeping the feasibility of the iterate and thanks to the separability of the approximations the process of its algorithm is not expensive.

Moreover, our method is considered more fast than the optimal gradient method for unconstrained optimization.

To speed up the convergence of the classical method of moving asymptotes we propose in this paper an explicit scheme for solving the kind of problems (4.1) which can be seen as an extension of the method of moving asymptotes proposed by Svanberg [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] for unconstrained optimization.

The method of moving asymptotes was originally proposed in [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF] for convex objective functions and further analyzed in [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF][START_REF] Svanberg | A globally convergent version of mma without linesearch[END_REF][START_REF] Svanberg | The method of moving asymptotes-modelling aspects and solution schemes[END_REF][START_REF] Svanberg | Mma and gcmma, versions september[END_REF] for the choice of the method's parameters and a modified approximations to achieve a good results.

Recently, by replacing the second order information in the expression of the asymptotes by a spectral parameters in [START_REF] Gomes-Ruggiero | Globally convergent modifications to the method of moving asymptotes and the solution of the subproblems using trust regions: theoretical and numerical results[END_REF][START_REF] Gomes-Ruggiero | A spectral updating for the method of moving asymptotes[END_REF] defined a new iterate scheme and proposed a new update of these asymptotes for constrained optimization. The new method is finitely convergent for the convex functions and globally convergent for the general functions based on the updating of the asymptotes with respect to a spectral parameters approximate the second derivative.

The numerical results show that the new approach of the moving asymptotes method works better than the classical method proposed in [START_REF] Birgin | Large-scale active-set box-constrained optimization method with spectral projected gradients[END_REF][START_REF] Birgin | Nonmonotone spectral projected gradient methods on convex sets[END_REF] and more easy to implemented thanks to the clarity of the instructions of the algorithm generated by this approach. In this paper, we aim to extend the Method of moving asymptotes to be independent with keeping the main properties of this method, the separability, the order of approximations and the accuracy of the solutions found by the generated algorithm.

The chapter is organized as follows. In section 2, we introduce the univariate approximations. In section 3 we present the method in the multidimensional case and establish the explicit scheme of these approximations.

In section 4 we propose the choice of the parameters of our news approximation functions, these choice give a good convergence to the original solution and control the convergence of the process and a numerical results are given in Section 5.

Univariate objective function 4.2.1 Position of the problem and approximations

We start by studying the one-dimensional nonlinear programming problem

minimize f (x) subject to l ≤ x ≤ u, (4.3)
where x ∈ IR is a variable, l and u are given real numbers such that l < u, f are real-valued typically twice continuously differentiable function of x, Since the simplicity of the one-dimensional case allows to detail all the necessary steps with very simple computations, let us first consider the general optimization problem (4.3) of a single real variable. To this end, we first list the necessary notation and terminology. Let n := 1 and Ω ⊂ IR be an open subset and f : Ω → IR be a given twice differentiable function in Ω. Throughout, we assume that f ′ does not vanish at a given suitable initial point x (0) ∈ Ω, that is f ′ (x (0) ) ̸ = 0, since if this is not the case we have nothing to solve. Starting from the initial design point x (0) the iterates x (k) are computed successively by solving sub-problems of the form: Find x (k+1) such that

f (x (k+1) ) = min x∈Ω f (k) (x), (4.4)
where the approximating function f (k) of the objective function f at the k-th externe iteration and r-th inner iteration has the following form:

f (k) (x) = a (k) + b (k) ( 1 x (k) -d (k) - 1 x -d (k) )(x (k) -d (k) ) 2 + η (k) ( 1 2
(x (k) -d (k) ) 3 x -d (k) + 1 2 (x (k) -d (k) )((x -2x (k) + d (k) ))) (4.5) η (k) = s T k-1 y k-1 s T k-1 s k-1 > 0, (4.6)
where

s k-1 = x (k) -x (k-1) and y k-1 = f ′ (x (k) ) -f ′ (x (k-1
) ) The parameters a (k) , b (k) are adjusted such that a first order approximation is satisfied, i.e

f (k) (x (k) ) = f (x (k) ) (4.7) ( f (k) ) ′ (x (k) ) = f ′ (x (k) ) (4.8)
η (k) is the spectral parameter, and

d (k) = x (k) + σ (k) , (4.9)
S (k) :=        -1 if g x (k) < 0, +1 if g x (k) > 0.
Where the asymptotes d (k) are adjusted heuristically as the optimization progresses or are guided by a proposed given function whose first and second derivative are evaluated at the current iteration point x (k) . Also, the approximated parameters a (k) , b (k) and η (k) will be determined for each iteration (k). To evaluate them, we use the objective function value, its first derivative, as well as its second derivatives at x (k) . The parameters a (k) , b (k) are determined i such a way that the following set of interpolation conditions are satisfied

f (k) (x (k) ) = f (x (k) ) ( f (k) ) ′ (x (k) ) = f ′ (x (k) )

NEW APPROACH OF MOVING ASYMPTOTES METHOD

Therefore, by a simple computation, we verify that a (k) , b (k) and c (k) are explicitly given by:

a (k) = f (x (k) ) b (k) = f ′ (x (k) )
Note that unlike the first order method discussed earlier, here second order version date i addition to data form previews iteration point are used. We now explain how the asymptotes can be chosen. We introduce the following definition: In what follows, we will always assume that the sequence of asymptotes {d (k) } is chosen in our approximate problems such that it forms a sequence of asymptotes. By defining the suitable index set We now are able to state the first result: k) . In addition, the function f (k) has an unique minimum at

I (k) = -∞, d (k) ∪ d (k) , +∞ . ( 4
x * k = d (k) + S (k) * (x (k) -d (k) ) 2 (1 - g x (k) η (k) 2 (x (k) -d (k) )
).

(4.11)

Proof 9 An important characteristic of our approximate problem obtained via th approximation function f (k) is its strict convexity in I (k) . But from the definition of I (k) and a simple calculation of its second derivative can be written in the form:

f (k) ′′ (x) = η (k) - 2b (k) x (k) -d (k) x (k) -d (k) x -d (k) 3 . (4.12)
Hence, to prove the convexity of f (k) , we have to show that

η (k) - 2b (k) x (k) -d (k) x (k) -d (k) x -d (k) 3 > 0, ∀x ∈ I (k) .
According to the definition of the set I (k) , it follows that x (k)d (k) and xd (k) have the same sign in the interval I (k) , It remains to show that,

η (k) - 2b (k) x (k) -d (k) > 0.
(4.13)

If we replace x (k) -d (k) by σ (k) in 4.13 η (k) -2 g(x (k) ) x (k) -d (k) = η (k) -2 g(x (k) ) σ (k) (4.14) = η (k) -2 g(x (k) ) σ (k) > 0 (4.15)
According to 4.15 we conclude that the inequality (4.13) satisfied, and then we immediately get the strict convexity of f (k) on I (k) . Furthermore, if f (k) attains its minimum at x (k) * , then it is easy to see that x (k) * is solution of the equation

η (k) 2 (x (k) -d (k) ) + (x (k) -d (k) ) 2 (x -d (k) ) 2 g(x (k) ) - η (k) 2 (x (k) -d (k) ) = 0 (4.16)
From this we get the equivalent equation

(x (k) -d (k) ) 2 (x -d (k) ) 2 = η (k) 2 (x (k) -d (k) ) η (k) 2 (x (k) -d (k) ) -g(x (k) ) = 1 1 -2g(x (k) ) η (k) (x (k) -d (k) ) = 1 1 - 2g(x (k) ) 2g(x (k) )+η (k) (x (k) -d (k) ) = 1 1 - 1 1+ η (k) 2g(x (k) ) (x (k) -d (k) )
As the sequence of asymptotes is feasible, then (x (k) -d (k) ) and g(x (k) ) have the same sign, and η (k) > 0 ∀k > 0 So

η (k) 2g(x (k) ) (x (k) -d (k) ) > 0 1 + η (k) 2g(x (k) ) (x (k) -d (k) ) > 1 0 < 1 1 + η (k) 2g(x (k) ) (x (k) -d (k) ) < 1 1 - 1 1 + η (k) 2g(x (k) ) (x (k) -d (k) )
> 0

Univariate objective function 69

Hence if x (k) * the root of f (k) , then we get that the point x (k) * satisfies the equation

x (k) * -d (k) 2 = x (k) -d (k) 2 1 - 2b (k) η (k) (x (k) -d (k) )
Now, by taking the square root and using the definition of feasible asymptotes we can see that the unique solution x

(k) * belonging to I (k) is given by

x * k = d (k) + S (k) (x (k) -d (k) ) 2 (1 - b (k) η (k) 2 (x (k) -d (k) )
).

Remark 4.2.2 An analysis of the previews profs reveals that instead of assuming that the objective function is convex, it suffices to only require that we have the condition

η (k) - 2b (k) x (k) -d (k) > 0. ∀k > 0.
(4.17)

Remark 4.2.3 It is easily see that our approximation can be seen as an extension of the approximation of Fleury, where in our method we use the second order information.

We have built a strictly convex approximation function of the objective function f at x (k) , which is minimum at k) . We have now to check that the sequence (x (k) defined by

x (k) * ∈ I (
x (k+1) = x (k) * .
converges to the solution x * of the initial problem. On the relationship between the new method and several of the most closely related ideas.Our approximation scheme leaves, as in the one-dimensional case, all well-known properties of convexity and separability of th MMA unchanged with the following major advantages:

• All our subproblems have an explicit solutions.

• It converges an iteration sequence that is bounded and converges to a local solution.

• It converges geometrically.

To simplify the notation, for every j = 1, ..., d, we use f , j to denote the first order partial derivative of f with respect to each variable x j , we also use the notation f ,,i j for the second-order partial derivatives with respect to x i first and then x j ,

Convergence analysis in IR

This subsection aims to show that the proposed method is convergent in the sense that the distance between the both sub sequence X (k) and Y (k) generated by theorem 4. Proof 10 Let µ be a fixed positive constant such that

(x) f Z (k) X (k) Y (k)
0 < 1 η (k) ≤ µ ∀k ≥ 0 (4.18)
and we define the sequence x (k+1) in the theorem (4.2.1) by

x (k+1) =            d (k) + (x (k) -d (k) ) 2 (1 -2 g(x (k) ) η (k) (x (k) -d (k) ) ) if g x (k) < 0, d (k) -(x (k) -d (k) ) 2 (1 -2 g(x (k) ) η (k) (x (k) -d (k) ) ) if g x (k) > 0. =        X (k+1) = x (k+1) /g x (k+1) < 0 , Y (k+1) = x (k+1) /g x (k+1) > 0 ,
If we suppose that g(x (0) ) > 0 (we can f course suppose the other case, just the notification will be changed)

x (k+1) =        X (k+1) = x 2(p+1) , p ∈ IN , Y (k+1) = x 2(p+1)+1 , p ∈ IN , =            d (k) + (X (k) -d (k) ) 2 (1 -2 g(X (k) ) η (k) (X (k) -d (k) ) ), d (k) -(Y (k) -d (k) ) 2 (1 -2 g(Y (k) ) η (k) (Y (k) -d (k) ) ).
X (k) and Y (k) are a both sub-sequence of the x (k) such that X

(k) = x 2p p∈IN and Y (k) = x 2p+1 p∈IN and g(X (k) ) > 0 ∀k ∈ IN, g(Y (k) ) < 0 ∀k ∈ IN, (4.19) d (k) = X (k) + σ (k) , Y (k) + σ (k) , (4.20)
X (k+1) -Y (k+1) = X (k) -Y (k) + (X (k) -d (k) ) 2 (1 -2 g X (k) η (k) (X (k) -d (k) ) ) (4.21) + (Y (k) -d (k) ) 2 (1 -2 g Y (k) η (k) (Y (k) -d (k) ) ) (4.22)
Let us note by

G (k) X = (X (k) -d (k) ) 2 (1 -2 g X (k) η (k) (X (k) -d (k) ) ) (4.23) G (k) Y = (Y (k) -d (k) ) 2 (1 -2 g Y (k) η (k) (Y (k) -d (k) ) ) (4.24) So X (k+1) -Y (k+1) = X (k) -Y (k) + G (k) X + G (k) Y (4.25) X (k+1) -Y (k+1) < X (k) -Y (k) + G (k) X + G (k) Y (4.26) X (k) is an increase sequence, indeed X (k+1) -X (k) = σ (k) + G (k) X > 0 ∀k ≥ 0, (4.27)
and Y (k) is a decrease sequence,

Y (k+1) -Y (k) = σ (k) -G (k) Y < 0 ∀k ≥ 0 (4.
η (k) σ (k) < 0 (4.29) then Y (k+1) -Y (k) < 0 ∀k ≥ 0, ( 4
Y (k) ∈ ]x * ,U max [ ∀k ≥ 0, (4.32)
and then Y (k) > X (k) ∀k ≥ 0, (4.33)

From (4.27), (4.30) and (4.91) we can easily check that

0 < Y (k+1) -X (k+1) < Y (k) -X (k) ∀k ≥ 0, (4.34) Y (k+1) -X (k+1) = Y (k) -X (k) -( G (k) X + G (k) Y ) (4.35) Y (k+1) -X (k+1) = Y (k) -X (k) -( G (k) X + G (k) Y ) (4.36) Y (k+1) -X (k+1) -Y (k) -X (k) = -( G (k) X + G (k) Y ) (4.37)
According to the last equality (4.37), we conclude

Y (k+1) -X (k+1) < Y (k) -X (k) ∀k ≥ 0 (4.38) If we pose Z (k) = Y (k) -X (k) Z (k+1) -Z (k) 2 = ( G (k) X + G (k) Y ) 2 = G (k) X + G (k) Y + 2 G (k) X G (k) Y Therefore G (k) X + G (k) Y = (X (k) -d (k) ) 2   1 -2 g X (k) η (k) (X (k) -d (k) )   + (Y (k) -d (k) ) 2   1 -2 g Y (k) η (k) (Y (k) -d (k) )   =   X (k) -d (k) - g X (k) η (k)   2 +   Y (k) -d (k) - g Y (k) η (k)   2 -      g X (k) η (k)   2 +   g Y (k) η (k)   2    =   σ (k) - g X (k) η (k)   2 +   σ (k) - g Y (k) η (k)   2 -      g X (k) η (k)   2 +   g Y (k) η (k)   2    =   σ (k) - g X (k) η (k)   2 +   σ (k) - g Y (k) η (k)   2 -      g X (k) η (k)   2 +   g Y (k) η (k)   2    < (2M 1 -1) 2   g X (k) η (k)   2 + (2M 2 + 1) 2   g Y (k) η (k)   2 < (2M -1) 2 (η (k) ) 2 g X (k) 2 + (2M -1) 2 (η (k) ) 2 g Y (k) 2 < (2M -1) 2 (η (k) ) 2 g X (k) 2 + g Y (k) 2
Now by using the first identity of Legendre we find

Z (k+1) -Z (k) 2 = ( G (k) X + G (k) Y ) 2 = G (k) X + G (k) Y + 2 G (k) X G (k) Y < 2 G (k) X + G (k) Y so 0 < Z (k+1) -Z (k) < 2M -1 η (k) g X (k) + g Y (k) , (4.39)
(4.40)

< (2M -1)µ g X (k) + g Y (k) , (4.41) or X (k) k∈IN and Y (k) k∈IN two sub-sequence of x (k) k∈IN then lim X (k) = limY (k) = lim x (k) = x (4.42)
g is a function continuously differentiable so

lim g(X (k) ) = g(lim X (k) ) = g( x) and lim g(Y (k) ) = g(limY (k) ) = g( x) (4.43)
According to (4.79) we have

g(X (k) ) < 0 ∀k ≥ 0 g(Y (k) ) > 0 ∀k ≥ 0 From (4.

The multivariate new approach of the MMA

To build up the approximate optimization subproblems P [k], taking into account the approximate optimization problem, we will seek to construct a successive sequence of subproblems P [k] k ∈ IN, at successive iteration k, we shall seek a suitable explicit rational approximating function f (k) , strictly convex and relatively easy to implement. The solution of the subproblems P [k] will be obtained explicitly and is denoted by x - * (k) . The optimum x - * (k) of the subproblem P [k] will be considered as the starting point x (k+1) := x - * (k) for the next subsequent approximate subproblem P [k + 1]. Therefore, for a given suitable initial approximation x (0) , the approximate subproblem P [k]. To reduce the computational cost, the Hessian of the objective function at each iteration will be replaced by a sequence of diagonal Hessian estimates. These approximate matrix use only first order information accumulated during the previews iterations. However, in view of practical difficulties of evaluating the second-order information, a fitting algorithmic scheme is proposed in order to adjust the curvature of the approximation. The purpose of the first part of this section is to give a complete discussion on the theoretical aspects concerning the multivariate setting. We will first describe the setup and notation for our approach.

4.3

The multivariate new approach of the MMA 75

The multivariate setting

To develop our method for multivariate case, we need to replace the approximating functions of the univariate objective function by suitable strictly convex multivariate approximating functions. The practical implementation of this method is considerably more complex than in the univariate case due to the fact that, at each iteration, the approximating function in the multivariate setting generate a sequence of diagonal Hessian estimates. In this section as well as in the univariate objective approximating function presented in previews section, the function value f (x (k) ), the first order derivatives ∂ f ∂ x j (x (k) ), for j = 1, ..., d, as well as the spectral parameters and the moving asymptotes at the design point x (k) are used to build up effort, we suggest to approximate at each iteration the second derivative f " (x (k) ) by some positive real value s (k) . In this situation, we shall propose the following procedure for selecting moving asymptotes

d (k) =    x (k) + σ (k) , σ (k) > 0 if g x (k) > 0, x (k) + σ (k) , σ (k) < 0 if g x (k) < 0.
It is clear that all the previews results easily carry over to the case in the proposition, the second derivative f " (x (k) is replaced by an approximate strictly positive parameters η (k) according to the constraints. Indeed, the statements of the theorem apply with straight forward changes. In the next section for the multivariate case, we will discuss a strategy to determinate at each iteration a reasonably good numerical approximation to the second derivative. we will also establish a multivariate version of theorem. We now give a short discussion about an extension of the above approach. Our study in this section has been in a framework that at each iteration, the second derivative need to be evaluate exactly. We will focus our analysis on examining what happen when the second derivative of the objective function f may not be known or is expensive to evaluate. Thus in order to reduce the computational cost.

Presentation of our method in R ⋉

In this section a generalization of our method to IR n is presented. The objective function being in general form f : IR n . We introduce for x ∈ Ω ⊂ IR n , the following approximating functions:

f (k) (x) = f (x (k) ) + ∑ n i=1 ∂ f ∂ x i (x (k) ) 1 x (k) i -d (k) i -1 x i -d (k) i x (k) i -d (k) i 2 + ∑ n i=1 η (k) i 2 x (k) i -d (k) i 3 x i -d (k) i + x (k) i -d (k) i x i -2x (k) i + d (k) i = f (x (k) ) + ∑ n i=1 g i (x (k) ) 1 x (k) i -d (k) i -1 x i -d (k) i x (k) i -d (k) i 2 + ∑ n i=1 η (k) i 2 x (k) i -d (k) i 3 x i -d (k) i + x (k) i -d (k) i x i -2x (k) i + d (k) i = f (x (k) ) + ∇ f (x (k) ) T .v(x, x (k) , d (k) ) + η (k) .w(x, x (k) , d (k) ) = f (x (k) ) + ∇ f (x (k) ) T .v (k) (x) + η (k) .w (k) (x), (4.47)
where v (k) : IR n -→ IR n and w (k) : IR n -→ IR n two functions define by

v (k) : IR n -→ IR n x -→ (v (k) 1 (x 1 ), . . . , v (k) n (x n )), (4.48
)

w (k) : IR n -→ IR n x -→ (w (k) 1 (x 1 ), . . . , w (k) n (x n )), (4.49)
where

for i = 1, . . . , n v (k) i (x i ) = 1 x (k) i -d (k) i -1 x i -d (k) i x (k) i -d (k) i 2 w (k) i (x i ) = x (k) i -d (k) i 3 x i -d (k) i + x (k) i -d (k) i x i -2x (k) i + d (k) i . (4.50)
The approximate functions f (k) are define on

I (k) = I (k) 1 × ... × I (k) n (4.51) I k i = -∞, d (k) i ∪ d (k) i , +∞ , i = 1, ..., n (4.52)
4.4 Presentation of our method in R ⋉

77

We can check easily that

v (k) (x (k) ) = w (k) (x (k) ) = 0 IR n Dv (k) (x (k) ) = Dw (k) (x (k) ) = 0 IR n , (4.53)
with

Dv (k) = (Dv (k) 1 , . . . , Dv (k) n ) and Dw (k) = (Dw (k) 1 , . . . , Dw (k)
n ). From (4.53), we can see that the functions define in (4.47) are an approximations of first order and we have

f (k) (x (k) ) = f (x (k) ) ∇ f (k) (x (k) ) = ∇ f (x (k) ) (4.54)
The first and second derivatives of the convex approximations can be given analytically by

∇ f (k) (x) =                         g 1 x (k) x (k) 1 -d (k) 1 2 x 1 -d (k) 1 2 + η (k) 1 2 x (k) 1 -d (k) 1   1 - x (k) 1 -d (k) 1 2 x 1 -d (k) 1 2    . . . g i x (k) x (k) i -d (k) i 2 x i -d (k) i 2 + η (k) i 2 x (k) i -d (k) i   1 - x (k) i -d (k) i 2 x i -d (k) i 2    . . . g n x (k) x (k) n -d (k) n 2 x n -d (k) n 2 + η (k) n 2 x (k) n -d (k) n   1 - x (k) n -d (k) n 2 x n -d (k) n 2                            (4.55) ∂ f (k) ∂ x i (x) := g i x (k) x (k) i -d (k) i 2 x i -d (k) i 2 + η (k) i 2 x (k) i -d (k) i   1 - x (k) i -d (k) i 2 x i -d (k) i 2    (4.56) ∂ 2 f (k) (x) ∂ x i ∂ x j = 0, ∀i ̸ = j (4.57) ∂ 2 f (k) ∂ x 2 i (x) := -g i x (k) x (k) i -d (k) i 2 x i -d (k) i 3 + η (k) i x (k) i -d (k) i 3 x i -d (k) i 3 . (4.58)
We suppose

σ (k) i > 2 g i x (k) η (k) i > 0 (4.59)

78

NEW APPROACH OF MOVING ASYMPTOTES METHOD

∇ 2 f (k) (x) =             ∂ 2 f (k) ∂ x 2 1 (x) 0 • • • 0 0 ∂ 2 f (k) ∂ x 2 2 (x) . . . . . . . . . . . . . . . 0 0 • • • 0 ∂ 2 f (k) ∂ x 2 n (x) ,             (4.60)
We can rewrite the Hessian matrix of f (k) as

∇ 2 f (k) (x) = A (k) .B (k) (x) (4.61)
where (.) is the Hadamard product of the diagonals matrix A (k) and B (k) defined by

A (k) =                     η (k) 1 -2 g 1 x (k) x (k) 1 -d (k) 1   0 • • • 0 0   η (k) 2 -2 g 2 x (k) x (k) 2 -d (k) 2 
 . . . . . . . . . . . . . . . 0 0 • • • 0   η (k) n -2 g n x (k) x (k) n -d (k) n                     (4.62)
B (k) (x) =                x (k) 1 -d (k) 1 x 1 -d (k) 1 3 0 • • • 0 0 x (k) 2 -d (k) 2 x 2 -d (k) 2 3 . . . . . . . . . . . . . . . 0 0 • • • 0 x (k) n -d (k) n x n -d (k) n 3                (4.63) Definition 4.4.1 A sequence of asymptotes d (k) = d (k) 1 , . . . , d (k) n defined by d (k)
i = x (k) i + σ (k) i , i = 1, . . . , n. (4.64
)

is called feasible if for all k ≥ 0, σ (k)
i > 2

g i( x (k) ) η (k) i > 0. i f g i x (k) > 0, i = 1, . . . , n σ (k) i < 2 g i( x (k) ) η (k) i < 0. i f g i x (k) < 0, i = 1, . . . , n.
σ (k) i = 2Mα k g i x (k) η (k) i , i = 1, . . . n. (4.66)
where the positive scalar α k is called the step length, this paramter is used to stabilize the convergence. Then, for each k > 0 the approximating function defined by (4.47) is a strictly convex function on I k . In addition, the function f (k) has an unique minimum at

x (k+1) ← x (k) * = d (k) + S (k) G (k) (4.67)
where

G (k) = diag G (k) 1 , ..., G (k) n and S (k) = S (k) 1 , ..., S (k) n T G (k) i = (x (k) i -d (k) i ) 2 (1 -2 g i x (k) η (k) i (x (k) i -d (k) i )
).

i =    -1 if g i x (k) < 0, 1 if g i x (k) > 0. (4.68) and S (k)
Proof 11 . The main ingredient here is a suitable application of the condition (4.59) imposed on the coefficient σ (k) . We first start by showing that the approximating function f (k) is well defined and strictly convex in I k . To this end we prove that ∇ 2 f (k) is positive semidefinite in I k . Indeed, a simple calculation reveals that

∇ 2 f (k) (x) =                Γ (k) 1 x (k) 1 -d (k) 1 x 1 -d (k) 1 3 0 • • • 0 0 Γ (k) 2 x (k) 2 -d (k) 2 x 2 - d(k) 2 3 . . . . . . . . . . . . . . . 0 0 • • • 0 Γ (k) n x (k) n -d (k) n x n -d (k) n 3                , (4.70)
where

Γ (k) i = η (k) i -2 g i x (k) x (k) i -d (k) i i = 1, . . . , n. (4.71)
In view of (4.70), it remains to show that the Hessian matrix on the right-hand side of (4.70) is positive semidefinite for all x ∈ I k . Since γ (k) is nonnegative (as can be seen in (4.59)), and the two terms x

(k) i -d (k) i 80 NEW APPROACH OF MOVING ASYMPTOTES METHOD and x i -d (k)
i have the same sign in the interval I k j , and ∀x ∈ I (k) , x T .∇ 2 f (k) (x).x ≥ 0 then f (k) is a convex function on I k . Furthermore, the function f (k) being well definite and continuous in I k , this implies the existence of a minimum, which by convexity is the unique critical point x (k) * . Now, looking for ∇ f (k) (x) = 0 R n we conclude that the optimum x (k) * is one solution of the system

                        g 1 x (k) x (k) 1 -d (k) 1 2 x 1 -d (k) 1 2 + η (k) 1 2 x (k) 1 -d (k) 1   1 - x (k) 1 -d (k) 1 2 x 1 -d (k) 1 2    . . . g i x (k) x (k) i -d (k) i 2 x i -d (k) i 2 + η (k) i 2 x (k) i -d (k) i   1 - x (k) i -d (k) i 2 x i -d (k) i 2    . . . g n x (k) x (k) n -d (k) n 2 x n -d (k) n 2 + η (k) n 2 x (k) n -d (k) n   1 - x (k) n -d (k) n 2 x n -d (k) n 2                            =                       0 . . . . . . . . . 0 . . . . . . . . . 0                       (4.72) g i x (k) x (k) i -d (k) i 2 x i -d (k) i 2 + η (k) i 2 x (k) i -d (k) i   1 - x (k) i -d (k) i 2 x i -d (k) i 2 
  = 0, i = 1, ..., n (4.73)
which, after trivial calculations, implies

                        x (k) 1 -d (k) 1 2 x 1 -d (k) 1 2 . . . x (k) i -d (k) i 2 x i -d (k) i 2 . . . x (k) n -d (k) n 2 x n -d (k) n 2                         =                      η (k) 1 2 (x (k) 1 -d (k) 1 ) η (k) 1 2 (x (k) 1 -d (k) i ) -g (k) 1 . . . η (k) i 2 (x (k) i -d (k) i ) η (k) i 2 (x (k) i -d (k) i ) -g (k) i . . . η (k) n 2 (x (k) n -d (k) n ) η (k) n 2 (x (k)
n -d (k) n ) -g (k) n                      (4.74)
4.4 Presentation of our method in R ⋉

81

We can rewrite the system (4.76) as

                        x (k) 1 -d (k) 1 2 x 1 -d (k) 1 2 . . . x (k) i -d (k) i 2 x i -d (k) i 2 . . . x (k) n -d (k) n 2 x n -d (k) n 2                         =                       1 1 - 1 1+ η (k) 1 2g 1 (x (k) ) (x (k) 1 -d (k) 1 )
. . .

1 1 - 1 1+ η (k) i 2g i (x (k) ) (x (k) i -d (k) i ) . . . 1 1 - 1 1+ η (k) n 2gn(x (k) ) (x (k) n -d (k) n )                       (4.75)
as in theorem 4.2.1 we can prove that

1 - 1 1 + η (k) i 2g i (x (k) ) (x (k) i -d (k) i )
> 0 i = 1, . . . , n Hence if x (k) * = (x (k) 1 * , . . . , x (k)
n * ) the root of f (k) , then we get that the point x

(k) * satisfies the system             x (k) 1 * -d (k) 1 2 . . . x (k) i * -d (k) i 2 . . . x (k) n * -d (k) n 2             =                  x (k) 1 -d (k) 1 2 1 -2 g (k) 1 η (k) 1 (x (k) 1 -d
(k) 1 ) . . . x (k) i -d (k) i 2 1 -2 g (k) i η (k) i (x (k) i -d (k) i ) . . . x (k) n -d (k) n 2 1 -2 g (k) n η (k) (x (k) n -d (k) n )                  (4.76)
and then

          x (k) 1 * . . . x (k) i * . . . x (k) n *           =           d (k) 1 . . . d (k) i . . . d (k) n           +                     S (k) 1 x (k) 1 -d (k) 1 2 1 -2 g (k) 1 η (k) 1 (x (k) 1 -d (k) 1 ) . . . S (k) i x (k) i -d (k) i 2 1 -2 g (k) i η (k) i (x (k) i -d (k) i ) . . . S (k) n x (k) n -d (k) n 2 1 -2 g (k) n η (k) (x (k) n -d (k) n )                     (4.77)
Therefore, after some simplification, the system (4.77) becomes

x

(k) * = d (k) + S (k) G (k) ,
where G (k) and S (k) are defined respectively by (4.68) and (4.69).

By condition (4.59) imposed on the parameter σ (k) , it can be deduced from the system (4.77) that the solvability of our subproblem can always be guaranteed. Indeed, under this condition, we will be sure that what is inside square root on the left of the system (4.77) is always nonnegative. This completes the proof of the theorem.

Multivariate convergence result

Thanks to the separability and convexity of the approximations proposed in the multidimensional case, we can extend in a consistent way the convergence results found in the univariate case

S = S 1 × • • • × S n ⊂ Ω containing x * , where S i = [l i , u i ] i = 1, . . . , n
such that , for any x 0 ∈ S, the scheme (4.67) are well defined, remain in S and converge to x * .

Proof 12 Let µ be a fixed positive constant such that

0 < 1 η (k) i ≤ µ, i = 1, . . . n. ∀k ≥ 0 (4.78)
we can rewrite the sequence x (k+1) = x

defined in the theorem 4.4.3 in the form

x (k+1) i =              d (k) i + (x (k) i -d (k) i ) 2 (1 -2 g i( x (k) ) η (k) i (x (k) -d (k) i ) ) if g i x (k) < 0, d (k) i -(x (k) i -d (k)
i ) 2 (1 -2 g i x (k) i η (k) i (x (k) i -d (k) i )
)

if g i x (k) > 0. i = 1, . . . , n =        X (k+1) i = x (k+1) i /g i x (k+1) < 0 , Y (k+1)
i = x (k+1) i /g i x (k+1) > 0 , i = 1, . . . , n
Now for each dimension i = 1, . . . , n, we suppose g i (x (0) ) > 0

x (k+1) i =        X (k+1) i = x 2(p+1) i , p ∈ IN , Y (k+1) i = x 2(p+1)+1 i , p ∈ IN , i = 1, . . . , n =            d (k) i + (X (k) i -d (k) i ) 2 (1 -2 g i( X (k) ) η (k) i (X (k) i -d (k) i )
),

d (k) i -(Y (k) i -d (k) i ) 2 (1 -2 g i( Y (k) ) η (k) i (Y (k) i -d (k) i )
).

i = 1, . . . , n 4.4 Presentation of our method in R ⋉ 83

X (k) = X (k) 1 , . . . , X (k) n and Y (k) = Y (k) 1 , . . . ,Y (k) n
are a both sub-sequence of the x (k) such that X (k) =

x 2p p∈IN and Y (k) = x 2p+1 p∈IN and

g i (X (k) ) > 0 ∀k ∈ IN, g i (Y (k) ) < 0 ∀k ∈ IN, i = 1, . . . , n (4.79)
d (k) i = X (k) i + σ (k) i , Y (k) i + σ (k) i , i = 1, . . . , n (4.80)
X (k+1) i -Y (k+1) i = X (k) i -Y (k) i + (X (k) i -d (k) i ) 2 (1 -2 g i X (k) η (k) (X (k) i -d (k) i ) ) (4.81)
+ (Y (k) i -d (k) i ) 2 (1 -2 g i Y (k) η (k) i (Y (k) i -d (k) i ) ) (4.82)
Let us note by G (k)

X i = (X (k) i -d (k) i ) 2 (1 -2 g i X (k) η (k) i (X (k) i -d (k) i ) ) (4.83) G (k)
Y i = (Y (k) i -d (k) i ) 2 (1 -2 g i Y (k) η (k) i (Y (k) i -d (k) i ) ) (4.84) So X (k+1) i -Y (k+1) i = X (k) i -Y (k) i + G (k) X i + G (k) Y i (4.85) X (k+1) i -Y (k+1) i < X (k) i -Y (k) i + G (k) X i + G (k) Y i (4.86) X (k) i is an increase sequence, indeed X (k+1) i -X (k) i = σ (k) i + G (k) X i > 0 ∀k ≥ 0, (4.87) and Y
(k) i is a decrease sequence, Y (k+1) i -
Y (k) i = σ (k) i -G (k) Y i < 0 ∀k ≥ 0 (4.88)
For a ∈ Ω and 1 ≤ i ≤ n fixed, we consider the ral function f i defined by

f i (x i ) = f (a 1 , a 2 , . . . , a i-1 , x i , a i+1 , . . . , a n ) i = 1, . . . , n
its definition domain being the open subset of R given by

D( f i ) = s ∈ R : (a 1 , a 2 , . . . , a i-1 , s, a i+1 , . . . , a n ) T ∈ Ω

NEW APPROACH OF MOVING ASYMPTOTES METHOD

If f i is derivable on a i , we say that the i-th partial derivative of exist on a and is equal to f ′ i (a i ). it's noted

∂ f ∂ x i (a) ou D i f (a) as f ′ i (a j ) = lim t→0 f i (a j + t) -f i (a j ) t we can see that ∂ f ∂ x j (a) = lim t→0 f (a + te j ) -f (a) t .
If all the partial derivatives

∂ f ∂ x 1 (a), . . . , ∂ f ∂ x n (a) exists on a ∈ Ω, then the function f is differentiable on a. Now, let us v ∈ R n \{0}.
The straight line passing through a and admitting the director vector v is parametered as follows {a + tv : t ∈ R} Let us the real function f v (t) = f (a + tv), its definition domain being

D( f v ) = {t ∈ R : a + tv ∈ Ω}.
it is an open subset of R that contains 0. If f v is differentiable in t = 0, we say that f is differentiable in a following the vector v. Furthermore f v (0) is called the derivative of f in a following v or also the directional derivative of f in a following v, and we note

D f (a, v) ou ∂ f ∂ v (a) So D f (a, v) = ∂ f ∂ v (a) = lim t→0 f v (t) -f v (0) t = lim t→0 f (a + tv) -f (a) t
If v = e i and f is differentiable in a following the vector e i , we can notice that D f (a, e j ) = ∂ f ∂ x j (a) Thanks to the directional derivative's definition, we can define the table of variation of each real function f i in the neighborhood of x i * , for that we take a j = x j * , for j = 1, . . . , n when j ̸ = i and

x i ∈ [l i , u i ] x i f ′ i (x i ) f i (x i ) l i x i * u i - 0 + f min f min
(k) i ∈ ]l i , x i * [ ∀k ≥ 0, (4.89)
Y (k) i ∈ ]x i * , u i [ ∀k ≥ 0, (4.90)
and then Y

(k) i > X (k) i ∀k ≥ 0, (4.91)
From (4.87), (4.88) and (4.91) we can easily check that

0 < Y (k+1) i -X (k+1) i < Y (k) i -X (k) i ∀k ≥ 0, (4.92)
Y (k+1) i -X (k+1) i = Y (k) i -X (k) i -( G (k)
X i + G (k) Y i ) (4.93) Y (k+1) i -X (k+1) i = Y (k) i -X (k) i -( G (k)
X i + G (k) Y i ) (4.94) Y (k+1) i -X (k+1) i -Y (k) i -X (k) i = -( G (k)
X i + G (k) Y i ) (4.95)
According to the last equality (4.95), we conclude

Y (k+1) i -X (k+1) i < Y (k) i -X (k) i ∀k ≥ 0 (4.96)
If we pose Z

(k) i = Y (k) i -X (k) i Z (k+1) i -Z (k) i 2 = ( G (k)
X i + G (k) Y i ) 2 = G (k) X i + G (k) Y i + 2 G (k) X i G (k) Y i 86 NEW APPROACH OF MOVING ASYMPTOTES METHOD Therefore G (k) X i + G (k) Y i = (X (k) i -d (k) i ) 2   1 -2 g i X (k) η (k) i (X (k) -d (k) i )   + (Y (k) i -d (k) i ) 2   1 -2 g i Y (k) η (k) i (Y (k) i -d (k) i )   =   X (k) i -d (k) i - g i X (k) η (k) i   2 +   Y (k) i -d (k) i - g i Y (k) η (k) i   2 -      g i X (k) η (k) i   2 +   g i Y (k) η (k) i   2    =   σ (k) i - g i X (k) η (k) i   2 +   σ (k) i - g i Y (k) η (k) i   2 -      g i X (k) η (k) i   2 +   g i Y (k) η (k) i   2    =   σ (k) i - g i X (k) η (k) i   2 +   σ (k) i - g i Y (k) η (k) i   2 -      g i X (k) η (k) i   2 +   g i Y (k) η (k) i   2    < (2M 1 -1) 2   g i X (k) η (k) i   2 + (2M 2 + 1) 2   g i Y (k) η (k) i   2 < (2M -1) 2 (η (k)
i ) 2 g i X (k) 2 + (2M -1) 2 (η (k)
i ) 2 g i Y (k) 2 < (2M -1) 2 (η (k
) i ) 2 g i X (k) 2 + g i Y (k) 2
Now by using the first identity of Legendre we find

Z (k+1) i -Z (k) i 2 = ( G (k)
X i + G (k) Y i ) 2 = G (k) X i + G (k) Y i + 2 G (k) X i G (k) Y i < 2 G (k) X i + G (k) Y i so 0 < Z (k+1) i -Z (k) i < 2M -1 η (k) i g i X (k) + g i Y (k) , (4.97)
(4.98)

< (2M -1)µ g i X (k) + g i Y (k) , (4.99)
4.4.2 Rules of updating the spectral parameters η (k) , d (k) and σ (k)

• Parameter η (k)

The motivation for using the spectral parameter instead of the second order information in our approximations is to reduce the number of computation and evaluation at each iteration k and the oscillation of the process when f " (x (k) ) < 0, and also to keep the precision of the approximate solution.

From the Mean Value Theorem of the Integral Calculus we know that, given a continuously differentiable, then:

∇ f (y) = ∇ f (x) + 1 0 ∇ 2 f (x + α(y -x))dα(y -x) (4.100)
By setting s = yx, the scalar

η = s T t s T s (4.101)
where t = ∇ f (y) -∇ f (x), or again by the Mean Value Theorem,

t = 1 0 ∇ 2 f (x + αs)dα s,
defines a Rayleigh quotient with respect to the average Hessian matrix 1 0 ∇ 2 f (x + αs)dα . Such quotient has its value between the smallest and the largest eigenvalue of the average Hessian matrix, what motivates the terminology spectral parameter for (4.101). Thus, if we require that the Hessian of the objective function f approximated by scalar matrices, we might say that ηI is the matrix of such type that best approximations the average Hessian. The idea is to use the spectral parameter 4.101 in the following way:

∇ 2 f (x) ≈ ηI ⇒ ∂ 2 f (x) ∂ x 2 j ≈ η
The idea behind the updating of ρ i is to increase or remain the same value of this parameter at each inner iteration, but never reduce it. Therefore, it is important that they decrease whenever an outer iteration starts to avoid slow convergence and generation of a small steps in the process. In terms of the parameters σ

i (x) is diagonal with

∂ 2 w (k) i ∂ x 2 j (x) ≥ 1 σ (k) j
2 for all j and x, This means that the curvature of the function w

i towards x j increases as σ

(k) j decreases. Thus, depending on the pattern of the variables in the previews iterations, they should be stabilized or released, according to the following rule. if k = 1 and k = 2:

σ (k) j = x max j -x min j 2 , (4.102)
and for k ≥ 3:

σ (k) j = γ (k) j σ (k-1) j , (4.103)
where

γ (k) j =          0.7 if x (k) j -x (k-1) j x (k-1) j -x (k-2) j < 0 1.2 if x (k) j -x (k-1) j x (k-1) j -x (k-2) j > 0 1 if x (k) j -x (k-1) j x (k-1) j -x (k-2) j = 0 (4.104) • Parameter d (k)

88

NEW APPROACH OF MOVING ASYMPTOTES METHOD

Each iteration of the present method computes a step length α (k) and then decides how far to move the asymptotes d (k) in terms of the step's value. The moving asymptotes expression is given by

d (k) i = x (k) i + 2Mα k g i x (k) η (k) i , (4.105)
where the positive scalar α (k) is called the step length. The success of the convergence process depends on effective choices of both the step length α (k) and then the asymptotes d (k) . Most moving asymptotes approaches require d (k) to be defined in terms of two lower and upper values L (k) and

U (k) as d (k) i =    L (k) i if f ,i x (k) < 0 U (k) i if f ,i x (k) > 0 (4.106) d (k) = d (k) 1 , d (k) 2 , . . . , d (k) n ⊤
, and to be updated by this following algorithm Algorithm 4 Update of asymptotes 1: For iteration number k = 0, 1, . . . and constants L min < U max , ξ ≥ 0, 0 < T 1 < 1 and 2: T 2 > 1 we compute for each i = 1, . . . , n

3: k < 2 : L (k) i := x (k) i -max 1, x (k) i U (k) i := x (k) i + max 1, x (k) i 4: k ≥ 2 : If sign x (k) i -x (k-1) i ̸ = sign x (k-1) i -x (k-2) i , then L (k) i := max x (k) i -max ξ , T 1 x (k-1) i -L (k-1) i , L max U (k) i := min x (k) i + max ξ , T 1 U (k-1) i -x (k-1) i ,U max else L (k) i := max x (k) i -max ξ , T 2 x (k-1) i -L (k-1) i , L min U (k) i := min x (k) i + max ξ , T 2 U (k-1) i -x (k-1) i ,U max
The sub problems generated by these approximations can be solved explicitly, where the separability and the existence of an explicit solution of the functions f (k) (x) and c (k) j (x), j = 1, . . . , m c can be exploited. In each iteration k, the asymptotes have to be adapted. The update rules are presented in the following algorithm, where the value of d (k) changes according to the convergence or divergence of the iterative process and the monotony of the objective function, for more information about this subject see ..., Algorithm 5 Update of asymptotes d (k) 1: For iteration k = 0, 1, . . . and constants L min < U max , ξ ≥ 0, 0 < C 1 < 1 and C 2 > 1 we compute for each i = 1, . . . , n 2:

S (k) i :=    -1, if ∂ f (x (k) ) ∂ x i < 0 1, if ∂ f (x (k) ) ∂ x i > 0 3: B (k) i := S (k) i L min , if S (k) i < 0 S (k) i U max , if S (k) i > 0 4: k < 2 : d (k) i := x (k) i + S (k) i max 1, x (k) i 5: k ≥ 2 If sign x (k) i -x (k-1) i ̸ = sign x (k-1) i -x (k-2) i , then d (k) i := S (k) i min S (k) i (x (k) i + S (k) i max ξ ,C 1 x (k-1) i -d (k-1) i , B (k) i else d (k) i := S (k) i min S (k) i (x (k) i + S (k) i max ξ ,C 2 x (k-1) i -d (k-1) i , B (k) i
We can now formulate the main algorithm of our approximations according to the theory study on the previews sections 90 NEW APPROACH OF MOVING ASYMPTOTES METHOD

Algorithm 6 NAMMA Method 1: Choose starting point x (0) ∈ IR n . Set parameter ξ = 0, L min = -∞, U max = ∞,C 2 > 1, 0 < C 1 < 1,
Compute f x (0) , g x (0) . Let k := 0 2: Stopping criteria. i , i = 1, . . . , n, by Algorithm 5 or let d (k) = x (k) + σ (k) and take σ (k) as defined in (4.59).

6: x (k+1) = d (k) + S (k) G (k) 7: while Stopping criteria not satisfies.

Numerical examples

In this section, we give some numerical result on NAMMA (new approach of the method of moving asymptotes). Our source code is written in Matlab 2017 using the Intel inside TM three core of the processor. Test problems are the standard unconstrained optimization problems and it will be found in [START_REF] Jamil | A literature survey of benchmark functions for global optimisation problems[END_REF]. The stopping criteria, we use are ||∇ f (x (k) )|| < ε, where ε is a given tolerance, which depends on the precision of the final solution we want to find. For the first examples the procedure was applied to the simple both dimensional quadratic functions

f 1 (x 1 , x 2 ) = x 1 -x 2 + 2x 2 1 + 2x 1 x 2 + x 2 2 ,
and

f 2 (x 1 , x 2 ) = (x 1 + 10x 2 ) 2 + 10x 4 1 + x 4 2
to know the behavior of the iterative sequence generated by the algorithm 5, and check numerically the theoretical results obtained in the previous sections.

92

NEW APPROACH OF MOVING ASYMPTOTES METHOD

x (k) = (x (k) 1 , x (k) 2 ) ∂ f ∂ x (x (k) ) ∂ f ∂ y (x (k) ) [ -

Numerical examples 93

We can see from the figures (4.4a), (4.4b) and the table 4.3 that distance between two successive iterations converge to zero when we get closer to the solution. In the table 4.3, the set of values of x (k) such that the derivatives of f at point x (k) are positive represents the sub sequence X (k) and those where the derivatives are negative represents the elements of the sub sequence Y (k) . And the figures (4.4c) and (4.4d) represent respectively the convergence of X (k) and Y (k) for different starting point x (0) = (1, -5) and x (0) = [START_REF] Bartlett | Active set vs. interior point strategies for model predictive control[END_REF][START_REF] Bartlett | Active set vs. interior point strategies for model predictive control[END_REF], which shows a coherence between the numerical and theoretical result. We have tested the new methods using the computational software Matlab 2017 with multiple-precision. We selected the following unimodal test functions f , g and the multimodal function h The rosenbrock's function

f (x) = N-1 ∑ i=1 100 x i+1 -x 2 i 2 + (1 -x i ) 2 where x = [x 1 , . . . , x N ] ∈ R N ,
the extended Woods's function

g(x) = N ∑ i=1 100 x 2 4i-3 -x 4i-2 2 + (x 4i-3 -1) 2 + 90 x 2 4i-1 -x 4i 2 + (1 -x 4i-1 ) 2 + 10.1 (x 4i-2 -1) 2 + (x 4i -1) 2 + 19.8 (x 4i-2 -1) (x 4i -1) ,
and extended Himmelblau function

h(x) = n/2 ∑ i=1 x 2 2i-1 + x 2i -11 2 + x 2i-1 + x 2 2i -7 2
These functions has a minimums

f i (x) = x 2 i ( 1 2 + 1 3 x i x n-2 x n-1 x n ) -x i (1 + 1 3 x 2 i ) i = 1, ..., n Problem 2 f (x) = n-1 ∑ i=1 f i (x) + f n (x) (4.108) f i (x) = 1 2 x 2 i - 0.1 3 x 3 i+1 i = 1, ..., n -1 f n (x) = 1 2 x 2 n - 0.1 3 x 3 1 Problem 3 f (x) = f 1 (x) + n ∑ i=2 f i (x) (4.109) f 1 (x) = x 1 ( 1 3 x 2 1 - 3 2 x + 1 1) + sin(x 1 -x 2 ) f i (x) = x i ( 1 3 x 2 i - 3 2 x i + 1) + sin(x i -x i-1 ) i = 1, ..., n Problem 4 f (x) = n ∑ i=1 f i (x) (4.110) f i (x) = x i sin x i + cos x i - 1 2n x 2 i + x n cos x i + x i + 1 3 (x i -1) 3 + 1 2n n ∑ i=1 x 2 i i=1,...,n Problem 5 f (x) = n ∑ i=1 f i (x) (4.111) f i (x) = 1 2 x 2 i -(1 -x i ) cos x i + 0.99x 2 i + 2x i i = 1, ..., n Problem 6 f (x) = n ∑ i=1 f i (x) = n 3 ∑ i=1 ( f 3i-2 (x) + f 3i-1 (x) + f 3i (x)) (4.112) f 3i-2 (x) = x 3i -2x 3i-1 -x 2 3i -1)x 3i-2 f 3i-1 (x) = 1 2 x 3i-2 x 2 3i-1 x 3i -x 2 3i-2 x 3i-1 + 1 3 x 3 3i-1 -2x 3i-1 f 3i (x) = x 3i (exp -x 3i-2 -exp -x 3i-1 ) Problem 7 f (x) = n-1 ∑ i=1 100 x i+1 -x 2 i 2 + (1 -x i ) 2 where x = [x 1 , . . . , x n ] ∈ R n , ( 4

Conclusion

We described a general approach to the first order optimization based on optimizing the objective with respect to the updates. This gives an explicit optimization algorithm which can be viewed as an extension of the method of moving asymptotes for solving a large scale optimization problems, we showed that the proposed algorithm can converge more quickly than very known methods like Spectral Parameter Gradient method (SPG) and need more less evaluations of the spectral parameters thanks to the separability of our approximations, the other main contribution of this work is to show that we develop new algorithms for large optimization independently to the classical methods.

Chapter 5

NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA

Introduction

In this chapter we purpose a new class of optimization method, this kind of methods can be belongs on the so called conservative convex separable approximation (CCSA) methods. These methods are intended for inequality constrained non linear programming problems. The new Sequential convex programming methods based on the MMA, proposed in this chapter, formulates separable and strictly convex non-linear subproblems iteratively by approximating the objective and the constraints. The asymptotes are introduced to truncate the feasible region. Due to the special structure, the resulting subproblems can be solved by appropriate methods, e.g., New approach of the method of moving asymptotes (NAMMA) presented in chapter 4. To ensure global convergence, a line search procedure is introduced. Moreover, an active set strategy is applied to reduce computation time. The iterates of this new sequential programming methods are not always guaranteed to be inside the corresponding feasible feasible region described by the constraints. As a consequence it is not able to solve some kind of optimization problems, for example the free material optimization problems as the compliance function is only well-defined on the feasible region of some of the constraints, for more information see [START_REF] Zowe | Free material optimization via mathematical programming[END_REF][START_REF] Rios | Derivative-free optimization: a review of algorithms and comparison of software implementations[END_REF][START_REF] Kočvara | Solving stress constrained problems in topology and material optimization[END_REF]. We propose a modification of the resulting algorithm that ensures feasibility with respect to a given set of inequality constraints. The new procedure expands the resulting subproblems by additional nonlinear constraints, that are passed to the subproblem directly to ensure their feasibility in each iteration step. They are refereed as feasibility constraints. In addition, other constraints may be violated within the optimization process. As globalization technique a line search procedure and an iterative algorithm for unconstrained optimization are used to ensure convergence. The resulting subproblems can be solved explicitly thanks to the Lagrangian function. . these approximation functions are defined on the set I (k)

I (k) = I (k) 1 × I (k) 2 × ... × I (k) n , (5.3)
where

I (k) j =] -∞, d (k) j [∪]d (k)
j , +∞[. Thus, the resulting approximation of the objective function at an iterate

x (k) ∈ R n is f (k) (x) := f x (k) + n ∑ i=1   ∂ f x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + n ∑ i=1 σ (k) i 1 2 (x (k) i -d (k) i ) 3 x i -d (k) i + 1 2 (x (k) i -d (k) i (x i -2x (k) i + d (k) i ))
(5.4)

102

NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA

The non linear inequality constraints c j (x), j = 1, ..., m c , are approximated analogously to 5.20 by

c (k) j (x) := c x (k) + n ∑ i=1   ∂ c j x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + n ∑ i=1 σ (k) i 1 2 (x (k) i -d (k) i ) 3 x i -d (k) i + 1 2 (x (k) i -d (k) i (x i -2x (k) i + d (k) i ))
(5.5)

the vector σ (k) = σ (k) 1 , . . . , σ (k) n
T contains strictly positive parameters that are initially set and updated as stated later on in this chapter. and the moving asymptotes d (k) are defined by:

d (k) = x (k) + σ (k) (5.6)
We obtain the subsequent sub problem by applying the approximations 5.20 and 5.21,

min x f (k) (x) s.t. c (k) j (x) ≤ 0, j = 1, . . . , m c x i ∈ I (k) i , i = 1, . . . , n (5.7)
The functions are defined on the subset I (k) given by 5.3. The first and second derivatives of the convex approximations can be given analytically by

∂ f (k) ∂ x i (x) := ∂ f x (k) ∂ x i x (k) i -d (k) i 2 x i -d (k) i 2 + σ (k) i 2 x (k) i -d (k) i   1 - x (k) i -d (k) i 2 x i -d (k) i 2    (5.8) ∂ 2 f (k) (x) ∂ x i ∂ x j = 0, ∀i ̸ = j (5.9) ∂ 2 f (k) ∂ x 2 i (x) := - ∂ f x (k) ∂ x i x (k) i -d (k) i 2 x i -d (k) i 3 + σ (k) i x (k) i -d (k) i 3 x i -d (k) i 3 (5.10)
The derivatives for inequality constraints c (k) j (x), j = 1, . . . , m c , can be obtained by replacing f (x) by c j (x), j = 1, . . . , m c .

∂ 2 c (k) j ∂ x 2 i (x) := - ∂ c j x (k) ∂ x i x (k) i -d (k) i 2 x i -d (k) i 3 + σ (k) i x (k) i -d (k) i 3 x i -d (k) i 3 (5.11)

Position of the problem 103

It is easy to see that the functions are strictly convex:

f (k) x (k) = f x (k) , c (k) j x (k) = c j x (k) , ∀ j = 1, . . . , m c ∇ f (k) x (k) = ∇ f x (k) , ∇c (k) j x (k) = ∇c j x (k) , ∀ j = 1, . . . , m c f (k) convex, c (k) j convex, ∀ j = 1, . . . , m c f (k) separable, c (k)
j separable, ∀ j = 1, . . . , m c

(5.12)

We introduce the terms σ

(k)
i , ρ (k,l) and ρ (k,l) i

, i = 1, ..., m c in the functions f (k,l) and the constraints c

(k,l) j aims to approximate the second order information by a spectral parameters to reduce the number of derivatives calculated during the algorithm generated by our approximation. In the sequel a possible motivation for such terms is given, with the aim of analyzing the parameters σ (k) i , ρ (k,l) and ρ (k,l) i of the method.let us define the functions f (k,l) and c (k,l) j by:

f (k,l) (x) := f x (k) + n ∑ i=1   ∂ f x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + ρ (k,l) 2 n ∑ i=1 σ (k) i (x (k)
i -d (k) i ) 3 x i -d (k) i + (x (k) i -d (k) i (x i -2x (k) i + d (k) i )) = v x, x (k) , σ (k) + ρ (k,ℓ) w x, x (k) , σ (k) (5.13)
The non linear inequality constraints c j (x), j = 1, ..., m c , are approximated analogously to 5.20 by

c (k,l) j (x) := c j x (k) + n ∑ i=1   ∂ c j x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + ρ (k,l) j 2 n ∑ i=1 σ (k) i (x (k) i -d (k) i ) 3 x i -d (k) i + (x (k) i -d (k) i (x i -2x (k) i + d (k) i )) = v j x, x (k) , σ (k) + ρ (k,ℓ) j w j x, x (k) , σ (k) (5.14)
And then the approximating functions are chosen such that:

f (k,l) (x) := v (k) (x) + ρ (k,ℓ) w (k) (x) c (k,l) j (x) := v (k) j (x) + ρ (k,ℓ) j w (k) j (x) (5.15)
The parameters ρ (k,ℓ) i are strictly positive, and within an outer iteration k, the only difference between two inner iterations are the values of these parameters.

NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA

And then We obtain the new subsequent sub problem by applying the approximations 5.13 and 5.14, 5.16) where α 0 , α i , β i and γ i are real numbers such that α 0 > 0,α i ≥ 0, β i ≥ 0, γ i ≥ 0 and β i + γ i > 0 for i = 1,...,m. Moreover, α i , β i > α 0 for all i such that α i > 0. The constants β i must be chosen large enough so that the variables y i are zero at the optimal solution, in case the original problem has a nonempty feasible set. Problem (5.2) always has feasible points and at least an optimal solution, even if problem (5.1) has an empty feasible set; further, every local solution of problem (5.2) satisfies the Karush Kuhn-Tucker conditions, since the feasible set of problem (5.2) is qualied in the sense that it naturally fullls a regularity condition. A CCSA method for solving problem (5.2) performs k outer and ℓ inner iterations. The indices (k, ℓ) are used to denote the ℓth inner iteration within the kth outer iteration. Let consider the conservability condition

min x f (k,l) (x) + α 0 z + m ∑ i=1 β i y i + 1 2 γ i y 2 i s.t. c (k,l) j (x) -α i z -y i ≤ 0, j = 1, . . . , m c x i ∈ I (k) i , i = 1, . . . , n (
(C.C) :    f (k,l) x(k,l) ≥ f x(k,ℓ) , c (k,l) j x(k,l) ≥ c j x(k,ℓ) , ∀ j ∈ {0, 1, . . . , m c } (5.17)
Since computing second derivatives of the objective function f and the constraints c j , j = 1, ..., m c is not possible or need an expensive time to calculate, for this reason we are approximated respectively by the scalars

ρ (k,l) j σ (k) i , that is ∂ 2 f (k,l) ∂ x 2 i (x) = - ∂ f x (k) ∂ x i x (k) i -d (k) i 2 x i -d (k) i 3 + ρ (k,l) σ (k) i x (k) i -d (k) i 3 x i -d (k) i 3 ≈ ∂ 2 f (x) ∂ x 2 j (5.18) ∂ 2 c (k,l) j ∂ x 2 i (x) = - ∂ c j x (k) ∂ x i x (k) i -d (k) i 2 x i -d (k) i 3 + ρ (k,l) j σ (k) i x (k) i -d (k) i 3 x i -d (k) i 3 ≈ ∂ 2 c j (x) ∂ x 2 j (5.19)

Second order approximations

The approximations proposed in this chapter can be interpreted as a generalization of the method CONLIN, [START_REF] Fleury | Shape optimal design by the convex linearization method[END_REF][START_REF] Fleury | Conlin: an efficient dual optimizer based on convex approximation concepts[END_REF], in which each approximation f (k) and c

(k) j is obtained by a linearization of the original functions in variables of the type 1 x jd j .

f (k) (x) := f x (k) + n ∑ i=1   ∂ f x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + n ∑ i=1 σ (k) i 1 2 (x (k) i -d (k) i ) 3 x i -d (k) i + 1 2 (x (k) i -d (k) i (x i -2x (k) i + d (k) i ))
(5.20)

Rules for updating the parameters ρ

(k,l) i , σ (k)
j and the asymptotes d (k) . 105

c (k) j (x) := c x (k) + n ∑ i=1   ∂ c j x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + n ∑ i=1 σ (k) i 1 2 (x (k) i -d (k) i ) 3 x i -d (k) i + 1 2 (x (k) i -d (k) i (x i -2x (k) i + d (k) i ))
(5.21)

The second derivative of the approximations f (k) and c

(k) j are given by (5.10) and (5.11). Since the approximations f (k) and c (k) j are separable functions, its mixed second derivatives are zero. We suppose that the objective function f and the constraints inequality c j are twice continuously differentiable, and we use in addition of 5.12:

diag(H

(k) f (k) (x (k) )) = diag(H (k) f (x (k) )) (5.22) diag(H (k) c (k) j (x (k) )) = diag(H (k) c j (x (k) )) (5.23)
The parameter σ (k) are determined in such that the conditions 5.22 and 5.23 are satisfied. Therefore by a simple computation, we verify that σ (k) are explicitly given by:

σ (k) = diag(H (k) f (x (k) )).e + 2∇ f (x (k) ).R (k) , (5.24) σ (k)
, j = diag(H

(k) c j (x (k) )).e + 2∇c j (x (k) ).R (k) , (5.25)
5.4 Rules for updating the parameters ρ

(k,l) i , σ (k)
j and the asymptotes d (k) .

The updating of parameters ρ (k,l) i and σ (k) j discussed in the sequel are suggested in [START_REF] Gomes-Ruggiero | A spectral updating for the method of moving asymptotes[END_REF]. As far as the parameter ρ (k,l) i for l = 0 the following values are used:

ρ (1,0) = 1; ρ (k+1,0) = max 0.1ρ (k, l(k)) , ρ min , ρ (1,0) i = 1; ρ (k+1,0) i = max 0.1ρ (k, l(k)) i , ρ min i , (5.26)
where l(k) is the number of inner iterations necessary to complete the kth outer iteration and ρ min i is a fixed strictly positive number. In each inner iteration, the updating of ρ

(k,ℓ) i is based on the solution of the latest sub problem. If c (k,l) j x(k,l) < c j x(k,l) , it is chosen ρ (k,l+1) i such that c (k,l+1) j x(k,l) = c j x(k,l) which gives ρ (k,ℓ+1) i = ρ (k,ℓ) i + δ (k,ℓ) i where δ (k,ℓ) = f x(k,ℓ) -f (k,ℓ) x(k,ℓ) w (k) x(k,ℓ) δ (k,ℓ) i = c i x(k,ℓ) -c (k,ℓ) i x(k,ℓ) w (k) i x(k,ℓ) (5.27) 106 NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA Thus ρ (k,ℓ+1) = min (k,ℓ) 10ρ (k,ℓ) , 1.1 ρ (k,ℓ) + δ (k,ℓ) if δ (k,ℓ) > 0 ρ (k,ℓ+1) = ρ (k,ℓ) if δ (k,ℓ) ≤ 0 (5.28) ρ (k,ℓ+1) i = min (k,ℓ) 10ρ (k,ℓ) i , 1.1 ρ (k,ℓ) i + δ (k,ℓ) i if δ (k,ℓ) i > 0 ρ (k,ℓ+1) i = ρ (k,ℓ) i if δ (k,ℓ) i ≤ 0 (5.29)
The idea behind the updating of ρ i is to increase or remain the same value of this parameter at each inner iteration, but never reduce it. Therefore, it is important that they decrease whenever an outer iteration starts to avoid slow convergence and generation of a small steps in the process. In terms of the parameters σ

k) i (x) is diagonal with ∂ 2 w (k) i ∂ x 2 j (x) ≥ 1 σ (k) j (
2 for all j and x, This means that the curvature of the function w

i towards x j increases as σ

(k) j decreases. Thus, depending on the pattern of the variables in the previews iterations, they should be stabilized or released, according to the following rule. if k = 1 and k = 2:

σ (k) j = x max j -x min j 2 , (5.30)
and for k ≥ 3:

σ (k) j = γ (k) j σ (k-1) j , (5.31)
where

γ (k) j =          0.7 if x (k) j -x (k-1) j x (k-1) j -x (k-2) j < 0 1.2 if x (k) j -x (k-1) j x (k-1) j -x (k-2) j > 0 1 if x (k) j -x (k-1) j x (k-1) j -x (k-2) j = 0
(5.32)

The sub problems generated by these approximations can be solved explicitly, where the separability and the existence of an explicit solution of the functions f (k) (x) and c (k) j (x), j = 1, . . . , m c can be exploited. In each iteration k, the asymptotes have to be adapted. The update rules are presented in the following algorithm, where the value of d (k) changes according to the convergence or divergence of the iterative process and the monotony of the objective function, for more information about this subject see .... To update the parameters ρ i between two consecutive inner iterations we adapt the approach given in [START_REF] Gomes-Ruggiero | A spectral updating for the method of moving asymptotes[END_REF]. To update ρ (k,l) i for the indices i = 1, ..., n associated to the approximations (5.13) and (5.14) for which conservativity in x k,l) does not hold we proceed as follows:

5.4 Rules for updating the parameters ρ (k,l) i , σ (k) j and the asymptotes d (k) . 107

Algorithm 7 Update of parameters ρ (k,l) i 1: Compute s (k,ℓ) = x(k,ℓ)x (k) , and for the indices i = 1, ..., n associated to the approximations f (k,l) (x) and c

(k,l) j for which conservativity does not hold in x (k,l) , compute 1: For iteration k = 0, 1, . . . and constants L min < U max , ξ ≥ 0, 0 < C 1 < 1 and C 2 > 1 we compute for each i = 1, . . . , n 2:

2: y (k,ℓ) = ∇ f x(k,ℓ) -∇ f x (k) ; η (k,ℓ) = s (k,ℓ) T y (k,ℓ) s (k,ℓ) T s (k,ℓ) ; δ (k,ℓ) = f x(k,ℓ) -f (k,ℓ) x(k,ℓ) w (k) x(k,ℓ) 3: y (k,ℓ) j = ∇c j x(k,ℓ) -∇c j x (k) ; η (k,ℓ) j = s (k,ℓ) T y (k,ℓ) j s (k,ℓ) T s (k,ℓ) ; δ (k,ℓ) j = c j x(k,ℓ) -c (k,ℓ) j x(k,ℓ) w (k) j x(k,ℓ) 4: If 1.1(ρ (k,l) i + δ (k,l) i ) ≤ 10ρ (k,l) i thensetρ (k,l+1) i = 1.1(ρ (k,l) i + δ (k,l) i ) 5: Otherwise 6: ρ (k,ℓ) i < η (k,ℓ) i < 1.1 ρ (k,ℓ) i + δ (k,ℓ) i then set 7: ρ (k,ℓ+1) i = C 1 η (k,ℓ) i +C 2 1.1 ρ (k,ℓ) i + δ (k,ℓ) i with C1 +C2 = 1, C1,C2 ≥ 0 8: Now if η (k,ℓ) i > 1.1 ρ (k,ℓ) i + δ (k,ℓ) i then set: 9: ρ (k,ℓ+1) i = C 3 η (k,ℓ) i +C 4 1.1 ρ (k,ℓ) i + δ (k,ℓ) i with C3 +C4 = 1, C3,C4 ≥ 0 10: Finally if η (k,ℓ) i ≤ ρ (k,ℓ) i then set ρ (k,ℓ+1) i = 10ρ (
S (k) i :=    -1, if ∂ f (x (k) ) ∂ x i < 0 1, if ∂ f (x (k) ) ∂ x i > 0 3: B (k) i := S (k) i L min , if S (k) i < 0 S (k) i U max , if S (k) i > 0 4: k < 2 : d (k) i := x (k) i + S (k) i max 1, x (k) i 5: k ≥ 2 If sign x (k) i -x (k-1) i ̸ = sign x (k-1) i -x (k-2) i , then d (k) i := S (k) i min S (k) i (x (k) i + S (k) i max ξ ,C 1 x (k-1) i -d (k-1) i , B (k) i else d (k) i := S (k) i min S (k) i (x (k) i + S (k) i max ξ ,C 2 x (k-1) i -d (k-1) i , B (k) i
For the choice of the constants C 1 and C 2 , Svanberg [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] and Zillober al [START_REF] Zillober | Very large scale optimization by sequential convex programming[END_REF] propose respectively the values

(C 1 ,C 2 ) = (0.7, 1
) and (C 1 ,C 2 ) = (0.7, 1.15). Within the MMA procedure ξ = 0 and U max = -L min = ∞ and ξ > 0. These two constants are introduced in the the previous algorithm to distinguish two different situations. If sign x

(k) i -x (k-1) i ̸ = sign x (k-1) i -x (k-2) i
, the distance between the asymptotes is reduced to prevent oscillation. As a consequence the domain shrinks. Otherwise, the distance is enlarged to allow larger steps and to speed up convergence. To start the algorithm we must initialize the parameters values of the lower and upper asymptotes. Svanberg [START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF] determines these values in the first iteration dependent on box constraints of the original problem. Now we can formulate the corresponding NSCP algorithm:

(0) ∈ IR n . Set parameter ξ > 0, U max = -L min = ∞, C 2 > 1, 0 < C 1 < 1.
Compute f x (0) , ∇ f x (0) , c j x (0) , ∇c j x (0) , j = 1, . . . , m c •. ) by algorithm [START_REF] Bertsekas | Convex optimization algorithms[END_REF].

: Compute d (k) = x (k) + σ (k) (or we can compute d (k) by algorithm (8)). 8: Let f (k) (x), c (k)
j (x), j = 1, . . . , m c be defined by (5.20) and (5.21). 9: Generates the subproblem 5.7. Let x (k+1) be the optimal solution of the sub-problem. 10: Solves the sub-problem by Algorithm 6, obtaining x(k,l) . 11: Tests the conservativity condition 12: If (5.17) does not hold for some index i = 1, ..., m 13: Updating of the parameters ρ

ρ j > 0, j = 1, . . . , m c Φ ρ x y = f (x) + m c ∑ j=1      y j c j (x) + ρ j 2 c 2 j (x), if j ∈ J(x) - y 2 j 2ρ j , otherwise (5.34)
where y ∈ R m c are the corresponding Lagrangian multipliers. Moreover, we define the active set respect to the augmented Lagrangian by J(x) and its complement by J(x), • Let (x ⋆ , y ⋆ ) be stationary for problem 5.33 and let the gradients of the active constraints be linearly independent in x * , i.e., Definition 5.5.1 holds. Then there exists a positive parameter in x * is a local minimizer for Φ ρ x y ⋆ , ∀ρ ≥ ρ ⋆ Proof 13 See Fletcher [START_REF] Fletcher | An exact penalty function for nonlinear programming with inequalities[END_REF][START_REF] Fletcher | An ideal penalty function for constrained optimization[END_REF] To ensure strict convexity of the approximated objective function f (k) (x) and thus an unique solution of the subproblem, we suppose that the parameters σ (k) and ρ (k,l) are strictly positive to get respectively

J(x) := {1 ≤ j ≤ m e } ∪ m e + 1 ≤ j ≤ m c | - y j ρ j ≤ c j (x) J(x) := {m e + 1 ≤ j ≤ m c | j / ∈ J} (
∂ 2 f (k) (x) ∂ 2 x i > 0 and ∂ 2 f (k,l) (x) ∂ 2 x i > 0
holds for all i = 1, . . . , n. and we compute at the value of k) in 5.10 we find:

∂ 2 f (k) (x) ∂ 2 x i > 0 at x (
∂ 2 f (k) ∂ x 2 i (x (k) ) := σ (k) i - ∂ f (x (k) ) ∂ x i x (k) i -d (k) i > 0 (5.36) σ (k) i > ∂ f (x (k) ) ∂ x i x (k) i -d (k) i
(5.37)

The algorithm 5 ensure that

∂ f x (k) ∂ x i and x (k) i -d (k) i
has the same sign for all i = 1, . . . , n, then the right quotient of inequality 5.38 is always positive and the inequality is true. Doing the same computation for 5.5 A New Sequential Convex Programming for constrained equality and/or inequality optimization 111 inequality constraints, we find:

σ (k) i, j > ∂ c j (x (k) ) ∂ x i x (k) i -d (k) i j = m e + 1, . . . , m c . (5.38)
And the equality constraints c j (x), j = 1, . . . , m e , are linearized by:

c (k) j (x) := c j x (k) + n ∑ i=1 ∂ c j x (k) ∂ x i x i -x (k) i . ( 5.39)
The objective function f and the inequality constraints c j (x), j = m e + 1, . . . , m c are approximated respectively by 5.20 and 5.21. The first and second order derivatives of the convex approximations can be given analytically by 5.10 and 5.11. The corresponding subproblem is formulated by

min x f (k) (x) s.t. c (k) j (x) = 0, j = 1, . . . , m e c (k) j (x) ≤ 0, j = m e + 1, . . . , m c x i ∈ I (k) i , i = 1, . . . , n (5.40)
Due to strict convexity of the approximations of the resulting subproblem 5.40 possesses an unique solution. We denote by the primal solution of subproblem 5.40 in iteration k by z (k) ∈ R n and the dual solution by v (k) ∈ R m c . In each iteration, it is tested yields a sufficient descent with respect to the augmented Lagrangian merit function. Therefore, the so-called Armijo steplength algorithm, see Armijo [START_REF] Armijo | Minimization of functions having lipschitz continuous first partial derivatives[END_REF]is applied. In each iteration k, the stepsize γ (k,p) , with γ (k,0) := 1, is reduced by a constant factor α ∈ (0, 1) iteratively, i.e., γ (k,i+1) := αγ (k,i)

(5.41)

until the following condition is satisfied for the first time

Φ ρ (k) x (k) y (k) + σ (k,i) d (k) ≤ Φ ρ (k) x (k) y (k) + rσ (k,i) ∇Φ ρ (k) x (k) y (k) T d (k) , (5.42)
where r ∈ (0, 1) is constant and where the search direction s i , i = 1, . . . , n, are introduced, with estimate the curvature of the approximated function f (k) (x). From the Mean value Theorem of the integral calculus we know that, given a continuously differentiable function f : R n → R we have that f (y) = f (x) + ∇ f (x + α(yx)) T (yx), for some α ∈ (0, 1). Moreover, if f is twice continuously differentiable, then: Such approximation will be used in the iterative process of our method if conservativity 5.17 does not hold for some approximating function f (k) or c (k) j in x(k,ℓ) . In such case, the corresponding function is modified with an increased parameter ρ i , that is, by computing ρ

(k) d ∈ R n+m c is given by s (k) d := z (k) -x (k) v (k) -y (k) . ( 5
∇ f (y) = ∇ f (x) + 1 0 ∇ 2 f (x + α(y -x))dα(y -x) ( 5
(k,ℓ+1) i such that ρ (k,ℓ+1) i > ρ (k,ℓ) i
. The second order information contained in the spectral parameter is then used to obtain ρ (k,ℓ+1) i . The points used to compute the direction s are the current estimate x (k) and the solution of the latest subproblem x(k,ł) , that is, s (k,l) = x(k,ł)x (k) . It is also necessary to compute vector t if c j x (k) > 0 and ∇c j x (k) T z (k)x (k) ̸ = 0 or c j x (k) < 0 and ∇c j x (k) T z (k)x (k) > 0 then The constants c 1 and c 2 respectively prevents that the penalty parameters converge too slowly and ensures that these last one do not increase too quickly. Zillober [START_REF] Zillober | A globally convergent version of the method of moving asymptotes[END_REF] proposes to set c 1 = 2 and c 2 = 10. To prove global convergence we update the asymptotes d (k) as in the chapter 3. Zillober [START_REF] Zillober | A globally convergent version of the method of moving asymptotes[END_REF] proposed an algorithms to adapt carefully a lower and upper asymptotes L (k) and U (k) under certain conditions. The asymptotes need to be feasible according to the definition in chapter 3 to ensure convergence of the new sequential convex programming (NSCP) methods for the optimization problems with equality and inequality constraints. In general we can choose different asymptotes for the objective function and each constraint as in the algorithms 2-6 to improve the performance of the algorithm, even the computational effort is much higher, otherwise it is possible to update them according to algorithm 8. There are also many authors proposed different algorithms to compute iteratively these asymptotes. The main algorithm to solve the problem (5.33) can be introduced as: NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA Algorithm 11

1: Choose starting point x (0) ∈ IR n and y (0) .

Compute f x (0) , ∇ f x (0) , c j x (0) , ∇c j x (0) , j = 1, . . . , m c . Set parameters ω ∈ ]0; 1 [, r ∈ (0, 1), β ∈ (0, 1), τ > 0, c 2 > c 1 > 1 and penalty parameters ρ 3: Solve (5.40). Let z (k) be the optimal solution of (5.40) and v (k) the vector of the corresponding Lagrangian multipliers.

4: If z (k) = x (k) , then STOP. x (k) , v (k) is a KKT point of (5.33).

5: Let s

(k) d = z (k) -x (k) v (k) -y (k) , δ (k) := z (k) -x (k)
2 and η (k) as defined in (4.6). Let i = 0 and ρ (k,0) := ρ (k-1) .

6: Compute Φ ρ (k, i) x (k) y (k) , ∇Φ ρ (k,i)

x (k) y (k) , ∇Φ ρ (k,i)

x (k) y (k) T s (k) d 7: If ∇Φ ρ (k,i) x (k) y (k) T s (k)
d , update penalty parameters according to Algorithm 10. Let i = i + 1 and go to Step 6. Otherwise, let ρ (k) := ρ (k,i) , i = 0 and σ (k,0) := 1 8: Compute f x (k) + σ (k,i) z (k)x (k) , c j x (k) + σ (k,i) z (k)x (k) , j = 1, . . . , m c , and

Φ ρ (k)
x (k) y (k) + σ (k,i) d (k) . 9: if (5.42) is not satisfied then let σ (k,i+1) := β σ (k,i) , i = i + 1 and repeat (Armijo). Otherwise, σ (k) := σ (k,i) . Compute ∇ f x (k) , ∇c j x (k) , j = 1, . . . , m c and go to Step 1.

Sub problem (5.40) can be solved by the algorithm 9 or by an interior point method, see [START_REF] Andersen | Implementation of interior point methods for large scale linear programming[END_REF][START_REF] Gondzio | Interior point methods 25 years later[END_REF][START_REF] Pólik | Interior point methods for nonlinear optimization[END_REF][START_REF] Potra | Interior-point methods[END_REF]. And according to [START_REF] Zillober | A combined convex approximation-interior point approach for large scale nonlinear programming[END_REF], we can reduce the size of the primal-dual system of linear equations if the number of constraints and variables is too large. For more information about the convergence proof, the choice of the asymptotes to control the curvature o f the merit function, and some numerical results for problems resulting from topology optimization, see [START_REF] Ni | Sequential convex programming methods for solving large topology optimization problems: implementation and computational results[END_REF] 5.6 A feasible sequential convex programming based on the NAMMA In many applications, we get the optimization problem's domain specified by other constraints. Since most nonlinear optimization methods cannot ensure feasibility during the solution process, these problems cannot solved appropriately. For example if we get c 1 (x) := log (e 1 (x)) c 2 (x) := e 2 (x) (5.51) where e 1 (x) and e 2 (x) are nonlinear functions. To ensure that c 1 (x) and c 2 (x) can be evaluated, the constraints e 1 (x) > 0, e 2 (x) > 0, (5.52) need to be satisfied. Not that we require e 1 (x) > 0 and e 2 (x) > 0 such that c 1 (x) and c 2 (x) are continuously differentiable for all x satisfying (5.51).

To guarantee feasibility of a given subset of constraints in each iteration, We present an extended version of the algorithm 12, which the resulting algorithm assumed that the constraints c j (x), j = 1, . . . , m c and the objective function f (x) can only be evaluated, if all feasibility constraints e j (x) ≤ 0, j = 1, . . . , m f , are satisfied. We extend the problem (5.33) by an additional feasibility constraints e j (x), j = 1, . . . , m f . We get min The objective function f (x) and constraints c j (x), j = 1, . . . , m c are supposed to be at least continuously differentiable on the subset F := x ∈ R n |e j (x) ≤ 0, j = 1, . . . , m f (5.54)

The functions e j (x), j = 1, . . . , m f , must be convex and at least twice continuously differentiable on IR n , for more information about this subject, see [START_REF] Lehmann | A strictly feasible sequential convex programming method[END_REF]. As a consequence, F is convex, these last condition is important to guarantee domain's feasibility,when the stepsize is reduced during a line search procedure.

Let us start the procedure by taking a feasible point x (0) ∈ F, as the previews algorithms, this one generates a sequence of convex subproblems, which are easy to solve explicitly due to their special structure. Moreover, we need to check at each iteration k, if the nonlinear constraints are satisfied to ensure the their feasibility. The objective function f and the constraints c j , j = 1, . . . , m c , are approximated by convex and separable functions according to (5.20), (5.21) denoted by f (k) and c (k) j , j = 1, ..., m c , on the other hand we keep the constraints e j (x), j = 1, . . . , m f in the generated subproblems. We can assume that the functions e 1 (x), . . . , e m f (x) and their derivatives are much easier to evaluate than the other constraints, objective and their gradients. The resulting subproblems at an iteration k

min x f (k) (x) x ∈ R n s.t.
f (k) (x) := f x (k) + n ∑ i=1   ∂ f x (k) ∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + n ∑ i=1 σ (k) i 1 2 (x (k) i -d (k) i ) 3 x i -d (k) i + 1 2 (x (k) i -d (k) i (x i -2x (
∂ x i x (k) i -d (k) i 2 1 x (k) i -d (k) i - 1 x i -d (k) i   + n ∑ i=1 σ (k) i 1 2 (x (k)
id

(k) i ) 3 x i -d (k) i + 1 2 (x (k)
id

(k) i )(x i -2x (k) i + d (k) i ))
The asymptotes d

i , i = 1, ..., n, are defined explicitly as in algorithm 6, or according to the algorithm 8. The solution x (k) ∈ R n of (5.55) lies in the set F 3: Solve (5.40). Let z (k) be the optimal solution of (5.40) and v (k) the vector of the corresponding Lagrangian multipliers.

4: If z (k) = x (k) , then STOP. x (k) , v (k) is a KKT point of (5.33).

5: Let s

(k) d = z (k) -x (k) v (k) -y (k) , δ (k) := z (k) -x (k)
2 and η (k) as defined in (4.6). Let i = 0 and ρ (k,0) := ρ (k-1) .

6: Compute Φ ρ (k, i) x (k) y (k) , ∇Φ ρ (k,i)

x (k) y (k) , ∇Φ ρ (k,i)

x (k) y (k) T s (k) d 7: If ∇Φ ρ (k,i) x (k) y (k) T s (k)
d , update penalty parameters according to Algorithm 10. Let i = i + 1 and go to Step 6. Otherwise, let ρ (k) := ρ (k,i) , i = 0 and σ (k,0) := 1 8: Compute f x (k) + σ (k,i) z (k)x (k) , c j x (k) + σ (k,i) z (k)x (k) , j = 1, . . . , m c ,, e j x (k) + σ (k,i) z (k)x (k) , j = 1, . . . , m f and Φ ρ (k)

x (k) y (k) + σ (k,i) d (k) . 9: if (5.42) is not satisfied then let σ (k,i+1) := β σ (k,i) , i = i + 1 and repeat (Armijo). Otherwise, σ (k) := σ (k,i) . Compute ∇ f x (k) , ∇c j x (k) , j = 1, . . . , m c and go to Step 1.

CONCLUSION

The main focus of this dissertation is the development of new approach and algorithms based on the method of moving asymptote for solving the unconstrained and constrained optimization problems. The goal of these additional modifications is to improve the computational performance, reduction of calculation time and generalize these approach for a kind of constrained optimization problems, where the feasible region define by an inequality constraints called feasibility constraints. The remaining constraints, so-called regular constraints, may be violated. The classical methods yielding a feasible sequence of iterates. The algorithms proposed generate a sequence of feasible iterates, they require function and gradient evaluations at infeasible points, i.e, at each iteration we check if the iterate point satisfies the feasibility constraints. The corresponding algorithm solves continuous nonlinear programs iteratively, by a sequence of convex subproblems. On subproblem level, the objective function and the regular constraints are replaced by a rational, convex and separable approximations, and we include the feasibility constraints directly in the subproblems generated by the algorithm. We use a line search procedure to ensure a global convergence with respect to feasibility constraints. Note that the convexity of the subproblems is necessary to have an unique solution and then formulates a new subproblem from this solution.

The corresponding algorithms was adapted to become easy to implement for large scale problems and then can be solved. If exists, the sparse structure of the gradients and the Hessian is exploited. Moreover, linear constraints are approximated optionally. A modification of the approximations and an active set strategy are applied to reduce the size of the subproblems and thus speed up the solution process. To satisfy feasibility constraints in every main iteration, we apply the active strategy only for the regular constraints. A global convergence of the sequence generated is established under basic assumptions, and we show the performance of the algorithms proposed, by some numerical comparisons with a another well-known algorithms.

As future work, is to apply these algorithms in the free materiel optimization (FMO), where sparse, large-scale optimizations problems are to be solved. Proceeding from a finite element discretization the design of a structure is to be optimized, such that it becomes as stiff as possible. The compliance function measures the stiffness of the resulting structure dependent on the material properties in each finite element. In addition, the total amount of material is bounded. Moreover, feasibility constraints are introduced to ensure positive definiteness of the elementary stiffness matrices.

CONCLUSION "version française"

  line search is performed along the projected search direction d (k) P . To ensure feasibility, the problems have to be convex.

) Theorem 2 . 3 . 1

 231 With the above notation, let Ω ⊂ R be an open subset of the real line, a given twice continuously differentiable function f in Ω, x(0) ∈ Ω and x(k) being respectively the initial and a current point of the sequence x(k) k≥0

Proposition 2 . 3 . 3

 233 Let d(k) be a sequence of asymptotes, where w is a continuous function satisfying (2.11) and let the assumptions (2.4) valid. Then, d(k) is feasible if and only if

  k) ∈ R. A straightforward calculation shows that the first and the second-order partial derivatives of f (k) w have the following expressions:

Theorem 3 . 3 . 1

 331 With the above notation, let Ω ⊂ R n be an open subset, a given twice continuously differentiable function f in Ω, x(0) ∈ Ω and x(k) being respectively the initial and a current point of the sequence x(k) k≥0 .

j

  and x j -d(k) j have the same sign in the interval I (k) j , and for all x in

Lemma 3 . 3 . 3

 333 Let Assumption 7 be satisfied and let the sequence x(k) k≥0 be as defined in Theorem 3.3.2.

Lemma 3 . 3 . 5 Proof 8

 3358 Let Assumption 7-8 be satisfied and let the sequence x(k) k≥0 be as defined in Theorem 3.3.2.Assume that the starting point x0 belongs to the interval B r , where r is defined in Assumption 6. Then, all terms of the sequence x(k) k≥0 lie inside the ball B r . Indeed, combining inequalities (3.45), (3.50) of Lemmas 3.3.3 and 3.3.4 respectively, we immediately obtain

Algorithm 3

 3 Modified version for non separable function 1: Input a feasible point x (0) , and set k = 0 2: Repeat 3: k ⇐ k + 1, choose a permutation σ , 4: If σ := {1, . . . , n} 5: For i = 1, . . . , n 6: Solve by the algorithm 2 the n one-dimensional problems arg min

[ 3 ]

 3 method, Newton's method, the BFGS Method and the present paper. Here w(x) = (1 + |x|) -4 exp(-10 |x| 0.5 ) log(e + |x|)10 and α(k) = 3 1 + 1 10 c(k) .

f 2 :

 2 R × R -→ R (x, y)

. 10 )Figure 4 . 1 Figure 4 . 2

 104142 Figure 4.1 Graph of f (k) for different values of η

Theorem 4 . 2 . 1

 421 In above notation, let Ω ⊂ IR be an open set of the real line, a given twice differentiable strictly convex in Ω, x 0 ∈ Ω and x (k) being respectively the initial and a current point of the sequence {x (k) } k≥0 . Let the choice of the asymptotes be feasible. Then for each k ≥ 0 the approximated function f (k) is a strictly convex function on I (

2 . 1

 21 decrease when the iteration k increase and the distance between two successive distances converges to zero NEW APPROACH OF MOVING ASYMPTOTES METHOD

Figure 4 . 3 3 Theorem 4 . 2 . 5

 433425 Figure 4.3 Behavior of the sequence x (k)

28 )

 28 According to (4.6), (4.15) and (4.79) we have g Y(k)

(4. 65 ) 4 . 4 79 Proposition 4 . 4 . 2

 654479442 Presentation of our method in R ⋉ Let d (k) = d of asymptotes, M a constant such that M > 1 and let the assumptions 4.65 be valid. Then d(k) is feasible if and only if

Theorem 4 . 4 . 3

 443 With the above notation, let Ω ⊂ R n be an open subset, a given continuously differentiable function f in Ω, x (0) ∈ Ω and x(k) being respectively the initial and a current point of the sequence x (k) k≥0 .

Theorem 4 . 4 . 4

 444 Let consider the sequence x (k) defined by Theorem 4.4.3, Assume that ∇ f (x * ) = 0 for some x * ⊂ Ω. Then there exists an open ball

  i . For this new sequential convex programming method, the Hessian matrix ∇ 2 xx w

3 :

 3 If x (k) satisfies 4

Figure 4 . 4

 44 Figure 4.4 Convergence x (k) , X (k) and Y (k)

Figure 4 . 5 1 f

 451 Figure 4.5 The evaluation's number of η (k) for our algorithm and SPG method

Figure 5 . 1

 51 Figure 5.1 Scheme of convergence iterations

  this new sequential convex programming method, the Hessian matrix ∇ 2 xx w

Algorithm 8

 8 k,ℓ) i .108NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA Update of asymptotes d(k)

5. 5 A

 5 New Sequential Convex Programming for constrained equality and/or inequality optimization 109 Algorithm 9 NSCP algorithm 1: Choose starting point x

1 3: 4 :

 14 5.26) for i = 1, ..., m. Let k := Stopping criteria: If x (k) satisfies the KKT conditions of problem (5.2), stop and take x (k) as a solution. Determine (ρ (k,l) , ρ (k,l) i

5: Set l = 0 6 :

 6 If k > 1, compute ρ (k,l) and ρ (k,l) i for i = 1, ..., m as in (5.26) and σ (k) as in (5.30)-(5.32).

7

 7

14 :

 14 Start a new inner iteration. Set l = l + 1. Go to step 9. 15: Otherwise, set x (k+1) = x(k,l) , k = k + 1 and go to step 3.

5. 5 A( 5 . 33 )

 5533 New Sequential Convex Programming for constrained equality and/or inequality optimization5.5.1 A new algorithm based on the SCP method of ZilloberThe New Sequential Convex Programming for constrained equality and inequality optimization is an extension of the both methods MMA and NSCP. we proceed from the following optimization problem, where equality constraints are included additionally,min x f (x) x ∈ R n s.t. c j (x) = 0, j = 1, . . . , m e c j (x) ≤ 0, j = m e + 1, . . . , m cTo ensure the convergence of our method to the exact solution of the optimization problem, let us introduce a merit function and the corresponding line search procedure, The merit function combines the objective function and the constraints in a suitable way. we consider the augmented Lagrangian function Φ ρ : R n+m c → R for a given set of penalty parameters 110 NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA

. 43 )

 43 Condition 5.42 ensures a sufficient descent in the augmented Lagrangian merit function. To update the penalty parameter ρ (k) i , i = 1, . . . , m c , additional parameters η (k)

1 0∇ 2 f 1 0∇ 2 f 45 ∇ 2 f 2 j∇ 2 2 i

 1212452222 .44) 112 NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA By setting s = yx, the scalar t = ∇ f (y)-∇ f (x), or again by the Mean Value Theorem t = (x + αs)dα s, defines a Rayleigh quotient with respect to the average Hessian matrix (x + αs)dα . Such quotient has its value between the smallest and the largest eigenvalue of the average Hessian matrix, what motivates the terminology spectral parameter for 5.45. Thus , if we require that the Hessian of the functions c i and f are approximated by scalar matrices, we might say that ηI is the matrix of such type that best approximates the average Hessian [] The idea is to replace the diagonal of the Hessian matrix diag(H (k) f ) and diag(H (k) c j ) by the spectral parameter 5.(x) ≈ η 0 I ⇒ ∂ 2 f (x) ∂ x c j (x) ≈ η j I ⇒ ∂ 2 c j (x) ∂ x ≈ η j (5.47)

= 2 ( 5 . 50 ) 1 jj = 1 , 2 :

 2550112 ∇ f i x(k,l) -∇ f i x(k) for the indices i ∈ {0, 1, . . . , m} associated to the approximations f(k) or c (k) j that od not verify condition 5.17, so that: ,ℓ) T s (k,ℓ) j = 0, . . . , m c(5.48)The penalty parameters are updated until the descent property∇Φ ρ (k) x (k) y (k) T d (k) ≤ -η (k) δ (k)where δ (k) ∈ R denotes the norm of the search direction with respect to the primal variable x (k) , i.e.,δ (k) := z (k)x (k)Within the update loop the penalty parameters are denoted by ρk,i j j = 1, ..., m c , where i denotes the ith penalty parameter update within iteration k. ρk,0 j is initialized by ρk-..., m c . The corresponding update is described by Algorithm 10 according to Zillober[START_REF] Zillober | Scpip-an efficient software tool for the solution of structural optimization problems[END_REF].5.5 A New Sequential Convex Programming for constrained equality and/or inequality optimization 113Algorithm 10 Update of the penalty parameters 1: Let c 1 > 1, c 2 > c 1 be suitable constants. Let x (k) ∈ IR n and y (k) ∈ IR m c be respectively the current primal and dual variables. Moreover, (z (k) , v (k) ) is the solution of subproblem (5.40) defined in x (k) and ρ(k,i) j , j = 1, ..., m e , is a given penalty parameter. if j ∈ {1 ≤ j ≤ m e } or j ∈ m e + 1 ≤ j ≤ m c | -

else 11 :

 11 ρ (k,l+1) := κ 1 ρ (k,l) j

(- 1 2 :

 12 ) j > 0, j = 1, . . . , m c .Let k := 0 Determine d(k) for the objective and constraints as in Algorithm 6 or by Algorithm 8. Let f (k) (x), c (k) j (x), j = 1, . . . , m c be defined by (5.20) and(5.21). Formulate(5.40) for the corresponding iteration k.

  y (k) + σ (k) s (k) d , k := k + 1. 11:

xf

  (x) x ∈ R n s.t. c j (x) = 0, j = 1, . . . , m e c j (x) ≤ 0, j = m e + 1, . . . , m c e j (x) ≤ 0, j = 1, . . . , m f(5.53)

  c

j

  (x) = 0, j = 1, . . . , m e c (k) j (x) ≤ 0, j = m e + 1, . . . , m c e j (x) ≤ 0, j = 1, . . . , PROGRAMMING METHOD BASED ON THE MMA The approximations are defined by

.

  for j = m e + 1, ..., m c c (k) j (x) := c x (k)

58 )(y e ) 2 j 2 ( 1 : 2 :

 582212 To assure global convergence of the algorithm, we apply a line search procedure. Where the augmented Lagrangian merit function(5.34) include the feasibility constraints e j , j = 1, ..., m f , it can be defined by several ways. The most popular and communally used functional for the problem (5.53) is given by: e ) j e j (x) + (ρ e ) j 2 e 2 j (x), if -(y e ) j (ρ e ) j ≤ e j (x)ρ e ) j c ) j > 0, j = 1, . . . , m c , and (ρ e ) j > 0, j = 1, . . . , m f . Moreover, we denote the Lagrangian multipliers for the constraints c j (x), j = 1, . . . , m c , and the feasibility constraints e j (x), j = 1, . . . , m f by y c = (y c ) 1 , . . . , (y c ) m c T ∈ R m c , and y e = (y e ) 1 , . . . , (y e ) m f T ∈ R m f . The penalty parameters are updated according to Algorithm 10. We can summarize the algorithm adapted to the optimization problems with feasibility constraints as follows: 118 NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA Algorithm 12 Choose starting point x (0) ∈ IR n and y (0) . Compute f x (0) , ∇ f x (0) , c j x (0) , ∇c j x (0) , j = 1, . . . , m c . Set parameters ω ∈ ]0; 1 [, r ∈ (0, 1), β ∈ (0, 1), τ > 0, c 2 > c 1 > 1 and penalty parameters ρ (-1) j > 0, j = 1, . . . , m c . Let k := 0 Determine d (k) for the objective and constraints as in Algorithm 6 or by Algorithm 8. Let f (k) (x), c (k) j (x), j = 1, . . . , m c be defined by (5.20) and (5.21). Formulate (5.40) for the corresponding iteration k.

  y (k) + σ (k) s (k) d , k := k + 1. 11:

  Numerical result for non separable functions . . . . . . . . . . . . . . . . . . . . . . 4.1 Variation table of f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Variation table of f i i = 1, . . . , n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Convergence of x (k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Numerical tests for non-convex non separable functions . . . . . . . . . . . . . . . .

	1/4 exp(-20 |x|) and . . . . . . . . . . . . . . . 3.6 List of symbols α(k) = 5 1 + 1 7γ (k) 1 , 2 1 + 1 4γ (k) 2 , 4 1 + 1 3γ (k) 3 List of symbols number of primal variables , x ∈ R n n primal variable of dimension n, f (x) objective function , m e

  Assume Assumptions 1-5 hold. Let the assumptions of theorem 2.3.1 be valid and let s(k) be defined by(2.24). Then the sequence x(k)

	Analysis	35
	Theorem 2.3.5 k≥0

Table 2 .

 2 1 Numerical comparisons of the[START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF] method, Newton's method, the BFGS Method and the present method. Here w

		12 .	.	.	.	10 -14
	.		Newton div. .	.	.
	.		BFGS	div. .	.	.
	.		[3]	div. .	.	.
	.		Present 6	-1.156436	-896.585243e -003 .
	x(0) = -	1 4	.	.	.	.
	.		Newton 13	.	.	.
	.		BFGS	13	.	.	.
	.		[3]	5	-1.156436	-896.585243e -003 .
	.		Present 5	.	.	.
	f 2 (x)		.	.	.	.
	x(0) = 0.25	.	.	.	.	10 -15
	.		Newton div. .	.	.
	.		BFGS	div. .	.	.
	.		[3]	div. .	.	.
	.		Present 8	-1.231394	-7.166822	.
	x(0) = -10	.	.	.	.
	.		Newton 110 .	.	.
	.		BFGS	110 .	.	.
	.		[3]	114 -1.231394	-7.166822	.
	.		Present 107 .	.	.
	f 3 (x)		.	.	.	.
	x(0) = -2.5 .	.	.	.	10 -16

Table 2 .

 2

	10 100 79.44e+303 .	.	.	.
		.	Newton div. .	.
		.	BFGS	div. .	.
		.	[3]	div. .	.
		.	Present 241 -1.156436	-896.585243e -003
	x(0) = 40 * 10 60	-21.33e+183 .	.	.
		.	Newton div. .	.
		.	BFGS	div. .	.
		.	[3]	div. .	.
		.	Present 152 -1.156436	-896.585243e -003
	x(0) = -30 * 10 10	9.00e+033	.	.	.
	.	.	Newton 44	.	.
	.	.	BFGS	44	.	.
	.	.	[3]	div. -1.156436 -896.585243e -003
	.	.	Present 40	.	.
	f 2 (x)	.	.	.	.
	x(0) = 26	19.14e+292 .	.	.
	.	.	Newton div. .	.
	.	.	BFGS	div. .	.
	.	.	[3]	div. .	.
	.	.	Present 556 -1.231394	-7.166822
	x(0) = 10	13.44e+042 .	.	.	.
	.	.	Newton div. .	.
	.	.	BFGS	div. .	.

2 Numerical comparisons of the

[START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]

method, Newton's method, the BFGS Method and the present paper. Here w(x) = (1 + |x|) -4 exp(-10 |x| 0.5 ) * log(e + |x|)

10

.

  .45) Proof 6 Let us fix a positive integer k. Using (3.35) and (3.37) we may write

Table 3

 3

	.1 Numerical comparison of the [3] method, Newton's method, the BFGS Method and the
	present method. Here w(x) = (1 + |x|) 1/2 exp(-2 |x|) and α(k

Table 3 .

 3

	30 * 10 100 9.00e+303	.	.	.	.	10 -7
		.	Newton 340 .	.
		.	BFGS	340 .	.
		.	[3]	div. .	.
		.	Present 238 -4.306510 -6.809174
	x(0) = -21 * 10 50	30.87e+152 .	.	.	.	10 -12
		.	Newton 173 .	.
		.	BFGS	173 .	.
		.	[3]	div. .	.
		.	Present 127 -4.306510	-6.809174
	x(0) = 30 * 10 10	8.99e+033	.	.	.	.	10 -15
	.	.	Newton 44	.	.
	.	.	BFGS	44	.	.
	.	.	[3]	div. 3.482467	-2.230440e + 001
	.	.	Present 40	.	.

2 Numerical comparisons of the

Table 3 .

 3

	-1) .	.	.			.	10 -16
	. . .	Newton div. BFGS div. [3] 13. .	1.63198080556606e + 000 1.79370052598410e + 000	T	. -17.3991210151531e+000 . . . .
	.	Present 5				.
	x(0) = (0, 0)	.	.	.			.	10 -15
	. . .	Newton 8 BFGS 7 [3] 6	.	1.63198080556606e + 000 1.79370052598410e + 000	T	-17.3991210151531e+000 . . . .
	.	Present 4	.			.	.

3 Numerical comparisons of the

[START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]

method, Newton's method, the BFGS Method and the present method. Here w(x) = (1 + |x|) 1/2 exp(-2 |x|) and α(k

Table 3 .

 3

	15, 10) .	.	.			.	10 -16
	. . .	Newton div. BFGS div. [3] 17. .	-895.108649662366e -003 -918.740159643646e -003	T	. 8.13353253920338e+000 . . . .
	.	Present 10	.			.
	x(0) = (0, 0)	.	.	.			.	10 -15
	. . .	Newton 8 BFGS 7 [3] 6	.	-895.108649662366e -003 -918.740159643646e -003	T	. 8.13353253920338e+000 . .
	.	Present 4	.			.	.

[START_REF] Bakhtiari | A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent[END_REF]

Numerical comparisons of the

[START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]

method, Newton's method, the BFGS Method and the present method. Here w(x) = (1+|x|) 1/2 exp(-2 |x|) and α(k

Table 3 .

 3

		of variables N iter N eval f (X N ) ≃ min f (x)	CPU time (s)
	Wood's function
	2	7	28	452.7579 * 10 -30	0.004
	3	12	35	-8.776523408	0.025
	4	15	51	12.7068 * 10 -30	0.067
	Powell's function
	2	13	42	8.54987 * 10 -18	0.003
	3	18	60	36.0706 * 10 -21	0.006
	4	34	73	14.3158 * 10 -24	2.077
	Branins's function
	2	30	120	397.887357 * 10 -3 0.016

[START_REF] Bendsoe | An analytical model to predict optimal material properties in the context of optimal structural design[END_REF]

Numerical result for non separable functions Remark 3.5.1 it is easy to check that the values found in the tables correspond to the minima and minimizer of each test function by calculating the gradients of each function at the point x N , conclude that it's near to zero, and check that the Hessian matrix of this function at this point is positive definite.

Table 4 .

 4 .30) Let us consider the table of variation of the function f in the neighborhood of x *

	x	L min	x *	U max
	g(x)	-	0	+
	f (x)
			f min f min

1 Variation table of f From (4.79) and table 4.1 X (k) ∈ ]L min , x * [ ∀k ≥ 0, (4.31)

Table 4 .

 4 2 Variation table of f i i = 1, . . . , n 4.4 Presentation of our method in R ⋉

	85

Table 4 .

 4

	617630506282/225179981368, -279374430311/112589990684]	-14.9340	15.0000
	[ 223078909527/225179981368, 182554721441/56294995342]	11.4483	-11.4483
	[ -842808070846/450359962737, -883902943720/1801439850948]	-7.4670	7.4670
	[ -538277928635/11529215046, 533993220509/225179981368]	5.7241	-5.7241
	[ -249707534978/225179981368, 281738333164/225179981368]	-3.7335	3.7335
	[ -788656779056/900719925474, 90574356241/56294995342]	2.8621	-2.8621
	[ -474887365299/450359962737, 309754251127/225179981368]	-1.8667	1.8667
	[ -28147390804/28147497671, 675541441004/450359962737]	1.4310	-1.4310
	[ -450359974431/450359962737, 337769958694/225179981368]	-0.9334	0.9334
	[ -900719898758/900719925474, 675539955799/450359962737]	0.7155	-0.7155
	[ -225179984292/225179981368, 675539930747/450359962737]	-0.4667	0.4667
	[ -225179978029/225179981368, 337769974976/225179981368]	0.3578	-0.3578
	[ -450359962528/450359962737, 337769972144/225179981368]	-0.2333	0.2333
	[ -112589990671/112589990684, 675539944151/450359962737]	0.1789	-0.1789
	[ -450359962759/450359962737, 675539944053/450359962737]	-0.1167	0.1167
	[ -450359962710/450359962737, 337769972064/225179981368]	0.0894	-0.0894
	[ -450359962748/450359962737, 84442493009/56294995342]	-0.0583	0.0583
	[ -112589990681/112589990684, 675539944116/450359962737]	0.0447	-0.0447
	[ -56294995342/56294995342, 168884986023/112589990684]	-0.0292	0.0292
	[ -225179981365/225179981368, 84442493013/56294995342]	0.0224	-0.0224
	[ -112589990684/112589990684, 337769972049/225179981368]	-0.0146	0.0146
	[ -450359962733/450359962737, 168884986027/112589990684]	0.0112	-0.0112
	[ -225179981369/225179981368, 675539944102/450359962737]	-0.0073	0.0073
	[ -900719925470/900719925474, 337769972053/225179981368]	0.0056	-0.0056
	[ -450359962737/450359962737, 675539944103/450359962737]	-0.0036	0.0036
	[ -900719925472/900719925474, 675539944106/450359962737]	0.0028	-0.0028
	[ -28147497671/28147497671, 84442493013/56294995342]	-0.0018	0.0018
	[ -112589990684/112589990684, 42221246506/28147497671]	0.0014	-0.0014
	[ -56294995342/56294995342, 168884986026/112589990684]	-0.0009	0.0009
	[ -225179981368/225179981368, 84442493013/56294995342]	0.0007	-0.0007
	[ -112589990684/112589990684, 337769972052/225179981368]	-0.0005	0.0005
	[ -450359962736/450359962737, 168884986026/112589990684]	0.0003	-0.0003
	[ -225179981368/225179981368, 675539944105/450359962737]	-0.0002	0.0002
	[ -900719925473/900719925474, 337769972052/225179981368]	0.0002	-0.0002
	[ -450359962737/450359962737, 675539944105/450359962737]	-0.0001	0.0001
	[ -900719925474/900719925474, 675539944105/450359962737]	0.0001	-0.0001
	[ -1, 337769972052/225179981368]	-0.0001	0.0001
	[ -450359962737/450359962737, 3/2]	0.0000	-0.0000
	[ -1, 3/2]	-0.0000	0.0000

[START_REF] Bachar | A moving asymptotes algorithm using new local convex approximation methods with explicit solutions[END_REF]

Convergence of x

(k)

Table 4 .

 4

			4 Numerical tests for non-convex non separable functions
	function x 0	Minimizer x *	Minimum	CPU time(s)
	f		(1, 1, . . . , 1)	+ f * = 0	2D 0.001 3D 0.030
	g		(1, 1, . . . , 1)	g * = 0	2D 0.004 3D 0.020
		(3, 2)	(-2.80511808695, 3.13131251825)		0.051
	h	(50, 35) (3.584428340330, -1.84812652696) (2, 2.5) (3.0, 2.0)	h * = 0	0.021 0.025
		(5, 3)	(-3.77931025337, -3.28318599128)		0.007

  5.35) It can be check easily that Φ ρ x y is differentiable. The penalty parameters ρ ∈ R m c must be carefully adapted during the solution process to guarantee a sufficient descent and global convergence, see[START_REF] Schittkowski | On the convergence of a sequential quadratic programming method with an augmented lagrangian line search function[END_REF]. Choosing the augmented Lagrangian merit function is motivated by the following properties, see[START_REF] Zillober | Global convergence of a nonlinear programming method using convex approximations[END_REF]:

	Definition

5.5.1

The linear independence constraint qualification (LICQ) is satisfied at a feasible solution x ∈ F, if the gradients of the active constraints are linearly independent at x. Lemma 5.5.2

• A point (x ⋆ , y ⋆ ) is stationary for Φ ρ x y defined by 5.34 for a positive fixed ρ ∈ R m c , if and only if it is stationary for problem 5.33.

  L'objectif principal de cette thèse est le développement des nouvelles approches et algorithmes basés sur la méthode des asymptotes mobiles pour résoudre les problèmes d'optimisation avec et sans contraintes. Le but de ces modifications est d'améliorer les performances de calcul, de réduire le temps de calcul et de généraliser ces approches pour une sorte de problèmes d'optimisation avec contraintes, où la région réalisable est définie par des contraintes d'inégalité appelée contrainte de faisabilité. Les contraintes restantes, les contraintes dites régulières, peuvent être violées. Les méthodes classiques donnent une séquence d'itérations qui peut ne pas satisfaire ces contraintes de faisabilité. Les algorithmes proposés génèrent une séquence d'itérations réalisables, ils nécessitent des évaluations de fonction et de gradient en des points irréalisables, c'est-à-dire qu'à chaque itération on vérifie si le point d'itération satisfait les contraintes de faisabilité. L'algorithme correspondant résout les programmes non linéaires continus de façon itérative, par une séquence de sous-problèmes convexes. Au niveau des sous-problèmes, la fonction objective et les contraintes régulières sont remplacées par une approximation rationnelle, convexe et séparable, et nous intégrons les contraintes de faisabilité directement dans les sous-problèmes générés par l'algorithme. Nous utilisons une procédure de recherche de lignes pour assurer une convergence globale par rapport aux contraintes de faisabilité. Notez que la convexité des sous-problèmes est nécessaire pour avoir une solution unique et formule ensuite un nouveau sous-problème à partir de cette solution. Les algorithmes correspondants ont été adaptés pour devenir faciles à mettre en oeuvre pour des problèmes à grande échelle et peuvent ensuite être résolus. S'il existe, la structure clairsemée des gradients et de la Hesse est exploitée. De plus, les contraintes linéaires sont approximées facultativement. Une modification des approximations et une stratégie d'ensemble active sont appliquées pour réduire la taille des sous-problèmes et ainsi accélérer le processus de solution. Pour satisfaire les contraintes de faisabilité dans chaque itération principale, nous appliquons la stratégie active uniquement pour les contraintes régulières. Une convergence globale de la séquence générée est établie à partir d'hypothèses de base, et nous montrons la performance des algorithmes proposés, par quelques comparaisons numériques avec d'autres algorithmes bien connu. Comme travail futur, il s'agit d'appliquer ces algorithmes dans l'optimisation du matériel libre (FMO), où des problèmes d'optimisations clairsemés et à grande échelle doivent être résolus. En partant d'une discrétisation par éléments finis, la conception d'une structure doit être optimisée, afin qu'elle devienne aussi rigide que possible. La fonction de conformité mesure la rigidité de la structure résultante en fonction des propriétés du matériau dans chaque élément fini. De plus, la quantité totale de matériel est limitée. De plus, des contraintes de faisabilité sont introduites pour assurer une définition positive des matrices élémentaires de rigidité.

Au chapitre 5, une extension de la nouvelle approche de la méthode de déplacement des asymptotes présentée au chapitre 4 pour les problèmes d'optimisation contraints est proposée, basée sur les méthodes de programmation séquentielle convexe proposées par[START_REF] Zillober | Very large scale optimization by sequential convex programming[END_REF]. L'idée est d'inclure les informations de second ordre fournies par ce paramètre dans les fonctions du modèle qui définissent les approximations rationnelles de la fonction objectif et les contraintes non linéaires, aux dépens d'évaluations de gradient supplémentaires par itération interne. Le paramètre spectral permet de conserver la séquence générée de façon pratique et conservatrice par rapport aux fonctions d'origine, tout en préservant la propriété de convergence globale. En ce qui concerne la fonction objectif, des approximations conservatrices assurent des valeurs décroissantes monotones, alors que pour les contraintes, la faisabilité d'un problème est garantie. La convexité stricte et la séparabilité du modèle sont conservées afin que les sous-problèmes aient une solution unique.Enfin, le chapitre 6 donne les conclusions de cette thèse et quelques suggestions pour les travaux futurs.

At each iteration, an explicit solution of the current sub problems generate a new sub problem close to the solution of original problem.

Acknowledgements

Acknowledgments Above all, I would like to thank the God almighty, my supreme creator for giving me the strength, the patience and the opportunity to achieve my best dream in the best possible conditions.

Firstly, I would like to address my sincere gratitude to my supervisors Prof. Allal Guessab and Prof. Otheman Nouisser for their support, their encouragements and their valuable guidance. I am very grateful for their valuable time spent in guiding my research and on sharing with me their expertise and their know-how. Finally, I would also like to say how much I appreciate their great availability and their professional and personal qualities.

My thanks must go also to my reporters Prof. ACHCHAB Boujemaa Prof. Dell'accio Francesco and Prof. Domingo Barrera for their precious time given for reading my dissertation and examine my works and also for establishing their reports. I am very thankful for their valuable comments which greatly improved the readability of my dissertation. I would also like to express my thanks to Prof. BENSOUDA Charaf for giving me the honor of chairing my jury as well as Prof. BECKER Roland and Prof. Belmahjoub Fayçal, to accept to be a member of my dissertation committee.

NEW SEQUENTIAL CONVEX PROGRAMMING METHOD BASED ON THE MMA

Position of the problem

We consider the general nonlinear optimization problem min x f (x) s.t. c j (x) ≤ 0, j = 1, . . . , m c x min i

where f (x) and c j (x) , j = 1, . . . , m c , are at least continuously differentiable on R n , x min j and x max j are given real numbers such that x min j < x max j for each j . Following Svanberg's approach, artificial variables y = (y 1 , . . . , y m ) T and z ∈ R are introduced, so that the following enlarged problem is addressed:

where α 0 , α i , β i and γ i are real numbers such that α 0 > 0, α i ≥ 0, β i ≥ 0, γ i ≥ 0 and β i + γ i > 0 for i = 1, . . . , m. Moreover, α i β i > α 0 for all i such that α i > 0. The constants β i must be chosen large enough so that the variables y i are zero at the optimal solution. First we will talk about the so-called method of moving asymptotes (MMA), see [START_REF] Svanberg | The method of moving asymptotes-a new method for structural optimization[END_REF][START_REF] Svanberg | A globally convergent version of mma without linesearch[END_REF][START_REF] Svanberg | The method of moving asymptotes-modelling aspects and solution schemes[END_REF][START_REF] Svanberg | A class of globally convergent optimization methods based on conservative convex separable approximations[END_REF][START_REF] Svanberg | Mma and gcmma, versions september[END_REF]. MMA is a non linear programming approximation that creates a sequential of convex and separable sub problems, which are easy to solve due to their special structure. We solve the sub problems generated by these approximations and we use the resulting primal solution x (k) ∈ R n in the corresponding iteration k to formulate a new sub problem. MMA achieves good results in practice, although no convergence proof is given. The idea behind the approximations presented in this chapter is the segmentation of the ndimensional problem space into n one-dimensional spaces. One of the fundamental features is the introduction of the spectral parameters and a descent direction in the flexible asymptote d i , i = 1, ..., n, for each optimization variable x i , i = 1, ..., n, which truncate the feasible region. Important additional features are:

1. A rational approximations of the non linear inequality constraints and the objective function with respect to a flexible asymptotes d i , i = 1, ..., n depending on a parameter σ i , i = 1, ..., n at the current iteration point.

2. General algorithm applicable to any large and sparse non linear problem.

3. Generation of convex and separable sub problems has an explicit solution,i.e, diagonal Hessian matrices of the lagrangian function.