Section 1.6: Notes and Discussion

This chapter has selectively introduced core concepts from convex optimization that are most pertinent to the algorithms and applications discussed in later chapters. While the treatment here is necessarily concise, readers seeking a more comprehensive foundation are encouraged to consult several classic references.

The textbook by Boyd and Vandenberghe (Boyd & Vandenberghe, 2004) is an excellent and widely-used introduction to convex optimization. It covers convex sets, convex functions, duality, and optimality conditions in detail, and emphasizes geometric intuition and practical modeling. Many of the definitions and examples in this chapter are inspired by this text.

Nesterov’s Introductory Lectures on Convex Programming (Nesterov, 2004) provides a more mathematically rigorous treatment, including several key lemmas on smooth and strongly convex functions (Lemma 1.4 and Lemma 1.5) that are presented in this chapter. It is particularly useful for readers interested in complexity analysis and the theoretical underpinnings of first-order methods.

Other notable references include the texts by Rockafellar (Rockafellar, 1970) and Bertsekas (Bertsekas, 2009), which offer deep insights into convex analysis, duality theory, and constrained optimization from a classical perspective.

The KKT condition is named after three mathematicians, William Karush, Harold W. Kuhn, and Albert W. Tucker. It was known due to Kuhn and Tucker, who first published the conditions in 1951 (Kuhn & Tucker, 2014). Later scholars discovered that the necessary conditions for this problem had been stated by Karush in his master’s thesis in 1939 (Karush, 1939). The Danskin Theorem originates from the work of Danskin (Danskin, 1967), while its generalized form for subdifferentiable cases is attributed to Bertsekas (Bertsekas, 2005).

References

• Bertsekas, D. (2005). Control of uncertain systems with a set-membership description of the uncertainty.

• Bertsekas, D. P. (2009). Convex Optimization Theory. Athena Scientific.

• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

• Danskin, J. M. (1967). The Theory of Max-min and Its Applications to Weapons Allocation Problems. Springer.

• Karush, W. (1939). Minima of Functions of Several Variables with Inequalities as Side Constraints (M.Sc. thesis). University of Chicago, Department of Mathematics.

• Kuhn, H. W., & Tucker, A. W. (2014). Nonlinear Programming. In G. Giorgi & T. H. Kjeldsen (Eds.), Traces and Emergence of Nonlinear Programming (pp. 247–258). Springer Basel. https://doi.org/10.1007/978-3-0348-0439-4_11

• Nesterov, Y. (2004). Introductory Lectures on Convex Programming: A Basic Course. Springer.

• Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.