Convex Optimization 2026, 34 - Centering & Classification

A bounded and nonempty interior C with point x inside it has a depth defined as depth(x, C) = dist(x, ℝⁿ \ C), i.e. the distance between x and the closest point outside of C. A Chebyshev center of C is any point of maximum depth in C. If C is convex, the depth is a concave function for x, so computing the Chebyshev center is a convex optimization problem. If C ⊂ ℝⁿ is defined by a set of convex inequalities, then the Chebyshev center can be found by maximizing R over g_i(x, R) = sup_{||u|| ≤ 1} f_i(x + Ru) ≤ 0 (Eq. 8.16). The Chebyshev center defines the center of the largest ball that lies in C. The maximum volume ellipsoid center of C can be defined similarly, though for an ellipsoid. It's written x_mvc. The analytic center x_ac of a set of convex inequalities and linear equalities f_i(x) ≤ 0. It's determined by minimizing -∑^m_i=1 log(-f_i(x)) for Fx = g (Eq. 8.18). The objective this defines is the logarithmic barrier associated with the set of inequalities. It's bounded below on the feasible set (p. 419). It approximates the inner border of C around x_ac (p. 421).

Given two sets of points in ℝⁿ with a function f: ℝⁿ → ℝ, that is positive on the first set and negative on the second, then the 0-level set {x : f(x) = 0} separates or classifies the two sets of points. The resulting inequalities can be weakened for weak separation. In linear discrimination, the function is affine, so geometrically it yields a hyperplane separating the two sets. The condition inequalities are strict, and homogeneous in the affine parameters, they are feasible iff the set of nonstrict linear inequalities a^Tx_i - b ≥ 1 or ≤ -1 (=t) is feasible. The existence of an affine classifying function is equivalent to a set of linear inequalities in the parameters. given ||a||₂ ≤ 1, t might be maximized for robust linear discrimination (p. 439). The optimal value for robust linear discrimination is positive iff the sets can be linearly discriminated, and ||a||₂ ≤ 1 is always tight at the optimum.

If two sets of points can't be linearly separated, finding an affine function that approximately classifies the points is generally difficult. A heuristic for approximate linear discrimination is based on support vector classifiers. When relaxing the constraints through a set of (nonnegative) variables u, v. Finding a sparse configuration for u, v that is still valid, the sum of u_i and v_i can be minimized as a convex optimization problem (Eq. 8.25). The number of misclassified points is weighed against the width of the slab that emerges as a result of the problem, which is given by 2/||a||₂. The standard support vector classifier for the sets x_i, y_j are solutions of minimizing ||a||₂ + γ(1^Tu + 1^Tv) (8.6.1).

When searching a nonlinear discriminant function from a subspace of functions that is positive on one set and negative on another. If it's quadratic, the parameters might satisfy the inequality conditions: f(x) = x^TPx + q^Tx + r; x_i^TPx_i + q^Tx_i + r > 0; y_i^TPy_i + q^Ty_i + r < 0. The nonstrict conditions are defined analogously to the linear separation functions. This approach can be generalized to polynomial separation functions (p. 430).