Lagrange-type Functions in Constrained Non-Convex Optimization / Edition 1

by Alexander M. Rubinov, Xiao-qi Yang

Overview

Lagrange and penalty function methods provide a powerful approach, both as a theoretical tool and a computational vehicle, for the study of constrained optimization problems. However, for a nonconvex constrained optimization problem, the classical Lagrange primal-dual method may fail to find a mini­ mum as a zero duality gap is not always guaranteed. A large penalty parameter is, in general, required for classical quadratic penalty functions in order that minima of penalty problems are a good approximation to those of the original constrained optimization problems. It is well-known that penaity functions with too large parameters cause an obstacle for numerical implementation. Thus the question arises how to generalize classical Lagrange and penalty functions, in order to obtain an appropriate scheme for reducing constrained optimiza­ tion problems to unconstrained ones that will be suitable for sufficiently broad classes of optimization problems from both the theoretical and computational viewpoints. Some approaches for such a scheme are studied in this book. One of them is as follows: an unconstrained problem is constructed, where the objective function is a convolution of the objective and constraint functions of the original problem. While a linear convolution leads to a classical Lagrange function, different kinds of nonlinear convolutions lead to interesting generalizations. We shall call functions that appear as a convolution of the objective function and the constraint functions, Lagrange-type functions.

Product Details

ISBN-13:	9781402076275
Publisher:	Springer US
Publication date:	11/30/2003
Series:	Applied Optimization , #85
Edition description:	2003
Pages:	286
Product dimensions:	6.10(w) x 9.25(h) x 0.03(d)

Table of Contents

	Preface	ix
	Acknowledgments	xiii
1.	Introduction	1
1.1	Introduction and motivation	1
1.2	Duality	6
1.3	Mathematical tools	10
1.4	Notation	12
2.	Abstract Convexity	15
2.1	Abstract convexity	15
2.1.1	Definitions and preliminary results	15
2.1.2	Fenchel-Moreau conjugacy and subdifferential	18
2.1.3	Abstract convex at a point functions	20
2.1.4	Subdifferential	23
2.1.5	Abstract convex sets	24
2.2	Increasing positively homogeneous (IPH) functions	25
2.2.1	IPH functions: definitions and examples	25
2.2.2	IPH functions defined on R[superscript 2 subscript ++] and R[superscript 2 subscript +]	26
2.2.3	Associated functions	32
2.2.4	Strictly IPH functions	41
2.2.5	Multiplicative inf-convolution	45
3.	Lagrange-Type Functions	49
3.1	Conditions for minimum in terms of separation functions	49
3.1.1	Problem P(f,g) and its image space	49
3.1.2	Optimality conditions through the intersection of two sets	51
3.1.3	Optimality conditions via separation functions: linear separation	53
3.1.4	Optimality conditions via separation functions: general situation	56
3.1.5	Perturbation function	61
3.1.6	Lower semicontinuity of perturbation function	62
3.2	Lagrange-type functions and duality	66
3.2.1	Convolution functions	66
3.2.2	Lagrange-type functions	68
3.2.3	Lagrange-type functions with multipliers	69
3.2.4	Linear outer convolution function	71
3.2.5	Penalty-type functions	72
3.2.6	Auxiliary functions for methods of centers	73
3.2.7	Augmented Lagrangians	73
3.2.8	Duality: a list of the main problems	76
3.2.9	Weak duality	78
3.2.10	Problems with a positive objective function	81
3.2.11	Giannessi scheme and RWS functions	82
3.3	Zero duality gap	85
3.3.1	Zero duality gap property	85
3.3.2	Special convolution functions	87
3.3.3	Alternative approach	90
3.3.4	Zero duality gap property and perturbation function	92
3.4	Saddle points	96
3.4.1	Weak duality	96
3.4.2	Saddle points	96
3.4.3	Saddle points and separation	99
3.4.4	Saddle points, exactness and strong exactness	103
4.	Penalty-Type Functions	109
4.1	Problems with a single constraint	109
4.1.1	Reformulation of optimization problems	109
4.1.2	Transition to problems with a single constraint	110
4.1.3	Optimal value of the transformed problem with a single constraint	113
4.2	Penalization of problems with a single constraint based on IPH convolution functions	115
4.2.1	Preliminaries	115
4.2.2	Class P	117
4.2.3	Modified perturbation functions	118
4.2.4	Weak duality	120
4.2.5	Associated function of the dual function	120
4.2.6	Zero duality gap property	123
4.2.7	Zero duality gap property (continuation)	128
4.3	Exact penalty parameters	129
4.3.1	The existence of exact penalty parameters	129
4.3.2	Exact penalization (continuation)	131
4.3.3	The least exact penalty parameter	134
4.3.4	Some auxiliary results. Class B[subscript X]	137
4.3.5	The least exact penalty parameter (continuation)	141
4.3.6	Exact penalty parameters for function s[subscript k]	143
4.3.7	The least exact penalty parameter for function s[subscript k]	146
4.3.8	Comparison of the least exact penalty parameters for penalty functions generated by s[subscript k]	148
4.3.9	Lipschitz programming and penalization with a small exact penalty parameter	153
4.3.10	Strong exactness	155
4.4	The least exact penalty parameters via different convolution functions	156
4.4.1	Comparison of exact penalty parameters	156
4.4.2	Equivalence of penalization	159
4.5	Generalized Lagrange functions for problems with a single constraint	161
4.5.1	Generalized Lagrange and penalty-type functions	161
4.5.2	Exact Lagrange parameters: class P[subscript *]	163
4.5.3	Zero duality gap property for generalized Lagrange functions	164
4.5.4	Existence of Lagrange multipliers and exact penalty parameters for convolution functions s[subscript k]	168
5.	Augmented Lagrangians	173
5.1	Convex augmented Lagrangians	173
5.1.1	Augmented Lagrangians	173
5.1.2	Convex augmenting functions	176
5.2	Abstract augmented Lagrangians	177
5.2.1	Definition of abstract Lagrangian	178
5.2.2	Zero duality gap property and exact parameters	179
5.2.3	Abstract augmented Lagrangians	181
5.2.4	Augmented Lagrangians for problem P(f, g)	185
5.2.5	Zero duality gap property for a class of Lagrange-type functions	188
5.3	Level-bounded augmented Lagrangians	190
5.3.1	Zero duality gap property	190
5.3.2	Equivalence of zero duality gap properties	196
5.3.3	Exact penalty representation	201
5.4	Sharp augmented Lagrangians	206
5.4.1	Geometric interpretation	206
5.4.2	Sharp augmented Lagrangian for problems with a single constraint	210
5.4.3	Dual functions for sharp Lagrangians	212
5.5	An approach to construction of nonlinear Lagrangians	215
5.5.1	Links between augmented Lagrangians for problems with equality and inequality constraints	215
5.5.2	Supergradients of the dual function	219
6.	Optimality Conditions	221
6.1	Mathematical preliminaries	222
6.2	Penalty-type functions	227
6.2.1	Differentiable penalty-type functions	227
6.2.2	Nondifferentiable penalty-type functions	232
6.3	Augmented Lagrangian functions	244
6.3.1	Proximal Lagrangian functions	244
6.3.2	Augmented Lagrangian functions	249
6.4	Approximate optimization problems	252
6.4.1	Approximate optimal values	252
6.4.2	Approximate optimal solutions	260
7.	Appendix: Numerical Experiments	265
7.1	Numerical methods	265
7.2	Results of numerical experiments	268
	Index	285

Editorial Reviews

From the reviews:

"Lagrange and penalty functions provide a powerful approach for study of constrained optimization problems. … The book gives a systematic and unified presentation of many important results that have been obtained in this area during last several years. … The book develops a unified approach to duality and penalization and to convergence analysis of the first and second order optimality conditions. … A number of impressive new results on the existence of an exact penalty parameter have been obtained in the book." (Vladimir Gaitsgory, gazette The Australian Mathematical Society, Vol. 32 (4), 2005)

"In the monograph a whole optimization theory is developed … . Besides a large number of theoretical statements, results of numerical experiments showing usefulness of the presented approach are also reported … . It is shown that a much larger class of optimization problems than that of the convex ones allow for a thorough theoretical analysis and deep results. … The monograph can be recommended to researchers in mathematical optimization being in interested in nonconvex problems." (Stephan Dempe, OR-News, Issue 23, 2005)

From the Publisher