Convex Optimization 2026, 11 - Convex Optimization

Convex optimization problems minimize a function f(x) subject to f_{1, ..., m}(x) ≤ 0, and a_i^Tx = b_i where f_i are convex. It follows that a by choosing a feasible set of convex optimization problems is convex, since the intersection of the domain ⅅ = ⋒^m_i=0 dom f_i (4.2.1.0). The converse formulation is the quasiconvex maximization problem (4.2.1.1). The equality constraint functions for convex optimization problems must be affine by implication. Some feasible set for problems with non-affine equality constraint functions may still be convex. The latter is the abstract convex optimization problem (4.2.1.2). Any locally optimal point of a convex optimization problem is (globally) optimal (4.2.2). The solution x is optimal for a convex optimization problem, iff ∇f₀(x)^T(y - x) ≥ 0 ∀ y ∈ X (4.2.3). Given an unconstrained problem, the optimal solution's condition reduces to ∇f₀(x) = 0.

Given problems with equality constraints only, assuming that the feasible set is both affine (given by convexity) and nonempty, the optimality condition is that ∇f₀(x)^T(y - x) ≥ 0 ∀ y: Ay = b. Since all such x are feasible, then y must have the form y = x + v; v ∈ N(A), so that ∇f₀(x)^Tv ≥ 0 ∀ v ∈ N(A) (4.2.3.2).

Given the problem of minimizing f₀(x), x ⪰ 0, then the optimality condition is ∇f₀(x)^T(y - x) ≥ 0 ∀ y ⪰ 0. The resulting space is unbounded below, unless ∇f₀(x) ⪰ 0, reducing the condition to a complementary ∇f₀(x)^Tx = 0 (4.2.3.3).