$\newcommand{\ones}{\mathbf 1}$
Duality
Sensitivity Analysis
Consider the convex optimization problem \[ \begin{array}{ll} \mbox{minimize} & f_0(x) \\ \mbox{subject to} & f_1(x) \leq s, \quad Ax=b, \end{array} \] with variables $x \in \mathbf{R}^n$, where $s$ is some fixed real number. Let $\lambda^\star$ be an optimal dual variable (Lagrange multiplier) associated with the constraint $f_1(x) \leq s$. Below we consider scenarios in which we change the value of $s$, and then solve the modified problem. We are interested in the optimal objective value of this modified problem, compared to the original one above.
If $\lambda^\star$ is large, then decreasing $s$
might decrease the optimal value
Incorrect.
will increase the optimal value a lot
Correct!
can leave the optimal value unchanged
Incorrect.
If $\lambda^\star$ is large, then increasing $s$
will decrease the optimal value a lot
Incorrect.
will increase the optimal value a lot
Incorrect.
can leave the optimal value unchanged
Correct!
If $\lambda^\star=0$, then increasing $s$
can decrease the objective value
Incorrect.
can increase the objective value
Incorrect.
will leave the optimal value unchanged
Correct!
Consider a convex optimization problem \[ \begin{array}{ll} \mbox{minimize} & f_0(x) \\ \mbox{subject to} & f_i(x) \leq 0, \quad i=1,\ldots, m\\ & Ax=b, \end{array} \] that satisfies Slater's constraint qualification.
The primal and dual problems have the same objective value.
True.
Correct!
False.
Incorrect.
The primal problem has a unique solution.
True.
Incorrect.
False.
Correct!
The dual problem is not unbounded.
True.
Correct!
False.
Incorrect.
Suppose $x^\star$ is optimal, with $f_1(x^\star) = -0.2$. Then for every dual optimal point $(\lambda^\star,\nu^\star)$, we have $\lambda^\star_1=0$.
True.
Correct!
False.
Incorrect.