Convex Optimization 2026, 37 - Unconstrained Minimization
The methods for solving an unconstrained optimization minimization on a convex and twice continuously differentiable function f(x), if assumed solvable, has an optimal point x*. Write the optimal value as p*. From the constraints on f, we know that its derivative at x* vanishes. When no analytical solution is possible, an iterative algorithm will compute a minimizing sequence for the problem, which is terminated after it hits some specified tolerance ε. Such methods often require a starting point x(0) within dom f and the sublevel set S = {x ∈ dom f | f(x) ≤ f(x(0))} to be closed. If this is true for all possible starting points, f is closed itself.
Assume that the objective function is strongly convex on S, then f can be approximated with an upper bound
(Eq. 9.8) which can be used to bound the suboptimality of the point x f(x) - p* (Eq. 9.9). There is in turn a bound on ||x - x*||2, which implies that x* is unique. From the upper bound inequality can be derived that the sublevel sets in S are bounded, which also implies that S itself is bounded (p. 460), and indirectly,
(Eq. 9.14). Define further the width W(C, q) and the condition number cond(C) of a convex set C
Assume a minimizing sequence x(k + 1) = x(k) + t(k)Δx(k), with t > 0 if x(k) is not optimal; and Δx as a step or search direction. Descent methods assume that f(x(k+1)) < f(x(k)) for non-optimal steps, so the sequence is entirely within dom f, and from convexity, Δf(x(k))T(y - x(k)) ≥ 0, which implies f(y) ≥ f(x(k)) (p. 463). The search direction in a descent method must make an acute angle with the negative gradient, which qualifies it as a descent direction. Such a method iterates through the steps until some criterion is satisfied (Algorithm 9.1). A convergence analysis for the gradient method can be extended with backtracking line search for an arbitrary norm. Any norm can be bounded in terms of the Euclidean norm. Assuming that f is strongly convex on the initial sublevel set S, the upper bound ∇2f(x) ≤ MI implies an upper bound on f(x + tΔ xsd). The step size must satisfy the exit condition for the backtracking line search.