$\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$
1. might decrease the optimal value
Incorrect.
2. will increase the optimal value a lot
Correct!
3. can leave the optimal value unchanged
Incorrect.

If $\lambda^\star$ is large, then increasing $s$
1. will decrease the optimal value a lot
Incorrect.
2. will increase the optimal value a lot
Incorrect.
3. can leave the optimal value unchanged
Correct!

If $\lambda^\star=0$, then increasing $s$
1. can decrease the objective value
Incorrect.
2. can increase the objective value
Incorrect.
3. 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.
1. True.
Correct!
2. False.
Incorrect.

The primal problem has a unique solution.
1. True.
Incorrect.
2. False.
Correct!

The dual problem is not unbounded.
1. True.
Correct!
2. 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$.
1. True.
Correct!
2. False.
Incorrect.