Selection strategies in projection methods for convex minimization problems

Andrzej Cegielski; Robert Dylewski

Discussiones Mathematicae, Differential Inclusions, Control and Optimization (2002)

  • Volume: 22, Issue: 1, page 97-123
  • ISSN: 1509-9407

Abstract

top
We propose new projection method for nonsmooth convex minimization problems. We present some method of subgradient selection, which is based on the so called residual selection model and is a generalization of the so called obtuse cone model. We also present numerical results for some test problems and compare these results with some other convex nonsmooth minimization methods. The numerical results show that the presented selection strategies ensure long steps and lead to an essential acceleration of the convergence of projection methods.

How to cite

top

Andrzej Cegielski, and Robert Dylewski. "Selection strategies in projection methods for convex minimization problems." Discussiones Mathematicae, Differential Inclusions, Control and Optimization 22.1 (2002): 97-123. <http://eudml.org/doc/271448>.

@article{AndrzejCegielski2002,
abstract = {We propose new projection method for nonsmooth convex minimization problems. We present some method of subgradient selection, which is based on the so called residual selection model and is a generalization of the so called obtuse cone model. We also present numerical results for some test problems and compare these results with some other convex nonsmooth minimization methods. The numerical results show that the presented selection strategies ensure long steps and lead to an essential acceleration of the convergence of projection methods.},
author = {Andrzej Cegielski, Robert Dylewski},
journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
keywords = {convex minimization; projection method; long steps; residual selection; obtuse cone selection},
language = {eng},
number = {1},
pages = {97-123},
title = {Selection strategies in projection methods for convex minimization problems},
url = {http://eudml.org/doc/271448},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Andrzej Cegielski
AU - Robert Dylewski
TI - Selection strategies in projection methods for convex minimization problems
JO - Discussiones Mathematicae, Differential Inclusions, Control and Optimization
PY - 2002
VL - 22
IS - 1
SP - 97
EP - 123
AB - We propose new projection method for nonsmooth convex minimization problems. We present some method of subgradient selection, which is based on the so called residual selection model and is a generalization of the so called obtuse cone model. We also present numerical results for some test problems and compare these results with some other convex nonsmooth minimization methods. The numerical results show that the presented selection strategies ensure long steps and lead to an essential acceleration of the convergence of projection methods.
LA - eng
KW - convex minimization; projection method; long steps; residual selection; obtuse cone selection
UR - http://eudml.org/doc/271448
ER -

References

top
  1. [1] A. Cegielski, Projection onto an acute cone and convex feasibility problems, J. Henry and J.-P. Yvon (eds.), Lecture Notes in Control and Information Science 197, Springer- Verlag, London (1994), 187-194. Zbl0816.90108
  2. [2] A. Cegielski, A method of projection onto an acute cone with level control in convex minimization, Mathematical Programming 85 (1999), 469-490. Zbl0973.90057
  3. [3] A. Cegielski, Obtuse cones and Gram matrices with non-negative inverse, Linear Algebra and its Applications 335 (2001), 167-181. Zbl0982.15028
  4. [4] A. Cegielski and R. Dylewski, Residual selection in a projection method for convex minimization problems, (submitted). Zbl1057.49021
  5. [5] J. Charalambous and A.R. Conn, An efficient method to solve the minimax problem directly, SIAM J. Num. Anal. 15 (1978), 162-187. Zbl0384.65032
  6. [6] R. Dylewski, Numerical behavior of the method of projection onto an acute cone with level control in convex minimization, Discuss. Math. Differential Inclusions, Control and Optimization 20 (2000), 147-158. Zbl1014.65048
  7. [7] S. Kim, H. Ahn and S.-C. Cho, Variable target value subgradient method, Mathematical Programming 49 (1991), 359-369. Zbl0825.90754
  8. [8] K.C. Kiwiel, The efficiency of subgradient projection methods for convex optimization, part I: General level methods, SIAM J. Control and Optimization 34 (1996), 660-676. Zbl0846.90084
  9. [9] K.C. Kiwiel, The efficiency of subgradient projection methods for convex optimization, part II: Implementations and extensions, SIAM J. Control and Optimization 34 (1996), 677-697. Zbl0846.90085
  10. [10] K.C. Kiwiel, Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems, Linear Algebra and Applications 252 (1997), 27-33. Zbl0870.65046
  11. [11] C. Lemaréchal and R. Mifflin, A set of nonsmooth optimization test problems, Nonsmooth Optimization, C. Lemarechal, R. Mifflin, (eds.), Pergamon Press, Oxford 1978, 151-165. 
  12. [12] C. Lemaréchal, A.S. Nemirovskii and Yu.E. Nesterov, New variants of bundle methods, Math. Progr. 69 (1995), 111-147. Zbl0857.90102
  13. [13] N.Z. Shor, Minimization Methods for Non-differentiable Functions, Springer-Verlag, Berlin 1985. Zbl0561.90058
  14. [14] H. Schramm and J. Zowe, A version of the bundle idea for minimizing of a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM J. Control and Optimization 2 (1992), 121-152. Zbl0761.90090
  15. [15] M.J. Todd, Some remarks on the relaxation method for linear inequalities,. Technical Report 419 (1979), Cornell University. 

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.