the reason behind dual the inner problem in robust optimization

Question

I have reading some material about Robust optimization. It seems that dual optimization theory is the main techniques to reformulate robust optimization.

for example: $$\min_x\qquad c^Tx$$ $$s.t\qquad a^Tx\leq b$$

where$$\qquad a\in \{a|Da\leq d\} $$

and the problem is equivalent $$\min_x\qquad c^Tx$$ $$s.t\qquad \max_{Da\leq d}a^Tx\leq b$$

and they use dual theory reformulate the max problem to min problem

which is $$\min_x\qquad c^Tx$$ $$s.t\qquad \min_{D^Tp=x,p\geq0}p^Td\leq b$$

and finally it equivalent to $$\min_{x,p}\qquad c^Tx$$ $s.t$ $$p^Td\leq b$$ $$D^Tp=x$$ $$p\geq0$$

My question is

1.why we use dual theory to reformulate the inner problem?

2.why we can omit the second minimize in constraints?

Answer 1

1. We use duality theory because we can do 'step 2'. It is a technique to turn a problem with uncountable many constraints into something manageable.

2. If you can find one $p \geq 0$ for which $D^Tp = x$ and $p^T d \leq b$, that is already sufficient to conclude that the minimum over $p\geq 0$ for which $D^Tp=x$ is less than or equal to $b$.

Answer 2

There are two points that need to be noted:

1. The variables in the objective function and the subproblem are different. Hence the minimization problem in the constraints does not influence the feasible region of $x$ directly.
2. Since the subproblem in the constraints is an optimization problem in the format: $min \ f(x)\leq b$ (it also works for $max \ f(x)\geq b$), the constraint can be meet as long as we can find a feasible solution meets $f(x)\leq b$ (or $f(x)\geq b$). Hence, we can just convert the optimization problem into inequality constraints.