Case 1: Energy Saving Measures – Insulation and Heat Regulation
6.1 Conclusions and Answers to Research Questions
Para melhorar a robustez do m´etodo quando aplicado com a penalidade exata ou com a fun¸c˜ao m´ınimo, precisamos de alguma forma incorporar a qualidade da escolha da dire¸c˜ao de Newton para FKP, mas sem perder a velocidade proporcionada pela informa¸c˜ao dual e pela fun¸c˜ao
m´ınimo. Al´em disso, n˜ao queremos calcular duas dire¸c˜oes de Newton diferentes, resolvendo dois sistemas lineares por itera¸c˜ao. Na tentativa de prever quando a dire¸c˜ao calculada a partir de Wc ou M pode ser ruim, vamos comparar as dire¸c˜oes dadas pelos gradientes da
fun¸c˜ao de m´erito, ∇12kFKP(x)k2
, e a fun¸c˜ao m´erito associada a reformula¸c˜ao, p. ex. ∇12kWc(x)k2
. Vamos usar o ˆangulo formado por esses vetores para decidir qual dire¸c˜ao de Newton calcular.
1. Calcula-se o ˆangulo entre o gradiente da fun¸c˜ao de m´erito 12kFKP(x)k2 e menos o gra-
diente da fun¸c˜ao de m´erito associada a reformula¸c˜ao.
2. Se o ˆangulo for suficientemente pequeno, a fun¸c˜ao de reformula¸c˜ao ´e apropriada para c´alculo da dire¸c˜ao de descida, e calcula-se a dire¸c˜ao de LM para a fun¸c˜ao de reformula¸c˜ao. Se n˜ao, calcula-se a dire¸c˜ao LM para a Fischer-Burmeister adaptada.
3. Calcula-se o ˆangulo entre essa dire¸c˜ao e menos o gradiente da fun¸c˜ao de m´erito12kFKP(x)k2.
4. Se o ˆangulo for suficientemente pequeno, essa ´e um boa dire¸c˜ao de descida e faz-se a busca na dire¸c˜ao calculada. Se n˜ao, a busca ´e feita na dire¸c˜ao de menos o gradiente da fun¸c˜ao de m´erito.
Como comprova o perfil de performance a seguir, de fato essa modifica¸c˜ao permitiu que a robustez do m´etodo LMMCP fosse transmitida para a penalidade exata e para a fun¸c˜ao m´ınimo. Al´em disso, a boa velocidade da penalidade n˜ao foi alterada e o m´etodo ´e quase sempre mais r´apido do que o LMMCP, resolvendo a mesma propor¸c˜ao de problemas.
0 0.2 0.4 0.6 0.8 1 1 2 4 8 LMMCP Exact Min
[1] H. Attouch and M. Th´era. A general duality principle for the sum of two operators. J.
Convex Anal., 3(1):1–24, 1996.
[2] A Auslender, M. Teboulle, and S. Ben-Tiba. Modified lagrangian methods for variational inequality problems. pre-print.
[3] A. Auslender, M. Teboulle, and S. Ben-Tiba. A logarithmic-quadratic proximal method for variational inequalities. Computational Optimization and Applications, 12:31–40, 1999.
[4] Alfred Auslender and Marc Teboulle. Lagrangian duality and related multiplier methods for variational inequality problems. SIAM J. Optim., 10(4):1097–1115, 2000.
[5] Alfred Auslender and Marc Teboulle. Asymptotic cones and functions in optimization
and variational inequalities. Springer Monographs in Mathematics. Springer-Verlag, New
York, 2003.
[6] Alfred Auslender, Marc Teboulle, and Sami Ben-Tiba. Interior proximal and multiplier methods based on second order homogeneous kernels. Math. Oper. Res., 24(3):645–668, 1999.
[7] Mokhtar S. Bazaraa, Hanif D. Sherali, and C. M. Shetty. Nonlinear programming. Wiley- Interscience [John Wiley & Sons], Hoboken, NJ, third edition, 2006. Theory and algo- rithms.
[8] D. Bertsekas. Constrained Optimization and Lagrange Multipliers. Academic Press, New York, 1982.
[9] D. Bertsekas. Nonlinear Programming. Athena Scientific, 1995.
[10] D. Bertsekas and A. Ozdaglar-Koksal. Enhanced optimality conditions and exact penalty functions, 2000.
[11] Stephen C. Billups, Steven P. Dirkse, and Michael C. Ferris. A comparison of large scale mixed complementarity problem solvers. Comput. Optim. Appl., 7(1):3–25, 1997. Computational issues in high performance software for nonlinear optimization (Capri, 1995).
[12] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2004.
[13] T. De Luca, F. Facchinei, and Kanzow C. A theoretical and numerical comparison of some semismooth algorithms for complementarity problems. Computational Optimization
and Applications, 16:173–205, 2000.
[14] G. di Pillo and L. Grippo. A new class of augmented Lagrangians in nonlinear program- ming. SIAM J. Control Optim., 17(5):618–628, 1979.
[15] G. Di Pillo and L. Grippo. A continuously differentiable exact penalty function for nonlinear programming problems with inequality constraints. SIAM J. Control Optim., 23(1):72–84, 1985.
[16] G. Di Pillo and L. Grippo. Exact penalty functions in constrained optimization. SIAM
J. Control Optim., 27(6):1333–1360, 1989.
[17] G. Di Pillo, L. Grippo, and F. Lampariello. A method for solving equality constrained optimization problems by unconstrained minimization. In Optimization techniques (Proc.
Ninth IFIP Conf., Warsaw, 1979), Part 2, volume 23 of Lecture Notes in Control and Information Sci., pages 96–105. Springer, Berlin, 1980.
[18] Jonathan Eckstein and Michael C. Ferris. Smooth methods of multipliers for complemen- tarity problems. Math. Program., 86(1, Ser. A):65–90, 1999.
[19] Jonathan Eckstein and Michael C. Ferris. Smooth methods of multipliers for complemen- tarity problems. Math. Program., 86(1, Ser. A):65–90, 1999.
[20] I. Ekeland. On the variational principle. J. Math. Anal. Appl., 47:324–353, 1974.
[21] Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and
complementarity problems, Vol. I. Springer Series in Operations Research. Springer-
[22] A. Fischer. A special Newton-type optimization method. Optimization, 24(3-4):269–284, 1992.
[23] R. Fletcher. A class of methods for nonlinear programming with termination and conver- gence properties. In Integer and nonlinear programming, pages 157–175. North-Holland, Amsterdam, 1970.
[24] R. Fletcher. A class of methods for non-linear programming. III. Rates of convergence. In Numerical methods for non-linear optimization (Conf., Dundee, 1971), pages 371–381. Academic Press, London, 1972.
[25] R. Fletcher. An exact penalty function for nonlinear programming with inequalities.
Math. Programming, 5:129–150, 1973.
[26] R. Fletcher and Shirley A. Lill. A class of methods for nonlinear programming. II. Com- putational experience. In Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin,
Madison, Wis., 1970), pages 67–92. Academic Press, New York, 1970.
[27] Torkel Glad and Elijah Polak. A multiplier method with automatic limitation of penalty growth. Math. Programming, 17(2):140–155, 1979.
[28] S. P. Han and O. L. Mangasarian. Exact penalty functions in nonlinear programming.
Math. Programming, 17(3):251–269, 1979.
[29] Christian Kanzow and Stefania Petra. On a semismooth least squares formulation of complementarity problems with gap reduction. Optim. Methods Softw., 19(5):507–525, 2004.
[30] Umberto Mosco. Dual variational inequalities. J. Math. Anal. Appl., 40:202–206, 1972.
[31] H. Mukai and E. Polak. A quadratically convergent primal-dual algorithm with global convergence properties for solving optimization problems with equality constraints. Math.
Programming, 9(3):336–349, 1975.
[32] H. Mukai and E. Polak. A quadratically convergent primal-dual algorithm with global convergence properties for solving optimization problems with equality constraints. Math.
Programming, 9(3):336–349, 1975.
[33] Jorge Nocedal and Stephen J. Wright. Numerical optimization. Springer Series in Ope- rations Research. Springer-Verlag, New York, 1999.
[34] T. Pennanen. Dualization of Monotone Generalized Equations. PhD thesis, University of Washington, 1999.
[35] Teemu Pennanen. Dualization of generalized equations of maximal monotone type. SIAM
J. Optim., 10(3):809–835, 2000.
[36] Tomasz Pietrzykowski. An exact potential method for constrained maxima. SIAM J.
Numer. Anal., 6:299–304, 1969.
[37] Li Qun Qi. Convergence analysis of some algorithms for solving nonsmooth equations.
Math. Oper. Res., 18(1):227–244, 1993.
[38] Li Qun Qi and Jie Sun. A nonsmooth version of Newton’s method. Math. Programming, 58(3, Ser. A):353–367, 1993.
[39] R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970.
[40] R. T. Rockafellar. Augmented lagrangians and applications of the proximal point algo- rithm in convex programming. Mathematics of Operations Research, 1:97–116, 1976.
[41] R. T Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal
on Control and Optimization, 14:887–898, August 1976.
[42] R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational analysis, volume 317 of Grun-
dlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1998.
[43] P. J. S. Silva. M´etodo de ponto proximal e separadores. Master’s thesis, Instituto de Matem´atica e Estat´ıstica, Universidade de S˜ao Paulo, 1997.
[44] P. J. S. Silva. T´opicos em M´etodos de Ponto Proximal. PhD thesis, Instituto de Ma-
tem´atica e Estat´ıstica, Universidade de S˜ao Paulo, 2000.
[45] P. J. S. Silva and J. Eckstein. Double-regularization proximal methods, with complemen- tarity applications. Computational Optimization and Applications, 33:115–156, 2006.
[46] W. I. Zangwill. Nonlinear Programming: An Unified Aproach. Prentice Hall, Englewood Cliffs, 1969.
[47] Willard I. Zangwill. Non-linear programming via penalty functions. Management Sci., 13:344–358, 1967.