Convex Optimization. Mikhail Moklyachuk

x ⪯ y Componentwise inequality between vectors x and y x ≺ y Strict componentwise inequality between vectors x and y X ⪯ Y Matrix inequality between symmetric matrices X and Y X ≺ Y Strict matrix inequality between symmetric matrices X and Y X ⪯_K Y Generalized inequality induced by proper cone K X ≺_K Y Strict generalized inequality induced by proper cone K int X Interior of set X ri X Relative interior of set X conv X Convex hull of set X aff X Affine hull of set X cone X Conic hull of set X Lin X Linear hull of set X

Closure of set X

Closed convex hull of set X dim X Dimension of set X ∂ X Boundary of set X K ^* Dual cone associated with cone K

A ray proceeding from a point

in the direction h Hpβ A hyperplane with the normal vector p

Half-spaces generated by hyperplane Hpβ π_X(a) Projection of point a onto set X ρ(X₁, X₂) Distance between sets X₁ and X₂ epi f Epigraph of function f Sr (f) Sublevel set of function f dom f Effective set of function f f₁ ⊕ f₂ Infimal convolution of functions f₁, f₂ μ(x\X) Minkowski function γX(x) Gauge function δ(x\X) Indicator function σ(x\X) Support function f ^* Conjugate function ∂f(x) Subdifferential of function f at point x

Superdifferential of function f at point x ∏(ℝ^m) Set of all non-empty subsets of the space ℝ^m

      Introduction

      Convex analysis and optimization have an increasing impact on many areas of mathematics and applications including control systems, estimation and signal processing, communications and networks, electronic circuit design, data analysis and modeling, statistics, and economics and finance. There are several fundamental books devoted to different aspects of convex analysis and optimization. Among them we can mention Optima and Equilibria: An Introduction to Nonlinear Analysis by Aubin (1998), Convex Analysis by Rockafellar (1970), Convex Analysis and Minimization Algorithms (in two volumes) by Hiriart-Urruty and Lemaréchal (1993) and its abridged version (2002), Convex Analysis and Nonlinear Optimization by Borwein and Lewis (2000), Convex Optimization by Boyd and Vandenberghe (2004), Convex Analysis and Optimization by Bertsekas et al. (2003), Convex Analysis and Extremal Problems by Pshenichnyj (1980), A Course in Optimization Methods by Sukharev et al. (2005), Convex Analysis: An Introductory Text by Van Tiel (1984), as well as other books listed in the bibliography (see Alekseev et al. (1984, 1987); Alekseev and Timokhov (1991); Clarke (1983); Hiriart-Urruty (1998); Ioffe and Tikhomirov (1979) and Nesterov (2004)).

      This book provides easy access to the basic principles and methods for solving constrained and unconstrained convex optimization problems. Structurally, the book has been divided into the following parts: basic methods for solving constrained and unconstrained optimization problems with differentiable objective functions, convex sets and their properties, convex functions, their properties and generalizations, subgradients and subdifferentials, and basic principles and methods for solving constrained and unconstrained convex optimization problems. The first part of the book describes methods for finding the extremum of functions of one and many variables. Problems of constrained and unconstrained optimization (problems with restrictions of inequality and inequality types) are investigated. The necessary and sufficient conditions of the extremum, the Lagrange method, are described.

The second part is the most voluminous in terms of the amount of material presented. Properties of convex sets and convex functions directly related to extreme problems are described. The basic principles of subdifferential calculus are outlined. The third part is devoted to the problems of mathematical programming. The problem of convex programming is considered in detail. The Kuhn–Tucker theorem is proved and the economic interpretations of the