Topology Foundations Slides The Weierstrass Foundation
Topology and the Existence of Optimal Solutions
The Existential Problem
Why do some optimization problems have no solution?
Consider minimizing \( f(x) = \frac{1}{x} \) on \( (0, 1] \):
The values decrease as \( x \to \infty \), but the domain is restricted.
As \( x \to 0^+ \), \( f(x) \to \infty \).
There is no minimum value attained within the set.
The Heine-Borel Theorem
Definition
A subset \( S \subset \mathbb{R}^n \) is compact if and only if it is both closed and bounded .
Closed: Contains all its limit points.
Bounded: Contained within a ball of finite radius.
Compactness ensures that "the boundary is reachable" and "the values cannot run away to infinity."
Continuity Matters
Continuity preserves the topological "connectedness" and "compactness" from the domain to the range.
Topological Definition
A function \( f: S \to \mathbb{R} \) is continuous if for every open set \( V \subset \mathbb{R} \), the inverse image \( f^{-1}(V) \) is open in \( S \).
Crucial Property
The image of a compact set under a continuous mapping is compact .
The Weierstrass Extreme Value Theorem
Let \( S \subset \mathbb{R}^n \) be a non-empty compact set and let \( f: S \to \mathbb{R} \) be a continuous function .
Then \( f \) attains its minimum and maximum on \( S \).
Mathematically: There exist \( x_{min}, x_{max} \in S \) such that \( f(x_{min}) \le f(x) \le f(x_{max}) \) for all \( x \in S \).
Relaxing the Assumptions
ADVANCED
Lower Semi-Continuity (LSC)
Informally: "Can only jump down."
Necessary for the existence of a minimum . A function is LSC if its epigraph is a closed set.
Upper Semi-Continuity (USC)
Informally: "Can only jump up."
Necessary for the existence of a maximum .
Generalization
An LSC function on a compact set attains its infimum.
What if the domain isn't compact?
The Coercivity Condition
A continuous function \( f: \mathbb{R}^n \to \mathbb{R} \) is coercive if: \( \lim_{\|x\| \to \infty} f(x) = \infty \)
Coercivity + Continuity on \( \mathbb{R}^n \) guarantees a global minimum exists.
Why? Because we can truncate the problem to a large enough compact ball.
Checklist for Existence
1
Continuity
The objective function must behave nicely.
2
Compactness
Closed and Bounded constraints in \(\mathbb{R}^n\).
3
Attainment
Does the function actually reach its bounds?
Topology and Existence Worksheet Existence and Topology
Theoretical Foundations of Convex Optimization • Lesson 1
Name:
Date:
Learning Objective
To mathematically verify the existence of optimal solutions using point-set topology. You will apply the Weierstrass Extreme Value Theorem and explore the implications of compactness and continuity on \(\mathbb{R}^n\).
1
Topological Verification
Determine if the following sets \( S \subset \mathbb{R}^2 \) are compact. Justify your answer using the Heine-Borel Theorem.
a) \( S = \{ (x, y) \in \mathbb{R}^2 \mid x^2 + y^2 < 1 \} \)
b) \( S = \{ (x, y) \in \mathbb{R}^2 \mid x + y = 1, x \ge 0, y \ge 0 \} \)
2
The Weierstrass Test
Consider the function \( f(x, y) = e^{-(x^2 + y^2)} \) on the domain \( D = \{ (x, y) \in \mathbb{R}^2 \mid x^2 + y^2 \ge 1 \} \).
i) Is \( D \) compact? Why or why not?
ii) Does \( f \) attain a maximum on \( D \)? If so, where? If not, why?
iii) Does \( f \) attain a minimum on \( D \)? Justify your answer using limits or topological properties.
3
Analytical Proof: Continuous Images
Theorem: Let \( f: S \to \mathbb{R}^m \) be a continuous function. If \( S \subset \mathbb{R}^n \) is compact, then the image \( f(S) = \{ f(x) \mid x \in S \} \) is compact.
Provide a formal proof sketch of this theorem using the property that a set is compact if and only if every sequence in the set has a convergent subsequence whose limit is in the set (Sequential Compactness).
4
Extension: Lower Semi-Continuity (LSC)
A function is LSC if for every \( x \in S \), \( \liminf_{y \to x} f(y) \ge f(x) \). Prove that if \( f \) is LSC on a compact set \( S \), it attains its infimum.
© 2026 Advanced Optimization Lab
Page 2 of 2
Convex Geometry Slides Geometric Landscapes
Convex Sets, Hulls, and Hyperplanes
Defining Convexity
SET THEORY
A set \( C \subset \mathbb{R}^n \) is convex if for any \( x, y \in C \) and any \( \lambda \in [0, 1] \):
\( \lambda x + (1-\lambda)y \in C \)
"The line segment connecting any two points in the set must lie entirely within the set."
Convex
Non-Convex
The Building Blocks
Hyperplanes
\( \{ x \mid a^T x = b \} \)
The 'flat' boundaries of our optimization space.
Halfspaces
\( \{ x \mid a^T x \le b \} \)
The foundational constraints of linear programming.
Euclidean Balls
\( \{ x \mid \|x-x_c\|_2 \le r \} \)
A natural result of norm-based constraints.
How to Build New Convex Sets
Intersection
The intersection of any number of convex sets is convex.
Affine Mappings
If \( C \) is convex, \( f(C) = \{Ax+b \mid x \in C\} \) is convex.
Minkowski Sum
\( C_1 + C_2 = \{x+y \mid x \in C_1, y \in C_2\} \)
Theorem
"A polyhedron is the intersection of a finite number of halfspaces and hyperplanes."
The Convex Hull
Definition
The convex hull of a set \( S \), denoted \( \text{conv}(S) \), is the set of all convex combinations of points in \( S \):
\( \{ \sum \lambda_i x_i \mid x_i \in S, \lambda_i \ge 0, \sum \lambda_i = 1 \} \)
Think of it as the smallest convex set that contains all points in \( S \).
Visual Metaphor
Stretch a rubber band around a set of pegs and let it snap tight.
Separating Hyperplanes
Separating Hyperplane Theorem
Suppose \( C \) and \( D \) are disjoint convex sets. Then there exists \( a \neq 0 \) and \( b \) such that:
\( a^T x \le b \) for all \( x \in C \)
This is a fundamental tool for proving optimality conditions and duality.
Supporting Hyperplanes
A supporting hyperplane of a set \( C \) at a boundary point \( x_0 \) is a hyperplane that:
Contains \( x_0 \)
Has the entire set \( C \) on one side
Convex Geometry Workshop Worksheet Convex Geometry Workshop
Theoretical Foundations of Convex Optimization • Lesson 2
Name:
Date:
SECTION 1
Verification & Proof
1.1 Use the mathematical definition of a convex set (\( \lambda x + (1-\lambda)y \in C \)) to prove that the halfspace \( H = \{ x \in \mathbb{R}^n \mid a^T x \le b \} \) is a convex set.
1.2 Show that if \( C_1 \) and \( C_2 \) are convex sets, their intersection \( C_1 \cap C_2 \) is also a convex set.
SECTION 2
The Convex Hull
Recall
\( \text{conv}(S) = \{ \sum_{i=1}^k \lambda_i x_i \mid x_i \in S, \lambda_i \ge 0, \sum \lambda_i = 1 \} \)
2.1 Sketch the convex hull of the following set of points in \( \mathbb{R}^2 \):
0
x
y
List the points that form the vertices of the resulting polygon (the "extreme points"):
SECTION 3
Separation & Supporting Hyperplanes
3.1 Consider the set \( C = \{ (x, y) \in \mathbb{R}^2 \mid y \ge x^2 \} \). Find the equation of a supporting hyperplane (a line in \( \mathbb{R}^2 \)) to the set \( C \) at the point \( (2, 4) \).
3.2 Given two disjoint sets \( C = \{ x \in \mathbb{R}^2 \mid \|x\|_2 \le 1 \} \) and \( D = \{ x \in \mathbb{R}^2 \mid x_1 \ge 2 \} \). Provide the vector \( a \) and constant \( b \) for a strictly separating hyperplane \( a^T x = b \).
Theoretical Challenge
The Separating Hyperplane Theorem requires sets to be convex. Provide a counter-example (sketch or description) of two non-convex disjoint sets that cannot be separated by a hyperplane.
Convex Optimization Series L2 • Geometric Analysis
Convex Functions Properties Slides The Convex Landscape
Functions, Epigraphs, and Global Extrema
What is a Convex Function?
A function \( f: \mathbb{R}^n \to \mathbb{R} \) is convex if its domain \( \text{dom } f \) is a convex set and for all \( x, y \in \text{dom } f, \lambda \in [0, 1] \):
\( f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y) \)
"The function value of the average is less than or equal to the average of the function values."
The Geometric Link: Epigraphs
Definition
The epigraph of \( f \) is the set of points lying above the graph:
\( \text{epi } f = \{ (x, t) \mid x \in \text{dom } f, f(x) \le t \} \)
The Bridge Theorem:
"A function is convex if and only if its epigraph is a convex set."
EPI f
Jensen's Inequality
For a convex function \( f \) and a random variable \( X \):
\( f(\mathbb{E}[X]) \le \mathbb{E}[f(X)] \)
Discrete Form
\( f(\sum \lambda_i x_i) \le \sum \lambda_i f(x_i) \)
Applications
Arithmetic-Geometric Mean Inequality, Information Theory (Entropy), Economics (Utility).
The Fundamental Theorem
"For a convex function, any local minimum is also a global minimum ."
Why it matters:
Optimization algorithms (like Gradient Descent) won't get stuck in "bad" local valleys.
Uniqueness:
If \( f \) is strictly convex , the global minimum is unique.
The Differentiable Case
1st Order Condition
A differentiable \( f \) is convex iff for all \( x, y \):
\( f(y) \ge f(x) + \nabla f(x)^T(y-x) \)
Geometric Intuition: The tangent plane at any point is a global underestimator of the function.
Building Convex Functions
1
Non-negative Scaling: \( \alpha f \) (for \( \alpha \ge 0 \))
2
Sum: \( f_1 + f_2 \)
3
Pointwise Max: \( \max(f_1, f_2) \)
"The maximum of a set of convex functions is always convex. The minimum is not necessarily convex."
Summary of Properties
Verification
Check the definition, epigraph, or 1st/2nd order conditions.
Convex Functions Problem Set Worksheet Convex Landscapes
Lesson 3: Properties of Convex Functions
MATH-701: ADVANCED OPTIMIZATION
Name:
"Your objective is to master the analytical tools for identifying convexity and to formally prove the unique relationship between local and global minima in convex domains."
1 Definitional Proofs
1.1 Use the definition of convexity (\( f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y) \)) to prove that the quadratic function \( f(x) = x^2 \) is convex on \( \mathbb{R} \).
1.2 Prove that the sum of two convex functions, \( g(x) = f_1(x) + f_2(x) \), is itself a convex function.
2 Jensen's Inequality
2.1 Consider the strictly convex function \( f(x) = -\ln(x) \) for \( x > 0 \). Use Jensen's Inequality to derive the Arithmetic-Geometric Mean Inequality : \[ \frac{1}{n} \sum_{i=1}^n x_i \ge \sqrt[n]{x_1 x_2 \dots x_n} \]
3 Global vs. Local
Theorem to Prove:
Let \( f \) be a convex function on a convex set \( C \). If \( x^* \) is a local minimum of \( f \) on \( C \), then \( x^* \) is a global minimum.
Proof structure: Assume \( x^* \) is a local minimum but not a global minimum. This implies there exists some \( z \in C \) such that \( f(z) < f(x^*) \). Use the definition of convexity to show this leads to a contradiction of \( x^* \) being a local minimum.
Properties of Convex Functions Lesson 3 Worksheet
Multivariate Second-Order Slides Curvature and the Hessian
Second-Order Conditions in Multivariate Spaces
Taylor's Quadratic Approximation
Near a point \( x \), a twice-differentiable function \( f \) can be approximated as:
\( f(x + \Delta x) \approx f(x) + \nabla f(x)^T \Delta x + \frac{1}{2} \Delta x^T \mathbf{H}(x) \Delta x \)
"The Hessian matrix \(\mathbf{H}(x)\) captures the local curvature of the function."
Anatomy of the Hessian
The Hessian \( \nabla^2 f(x) \) is the matrix of second-order partial derivatives:
\( [H]_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} \)
If \( f \) has continuous second derivatives, the Hessian is symmetric (Clairaut's Theorem).
Structure
[ f_xx f_xy f_xz ]
[ f_yx f_yy f_yz ]
[ f_zx f_zy f_zz ]
Definiteness and Convexity
Positive Definite (PD)
\( v^T H v > 0 \) for all \( v \neq 0 \)
Strictly convex; Unique global minimum.
Positive Semi-Definite (PSD)
\( v^T H v \ge 0 \) for all \( v \)
Convex; Global minimum exists (but may not be unique).
Indefinite
\( v^T H v \) can be \( + \) or \( - \)
Saddle point; Non-convex.
Spectral Analysis
A symmetric matrix is PSD if and only if all its eigenvalues \( \lambda_i \) are non-negative :
\( \lambda_i \ge 0, \quad \forall i \)
This connects Linear Algebra directly to the geometry of Optimization.
Sylvester's Criterion
For checking Positive Definiteness without calculating eigenvalues:
Leading Principal Minors
All upper-left \( k \times k \) sub-determinants must be strictly positive.
Example (2x2):
1. \( H_{11} > 0 \)
2. \( \text{det}(H) > 0 \)
Note: Checking PSD (non-strict) requires checking all principal minors, not just leading ones!
The Quadratic Form
\( f(x) = \frac{1}{2} x^T \mathbf{Q} x + c^T x + d \)
The Hessian of a quadratic form is simply the matrix \( \mathbf{Q} \).
Observation
The curvature of a quadratic function is constant across the entire domain.
Optimality
If \( \mathbf{Q} \) is PD, the global minimum is \( x^* = -\mathbf{Q}^{-1} c \).
Hessian Analysis Lab Worksheet Hessian Analysis Lab
Lesson 4: Multivariate Second-Order Conditions
Student:
ADVANCED CALCULUS & LINEAR ALGEBRA
Lab Objectives
Compute Hessians for multivariate functions
Classify critical points using eigenvalue tests
Verify convexity using Sylvester's Criterion
Analyze local vs global quadratic forms
1. Hessian Computation
Compute the Hessian matrix \( \nabla^2 f(x, y) \) for the function: \[ f(x, y) = x^3 + 2xy + y^2 - 4x \]
Find all critical points and evaluate the Hessian at each point.
2. Point Classification
For each critical point found in Section 1, determine its nature (Local Min, Local Max, or Saddle Point) using the Eigenvalue Test . Show your work for calculating the characteristic equation and roots.
Point 1 Analysis:
Point 2 Analysis:
3. Global Convexity via Sylvester's
Consider the function \( f(x, y) = ax^2 + 4xy + 2y^2 \). Find the range of values for the parameter \( a \) such that \( f \) is globally convex on \( \mathbb{R}^2 \). Use Sylvester's Criterion (Leading Principal Minors).
Hessian Analysis Lab Lesson 4 • Curvature
Duality Saddle Points Slides The Primal and the Dual
Duality, Saddle Points, and Min-Max Theory
The Lagrangian Bridge
For an optimization problem with inequality constraints \( g_i(x) \le 0 \):
\( L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) \)
"The Lagrangian incorporates constraints directly into the objective function using dual variables (Lagrange multipliers)."
The Two Perspectives
Primal Problem (\( p^* \))
\( \min_x \max_{\lambda \ge 0} L(x, \lambda) \)
Focuses on the original feasible space. If constraints are violated (\( g_i > 0 \)), the inner max goes to infinity.
Dual Problem (\( d^* \))
\( \max_{\lambda \ge 0} \min_x L(x, \lambda) \)
Focuses on the space of multipliers. The dual function \( g(\lambda) = \inf_x L(x, \lambda) \) is always concave .
The Duality Gap
Weak Duality
\( d^* \le p^* \)
The dual optimal is always a lower bound for the primal optimal.
Duality Gap
\( p^* - d^* \)
Strong Duality
\( p^* = d^* \)
Common in convex problems satisfying Slater's Condition .
The Saddle Point
A pair \( (x^*, \lambda^*) \) is a saddle point of the Lagrangian if:
\( L(x^*, \lambda) \le L(x^*, \lambda^*) \le L(x, \lambda^*) \)
Minimum with respect to \( x \), Maximum with respect to \( \lambda \).
Saddle
Guaranteeing Strong Duality
Slater's Condition
"For a convex primal problem, if there exists at least one point in the interior of the feasible set..."
There exists \( x \) such that \( g_i(x) < 0 \) for all \( i \).
Result: Strong Duality Holds (\( d^* = p^* \))
The Power of the Dual
Computational Ease
Sometimes the dual has fewer variables or a simpler structure (e.g., dual of an SVM).
Sensitivity
Dual variables \( \lambda^* \) represent the shadow prices or sensitivity of the optimal value to constraint changes.
"Solving the dual gives us a lower bound for free and deep insights into the structure of the problem."
The Road to Optimality
Topology
Ensures a solution exists.
Convexity
Ensures local is global.
Duality
Duality Decoded Case Study Worksheet Duality Decoded
Lesson 5: Primal-Dual Analysis & Saddle Points
NAME:
ADVANCED THEORETICAL OPTIMIZATION
The Primal Problem
Consider the following constrained optimization problem in \( \mathbb{R}^2 \):
Minimize \( f(x, y) = x^2 + y^2 \)
1
Construct the Lagrangian
Write the Lagrangian function \( L(x, y, \lambda) \) for this problem.
2
The Dual Function
Find the Lagrange dual function \( q(\lambda) = \inf_{x,y} L(x, y, \lambda) \). (Hint: Minimize \( L \) with respect to \( x \) and \( y \) by setting partial derivatives to zero, then substitute back in terms of \( \lambda \)).
3
Solve the Dual
State the dual problem (\( \max_{\lambda \ge 0} q(\lambda) \)) and solve for the dual optimal \( \lambda^* \) and the dual optimal value \( d^* \).
4
Strong Duality Check
Primal Solution:
Calculate \( p^* \) by solving the original problem (e.g., using symmetry or substitution).
Conclusion:
Compare \( p^* \) and \( d^* \). Does strong duality hold? Is Slater's condition satisfied?
Saddle Point Verification
Verify that your calculated \( (x^*, y^*, \lambda^*) \) constitutes a saddle point of the Lagrangian. Show that \( L(x^*, y^*, \lambda) \le L(x^*, y^*, \lambda^*) \le L(x, y, \lambda^*) \) for all \( x, y \in \mathbb{R} \) and \( \lambda \ge 0 \).
Duality & Saddle Points Case Study • Lesson 5
