1
$\begingroup$

I have this little confusion related to interior point method. In this method we use the log barrier function to approximate the real barrier which is not differential

Now when we find the optimal solution for this objective with log barrier function lets say $x^*(t)$ and its dual $\lambda^*(t)$ and $\gamma^*(t)$ where $\lambda$ is Lagrangian multiplier for the inequality constraints and $\gamma$ for the equality constraints. Now it's proved that the duality gap for $x^*(t)$ and $\gamma^*(t),\lambda^*(t)$ is m/t.

I believe $x^*$ and $\gamma^*(t),\lambda^*(t)$ are for the approximated function with log barrier. However, the real function is still there. They say that the

$f(x^*(t)) - p^* \le m/t$ where $p^*$ is the actual optimum of the original function

I didn't get how this came to be true. I mean m/t bound is for the primal and dual optimal of the approximated function. How come it applies for the optimal of the approximated function and optimal of the original function. Suggestions?

$\endgroup$
4
$\begingroup$

Given that you already accept that the duality gap along the central path is $m/t$, then the inequality you're struggling with is really rather simple. Remember, the dual problem provides lower bounds for the optimal value of the primal. So $p^*$ is necessarily in between the objective values of any feasible primal point and any feasible dual point.

That is: we have $$f(x^*(t)) - g(\gamma^*(t),\lambda^*(t)) = m/t$$ where $g$ is the dual objective. But we also have $$p^* \leq f(x) \quad \forall x\text{ feasible}$$ and $$p^* \geq g(\gamma,\lambda) \quad \forall \gamma,\lambda\text{ feasible}$$ Thus for any feasible primal and dual points, we have $$f(x)-p^* \leq f(x) - g(\gamma,\lambda) \quad \forall x,\gamma,\lambda\text{ feasible}$$ And along the central path, $$f(x^*(t))-p^* \leq f(x^*(t)) - g(\gamma^*(t),\lambda^*(t))=m/t.$$

EDIT: Actually, it looks like you may not accept the premise that the $m/t$ difference applies to the original problem. So let's look at this for an LP. The primal and dual problems are $$\begin{array}{llcll} \text{minimize} & c^T x & \quad & \text{maximize} & b^T \lambda \\ \text{subject to} & A x = b & & \text{subject to} & A^T \lambda + \gamma = c \\ & x \succeq 0 & & & \gamma \succeq 0 \end{array}$$ I prefer $y$ and $z$ above to $\lambda$ and $\gamma$, but for consistency I am keeping your variable names. $\lambda$ is the Lagrange multiplier for the equality constraints, $\gamma$ is the Lagrange multiplier for the inequalities. The barrier problem for the primal is $$\begin{array}{ll} \text{minimize} & t c^T x - \textstyle \sum_{i=1}^m \log x_i \\ \text{subject to} & A x = b \end{array}$$ Note that the domain of this problem is limited to $x\succ 0$ by the barrier term. The optimality conditions for a fixed $t>0$ satisfy $$t c - \mathop{\textrm{diag}}(x)^{-1} \mathbf{1} - A^Ty = 0 \quad Ax=b \quad x \succ 0$$ where $y$ is a Lagrange multiplier for the equality constraints. That second term is a bit clumsy: define $z_i\triangleq x_i^{-1}$ for $i=1,2,\dots,m$ so $$t c - z - A^Ty =0 \quad Ax=b \quad x,z \succ 0 \quad z_i\triangleq x_i^{-1},~i=1,2,\dots,m$$ By inspection, we see that if $(x,y,z)$ satisfies these equality constraints, then $(\gamma,\lambda)=(t^{-1}z,t^{-1}y)$ is a feasible dual point for the original problem. The duality gap for this primal/dual pair $(x,\gamma,\lambda)$ is $$c^Tx-b^T\lambda=c^Tx-t^{-1}b^Ty=c^Tx-t^{-1}x^TA^Ty=(c-t^{-1}A^Ty)^Tx=t^{-1}z^Tx=m/t.$$ So even though we're looking at the modified barrier model, the set of optimal points $x^*(t)$ are all feasible for the original, and they all lead to feasible dual points $(\gamma^*(t),\lambda^*(t))$ for the dual problem as well. The duality gap for the original model is $m/t$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.