An improved partial bundle method for linearly constrained minimax problems
Abstract
In this paper, we propose an improved partial bundle method for solving linearly constrained minimax problems. In order to reduce the number of component function evaluations, we utilize a partial cutting-planes model to substitute for the traditional one. At each iteration, only one quadratic programming subproblem needs to be solved to obtain a new trial point. An improved descent test criterion is introduced to simplify the algorithm. The method produces a sequence of feasible trial points, and ensures that the objective function is monotonically decreasing on the sequence of stability centers. Global convergence of the algorithm is established. Moreover, we utilize the subgradient aggregation strategy to control the size of the bundle and therefore overcome the difficulty of computation and storage. Finally, some preliminary numerical results show that the proposed method is effective.References
I. Averbakh and O. Berman, Minimax p-traveling salemen location problems on a tree, Annals of Operations Research, vol. 110, pp. 55-68, 2002.
A. Baums, Minimax method in optimizing energy consumption in real-time embedded systems, Automatic Control and Computer Sciences, vol. 43, pp. 57-62, 2009.
J. F. Bonnans, J. C. Lemaréchal and C. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Second ed, Springer-Verlag, 2006.
J. V. Burke, A. S. Lewis and M. L. Overton, A robust gradient sampling algorithm for nonsmooth,nonconvex optimization, SIAM Journal on Optimization, vol. 15, pp. 751-779, 2005.
E. W. Cheney and A. A. Goldstein, Newton’s method for convex programming and Tchebycheff approximations, Numerische Mathematik, vol. 1, pp. 253-268, 1959.
M. Gaudioso, G. Giallombardo and G. Miglionico, An incremental method for solving convex finite min-max problems, Mathematics of Operations Research, vol. 31, pp. 173-187, 2006.
W. Hare and M. Macklem, Derivative-free optimization methods for finite minimax problems, Optimization Methods and Software, vol. 28, pp. 300-312, 2013.
W. Hare and J. Nutini, A derivative-free approximate gradient sampling algorithm for finite minimax problems, Computational Optimization and Applications, vol. 56, pp. 1-38, 2013.
J. B. Jian, C. M. Tang and F. Tang, A feasible descent bundle method for inequality constrained minimax problems (in Chinese), Science China: Mathematics, vol. 45, pp. 2001-2024, 2015.
J. E. Kelley, The cutting-plane method for solving convex programs, Journal of the society for Industrial and Applied Mathematics, vol. 8, pp. 703-712, 1960.
K. C. Kiwiel, Method of Descent for Nondifferentiable Optimization, Lecture Note in Mathematics 1133, Springer-Verlag, 1985.
K. C. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization, Mathematical Programming, vol. 46, pp. 105-122, 1990.
K. C. Kiwiel, A projection-proximal bundle method for convex nondifferentiable minimization, In M. Théra et al. (Eds), Ill-posed Variational Problems and Regularization Techniques, Lecture Notes in Econom. Math. Systems 477, pp. 137-150, Berlin: Springer-Verlag, 1999.
K. C. Kiwiel, A proximal bundle method with approximate subgradient linearizations, SIAM Journal on Optimization, vol. 16, pp. 1007-1023, 2006.
K. C. Kiwiel, A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming, SIAM Journal on Optimization, vol. 17, pp. 1015-1034, 2006.
C. Lemaréchal, An extention of Davidon methods to nondifferentiable problems, Mathematical Programming Study, vol. 3, pp. 95-109, 1975.
X. S. Li and S. C. Fang, On the entropic regularization method for solving min-max problems with applications, Mathematical Method of Operations Research, vol. 46, pp. 119-130, 1997.
G. Liuzzi, S. Lucidi and M. Sciandrone, A derivative-free algorithm for linearly constrained finite minimax problems, SIAM Journal on Optimization, vol. 16, pp. 1054-1075, 2006.
L. Luksan and J. Vlcek, Test problems for nonsmooth unconstrained and linearly constrained optimization, Technical Report No.798, Institute of Computer Science, Academy of Science of the Czech Republic, Prague, 2000.
MOSEK The MOSEK optimization tooltox for MATLAB manual, Version 7.1 (Revision 30) MOSEK ApS, Denmark, http://www.mosek.com, 2015.
M. L. Overton, Algorithms for nonlinear ℓ1and ℓ∞fitting, In M.J.D.Powell (Ed.), Nonlinear Optimization, pp. 213-221, 1982.
C. M. Tang, J. B. Jian and G. Y. Li, A proximal-projection partial bundle method for convex constrained minimax problems, Manuscript, 2015.
F. Y. Wang, Y. Yamamoto and M. Yu, A minimax rule for portfolio selection in frictional markets, Mathematical Methods of Operations Research, vol. 57, pp. 141-155, 2003.
F. S. Wang and K. C. Zhang, A hybrid algorithm for nonlinear minimax problems, Annals of Operations Research, vol. 164, pp. 167-191, 2008.
F. S. Wang and K. C. Zhang, A hybrid algorithm for linearly constrained minimax problems, Annals of Operations Research, vol. 206, pp. 501-525, 2013.
G. A. Waston, The minimax solution of an overdetermined system of nonlinear equations, Journal of the Institute of Mathematics and its Applications, vol. 23, pp. 167-180, 1979.
P. Wolf, A method of conjugate subgradient for minimizing nondifferentiable function, Mathematical Programming Study, vol. 3, pp. 145-173, 1975.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
