MERIT
Central Idea
Applications
Downloads

  • 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.