Comptes Rendus
no. 11-12
Numerical Analysis
Round-off estimates for second-order conic feasibility problems
[Estimations dʼarrondi pour des problèmes de faisabilité coniques du second ordre]

Présenté par : Philippe G. Ciarlet

Felipe Cucker1 ; Javier Peña2 ; Vera Roshchina1
1 Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong
2 Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213-3890, USA
Comptes Rendus. Mathématique, Volume 350 (2012) no. 11-12, pp. 639-641.

Nous présentons une analyse de la méthode des points intérieurs pour résoudre les problèmes de faisabilité des systèmes coniques du second ordre. Une caractéristique principale de cet algorithme est que les opérations arithmétiques sont effectuées en précision finie. Des estimations du nombre des opérations arithmétiques et de la précision requise sont obtenues.

We present the analysis of an interior-point method to decide feasibility problems of second-order conic systems. A main feature of this algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2012.06.013

Felipe Cucker 1 ; Javier Peña 2 ; Vera Roshchina 1

1 Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong
2 Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213-3890, USA 
@article{CRMATH_2012__350_11-12_639_0,
     author = {Felipe Cucker and Javier Pe\~na and Vera Roshchina},
     title = {Round-off estimates for second-order conic feasibility problems},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {639--641},
     publisher = {Elsevier},
     volume = {350},
     number = {11-12},
     year = {2012},
     doi = {10.1016/j.crma.2012.06.013},
     language = {en},
}
TY  - JOUR
AU  - Felipe Cucker
AU  - Javier Peña
AU  - Vera Roshchina
TI  - Round-off estimates for second-order conic feasibility problems
JO  - Comptes Rendus. Mathématique
PY  - 2012
SP  - 639
EP  - 641
VL  - 350
IS  - 11-12
PB  - Elsevier
DO  - 10.1016/j.crma.2012.06.013
LA  - en
ID  - CRMATH_2012__350_11-12_639_0
ER  - 
%0 Journal Article
%A Felipe Cucker
%A Javier Peña
%A Vera Roshchina
%T Round-off estimates for second-order conic feasibility problems
%J Comptes Rendus. Mathématique
%D 2012
%P 639-641
%V 350
%N 11-12
%I Elsevier
%R 10.1016/j.crma.2012.06.013
%G en
%F CRMATH_2012__350_11-12_639_0
Felipe Cucker; Javier Peña; Vera Roshchina. Round-off estimates for second-order conic feasibility problems. Comptes Rendus. Mathématique, Volume 350 (2012) no. 11-12, pp. 639-641. doi : 10.1016/j.crma.2012.06.013. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2012.06.013/

[1] F. Alizadeh; D. Goldfarb Second-order cone programming, Math. Program., Volume 95 (2003), pp. 3-51

[2] R.H. Bartels A stabilization of the simplex method, Numer. Math., Volume 16 (1971), pp. 414-434

[3] D. Cheung; F. Cucker Solving linear programs with finite precision: II. Algorithms, J. Complexity, Volume 22 (2006), pp. 305-335

[4] R.J. Clasen Techniques for automatic tolerance control in linear programming, Comm. ACM, Volume 9 (1966), pp. 802-803

[5] F. Cucker; J. Peña A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine, SIAM J. Optim., Volume 12 (2002), pp. 522-554

[6] F. Cucker; J. Peña; V. Roshchina Solving second-order conic systems with finite-precision (preprint. Available at) | arXiv

[7] W. Ogryczak The simplex method is not always well behaved, Linear Algebra Appl., Volume 109 (1988), pp. 41-57

[8] J. Renegar Linear programming, complexity theory and elementary functional analysis, Math. Program., Volume 70 (1995), pp. 279-351

[9] J. Renegar A Mathematical View of Interior-Point Methods in Convex Optimization, SIAM, 2000

[10] S.M. Robinson A characterization of stability in linear programming, Oper. Res., Volume 25 (1977), pp. 435-447

[11] M. Sousa Lobo; L. Vandenberghe; S. Boyd; H. Lebret Applications of second-order cone programming, Linear Algebra Appl., Volume 284 (1998), pp. 193-228

[12] S. Storoy Error control in the simplex-technique, BIT, Volume 7 (1967), pp. 216-225

[13] T. Tsuchiya A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Optim. Methods Softw., Volume 11 (1999), pp. 141-182

[14] J.R. Vera On the complexity of linear programming under finite precision arithmetic, Math. Program., Volume 80 (1998), pp. 91-123

[15] P. Wolfe Error in the solution of linear programming problems (L.R. Ball, ed.), Error in Digital Computation, John Wiley & Sons, 1965, pp. 271-284

Cité par Sources :

Commentaires - Politique