Primal interior point method for minimization of generalized minimax functions

Ladislav Lukšan; Ctirad Matonoha; Jan Vlček

Kybernetika (2010)

  • Volume: 46, Issue: 4, page 697-721
  • ISSN: 0023-5954

Abstract

top
In this paper, we propose a primal interior-point method for large sparse generalized minimax optimization. After a short introduction, where the problem is stated, we introduce the basic equations of the Newton method applied to the KKT conditions and propose a primal interior-point method. (i. e. interior point method that uses explicitly computed approximations of Lagrange multipliers instead of their updates). Next we describe the basic algorithm and give more details concerning its implementation covering numerical differentiation, variable metric updates, and a barrier parameter decrease. Using standard weak assumptions, we prove that this algorithm is globally convergent if a bounded barrier is used. Then, using stronger assumptions, we prove that it is globally convergent also for the logarithmic barrier. Finally, we present results of computational experiments confirming the efficiency of the primal interior point method for special cases of generalized minimax problems.

How to cite

top

Lukšan, Ladislav, Matonoha, Ctirad, and Vlček, Jan. "Primal interior point method for minimization of generalized minimax functions." Kybernetika 46.4 (2010): 697-721. <http://eudml.org/doc/196755>.

@article{Lukšan2010,
abstract = {In this paper, we propose a primal interior-point method for large sparse generalized minimax optimization. After a short introduction, where the problem is stated, we introduce the basic equations of the Newton method applied to the KKT conditions and propose a primal interior-point method. (i. e. interior point method that uses explicitly computed approximations of Lagrange multipliers instead of their updates). Next we describe the basic algorithm and give more details concerning its implementation covering numerical differentiation, variable metric updates, and a barrier parameter decrease. Using standard weak assumptions, we prove that this algorithm is globally convergent if a bounded barrier is used. Then, using stronger assumptions, we prove that it is globally convergent also for the logarithmic barrier. Finally, we present results of computational experiments confirming the efficiency of the primal interior point method for special cases of generalized minimax problems.},
author = {Lukšan, Ladislav, Matonoha, Ctirad, Vlček, Jan},
journal = {Kybernetika},
keywords = {unconstrained optimization; large-scale optimization; nonsmooth optimization; generalized minimax optimization; interior-point methods; modified Newton methods; variable metric methods; global convergence; computational experiments; unconstrained optimization; large-scale optimization; nonsmooth optimization; generalized minimax optimization; interior-point methods; modified Newton methods; variable metric methods; global convergence; computational experiments},
language = {eng},
number = {4},
pages = {697-721},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Primal interior point method for minimization of generalized minimax functions},
url = {http://eudml.org/doc/196755},
volume = {46},
year = {2010},
}

TY - JOUR
AU - Lukšan, Ladislav
AU - Matonoha, Ctirad
AU - Vlček, Jan
TI - Primal interior point method for minimization of generalized minimax functions
JO - Kybernetika
PY - 2010
PB - Institute of Information Theory and Automation AS CR
VL - 46
IS - 4
SP - 697
EP - 721
AB - In this paper, we propose a primal interior-point method for large sparse generalized minimax optimization. After a short introduction, where the problem is stated, we introduce the basic equations of the Newton method applied to the KKT conditions and propose a primal interior-point method. (i. e. interior point method that uses explicitly computed approximations of Lagrange multipliers instead of their updates). Next we describe the basic algorithm and give more details concerning its implementation covering numerical differentiation, variable metric updates, and a barrier parameter decrease. Using standard weak assumptions, we prove that this algorithm is globally convergent if a bounded barrier is used. Then, using stronger assumptions, we prove that it is globally convergent also for the logarithmic barrier. Finally, we present results of computational experiments confirming the efficiency of the primal interior point method for special cases of generalized minimax problems.
LA - eng
KW - unconstrained optimization; large-scale optimization; nonsmooth optimization; generalized minimax optimization; interior-point methods; modified Newton methods; variable metric methods; global convergence; computational experiments; unconstrained optimization; large-scale optimization; nonsmooth optimization; generalized minimax optimization; interior-point methods; modified Newton methods; variable metric methods; global convergence; computational experiments
UR - http://eudml.org/doc/196755
ER -

References

top
  1. Bertsekas, D. P., Nondifferentiable optimization via approximation, In: Nondifferentiable Optimization (M. L. Balinski and P.Wolfe, eds.), Math. Programming Stud. 3 (1975), 1–25. (1975) Zbl0383.49025MR0440906
  2. Coleman, T. F., Garbow, B. S., Moré, J. J., 10.1145/6187.6190, ACM Trans. Math. Software 11 (1985), 363–377. (1985) MR0828562DOI10.1145/6187.6190
  3. Coleman, T. F., Moré, J. J., 10.1007/BF02612334, Math. Programming 28 (1984), 243–270. (1984) MR0736293DOI10.1007/BF02612334
  4. Demyanov, V. F., Malozemov, V. N., Introduction to Minimax, Dover Publications, 1990. (1990) MR1088479
  5. Fletcher, R., Practical Methods of Optimization, Second edition. Wiley, New York 1987. (1987) Zbl0905.65002MR0955799
  6. Gill, P. E., Murray, W., 10.1007/BF01585529, Math. Programming 7 (1974), 311–350. (1974) Zbl0297.90082MR0356503DOI10.1007/BF01585529
  7. Griewank, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, SIAM, Philadelphia 2000. (2000) Zbl0958.65028MR1753583
  8. Griewank, A., Toint, P. L., 10.1007/BF01399316, Numer. Math. 39 (1982), 119–137. (1982) MR0664541DOI10.1007/BF01399316
  9. Le, D., 10.1137/0906016, SIAM J. Sci. Stat. Computat. 6 (1985), 193–208. (1985) Zbl0561.65033MR0773291DOI10.1137/0906016
  10. Le, D., 10.1145/214408.214416, ACM Trans. Math. Software 11 (1985), 250–262. (1985) Zbl0581.65033MR0814340DOI10.1145/214408.214416
  11. Lukšan, L., Matonoha, C., Vlček, J., 10.1002/nla.354, Numer. Linear Algebra Appl. 11 (2004), 431–453. (2004) MR2067814DOI10.1002/nla.354
  12. Lukšan, L., Matonoha, C., Vlček, J., 10.1007/s10543-008-0197-5, BIT Numer. Math. 48 (2008), 763–768. (2008) Zbl1203.65092MR2465702DOI10.1007/s10543-008-0197-5
  13. Lukšan, L., Matonoha, C., Vlček, J., Primal interior-point method for large sparse minimax optimization, Kybernetika 45 (2009), 841–864. (2009) Zbl1198.90394MR2599116
  14. Lukšan, L., Matonoha, C., Vlček, J., 10.1080/10556780601114204, Optimization Methods and Software 22 (2007), 737–753. (2007) Zbl1193.90197MR2354765DOI10.1080/10556780601114204
  15. Lukšan, L., Spedicato, E., 10.1016/S0377-0427(00)00420-9, J. Comput. Appl. Math. 124 (2000), 61–93. (2000) MR1803294DOI10.1016/S0377-0427(00)00420-9
  16. Lukšan, L., Vlček, J., Sparse and Partially Separable Test Problems for Unconstrained and Equality Constrained Optimization, Technical Report V-767, ICS AS ČR, Prague 1998. (1998) 
  17. Lukšan, L., Vlček, J., Variable metric method for minimization of partially separable nonsmooth functions, Pacific J. Optim. 2 (2006), 59–70. (2006) MR2548209
  18. Pillo, G. Di, Grippo, L., Lucidi, S., 10.1023/A:1022627226891, J. Optim. Theory Appl. 95 (1997), 1–24. (1997) Zbl0890.90165MR1477348DOI10.1023/A:1022627226891
  19. Vanderbei, J., Shanno, D. F., 10.1023/A:1008677427361, Comput. Optim. Appl. 13 (1999), 231–252. (1999) Zbl1040.90564MR1704122DOI10.1023/A:1008677427361
  20. Xu, S., 10.1023/A:1011211101714, Computational Optim. Appl. 20 (2001), 267–279. (2001) MR1857058DOI10.1023/A:1011211101714

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.