• It's about a computational approach to derive sub-optimality guarantees.

  • You want to know how much the solution can be trusted . . .

The Central Idea

Let mathcal{P}(v,x) be an optimization problem structure with given and optimization variables partitioned as (v,x).

Example:

 begin{array}{lcr} begin{array}{rl} mathbf{X}=arg max & mbox{tr}(mathbf{R} mathbf{X})  mbox{s.t.} & mbox{tr}(mathbf{Q} mathbf{X})leq t  end{array} &quad begin{array}{c} mbox{       variable partitioning       }  Longrightarrow end{array} & quad begin{array}{l} mathbf{R}, mathbf{Q}, t  rightarrow  v  mathbf{X}  rightarrow x end{array} end{array}
 ~

Now suppose mathcal{P}(v,x) is a “difficult” optimization problem; however,

  • A sequence v_1,v_2,v_3, cdots of v can be constructed such that the associated global optima of the problem, viz.  x_k=arg max_x mathcal{P}(v_k,x) are known for any v_k, and the “distance” between v and v_k, is decreasing with k.

  • A sub-optimality guarantee of the obtained solutions x_k can be efficiently computed using the distance between v and v_k.

Then, computational sub-optimality guarantees can be obtained along with the approximate solutions, that might

  • outperform existing analytically derived sub-optimality guarantees, or

  • be the only class of sub-optimality guarantees in cases where no a priori known analytical guarantees are available for the given problem.

 ~ ~
alt text 

An illustration of the cone approximation technique used for MERIT's derivation in unimodular quadratic programming. See Applications for details.