Abstract
This paper presents, within a unified framework, a potentially powerful canonical dual transformation method and associated generalized duality theory in nonsmooth global optimization. It is shown that by the use of this method, many nonsmooth/nonconvex constrained primal problems in ℝn can be reformulated into certain smooth/convex unconstrained dual problems in ℝm with m ⩽ n and without duality gap, and some NP-hard concave minimization problems can be transformed into unconstrained convex minimization dual problems. The extended Lagrange duality principles proposed recently in finite deformation theory are generalized suitable for solving a large class of nonconvex and nonsmooth problems. The very interesting generalized triality theory can be used to establish nice theoretical results and to develop efficient alternative algorithms for robust computations.
Article PDF
Similar content being viewed by others
References
Auchmuty, G (1983), Duality for non-convex variational principles, J. Diff. Equations, 50: 80-145
Auchmuty, G (1989), Duality algorithms for nonconvex variational principles, Numer. Funct. Anal. and Optim., 10: 211-264.
Auchmuty, G. (1997), Min-max problems for non-potential operator equations. in Optimization Methods in Partial Differential Equations (South Hadley, MA, 1996), 19-28, Contemp. Math., 209, Amer. Math. Soc., Providence, RI, 1997.
Benson, H. (1995), Concave minimization: theory, applications and algorithms, in R. Horst and P. Pardalos, (eds.) Handbook of Global Optimization, Kluwer Academic Publishers, pp. 43-148.
Casciaro, R. and Cascini, A. (1982), A mixed formulation and mixed finite elements for limit analysis, Int. J. Solids and Struct., 19: 169-184.
Clarke, F.H. (1985), The dual action, optimal control, and generalized gradients, Mathematical Control Theory, Banach Center Publ., 14, PWN, Warsaw, pp. 109-119.
Crouzeix, J.P. (1981), Duality framework in quasiconvex programming, in S. Schaible and W.T. Ziemba, (eds.) Generalized Convexity in Optimization and Economics, Academic Press, pp. 207-226.
Dem'yanov, V.F., Stavroulakis, G.E., Polyakova, L.N. and Panagiotopoulos, P.D. (1996), Quasidifferentiability and Nonsmooth Modelling in Mechanics, Engineering and Economics. Kluwer Academic Publishers: Dordrecht.
Ekeland, I. (1977), Legendre duality in nonconvex optimization and calculus of variations, SIAM J. Control and Optimiz., 15: 905-934.
Ekeland, I (1990), Convexity Methods in Hamiltonian Mechanics, Springer-Verlag, 247pp.
Ekeland, I and Temam, R (1976), Convex Analysis and Variational Problems, North-Holland.
Ericksen, J.L. (1975). Equilibrium of bars, J. Elasticity 5: 191-202.
Fukushima, M. and Qi, L.Q. (eds) (1999), Reformulation — Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods. Kluwer Academic Publishers, Dordrecht/Boston/ London, 161-180.
Gao, D.Y. (1988a). On the complementary bounding theorems for limit analysis, Int. J. Solids Struct., 24: 545-556.
Gao, D.Y. (1988b), Panpenalty finite element programming for plastic limit analysis, Compute & Struct., 28: 749-755.
Gao, D.Y. (1996), Post-buckling analysis of nonlinear extended beam theory and dual variational principles, in L.A. Godoy, M. Rysz and L. Suarez, (eds.), Applied Mechanics in Americas Vol. 4, eds. Proc of PACAM V, San Juan, Puerto Rico, Iowa Univ. Press.
Gao, D.Y. (1997), Dual extremum principles in finite deformation theory with applications in post-buckling analysis of nonlinear beam model, Appl. Mech. Reviews, ASME, 50 (11): S64-S71.
Gao, D.Y. (1998a), Bi-complementarity and duality: A framework in nonlinear equilibria with application to contact problem, J. Math. Analy. Appl., 221: 672-697.
Gao, D.Y. (1998b), Duality, triality and complementary extremum principles in nonconvex parametric variational problems with applications, IMA J. Applied Math., 61, 199-235.
Gao, D.Y. (1998c), Minimax and triality theory in nonsmooth variational problems, in M. Fukushima and L.Q. Qi (eds.), Reformulation — Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers, Dordrecht/Boston/ London, pp. 161-180.
Gao, D.Y. (1999a), Duality Principles in Nonconvex Systems: Theory, Methods and Applications, Kluwer Academic Publishers, Dordrecht/Boston/London, 472pp.
Gao, D.Y. (1999b), Duality-Mathematics, in John G. Webster (ed), Encyclopedia of Electrical and Electronics Engineering, John Wiley & Sons, Inc., 6, 68-77.
Gao, D.Y., Ogden, R.W. and Stavroulakis, G.E. (eds.) (2000), Nonsmooth and Nonconvex Mechanics, Kluwer Academic Publishers, Dordrecht/Boston/London.
Gao, D.Y. and Strang, G. (1989), Geometric nonlinearity: Potential energy, complementary energy, and the gap function, Quart. Appl. Math., XLVII(3): 487-504.
Gay, D.M., Overton, M.L. and Wright, M.H. (1998), A primal-dual interior method for nonconvex nonlinear programming. In Advances in nonlinear programming (Beijing, 1996), 31-56, Appl. Optim., 14, Kluwer Acad. Publ., Dordrecht, 1998.
Hiriart-Urruty, J.-B. (1985), Generalized differentiability, duality and optimization for problems dealing with differences of convex functions, in F.H. Clarke V.F. Demyanov and F. Giannessi, (eds.), Lecture Notes in Economics and Mathematical Systems, Plenum, New York.
Horst, R. and Pardalos, P.M. (1995), Handbook in Global Optimization, Kluwer Academic Publishers, Boston.
Maier, G. (1969), Complementarity plastic work theorems in piecewise-linear elastoplasticity, Int. J. Solids Struct., 5: 261-270.
Maier, G., Carvelli, V. and Cocchetti, G. (2000), On direct methods for shakedown and limit analysis, Plenary lecture at the 4th EUROMECH Solid Mechanics Conf., Metz, France, June 26–30, to appear in Eur. J. Mech., A/Solids.
Martínez-Legaz, J.-E. and Singer, I. (1995), Dualities associated to binary operations on R.J. Convex Anal., 2, (1–2): 185-209.
Martínez-Legaz, J.-E.; and Singer, I. (1998). On Φ-convexity of convex functions. Linear Algebra Appl., 278 (1–3): 163-181.
Mistakidis, E.S. and Stavroulakis, G.E. (1998), Nonconvex Optimization in Mechanics, Algorithms, Heuristics and Engineering Applications by the F.E.M., Kluwer Academic Publishers, Dordrecht /Boston/London, 285pp.
Moreau, J.J. (1968), La notion de sur-potentiel et les liaisons unilatérales en élastostatique, C.R. Acad. Sc. Paris, 267 A, 954-957.
Moreau, J.J., Panagiotopoulos, P.D. and Strang, G. (1988), Topics in nonsmooth mechanics. Birkhuser Verlag, Basel-Boston, MA, 329pp.
Motreanu, D. and Panagiotopoulos, P.D. (1999). Minimax Theorems and Qualitative Properties of the Solutions of Hemivariational Inequalities. Kluwer Academic Publishers, Dordrecht.
Panagiotopoulos, P.D. (1985), Inequality Problems in Mechanics and Applications, Birkhäuser, Boston.
Penot, J.P. and Volle, M. (1990), On quasiconvex duality, Math. Oper. Res., 14: 195-227.
Polyak, R.A. and Griva, I. (2000), Nonlinear rescaling in discrete minimax, in D.Y. Gao, R.W. Ogden and G. Stavroulakis (eds.), Nonsmooth and Nonconvex Mechanics, Kluwer Academic Publishers, Dordrecht/Boston/London.
Rockafellar, R.T. (1974), Conjugate Duality and Optimization, SIAM, J.W. Arrowsmith Ltd., Bristol 3, England.
Rockafellar, R.T. and Wets, R.J.B. (1997). Variational analysis, Springer: Berlin, New York.
Sewell, M.J. (1987), Maximum and Minimum Principles, Cambridge Univ. Press, 468pp.
Singer, I. (1986), A general theory dual optimization problems, J. Math. Anal. Appl., 116: 77-130.
Singer, I. (1992). Some further duality theorems for optimization problems with reverse convex constraint sets. J. Math. Anal. Appl., 171(1): 205-219.
Singer, I. (1996), On dualities between function spaces. Math. Methods Oper. Res., 43(1): 35-44.
Singer, I. (1998), Duality for optimization and best approximation over finite intersections. Numer. Funct. Anal. Optim., 19(7–8), 903-915.
Strang, G. (1986), Introduction to Applied Mathematics, Wellesley-Cambridge Press, 758pp.
Thach, P.T. (1993), Global optimality criterion and a duality with a zero gap in nonconvex optimization. SIAM J. Math. Anal. 24(6): 1537-1556.
Thach, P.T. (1995), Diewert-Crouzeix conjugation for general quasiconvex duality and applications. J. Optim. Theory Appl., 86(3): 719-743.
Thach, P.T., Konno, H. and Yokota, D. (1996), Dual approach to minimization on the set of Pareto-optimal solutions. J. Optim. Theory Appl., 88(3): 689-707.
Toland, J.F. (1978), Duality in nonconvex optimization, J. Math. Anal. and Appl., 66: 399-415.
Toland, J.F. (1979), A duality principle for non-convex optimization and the calculus of variations, Arch. Rat. Mech. Anal. 71: 41-61
Tuy, H. (1991), Polyhedral annexation, dualization and dimension reduction technique in global optimization, J. Global Optim., 1: 229-244.
Tuy, H. (1995), D.C. optimization: theory, methods and algorithms, in R. Horst and P. Pardalos (eds.), Handbook of Global Optimization, Kluwer Academic Publishers, 149-216.
Walk, M. (1989), Theory of duality in mathematical programming, Springer-Verlag, Wien/New York.
Wright, M.H. (1998), The interior-point revolution in constrained optimization, in R. DeLeone, A. Murli, P. M. Pardalos and G. Toraldo (eds.), High-Performance Algorithms and Software in Nonlinear Optimization 359-381, Kluwer Academic Publishers, Dordrecht.
Wright, S.J. (1997), Primal-Dual Interior-Point Methods, SIAM, Philadelphia, PA, 289pp.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Yang Gao, D. Canonical Dual Transformation Method and Generalized Triality Theory in Nonsmooth Global Optimization*. Journal of Global Optimization 17, 127–160 (2000). https://doi.org/10.1023/A:1026537630859
Issue Date:
DOI: https://doi.org/10.1023/A:1026537630859