Consider the following primal
$$
(1) \quad \max_{y,\nu\geq 0} c^\top x \quad \text{ s.t. } ||By-a+\nu||_2\leq \epsilon
$$
whose dual is
$$
(2) \quad \min_{x\geq 0} a^\top x + \epsilon||x||_2 \quad \text{ s.t. } B^\top x =c
$$
with $\epsilon> 0$.
Suppose I assume that linear independence constraint qualification (LICQ) holds for (2). That is, for every $x\in \{x\in \mathbb{R}^: x\geq 0, B^\top x=c\}$, the binding constraints are linearly independent. I'm not sure this is needed for what I want to show below (please advise).
Suppose that (1) and (2) are feasible.
Question (i): Does strong duality applies? That is, can we claim
$$
\max_{y,\nu\geq 0, ||By-a+\nu||_2\leq \epsilon} c^\top x = \min_{x\geq 0, B^\top x =c} a^\top x + \epsilon||x||_2
$$
Question (ii): How do we classify (1) and (2) according to the terminology in the optimisation literature? I believe that (1) is a quadratically constrained linear optimization problem. What about (2)?
Best Answer
Strong duality applies, since (2) satisfies the Slater condition if it's feasible. Convex optimization problems that satisfy Slater's condition have no duality gap. You can replace Slater's condition with the Linearity constraint qualification or the LICQ in this reasoning. It is sufficient that either the primal or the dual problem satisfies any of these conditions.
(1) and (2) are second order cone optimization problems.