# How is this alternative system of inequalities derived?

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)$$

and

$$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?

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