How to Read: Convex optimization [Reading Guide]

This guide will help you navigate "Convex optimization" (arXiv:2106.01946.pdf), a textbook from 2010 (updated in 2021) covering convex optimization, with a focus on its application in computer vision.

First pass (5–10 min)

What to skim in this paper:

• Title Page (Page 1): Note the authors and the publishing institution (MIPT). The title "Выпуклая оптимизация" (Convex optimization) clearly states the subject.
• Copyright/Description Page (Page 2): Read the brief description. It highlights that the book primarily covers convex optimization due to its rich theory and effective practical methods. It's intended for 3rd-year MIPT students studying "Optimization."
• Table of Contents (Pages 4–8): Quickly scan the main chapter titles and top-level sections. This reveals the book's structure: Chapter 1 on "Fundamentals of convex analysis," Chapter 2 on "Efficiency of numerical methods of convex optimization," and Chapter 3 on "Examples of problems and their practical solutions."
• Introduction (Pages 9–10): Read the introduction to understand the authors' pedagogical approach. They mention it's based on a two-semester course, omits some proofs to cover more themes, includes advanced material (e.g., conic optimization, robust optimization, accelerated gradient methods), and features a dedicated chapter for examples.
• Conclusion (Page 342): Briefly read the conclusion to grasp the authors' reflections on the book's scope and what it intentionally omits (e.g., non-convex, stochastic, distributed optimization).

What to notice:

• Contributions/Focus: This is a textbook, so its "contribution" is its comprehensive and specific pedagogical approach. It aims to provide a foundation in convex analysis and numerical methods, with a particular emphasis on advanced topics like conic optimization (including robust optimization) and accelerated gradient methods.
• Problem Setting: The book serves as a curriculum for a two-semester university course, bridging theoretical foundations with practical numerical methods. The core problem addressed is how to effectively solve convex optimization problems.
• Target Audience: Primarily students, suggesting a structured, didactic approach with definitions, theorems, and examples.

Second pass (up to 1 hour)

Using SpatialRead in the Second Pass

• Use the Screenshot tool to capture figures, tables, diagrams, and formulae from the PDF and use AI for simple explanations.
• Ask: "Explain Figure X at a high level", "Compare Table 2 vs 3", or "What does the y-axis represent here?"
• Download SpatialRead →

What sections/figures to focus on:

• Chapter 1: Fundamentals of convex analysis (Pages 14–132):
  • Section 1.2 "Convex sets and convex functions" (Page 17): Pay close attention to Definition 1.2 (convex set, Page 18) and Definition 1.4 (convex function, Page 19). Figure 1.1 and Figure 1.2 on Page 18 visually illustrate convex and non-convex sets.
  • Section 1.3 "Cones and order relations" (Page 24): Understand Definition 1.8 (cone, Page 24) and Definition 1.9 (convex cone, Page 25). Note the examples of cones like the Lorentz cone (Example 1.15, Page 26) and the semidefinite cone (Example 1.16, Page 26).
  • Section 1.9 "Extremal problems and duality" (Page 38): Grasp the formal definitions of optimization problems (1.11, 1.12, Page 38). Skim Section 1.9.1 "Lagrange multiplier rule" (Page 40) and Section 1.9.4 "Convex programming problems" (Page 47) to understand the general setup. Figure 1.3 on Page 45 provides a geometric interpretation of Lagrange multipliers. Figure 1.4 and Figure 1.5 on Pages 48-49 illustrate the geometric interpretation of duality.
  • Section 1.14 "Conic programming" (Page 96): This is a key advanced topic. Read Definition 1.20 (symmetric cone, Page 97) and the list of symmetric cones that are important for optimization.
• Chapter 2: Efficiency of numerical methods (Pages 133–257):
  • Section 2.1 "Black box concept" (Page 134): Understand the "oracle" model for analyzing algorithm complexity.
  • Table 2.1 "Optimal estimates of the number of oracle calls N (subgradient)" (Page 137): This table is crucial for understanding the theoretical efficiency of different methods for various classes of convex functions.
  • Skim the introductions of major method categories: Section 2.4 "Gradient descent methods" (Page 164), Section 2.6 "Conditional gradient method" (Page 176), Section 2.7 "Accelerated Meta-algorithm" (Page 178), and Section 2.9 "Interior-point methods" (Page 186).
• Chapter 3: Examples of problems and their practical solutions (Pages 258–341):
  • Scan the titles of the main sections (e.g., 3.1 "Wasserstein distance and barycenters," 3.2 "Relaxations of polynomial problems," 3.3 "Truss topology optimization," 3.4 "System identification," 3.5 "Applications of semidefinite programming") to get a sense of the practical applications.

Key terms/questions to note:

• What are the fundamental properties of convex sets and functions?
• How are optimization problems formally defined, and what is the role of duality?
• What are the main types of cones used in conic programming, and why are they important?
• How is algorithm efficiency measured in the "black box" model, and what are the optimal complexity bounds for different problem classes (refer to Table 2.1)?
• What are the core ideas behind gradient descent, conditional gradient, accelerated methods, and interior-point methods?
• What kinds of real-world problems can be formulated and solved using convex optimization?

Third pass (1–5 hours)

Using SpatialRead in the Third Pass

• Highlight complex keywords, dense paragraphs, equations, or proofs and ask for a plain-English explanation that preserves notation.
• Use AI to explain the concepts in a way that is easy to understand.
• Ask for alternative phrasings or analogies to confirm understanding without changing technical meaning.
• Connect concepts with each other using AI to build a comprehensive understanding of the paper.
• Download SpatialRead →

Deep reading guidance:

• Methods:
  • Convex Analysis (Chapter 1): Delve into the details of the proofs or the underlying ideas. For instance, study the derivation of the Karush-Kuhn-Tucker (KKT) conditions (Theorem 1.16, Page 51) and the conditions for strong duality (Section 1.9.5, Page 54, and Slater's conditions, Page 56). Understand the various forms of Farkas' Lemma (Section 1.12, Page 82) and their implications.
  • Numerical Methods (Chapter 2):
    • For gradient-type methods, analyze the convergence proofs for specific algorithms. For example, Algorithm 2.5 (Page 170) and Algorithm 2.6 (Page 171) provide optimal rates for smooth convex problems. Understand the concept of "inexact oracle" (Section 2.10.1, Page 212) and how it affects convergence, as described in Algorithm 2.10 (Page 223) and Algorithm 2.12 (Page 235).
    • For interior-point methods, focus on the properties of self-concordant barriers (Section 2.9.1, Page 187) and how they enable polynomial-time complexity. Understand the geometric interpretation of Newton's method (Figure 2.1, Page 191).
    • Conic Programming (Section 1.14): Study how different problem types (e.g., linear programming, conic quadratic programming, semidefinite programming) are represented as conic programs (Section 1.14.1, Page 96). Pay attention to the transformations and relaxations of quadratic problems (Section 1.14.2, Page 99) and the concept of conic representation of sets and functions (Section 1.14.3, Page 101).
    • Robust Optimization (Section 1.15): Examine the robust version of conic programming (Section 1.15.1, Page 124) and the concept of positive cones (Section 1.15.2, Page 126), which are critical for handling uncertainty.
• Results: The "results" are the theoretical guarantees and complexity bounds. Compare the performance of different methods (e.g., gradient descent vs. accelerated methods, exact vs. inexact oracles) as discussed in sections like 2.10.6 (Page 238) and 2.10.8 (Page 245).
• Limitations: Re-read the conclusion (Page 342) to reinforce the book's stated limitations and understand why certain advanced topics are not covered.

Replication pointers (if applicable):

• Work through examples: Chapter 3 ("Examples of problems and their practical solutions," Page 258) is designed for practical application. Choose a few examples (e.g., Monge problem in Section 3.1.1, truss topology in Section 3.3.1, system identification in Section 3.4, or max clique in Section 3.5.5) and try to formulate them mathematically based on the concepts from Chapters 1 and 2.
• Engage with exercises: The "Упражнение" (Exercise) prompts scattered throughout the text (e.g., Exercise 1.1 on Page 16, Exercise 1.3 on Page 19, Exercise 1.6 on Page 29) are excellent opportunities to test your understanding and apply the theoretical concepts.
• Understand modeling paradigms: Section 3.9.2 "Optimization packages" (Page 322) discusses how optimization problems are formulated for numerical solvers. While specific tools are not to be mentioned in this guide, understanding the concept of modeling languages (like the example in Section 3.9.2, Page 323) is crucial for translating mathematical formulations into solvable problems. Focus on the structure of these examples to learn how to represent problems effectively.