From Convex Optimization by Boyd and Vandenberghe:

Given the set of inequalities:

$$a^Tx_i - b \gt 0 \text{ for } i = 1, \dots, N, \text{ and } a^Ty_i - b \lt 0 \text{ for } i = 1, \dots, M$$

The strong alternative of them is the existence of $\lambda, \tilde \lambda$ such that:

$\lambda \ge 0, \space \space \space \tilde \lambda \ge 0, \space \space \space (\lambda, \tilde \lambda ) \neq0, \space \space \space \sum_{i=1}^N\lambda_ix_i = \sum_{i=1}^M\tilde\lambda_iy_i, \space \space \space 1^T\lambda = 1, \space \space \space 1^T \tilde \lambda = 1$

Can someone explain how this is derived?

From what I understand:

The system can be written as $$b1 - A_N^Tx \lt 0 \text{ and } A_M^Ty - b1 \lt 0$$

where $A_N = [a, a, \dots, a]$ with $N$ a column vectors and $A_M$ defined similarly.

Then $$L(x,y, \lambda, \tilde \lambda) = \lambda^T(b1-A_N^TX) + \tilde \lambda(A_M^Ty - b1)$$


$$g(\lambda, \tilde \lambda) = \inf_{x,y} L = \lambda^T(b1) - \tilde \lambda ^T(b1) + \inf_x (-\lambda^T A_N^Tx) + \inf_y(\tilde \lambda^T A_M^Ty)$$

which should be

$$g(\lambda, \tilde \lambda) = b1^T\lambda - b1^T\tilde\lambda \space \space \space \text{ if }\space \space \space A_M\tilde\lambda = 0, \space \space \space A_N\lambda = 0$$

and therefore the alternatives should be:

$\lambda \ge 0, \space \space \space\tilde \lambda \ge 0, \space \space \space\lambda \neq 0, \space \space \space\tilde \lambda \neq 0, \space \space \space A_M\tilde\lambda = 0, \space \space \space A_N\lambda = 0, \space \space \space b1^T\lambda \ge b 1^T \tilde \lambda$

How are these equivalent or what am I doing incorrectly?

  • 1
    $\begingroup$ The variables are $a$ and $b$. You should be optimizing over those, not $x$ and $y$ $\endgroup$ – Michael Grant Jun 8 at 16:23

Your Answer

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

Browse other questions tagged or ask your own question.