Abstract

Proximity control is a well-known mechanism in bundle method for nonsmooth optimization. Here we show that it can be used to optimize a large class of nonconvex and nonsmooth functions with additional structure. This includes for instance nonconvex maximum eigenvalue functions, and also infinite suprema of such functions.

Author information

Contact details are reproduced from the original publication and may be historical.

Pierre Apkarian

ONERA-CERT, av. Edouard Belin, 31055 Toulouse, France

Dominikus Noll

Université Paul Sabatier, Institut de Mathématiques, 31062 Toulouse, France

noll@mip.ups-tlse.fr

Olivier Prot

Université de Limoges, Département de Mathématiques, 123, av. Albert Thomas, 87060 Limoges, France

Keywords

  • Nonsmooth calculus
  • nonsmooth optimization
  • Clarke subdifferential
  • spectral bundle method
  • maximum eigenvalue function
  • semi-infinite problem
  • H-infinity-norm

References

  1. E. Anderson et al.: LAPACK User’s Guide, SIAM, Philadelphia (1992).Google Scholar
  2. P. Apkarian, D. Noll: Nonsmooth optimization for multidisk H∞ synthesis, Eur. J. Control 12(3) (2006) 229–244.https://doi.org/10.3166/ejc.12.229-244Google Scholar
  3. P. Apkarian, D. Noll: Controller design via nonsmooth multi-directional search, SIAM J. Control Optimization 44 (2006) 1923–1949.https://doi.org/10.1137/S0363012904441684Google Scholar
  4. P. Apkarian, D. Noll: IQC analysis and synthesis via nonsmooth optimization, Syst. Control Lett. 55(12) (2006) 971–981.https://doi.org/10.1016/j.sysconle.2006.06.008Google Scholar
  5. P. Apkarian, D. Noll: Nonsmooth H∞ synthesis, IEEE Trans. Autom. Control 51 (2006) 71–86.https://doi.org/10.1109/TAC.2005.860290Google Scholar
  6. P. Apkarian, D. Noll: Nonsmooth optimization for multiband frequency domain control design, Automatica 43(4) (2007) 724–731.https://doi.org/10.1016/j.automatica.2006.08.031Google Scholar
  7. P. Apkarian, V. Bompart, D. Noll: Nonsmooth structured control design with applications to PID loopshaping of a process, Int. J. Robust Nonlinear Control 17(14) (2007) 1320–1342.https://doi.org/10.1002/rnc.1175Google Scholar
  8. P. Apkarian, D. Noll, O. Prot: Nonsmooth methods for analysis and synthesis with integral quadratic constraints, in: Conference Proceedings, ACC (New Orleans, 2007).Google Scholar
  9. P. Apkarian, D. Noll, O. Prot: Trust region spectral bundle method for nonconvex maximum eigenvalue functions, SIAM J. Optim. 19(1) (2008) 281–306.https://doi.org/10.1137/060665191Google Scholar
  10. V. Bompart: Optimisation non Lisse pour la Commande des Systèmes de l’Aéronautique, Thèse de l’Université Paul Sabatier, Toulouse (November 2007).Google Scholar
  11. V. Bompart, P. Apkarian, D. Noll: Nonsmooth techniques for stabilizing linear systems, in: Proceedings of the American Control Conference (New York, 2007).https://doi.org/10.1109/ACC.2007.4282408Google Scholar
  12. V. Bompart, D. Noll, P. Apkarian: Second-order nonsmooth optimization of the H∞ norm, Numer. Math. 107(3) (2007) 433–454.https://doi.org/10.1007/s00211-007-0095-9Google Scholar
  13. S. Boyd, V. Balakrishnan: A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its L∞ -norm, Syst. Control Lett. 15 (1990) 1–7.https://doi.org/10.1016/0167-6911(90)90037-UGoogle Scholar
  14. S. Boyd, V. Balakrishnan, P. Kabamba: A bisection method for computing the H∞ norm of a transfer matrix and related problems, Math. Control Signals Syst. 2 (1989) 207–219.https://doi.org/10.1007/BF02551385Google Scholar
  15. S. Boyd, L. Elghaoui, E. Feron, V. Balakrishnan: Linear Matrix Inequalities in System and Control Theory, SIAM Studies in Applied Mathematics 15, SIAM, Philadelphia (1994).https://doi.org/10.1137/1.9781611970777Google Scholar
  16. J. V. Burke, D. Henrion, A. S. Lewis, M. L. Overton: HIFOO - A MATLAB package for fixed-order controller design and H-infinity optimization, in: Proceedings of ROCOND 2006 (Toulouse, July 2006).https://doi.org/10.3182/20060705-3-FR-2907.00059Google Scholar
  17. J. V. Burke, A. S. Lewis, M. L. Overton: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim. 15 (2005) 751–779.https://doi.org/10.1137/030601296Google Scholar
  18. B. M. Chen: H∞ Control and its Applications, Lecture Notes in Control and Information Sciences 235, Springer, New York (1998).https://doi.org/10.1007/978-1-84628-529-5Google Scholar
  19. F. Clarke: Optimization and Nonsmooth Analysis, Canadian Math. Society Series, John Wiley & Sons, New York (1983).Google Scholar
  20. J. Cullum, W. Donath, P. Wolfe: The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices, in: Nondiffer. Optim., Math. Program. Study 3, M. L. Balinski, P. Wolfe (eds.), North Holland, Amsterdam (1975) 35–55.https://doi.org/10.1007/BFb0120698Google Scholar
  21. B. Fares, D. Noll, P. Apkarian: Robust control via sequential semidefinite programming, SIAM J. Control Optimization 40 (2002) 1791–1820.https://doi.org/10.1137/S0363012900373483Google Scholar
  22. R. Fletcher: Semidefinite matrix constraints in optimization, SIAM J. Control Optimization 23 (1985) 493–513.https://doi.org/10.1137/0323032Google Scholar
  23. A. Fuduli, M. Gaudioso, G. Giallombardo: A DC piecewise affine model and a bundling technique in nonconvex nonsmooth optimization, Optim. Methods Softw. 19 (2004) 89–102.https://doi.org/10.1080/10556780410001648112Google Scholar
  24. A. Fuduli, M. Gaudioso, G. Giallombardo: Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim. 14 (2004) 743–756.https://doi.org/10.1137/S1052623402411459Google Scholar
  25. D. Gangsaas, K. Bruce, J. Blight, U.-L. Ly: Application of modern synthesis to aircraft control: three case studies, IEEE Trans. Autom. Control 31 (1986) 995–1014.https://doi.org/10.1109/TAC.1986.1104161Google Scholar
  26. C. Helmberg, K. C. Kiwiel: A spectral bundle method with bounds, Math. Program., Ser. A 93 (2002) 173–194.https://doi.org/10.1007/s101070100270Google Scholar
  27. C. Helmberg, F. Oustry: Bundle methods to minimize the maximum eigenvalue function, in: Handbook of Semidefinite Programming. Theory, Algorithms and Applications, H. Wolkowicz et al. (ed.), Int. Ser. Oper. Res. Manag. Sci. 27, Kluwer, Dordrecht (2000) 307–337.https://doi.org/10.1007/978-1-4615-4381-7_11Google Scholar
  28. C. Helmberg, F. Rendl: Spectral bundle method for semidefinite programming, SIAM J. Optim. 10 (2000) 673–696.https://doi.org/10.1137/S1052623497328987Google Scholar
  29. J. W. Helton, O. Merino: Coordinate optimization for bi-convex matrix inequalities, in: Proc. IEEE Conf. Decision and Control (San Diego, 1997) 3609–3613.https://doi.org/10.1109/CDC.1997.652414Google Scholar
  30. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms. Part 1: Fundamentals; Part II: Advanced Theory and Bundle Methods, Grundlehren der mathematischen Wissenschaften 305, 306, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-06409-2_1Google Scholar
  31. Y. S. Hung, A. G. J. MacFarlane: Multivariable Feedback: A Classical Approach, Lect. Notes in Control and Information Sciences 40, Springer, Berlin (1982).https://doi.org/10.1007/BFb0043756Google Scholar
  32. L. H. Keel, S. P. Bhattacharyya, J. W. Howe: Robust control with structured perturbations, IEEE Trans Autom. Control 36 (1988) 68–77.https://doi.org/10.1109/9.362Google Scholar
  33. K. C. Kiwiel: Proximity control in bundle methods for convex nondifferentiable minimization, Math. Programming, Ser. A 46 (1990) 105–122.https://doi.org/10.1007/BF01585731Google Scholar
  34. K. C. Kiwiel: Methods of Descent for Nondifferentiable Optimization, Lect. Notes in Math. 1133, Springer, Berlin (1985).https://doi.org/10.1007/BFb0074500Google Scholar
  35. K. C. Kiwiel: A linearization algorithm for computing control systems subject to singular value inequalities, IEEE Trans. Autom. Control 31 (1986) 595–602.https://doi.org/10.1109/TAC.1986.1104345Google Scholar
  36. F. Leibfritz: COM P Le IB, COnstrained Matrix-optimization Problem LIbrary - a collection of test examples for nonlinear semidefinite programs, control system design and related problems, Tech. Report, Universität Trier, Trier (2003).Google Scholar
  37. C. Lemaréchal: An extension of Davidson method to nondifferentiable problems, in: Nondiffer. Optim., Math. Program. Study 3, M. L. Balinski, P. Wolfe (eds.), North Holland, Amsterdam (1975) 95–109.Google Scholar
  38. C. Lemaréchal: Bundle methods in nonsmooth optimization, in: Nonsmooth Optimization, Proc. IIASA Workshop 1977, C. Lemaréchal, R. Mifflin (eds.), IIASA Proc. Ser. 3, Pergamon Press, Oxford (1978) 79–102.Google Scholar
  39. C. Lemaréchal: Nondifferentiable optimization, in: Handbooks in Operations Research and Management Sciences 1, G. L. Nemhauser et al. (ed.), North-Holland, Amsterdam (1989) 529–572.https://doi.org/10.1016/S0927-0507(89)01008-XGoogle Scholar
  40. C. Lemaréchal, A. Nemirovskii, Y. Nesterov: New variants of bundle methods, Math. Program., Ser. B 69 (1995) 111–147.https://doi.org/10.1007/BF01585555Google Scholar
  41. D. Mayne, E. Polak: Algorithms for the design of control systems subject to singular value inequalities, Math. Program. Study 18 (1982) 112–134.https://doi.org/10.1007/BFb0120976Google Scholar
  42. D. Mayne, E. Polak, A. Sangiovanni: Computer aided design via optimization, Automatica 18(2) (1982) 147–154.https://doi.org/10.1016/0005-1098(82)90104-2Google Scholar
  43. D. Noll, P. Apkarian: Spectral bundle method for nonconvex maximum eigenvalue functions: first-order methods, Math. Program., Ser. B 104 (2005) 701–727.https://doi.org/10.1007/s10107-005-0634-zGoogle Scholar
  44. P. A. Parrilo: On the numerical solution of LMIs derived from the KYP lemma. in: Proc. IEEE Conf. Decision and Control 3 (Phoenix, Arizona, 1999) 2334–2338.https://doi.org/10.1109/CDC.1999.831271Google Scholar
  45. E. Polak: On the mathematical foundations of nondifferentiable optimization in engineering design, SIAM Rev. 29 (1987) 21–89.https://doi.org/10.1137/1029002Google Scholar
  46. E. Polak: Optimization: Algorithms and Consistent Approximations, Applied Mathematical Sciences 124, Springer, New York (1997).https://doi.org/10.1007/978-1-4612-0663-7Google Scholar
  47. J.-B. Thevenet, D. Noll, P. Apkarian: Nonlinear spectral SDP method for BMI-constrained problems: applications to control design, in: Informatics in Control, Automation and Robotics I (Setúbal, 2004), J. Braz et al. (ed.), Springer, Berlin (2006) 61–72.https://doi.org/10.1007/1-4020-4543-3_7Google Scholar
  48. P. Wolfe: A method of conjugate subgradients for minimizing nondifferentiable functions, in: Nondiffer. Optim., Math. Program. Study, M. L. Balinski, P. Wolfe (eds.), North Holland, Amsterdam (1975) 145–173.https://doi.org/10.1007/BFb0120703Google Scholar
  49. K. Zhou, J. C. Doyle, K. Glover: Robust and Optimal Control, Prentice Hall, Upper Saddle River (1996).Google Scholar

Suggested citation

P. Apkarian, D. Noll, O. Prot. “A Proximity Control Algorithm to Minimize Nonsmooth and Nonconvex Semi-Infinite Maximum Eigenvalue Functions.” Journal of Convex Analysis 16 (2009), No. 3&4, 641–666. https://doi.org/10.68381/jca16037

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2009. Rights now held by Banach Press LLC.