Convex Functions and Convex and Nonconvex Optimization Problems

A fundamental property of an optimization problem is the form of the cost function to be minimized.

This book has already introduced, or will introduce, several problems formulated as the minimization of an objective function: homography estimation, camera calibration, the PnP problem, reprojection-error minimization, and Bundle Adjustment. The behavior of optimization algorithms depends substantially on the structure of this function.

Definizione 12   A function $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ is called convex if, for every pair of points $\boldsymbol{x},\boldsymbol{y}$ in its domain and for every $\lambda \in [0,1]$, the inequality

$$f \left( \lambda \boldsymbol{x} + (1-\lambda)\boldsymbol{y} ... ...\leq \lambda f(\boldsymbol{x}) + (1-\lambda)f(\boldsymbol{y}).$$ (4.71)

holds. Geometrically, the segment joining any two points on the graph of the function always lies above the graph itself.

A function is called concave if its opposite, $-f$, is convex.

Convex functions are particularly important in optimization because they have a fundamental property:

Every local minimum is also a global minimum.

It follows that an iterative algorithm converging to a local minimum automatically solves the global problem.

Another important characterization concerns the Hessian matrix.

Theorem 2   If $f$ is twice differentiable ($f \in C^2$), then $f$ is convex if and only if the Hessian matrix

$$\nabla^2 f(\boldsymbol{x})$$ (4.72)

is positive semidefinite at every point in the domain.

Convex functions also have several other notable properties:

• the intersection of convex sets is also a convex set;
• the epigraph of the function,
  

  $$\left\{ (\boldsymbol{x},t) \in \mathbb{R}^{n}\times\mathbb{R} \;\vert\; f(\boldsymbol{x}) \leq t \right\},$$ (4.73)

  
  
  is a convex set;
• Jensen's inequality holds:
  

  $$f \left( \mathbf{E}[\boldsymbol{X}] \right) \leq \mathbf{E}[f(\boldsymbol{X})].$$ (4.74)

  
  

Typical examples of convex functions are:

• quadratic functions with matrix $\boldsymbol{Q}\succeq 0$:
  

  $$f(\boldsymbol{x}) = \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{b}^{\top} \boldsymbol{x} + c;$$ (4.75)

  
  

• the $\ell_1$, $\ell_2$, and $\ell_\infty$ norms;
• the log-sum-exp function
  

  $$f(\boldsymbol{x}) = \log \left( \sum_i e^{x_i} \right).$$ (4.76)

  
  

In computer vision, many problems can be formulated as convex problems: linear least squares, matching problems, graph flows, segmentation, and numerous relaxations used in object recognition.

A linear programming (LP) problem has the form

$$\min_{\boldsymbol{x}} \boldsymbol{c}^{\top}\boldsymbol{x} \q... ...s.t.} \qquad \boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}.$$ (4.77)

The feasible region is a convex polyhedron and, if a solution exists, the optimum lies at one of the vertices of the polyhedron.

An important generalization is quadratic programming (QP)

$$\min_{\boldsymbol{x}} \frac{1}{2} \boldsymbol{x}^{\top} \bol... ...{s.t.} \qquad \boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}$$ (4.78)

with $\boldsymbol{Q}\succeq 0$.

Other important classes include:

• Second-Order Cone Programming (SOCP);
• Semidefinite Programming (SDP).

Unfortunately, many of the most interesting problems in computer vision do not belong to the class of convex problems.

Camera calibration, the PnP problem, Bundle Adjustment, relative-pose estimation, multiview triangulation, and most SLAM problems generate nonconvex cost functions. In such cases, multiple local minima, saddle points, and flat regions of the solution space may exist.

Consequently, algorithms such as Newton, Gauss-Newton, and Levenberg-Marquardt generally provide no guarantees of convergence to the global minimum, and the quality of the solution depends strongly on the initial estimate.

To address these difficulties, one frequently uses:

• robust initialization;
• multiscale or coarse-to-fine strategies;
• outlier-robust techniques such as RANSAC;
• convex relaxations and approximations;
• optimization directly on geometric manifolds;
• multiple optimizations from different initial points (multi-start).

In practice, much of optimization in computer vision consists precisely in transforming a strongly nonconvex problem into a sufficiently well-conditioned problem that can be solved reliably using iterative techniques.