Mikhail Moklyachuk - Convex Optimization

1 Cover

2 Title Page Series Editor Nikolaos Limnios

3 Copyright First published 2020 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd 27-37 St George’s Road London SW19 4EU UK www.iste.co.uk John Wiley & Sons, Inc. 111 River Street Hoboken, NJ 07030 USA www.wiley.com © ISTE Ltd 2020 The rights of Mikhail Moklyachuk to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Control Number: 2020943973 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 978-1-78630-683-8

4 Notations

5 Introduction

6 1 Optimization Problems with Differentiable Objective Functions1.1. Basic concepts 1.2. Optimization problems with objective functions of one variable 1.3. Optimization problems with objective functions of several variables 1.4. Constrained optimization problems 1.5. Exercises

7 2 Convex Sets2.1. Convex sets: basic definitions 2.2. Combinations of points and hulls of sets 2.3. Topological properties of convex sets 2.4. Theorems on separation planes and their applications 2.5. Systems of linear inequalities and equations 2.6. Extreme points of a convex set 2.7. Exercises

8 3 Convex Functions3.1. Convex functions: basic definitions 3.2. Operations in the class of convex functions 3.3. Criteria of convexity of differentiable functions 3.4. Continuity and differentiability of convex functions 3.5. Convex minimization problem 3.6. Theorem on boundedness of Lebesgue set of a strongly convex function 3.7. Conjugate function 3.8. Basic properties of conjugate functions 3.9. Exercises

9 4 Generalizations of Convex Functions4.1. Quasi-convex functions 4.2. Pseudo-convex functions 4.3. Logarithmically convex functions 4.4. Convexity in relation to order 4.5. Exercises

10 5 Sub-gradient and Sub-differential of Finite Convex Function 5.1. Concepts of sub-gradient and sub-differential 5.2. Properties of sub-differential of convex function 5.3. Sub-differential mapping 5.4. Calculus rules for sub-differentials 5.5. Systems of convex and linear inequalities 5.6. Exercises

11 6 Constrained Optimization Problems6.1. Differential conditions of optimality 6.2. Sub-differential conditions of optimality 6.3. Exercises 6.4. Constrained optimization problems 6.5. Exercises 6.6. Dual problems in convex optimization 6.7. Exercises

12 Solutions, Answers and Hints

13 References

14 Index

15 End User License Agreement

1 Chapter 1 Figure 1.1. Example 1.5 Figure 1.2. Example 1.6

2 Chapter 2 Figure 2.1. Convex set X 1 . Non-convex set X 2 Figure 2.2. X 1 is a cone . X 2 is a convex cone Figure 2.3. Conjugate cones Figure 2.4. Affine set and linear subspace Figure 2.5. a) Convex hull. b) Conic hull Figure 2.6. a) Convex polyhedron. b) Polyhedral cone Figure 2.7. Unbounded closed convex set Figure 2.8. Projection of a point onto a set Figure 2.9. Sets X1 and X2 are: a) properly separated; b) strongly separated; c)...Figure 2.10. a), c) Properly supporting hyperplanes; b) supporting hyperplane

3 Chapter 3Figure 3.1. Convex function Figure 3.2. Epigraph of convex function Figure 3.3. Epigraph of nonconvex function Figure 3.4. Separating linear function

4 Chapter 5Figure 5.1. Example 5.1

1 Cover

2 Table of Contents

3 Title Page Series Editor Nikolaos Limnios

4 Copyright First published 2020 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd 27-37 St George’s Road London SW19 4EU UK www.iste.co.uk John Wiley & Sons, Inc. 111 River Street Hoboken, NJ 07030 USA www.wiley.com © ISTE Ltd 2020 The rights of Mikhail Moklyachuk to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Control Number: 2020943973 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 978-1-78630-683-8

5 Notations

6 Introduction

7 Begin Reading

8 Solutions, Answers and Hints

9 References

10 Index

11 End User License Agreement

1 v

2 iii

3 iv

4 ix

5 x

6 xi

7 xii

8 1

9 2

10 3

11 4

12 5

13 6

14 7

15 8

16 9

17 10

18 11

19 12

20 13

21 14

22 15

23 16

24 17

25 18

26 19

27 20

28 21

29 22

30 23

31 24

32 25

33 26

34 27

35 28

36 29

37 30

38 31

39 32

40 33

41 34

42 35

43 36

44 37

45 38

46 39

47 40

48 41

49 42

50 43

51 44

52 45

53 46

54 47

55 48

56 49

57 50

58 51

59 52

60 53

61 54

62 55

63 56

64 57

65 58

66 59

67 60

68 61

69 62

70 63

71 64

72 65

73 66

74 67

75 68

76 69

77 70

78 71

79 72

80 73

81 74

82 75

83 76

84 77

85 78

86 79

87 80

88 81

89 82

90 83

91 84

92 85

93 86

94 87

95 88

96 89

97 90

98 91

99 92

100 93

101 94

102 95

103 96

104 97

105 98

106 99

107 100

108 101

109 102

110 103

111 104

112 105

113 106

114 107

115 108

116 109

117 111

118 112

119 113

120 114

121 115

122 116

123 117

124 118

125 119

126 120

127 121

128 122

129 123

130 124

131 125

132 126

133 127

134 128

135 129

136 130

137 131

138 132

139 133

140 134

141 135

142 136

143 137

144 138

145 139

146 140

147 141

148 142

149 143

150 144

151 145

152 146

153 147

154 148

155 149

156 150

157 151

158 152

159 153

160 154

161 155

162 156

163 157

164 158

165 159

166 160

167 161

168 162

169 163

170 164

171 165