I'm going through an article lately and there is one point which is very confusing. So, we have the following original constrained binary quadratic problem as the following. The pre-assumption of certain parameters are $Q\in Z^{n*n}$, $A\in Z^{n*n}$, and $b\in Z^{n*1}$.

$\text{min}$ $x^{T}Qx$,

$s.t.,$ $Ax\leq b$ $\text{and}$ $x\in \{0,1\}^{n}$. Let's call this optimization problem the problem $P$.

Now, by the classical lagrangian reduction, this can be relaxed as

$\text{min}$ $x^{T}Qx+\lambda^{T}(Ax-b)$,

$s.t.,$ $x\in \{0,1\}^{n}$ and $\lambda >0$. Let's call this optimization problem the problem $L_{\lambda}$.

Since the relaxation serves as a lower bound, we ideally plan to make it as maximum as possible. So, let $d(\lambda) = x^{T}Qx + \lambda^{T}(Ax-b)$, we have the other optimization,

$\text{max}$ $d(\lambda)$

$s.t.,$ $\lambda \geq 0$. Let's call this optimization problem the problem $L$.

So far so good. Now, here is the confusing point.

The article mentioned that the problem $L$ can be rewritten as the following.

$max$ $\mu$

$s.t.,$ $\mu \leq x^{T}Qx + \lambda^{T}(Ax-b) $ for any $x\in \{0,1\}^{n}$ and $\lambda \geq 0$.

Let's call the last optimization problem the problem $W$.

I do not quite understand why this is a rewritten. So, suppose $\mu_{0}$ is the optimal solution of problem $W$, then it follows that $\mu_{0}\leq x^{T}Qx+\lambda^{T}(Ax-b)$ for any $x\in \{0,1\}^{n}$ and $\lambda \geq 0$. While on the other hand, for the problem $L$, what I understand it is like this: for each given $\lambda$, there is one optimization problem $L_{\lambda}$, and one optimal solution (which we take a minimum by the definition of $L_{\lambda}$). Then, finally, among all the optimum solutions, one maximum value is chosen. Somehow, I can not see that in the formulation of the optimization problem $W$.

Or did I overthink? Any comments would be greatly appreciated.


You have not defined $d(\lambda)$ (and, therefore, problem $L$) correctly. It should be $$ d(\lambda) = \min_{x \in \{0,1\}^n} \left(x^TQx+\lambda^T(Ax-b)\right). $$ Now note that any problem of the form $$ \begin{align} \text{maximize }&\min_zf(z)\\ \text{subject to }& \mathcal{C}, \end{align} $$ where $z$ is the (vector) optimization variable and $\mathcal{C}$ is a set of constraints, can be equivalently written as $$ \begin{align} \text{maximize }&t\\ \text{subject to }& t\leq f(z) \text{ for all } z, \\ & \mathcal{C}. \end{align} $$ where the optimaziation variables are the vector $z$ and the scalar $t$.

  • $\begingroup$ Could you be more specific why I have not defined $d(\lambda)$ correctly? $\endgroup$ Feb 14 '17 at 2:07
  • $\begingroup$ You left the minimization with respect to $x$ out of your definition of $d(\lambda)$. Computing $d(\lambda)$ requires minimizing the expression with respect to $x$. $\endgroup$ Feb 14 '17 at 2:31
  • $\begingroup$ I see. So, when an optimization problem is considered, the minimization or maximization is always with respect to a certain variable which needs to be emphasized, right? In this case, it need to mention that $x$ is the variable, not $\lambda$. I think I simply mis-treat $\lambda$ as a variable also, which is a mistake. $\endgroup$ Feb 14 '17 at 2:36

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.