O. Quadratique-dans, adire lorsque la fonction objective q satisfait q(?x) = ? 2 q(x) pour ? ? R et avec contraintes de bo??tebo??te : de la forme x ? [?1, 1] d . La classe desprobì emes quadratiques homogénéisés avec contraintes de bo??tebo??te contientégalementcontientégalement lesprobì emes dont la fonction objective est de la forme x T Qx + b T x puisqu'il suffit d'ajouter une variable t ? [?1, 1] pour le rendre homogène (prendre x T Qx + tb T x comme fonction objective) En reprenant notre notation, les conditions duprobì eme sont les suivantes : les matrices A f i ont pour entrée 1 pour la coordonnée (i, i) et 0 ailleurs

. Dans, Ye montre que ce résultat demeure vrai si on ajoute des contraintes d'´ egalités quadratiques

. Zhang, lorsque tous les termes hors diagonale de la matrice Q f 0 sont positifs ou nuls alors Val(QP ) = Val(ShorD) Dans le [Zha00, Theorem 4], Zhangétend Zhangétend son précédent résultat aux matrices Q f 0 telles qu'il existe ? ? {?1, 1} d+1 satisfaisant Q f 0 (i, j)? i ? j ? 0 pour tout i, j, i = j (Zhang appelle cette condition, la condition de almost OD-nonnegative) Par ailleurs

. Val, contraintes Q f i et Q f 0 ont deséléments deséléments hors diagonale positifs ou nuls, ou d` es que la famille des (Q f i ) i={1...,m} vérifie une condition almost OD-nonnegative uniforme. Plusieurs travaux [Mor93, SW95, BTT96, Pol98] font mention du cas particulier des probì emes quadratiques avec une unique contrainte (i.e. m = 1) : s'il existe ? ? 0 tel que A f 0 ? ?A f 1 ? S d ? alors Val(QP ) = Val(ShorD), ShorD) demeure vrai d` es que toutes les matrices des

R. , ×. R. , and ?. T}, L'optimisation sur le cône du second ordre consistè a contraindre les variables duprobì emè a apparteniràappartenirà un cône de Lorentz pour une certaine dimension, Pour 8.2. CARACTÉRISATIONCARACT´CARACTÉRISATION DU PLUS PETIT POINT FIXE (-4

U. Mot-sur-l-'implémentationimpl´implémentation and . De-l-'analyseur-le-prototype-se-met-en-pause-jusque-la-touche, entrée " soit enfoncée et l'itération sur les politiques se met en route Le prototype utilise l'heuristique classique de la définition 3.10 pour choisir la politique initiale : c'est-` a-dirè a chaque point de contrôle d` es qu'il y a une intersection. Par exemple, au point de contrôle 11, pour la variable x, le prototype retourne le texte suivant : Choix Politique Initiale Politique gauche pour l'inf pour x[11]: oo Politique droite pour l'inf pour x[11]: max(x(-)[10],x(-)[15]) Choix politique pour l'inf pour x, Politique gauche pour le sup pour x[11]: max(y(+)[10],y(+)

A. A. Adjé, S. Gaubert, and E. Goubault, De plus, on pourrait construire une itération sur les politiques (croissante) pour calculer un point fixe négatif de la semidifférentielle. Lorsqu'un point fixe est le plus petit, l'itération sur les politiques retournerait le point fixe nul, dans le cas contraire, cette itération fournirait une direction de descente Infinite Dimensional Analysis 3rd Edition Coupling policy iteration with semidefinite relaxation to compute accurate numerical invariants in static analysis, aux fonctions stables sur les rationnels. On utiliserait la structure discrète des rationnels, 2006.

A. Adjé, S. Gaubert, and E. Goubault, Computing the smallest fixed point of nonexpansive mappings arising in game theory and static analysis of programs, Proceedings of MTNS'08, 2008.

S. Xavier-allamigeon, E. Gaubert, . Goubault, M. Inferring-min, ]. A. Max-plus-polyhedraagg10 et al., Inferring Min and Max Invariants Using Max-Plus Polyhedra, Proceedings of the 15th International Static Analysis Symposium Programming Languages and Systems, pp.189-204, 1977.
DOI : 10.1007/978-3-540-69166-2_13

]. B. Bcc-+-02, P. Blanchet, R. Cousot, J. Cousot, L. Feret et al., Design and implementation of a special-purpose static program analyzer for safety-critical real-time embedded software

]. A. Bec07 and . Beck, Quadratic matrix programming, SIAM Journal on Optimization, vol.17, issue.4, pp.1224-1238, 2007.

]. A. Bec09 and . Beck, Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming, Journal of Optimization Theory and Applications, vol.142, issue.10, pp.1-29, 1007.

]. R. Bel52 and . Bellman, On the theory of dynamic programming, Proceedings of the National Academy of Sciences of the U.S.A, pp.716-719, 1952.

]. R. Bel57 and . Bellman, Dynamic Programming, 1957.

M. [. Blyth and . Janowitz, Residuation Theory, 1972.

]. F. Bla95 and . Blanchini, Nonquadratic lyapunov functions for robust control, Automatica, vol.31, pp.451-461, 1995.

]. F. Bou93 and . Bourdoncle, Efficient chaotic iteration strategies with widenings, Proceedings of the International Conference on Formal Methods in Programming and their Applications, pp.128-141, 1993.

B. [. Brualdi and . Shader, Matrices of Sign-Solvable Linear Systems. Number 116 in Cambridge Tracts in Mathematics, 1995.

A. [. Bonnans and . Shapiro, Perturbation Analysis of Optimization Problems, 2000.
DOI : 10.1007/978-1-4612-1394-9

A. [. Ben-tal, E. Ben-israel, and . Rosinger, A helly-type theorem and semiinfinite programming, pp.127-135, 1979.

M. [. Ben-tal and . Teboulle, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Mathematical Programming, vol.47, issue.1, pp.51-63, 1996.
DOI : 10.1007/BF02592331

]. S. But30 and . Butterworth, On the theory of filter amplifiers, Wireless Engineer, vol.7, pp.536-541, 1930.

L. [. Boyd and . Vandenberghe, Convex optimization, 2004.

P. Cousot and R. Cousot, Static determination of dynamic properties of programs, Proceedings of the Second International Symposium on Programming, pp.106-130, 1976.

R. [. Cousot and . Cousot, Abstract interpretation, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages , POPL '77, pp.238-252, 1977.
DOI : 10.1145/512950.512973

URL : https://hal.archives-ouvertes.fr/inria-00528590

]. P. Cc92a, R. Cousot, and . Cousot, Abstract interpretation frameworks, Journal of Logic and Computation, vol.2, issue.4, pp.511-547, 1992.

]. P. Cc92b, R. Cousot, and . Cousot, Comparing the Galois connection and widening/narrowing approaches to abstract interpretation, invited paper, Proceedings of the International Workshop Programming Language Implementation and Logic Programming, PLILP '92, pp.13-17, 1992.

E. [. Clarke and . Emerson, Design and synthesis of synchronization skeletons using branching time temporal logic, Logics of Programs, pp.52-71, 1982.
DOI : 10.1007/BFb0025774

A. Costan, S. Gaubert, E. Goubault, M. Martel, and S. Putot, A Policy Iteration Algorithm for Computing Fixed Points in Static Analysis of Programs, Proceedings of the 17th International Conference on Computer Aided Verification (CAV'05), pp.462-475, 2005.
DOI : 10.1007/11513988_46

N. [. Cousot and . Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages , POPL '78, pp.84-97, 1978.
DOI : 10.1145/512760.512770

]. A. Con93 and . Condon, On algorithms for simple stochastic games, Advances in Computational Complexity Theory, pp.51-73, 1993.

G. Cochet-terrasson, . Cohen, . Gaubert, J. Mcgettrick, and . Quadrat, Numerical computation of spectral elements in max-plus algebra, Proc. IFAC Conf. on Syst. Structure and Control, 1998.

J. Cochet-terrasson, S. Gaubert, and J. Gunawardena, A constructive fixed point theorem for min-max functions, Dynamics and Stability of Systems, vol.14, issue.4, pp.407-433, 1999.
DOI : 10.1080/026811199281967

]. J. Dan67 and . Danskin, The Theory of Max Min, 1967.

[. Dhingra and S. Gaubert, How to solve large scale deterministic games with mean payoff by policy iteration, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools , valuetools '06, 2006.
DOI : 10.1145/1190095.1190110

E. Dijkstra, Notes on structured programming, 1970.

]. J. Doo93 and . Doob, Measure Theory, 1993.

]. H. Eve57 and . Everett, Recursive games, Contributions to the Theory of Games, pp.47-78, 1957.

[. Feron and F. Alegre, Control software analysis, part I : Open-loop properties, 2008.

]. E. Fa08b, F. Feron, and . Alegre, Control software analysis, part II : Closed-loop analysis, p.812, 1986.

]. J. Fer04 and . Feret, Static analysis of digital filters, European Symposium on Programming number 2986 in LNCS, 2004.

]. K. For91 and . Forsman, Construction of lyapunov functions using gröbner bases, Proc. of the 30th Conf. on Decision and Control, pp.798-799, 1991.

T. [. Filar and . Raghavan, Algorithms for stochastic games-a survey, Zeitschrift für Operations Research, vol.35, pp.437-472, 1991.

[. Friedmann, An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it, 2009 24th Annual IEEE Symposium on Logic In Computer Science, pp.145-156, 2009.
DOI : 10.1109/LICS.2009.27

K. [. Filar and . Vrieze, Competitive Markov Decision Processes, 1997.
DOI : 10.1007/978-1-4612-4054-9

J. [. Gaubert and . Gunawardena, The perron-frobenius theorem for homogeneous monotone functions, Transactions of the American Mathematical Society, vol.356, issue.12, pp.4931-4950, 2004.
DOI : 10.1090/S0002-9947-04-03470-1

E. [. Gaubert, A. Goubault, S. Taly, and . Zennou, Static Analysis by Policy Iteration on Relational Domains, Proceedings of European Symposium Of Programming, pp.237-252, 2007.
DOI : 10.1007/978-3-540-71316-6_17

. Ghk-+-80-]-g, K. H. Gierz, K. Hofmann, J. D. Keimel, M. Lawson et al., A compendium of continuous lattices, 1980.

]. D. Gil57 and . Gillette, Stochastic games with zero stop probabilities, Contributions to the Theory of Games, pp.179-188, 1957.

]. H. Gim06 and . Gimbert, Jeux positionnels, 2006.

D. [. Garey and . Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979.

R. [. Gaubert, S. Katz, and . Sergeev, Tropical linear-fractional programming and parametric mean payoff games, Third international Workshop on Invariant Generation, 2010.
DOI : 10.1016/j.jsc.2011.12.049

URL : https://hal.archives-ouvertes.fr/hal-00782737

M. [. Goberna and . López, Linear semi-infinite programming theory: An updated survey, European Journal of Operational Research, vol.143, issue.2, pp.390-405, 2002.
DOI : 10.1016/S0377-2217(02)00327-2

L. [. Grötschel, A. Lovász, and . Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol.2, 1988.

E. Goubault and S. Putot, A zonotopic framework for functional abstractions, Formal Methods in System Design, vol.2, issue.1???4
DOI : 10.1007/s10703-015-0238-z

E. Goubault, S. Putot, P. Baufreton, J. Gassinogs07a-]-t, H. Gawlitza et al., Static Analysis of the Accuracy in Control Systems: Principles and Experiments, Formal Methods for Industrial Critical System Programming Languages and Systems71316-6_21. [GS07b] T. Gawlitza and H. Seidl. Precise relational invariants through strategy iteration, pp.3-20, 2007.
DOI : 10.1007/978-3-540-79707-4_3

. [. Springer, H. Gawlitza, A. Seidl, S. Adjé, E. Gaubert et al., Abstract interpretation meets convex optimization. Submitted to Journal Symbolic of Computa- tion. [Gun94] J. Gunawardena. Min-max functions. Discrete Event Dynamic Systems Generalized semiinfinite programming : A tutorial, J. Comput. Appl. Math, vol.4, issue.2172, pp.377-406394, 1994.

X. Michel, D. P. Goemans, . J. Williamsonhk66-]-a, K. Hoffman, K. O. Hettich et al., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming On nonterminating stochastic games Semi-infinite programming : theory, methods and applications An axiomatic basis for computer programming Rigorous error bounds for the optimal value in semidefinite programming Computation of piecewise quadratic lyapunov functions for hybrid systems Lurupa -rigorous error bounds in linear programming, How60] R. Howard. Dynamic Programming and Markov Processes. WileyJR98] Mikael Johansson and Anders Rantzer Algebraic and Numerical Algorithms and Computer-assisted Proofs, pp.1115-1145359, 1960.

M. [. Kim and . Kojima, Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods and Software, pp.201-224, 2000.

M. [. Kim and . Kojima, Exact solutions of some nonconvex quadratic optimization problems via sdp and socp relaxations, Computational Optimization and Applications, vol.26, issue.2, pp.143-1541025794313696, 1023.
DOI : 10.1023/A:1025794313696

]. S. Kle52 and . Kleene, Introduction to Metamathematics, 1952.

J. Leroux and G. Sutre, Accelerated Data-Flow Analysis, Static Analysis, 14th International Symposium Proceedings, pp.184-199, 2007.
DOI : 10.1007/978-3-540-74061-2_12

URL : https://hal.archives-ouvertes.fr/hal-00346005

J. Leroux and G. Sutre, Acceleration in Convex Data-Flow Analysis, Foundations of Software Technology and Theoretical Computer Science, 27th International Conference Proceedings, pp.520-531, 2007.
DOI : 10.1007/978-3-540-77050-3_43

URL : https://hal.archives-ouvertes.fr/hal-00346295

]. M. Ls07c, G. López, and . Still, Semi-infinite programming, European Journal of Operations Research, vol.180, pp.491-518, 2007.

C. [. Leveson and . Turner, An investigation of the Therac-25 accidents, Computer, vol.26, issue.7, pp.18-41, 1993.
DOI : 10.1109/MC.1993.274940

]. J. Lö04 and . Löfberg, Yalmip : A toolbox for modeling and optimization in MATLABMar98] F. Martin. PAG ? an efficient program analyzer generator, Proceedings of the CACSD Conference, pp.46-67, 1998.

]. M. Mar02 and . Martel, Static analysis of the numerical stability of loops, Static Analysis, pp.3-14, 2002.

J. Glenford, T. Myers, T. M. Badgett, C. Thomas, I. Sandler et al., The Art of Software Testing, 2004.

]. A. Min01a and . Miné, A new numerical abstract domain based on difference-bound matrices

A. Miné, Weakly Relational Numerical Abstract Domains, 2004.

]. J. Mor70 and . Moreau, Inf-convultion, sous-additivé, convexité des fonctions numériques, Journal Mathématiques de Pures et Appliquées, vol.49, pp.109-154, 1970.

]. J. Mor93 and . Moré, Generalizations of the trust region problem, Optimization Methods and Software, vol.2, pp.189-209, 1993.

R. [. Mallet-paret and . Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators. Discrete and Continuous Dynamical Systems, pp.519-562, 2002.

A. [. Nesterov and . Nemirovski, Interior point polynomial algorithms in convex programming, Society for Industrial and Applied Mathematics, 1994.
DOI : 10.1137/1.9781611970791

]. R. Nus86 and . Nussbaum, Convexity and log convexity for spectral radius, Linear Algebra And Its Applications, pp.59-122, 1986.

]. R. Nus88 and . Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Memoirs of the AMS, vol.75, issue.391, 1988.

]. G. Ols91 and . Olsder, Eigenvalues of dynamical max-min systems, Discrete Event Dynamic Systems, vol.1, pp.177-207, 1991.

]. O. Ore44 and . Ore, Galois connexions. Transactions of, pp.493-513, 1944.

]. S. Ovc02 and . Ovchinnikov, Max-min representation of piecewise linear functions. Contributions to Algebra and Geometry, pp.297-302, 2002.

]. B. Pol98 and . Polyak, Convexity of quadratic transformations and its use in control and optimization, Journal of Optimization Theory and Applications, vol.99, issue.10, pp.553-5831021798932766, 1023.

M. [. Pardalos and . Ramana, Semidefinite programming, Interior Point Methods of Mathematical Programming, pp.369-398, 1997.

J. [. Queille and . Sifakis, Specification and verification of concurrent systems in CESAR, International Symposium on Programming, pp.337-351, 1982.
DOI : 10.1007/3-540-11494-7_22

]. H. Ric53 and . Rice, On completely recursively enumerable classes and their key arrays. Transaction of the, pp.358-366, 1953.

]. R. Roc84 and . Rockafellar, Directional differentiability of the optimal value function in a nonlinear programming problem, Mathematical Programming Study, vol.21, pp.213-226, 1984.

]. R. Roc96 and . Rockafellar, Convex Analysis, 1996.

]. A. Rub00 and . Rubinov, Abstract Convexity and Global optimization, 2000.

]. H. Sch71 and . Schaefer, Topological Vector Spaces, 1971.

]. L. Sha53 and . Shapley, Stochastic games, Proceedings of the National Academy of Sciences, pp.1095-1100, 1953.

]. A. Sha05 and . Shapiro, On duality theory of convex semi-infinite programming. Optimization, pp.535-543, 2005.

]. A. Sha09 and . Shapiro, Semi-infinite programming, duality, discretization and optimality conditions. Optimization, pp.133-161, 2009.

]. N. Sho87 and . Shor, Quadratic optimization problems, Tekhnicheskaya Kibernetika, vol.1, pp.128-139, 1987.

]. V. Sim96 and . Sima, Algorithm for Linear-quadratic optimization, 1996.

]. I. Sin97 and . Singer, Abstract Convex Analysis, 1997.

]. M. Sio58 and . Sion, On general minimax theorems, Pacific Journal of mathematics, vol.8, pp.171-176, 1958.

]. R. Ske92 and . Skeel, Roundoff error and the patriot missile, SIAM News, vol.25, issue.411, 1992.

H. [. Sankaranarayanan, Z. Sipma, and . Manna, Scalable Analysis of Linear Systems Using Mathematical Programming, The Sixth International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI'05), pp.25-41, 2005.
DOI : 10.1007/978-3-540-30579-8_2

]. J. Stu99 and . Sturm, Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software, pp.11-12625, 1999.

H. [. Stern and . Wolkowicz, Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations, SIAM Journal on Optimization, vol.5, issue.2, pp.286-313, 1995.
DOI : 10.1137/0805016

]. A. Tar55 and . Tarski, A lattice-theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics, vol.5, issue.2, pp.285-309, 1955.

A. [. Tal and . Nemirowski, Lecture on Modern Convex Optimization : Analysis, Algorithm and Engineering Applications, Society For Industrial Mathematics, 2001.

. Vav90, A. Stephen, and . Vavasis, Quadratic programming is in np, Information Processing Letters, vol.36, issue.2, pp.73-77, 1990.

A. Ismael, F. Vaz, M. G. Edite, and . Fernandes, Solving semi-infinite programming problems by using an interface between matlab and sipampl, Proceedings of the 6th WSEAS International Conference on Simulation, Modelling and Optimization, pp.283-288, 2006.

. A. Vfg04, . F. Ismael, . Vaz, M. G. Edite, M. Fernandes et al., Sipampl : Semi-infinite programming with ampl, ACM Trans. Math. Softw, vol.30, issue.1, pp.47-61, 2004.

J. Vöge and M. Jurdzinski, A Discrete Strategy Improvement Algorithm for Solving Parity Games, Lecture Notes in Computer Science, vol.1855, issue.100, pp.202-215295, 1928.
DOI : 10.1007/10722167_18

M. Volle, De l'Informatique : Savoir vivre avec l'automate, Economica, 2006.

]. N. Vor77, Vorob'ev. Game Theory. Lectures for Economists and Systems Scientists, 1977.

]. G. Win93 and . Winskel, The formal semantics of programming languages, 1993.

]. S. Zha00 and . Zhang, Quadratic maximization and semidefinite relaxation, Mathematical Programming, pp.453-465, 2000.

U. Zwick and M. Paterson, The complexity of mean payoff games on graphs, Theoretical Computer Science, vol.158, issue.1-2, pp.343-359, 1996.
DOI : 10.1016/0304-3975(95)00188-3