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 ,
Ye montre que ce résultat demeure vrai si on ajoute des contraintes d'´ egalités quadratiques ,
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 ,
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 ,
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 ,
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(+) ,
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. ,
Computing the smallest fixed point of nonexpansive mappings arising in game theory and static analysis of programs, Proceedings of MTNS'08, 2008. ,
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
Design and implementation of a special-purpose static program analyzer for safety-critical real-time embedded software ,
Quadratic matrix programming, SIAM Journal on Optimization, vol.17, issue.4, pp.1224-1238, 2007. ,
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. ,
On the theory of dynamic programming, Proceedings of the National Academy of Sciences of the U.S.A, pp.716-719, 1952. ,
Dynamic Programming, 1957. ,
Residuation Theory, 1972. ,
Nonquadratic lyapunov functions for robust control, Automatica, vol.31, pp.451-461, 1995. ,
Efficient chaotic iteration strategies with widenings, Proceedings of the International Conference on Formal Methods in Programming and their Applications, pp.128-141, 1993. ,
Matrices of Sign-Solvable Linear Systems. Number 116 in Cambridge Tracts in Mathematics, 1995. ,
Perturbation Analysis of Optimization Problems, 2000. ,
DOI : 10.1007/978-1-4612-1394-9
A helly-type theorem and semiinfinite programming, pp.127-135, 1979. ,
Hidden convexity in some nonconvex quadratically constrained quadratic programming, Mathematical Programming, vol.47, issue.1, pp.51-63, 1996. ,
DOI : 10.1007/BF02592331
On the theory of filter amplifiers, Wireless Engineer, vol.7, pp.536-541, 1930. ,
Convex optimization, 2004. ,
Static determination of dynamic properties of programs, Proceedings of the Second International Symposium on Programming, pp.106-130, 1976. ,
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
Abstract interpretation frameworks, Journal of Logic and Computation, vol.2, issue.4, pp.511-547, 1992. ,
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. ,
Design and synthesis of synchronization skeletons using branching time temporal logic, Logics of Programs, pp.52-71, 1982. ,
DOI : 10.1007/BFb0025774
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
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
On algorithms for simple stochastic games, Advances in Computational Complexity Theory, pp.51-73, 1993. ,
Numerical computation of spectral elements in max-plus algebra, Proc. IFAC Conf. on Syst. Structure and Control, 1998. ,
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
The Theory of Max Min, 1967. ,
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
Notes on structured programming, 1970. ,
Measure Theory, 1993. ,
Recursive games, Contributions to the Theory of Games, pp.47-78, 1957. ,
Control software analysis, part I : Open-loop properties, 2008. ,
Control software analysis, part II : Closed-loop analysis, p.812, 1986. ,
Static analysis of digital filters, European Symposium on Programming number 2986 in LNCS, 2004. ,
Construction of lyapunov functions using gröbner bases, Proc. of the 30th Conf. on Decision and Control, pp.798-799, 1991. ,
Algorithms for stochastic games-a survey, Zeitschrift für Operations Research, vol.35, pp.437-472, 1991. ,
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
Competitive Markov Decision Processes, 1997. ,
DOI : 10.1007/978-1-4612-4054-9
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
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
A compendium of continuous lattices, 1980. ,
Stochastic games with zero stop probabilities, Contributions to the Theory of Games, pp.179-188, 1957. ,
Jeux positionnels, 2006. ,
Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979. ,
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
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
Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol.2, 1988. ,
A zonotopic framework for functional abstractions, Formal Methods in System Design, vol.2, issue.1???4 ,
DOI : 10.1007/s10703-015-0238-z
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
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. ,
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. ,
Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods and Software, pp.201-224, 2000. ,
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
Introduction to Metamathematics, 1952. ,
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
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
Semi-infinite programming, European Journal of Operations Research, vol.180, pp.491-518, 2007. ,
An investigation of the Therac-25 accidents, Computer, vol.26, issue.7, pp.18-41, 1993. ,
DOI : 10.1109/MC.1993.274940
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. ,
Static analysis of the numerical stability of loops, Static Analysis, pp.3-14, 2002. ,
The Art of Software Testing, 2004. ,
A new numerical abstract domain based on difference-bound matrices ,
Weakly Relational Numerical Abstract Domains, 2004. ,
Inf-convultion, sous-additivé, convexité des fonctions numériques, Journal Mathématiques de Pures et Appliquées, vol.49, pp.109-154, 1970. ,
Generalizations of the trust region problem, Optimization Methods and Software, vol.2, pp.189-209, 1993. ,
Eigenvalues for a class of homogeneous cone maps arising from max-plus operators. Discrete and Continuous Dynamical Systems, pp.519-562, 2002. ,
Interior point polynomial algorithms in convex programming, Society for Industrial and Applied Mathematics, 1994. ,
DOI : 10.1137/1.9781611970791
Convexity and log convexity for spectral radius, Linear Algebra And Its Applications, pp.59-122, 1986. ,
Hilbert's projective metric and iterated nonlinear maps, Memoirs of the AMS, vol.75, issue.391, 1988. ,
Eigenvalues of dynamical max-min systems, Discrete Event Dynamic Systems, vol.1, pp.177-207, 1991. ,
Galois connexions. Transactions of, pp.493-513, 1944. ,
Max-min representation of piecewise linear functions. Contributions to Algebra and Geometry, pp.297-302, 2002. ,
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. ,
Semidefinite programming, Interior Point Methods of Mathematical Programming, pp.369-398, 1997. ,
Specification and verification of concurrent systems in CESAR, International Symposium on Programming, pp.337-351, 1982. ,
DOI : 10.1007/3-540-11494-7_22
On completely recursively enumerable classes and their key arrays. Transaction of the, pp.358-366, 1953. ,
Directional differentiability of the optimal value function in a nonlinear programming problem, Mathematical Programming Study, vol.21, pp.213-226, 1984. ,
Convex Analysis, 1996. ,
Abstract Convexity and Global optimization, 2000. ,
Topological Vector Spaces, 1971. ,
Stochastic games, Proceedings of the National Academy of Sciences, pp.1095-1100, 1953. ,
On duality theory of convex semi-infinite programming. Optimization, pp.535-543, 2005. ,
Semi-infinite programming, duality, discretization and optimality conditions. Optimization, pp.133-161, 2009. ,
Quadratic optimization problems, Tekhnicheskaya Kibernetika, vol.1, pp.128-139, 1987. ,
Algorithm for Linear-quadratic optimization, 1996. ,
Abstract Convex Analysis, 1997. ,
On general minimax theorems, Pacific Journal of mathematics, vol.8, pp.171-176, 1958. ,
Roundoff error and the patriot missile, SIAM News, vol.25, issue.411, 1992. ,
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
Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software, pp.11-12625, 1999. ,
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 lattice-theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics, vol.5, issue.2, pp.285-309, 1955. ,
Lecture on Modern Convex Optimization : Analysis, Algorithm and Engineering Applications, Society For Industrial Mathematics, 2001. ,
Quadratic programming is in np, Information Processing Letters, vol.36, issue.2, pp.73-77, 1990. ,
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. ,
Sipampl : Semi-infinite programming with ampl, ACM Trans. Math. Softw, vol.30, issue.1, pp.47-61, 2004. ,
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
De l'Informatique : Savoir vivre avec l'automate, Economica, 2006. ,
Vorob'ev. Game Theory. Lectures for Economists and Systems Scientists, 1977. ,
The formal semantics of programming languages, 1993. ,
Quadratic maximization and semidefinite relaxation, Mathematical Programming, pp.453-465, 2000. ,
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