Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 11

Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 11

Binary Hypothesis Testing

  • The goal is to determine which of two distributions generated an observed sample.
  • A randomized detector is introduced as a policy for attributing observations to distributions.
  • Scalarizing the problem simplifies the solution.
  • Minimizing the total number of errors leads to a simple solution based on maximum likelihood.
  • Minimizing the maximum of false positive and false negative errors results in a non-deterministic detector.

Experiment Design

  • The concept of experiment design involves linear measurements and a measurement vector.
  • The measurements are normalized to have the same standard deviation.
  • The goal is to choose the best subset of experiments to obtain the best estimate of a parameter.
  • The optimality criterion is based on the size of the confidence ellipsoid.
  • A simple experiment design method is to choose the experiment with the highest signal-to-noise ratio.
  • The Gaussian model allows for the experiment design problem to be formulated as an integer programming problem.
  • A relaxation technique for solving experiment design problems is introduced.
  • The speaker suggests using a probabilistic approach to determine which experiment to perform.
  • The rounded solution may not minimize the confidence ellipsoid volume but is close to the optimal solution.
  • The assumption of M (the number of experiments) being much larger than P (the number of options) is made.
  • The speaker introduces the concept of D-optimal experiment design.

Optimization Problems Involving Polyhedra and Ellipsoids

  • The goal is to find the minimum volume ellipsoid that covers the given experiments.
  • The experiments with higher signal-to-noise ratio (SNR) are more desirable and should be chosen.
  • The optimal experiment design chooses two experiments that are closest to orthogonal to each other.
  • Adding a budget constraint allows for cost-effective experiment design.
  • Complex constraints can be incorporated into the convex optimization problem.
  • The volume of the ellipsoid is inversely proportional to the square root of the determinant of W.
  • Determining if two polyhedra intersect is a convex problem.
  • Finding the minimum distance between two polyhedra is a convex optimization problem.

Minimum Volume Ellipsoid

  • This can be formulated as a convex optimization problem.
  • One application is in outlier detection.
  • A method called "ellipsoidal peeling" can be used to iteratively remove outliers and find the minimum volume ellipsoid.
  • Finding the minimum volume ellipsoid that covers a polyhedron given an inequality form is NP-hard.
  • The dual problem of finding the maximum volume ellipsoid that fits inside a polyhedron is tractable if the polyhedron is described by inequalities but NP-hard if it's described by its vertices.
  • The Löwner-John ellipsoid is the minimum volume ellipsoid that covers a convex bounded set with non-empty interior.
  • Ellipsoids are universal approximators of convex sets within a factor of √n.
  • Any norm on ℝ^n can be approximated with a quadratic norm with error no more than the fourth root of n.

Overwhelmed by Endless Content?