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

Cucker, Felipe1 ; Peña, Javier2 ; Roshchina, Vera1
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, Tome 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
Cucker, Felipe 1 ; Peña, Javier 2 ; Roshchina, Vera 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 = {Cucker, Felipe and Pe\~na, Javier and Roshchina, Vera},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2012.06.013/}
}
TY  - JOUR
AU  - Cucker, Felipe
AU  - Peña, Javier
AU  - Roshchina, Vera
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2012.06.013/
DO  - 10.1016/j.crma.2012.06.013
LA  - en
ID  - CRMATH_2012__350_11-12_639_0
ER  - 
%0 Journal Article
%A Cucker, Felipe
%A Peña, Javier
%A Roshchina, Vera
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2012.06.013/
%R 10.1016/j.crma.2012.06.013
%G en
%F CRMATH_2012__350_11-12_639_0
Cucker, Felipe; Peña, Javier; Roshchina, Vera. Round-off estimates for second-order conic feasibility problems. Comptes Rendus. Mathématique, Tome 350 (2012) no. 11-12, pp. 639-641. doi : 10.1016/j.crma.2012.06.013. http://www.numdam.org/articles/10.1016/j.crma.2012.06.013/

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

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

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

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

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

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

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

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

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

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

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

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

[13] Tsuchiya, T. 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] Vera, J.R. On the complexity of linear programming under finite precision arithmetic, Math. Program., Volume 80 (1998), pp. 91-123

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

Cité par Sources :