Boss relaxation

From Wikipedia, the free encyclopedia

Boss relaxation is a relaxation technique in mathematical programming which removes difficult or complicating constraints and relies on the policy-implementer to use his or her authority to not satisfy any violated constraints in the underlying system.

[edit] Mathematical description

Given an optimization problem, \mathcal{P}, of the form:

\min_x\ f(x)
s.t.
g(x) \leq 0
h(x) \leq 0,

where x \in \mathbb{R}^n, f(x): \mathbb{R}^n \rightarrow \mathbb{R}, g(x): \mathbb{R}^n \rightarrow \mathbb{R}^m, h(x): \mathbb{R}^n \rightarrow \mathbb{R}^l, and the 0's in the constraints are of appropriate dimension.

If the constraints represented by h(x) \leq 0 are difficult or intractable, they can be removed to give the Boss-Relaxed problem, \mathcal{P}':

\min_x\ f(x)
s.t.
g(x) \leq 0

Suppose x * and x * ' are the optimal solutions to \mathcal{P} and \mathcal{P}', respectively. If x * = x * ', then the Boss Relaxation results in the same optimal solution. Otherwise, the policy-implementer is left to use his or her authority to implement the solution which does not satisfy all the constraints of the original system.

Retrieved from "http://en.wikipedia.org../../../b/o/s/Boss_relaxation.html"