1
$\begingroup$

I'm currently trying to derive the dual problem of a nonconvex optimization problem. For context: I want to find an upper bound of the worst-case approximation error when approximating the elements of one convex set by elements of another, i.e., the original problem is a max-min problem. I've derived the dual problem of the inner (convex) minimization problem to express the original problem as a joint maximization problem. Unfortunately, the resulting problem contains a bilinear term which currently gives me trouble in deriving its dual. Note that I'm specifically interested in the dual problem of a nonconcave maximization problem which, unless I'm completely off track, should always exist and be a convex minimization problem. The optimal value of said problem should therefore provide an upper bound on the original problem.

Consider the problem $$ \begin{array}{cl} \text{maximize}_{x,z,u} & \langle x, z \rangle - u \\ \text{s.t.} & \|x\|_A \leq u \\ & \|z\|_B \leq 1 \end{array} $$ where $\|\cdot\|_A$ and $\|\cdot\|_B$ are arbitrary proper norms. (Note that in the actual problem I'm dealing with, there's an additional norm constraint on $x$ of the form $\|x\|_C \leq 1$.) My idea to attack the problem was to use conic duality by rewriting the problem as $$ \begin{array}{cl} \text{maximize}_{x,z,u,t} & \langle x, z \rangle - u \\ \text{s.t.} & (x,u) \in K_A \\ & (z,t) \in K_B \\ & t = 1 \end{array} $$ where $K_A$ and $K_B$ are the epigraphs of $\|\cdot\|_A$ and $\|\cdot\|_B$, respectively, i.e., the norm cones of the respective norms. The dual function for $\lambda \in \mathbb{R}$ then reads $$ \begin{align*} g(\lambda) &= \sup\{\langle x, z \rangle - u + \lambda(t-1)\} \\ &= -\lambda + \sup\{\langle x, z \rangle - u + \lambda t\} \end{align*} $$ where the supremum is taken over $((x,u), (z,t)) \in K_A \times K_B$. The usual strategy here seems to figure out when the supremum is unbounded and use the condition in the dual formulation of the problem. For example, if we only had to take the supremum over $K_A$, i.e., $(z,t)$ weren't primal but dual variables, then the supremum would be $\lambda t$ if $(z,-1)$ were in the polar of $K_A$ and $\infty$ otherwise due to the definition of the polar cone $K_A^\circ = \{y \mid \langle y, x \rangle \leq 0 \;\forall x \in K_A\}$. Obviously, this strategy doesn't apply here so I'm at a bit of a loss as to how to proceed.

Edit: As suggested by LinAlg, I've tried writing the supremum as two nested suprema with the inner one taken over the cone $(x,u) \in K_A$, i.e., $$ \begin{align*} \sup\{\langle x, z \rangle - u + \lambda t\} &= \sup_{(z,t) \in K_B} \left\{\sup_{(x,u) \in K_A} \{\langle x, z \rangle - u \} + \lambda t \right\} \\ \end{align*}. $$ As I mentioned before, the inner supremum is only bounded if $(z,-1)$ belongs to the polar cone $K_A^\circ$ which means the dual function can be simplified to $$ g(\lambda) = -\lambda + \sup_{\substack{(z,t) \in K_B \\ (z,-1) \in K_A^\circ}} \lambda t = -\lambda + \sup_{\substack{(z,t) \in K_B \\ (z,1) \in K_A^*}} \lambda t $$ Since $(z,t) \in K_B$ simply means $\|z\|_B \leq t$, we could choose $t$ arbitrarily large in the supremum which means we must have $\lambda \leq 0$ for the supremum to remain bounded. However, this means the supremum is $0$ since we can choose $z^\star = 0$ and $t^\star = 0$ (which is clearly not primal feasible). The resulting dual problem is $$ \begin{array}{cl} \text{minimize} & -\lambda \\ \text{s.t.} & \lambda \leq 0 \end{array} $$ which is clearly $0$.

Is my reasoning correct until here? The problem is when I apply the same argument to my original problem, I end up with a very similar dual problem with optimal value $0$. However, this bound is impossible since my problem is of the form $$ \sup_{x \in X} \inf_{z \in Z} \|x - z\| $$ where $X$ and $Z$ are norm balls. This error can only be zero if $X \subseteq Z$ which is not the case in my problem.

Edit 2: Updated the original question to fix an inaccuracy regarding the Lagrange multiplier.

$\endgroup$
7
  • $\begingroup$ you can split up the supremum into two supremums and use the polar cone for the inner supremum; then simplify the polar cone to an expression involving the dual-norm, and hope you can solve the outer supremum problem $\endgroup$
    – LinAlg
    Commented Jul 3, 2018 at 13:12
  • $\begingroup$ That's a good point. I'll give it a try. Thank you! $\endgroup$
    – nkoep
    Commented Jul 3, 2018 at 15:50
  • $\begingroup$ I've updated my original question, but I'm still somewhat skeptical that my reasoning is correct. $\endgroup$
    – nkoep
    Commented Jul 5, 2018 at 8:25
  • $\begingroup$ there is an error in your lagrangian, since you do maximization, it should be $-\lambda$; in general you should not expect strong duality here $\endgroup$
    – LinAlg
    Commented Jul 5, 2018 at 12:33
  • $\begingroup$ You're right. However, in the original problem where I introduced the slack variable $t$, I could have used the constraint $t = 1$ instead of $t \leq 1$ in which case the dual variable $\lambda$ wouldn't have to be nonnegative (since any feasible $t$ would make the term $\lambda(t-1)$ disappear in the Lagrangian anyway). In other words, I end up with the same dual problem. Regarding strong duality: I wasn't really hoping for that ;) I'm actually interested in a theoretical upper bound of the problem, but since I couldn't think of a way to bound it, I thought I'd give duality a try. $\endgroup$
    – nkoep
    Commented Jul 5, 2018 at 13:17

1 Answer 1

0
$\begingroup$

It looks like the dual problem is in fact unbounded, which is unfortunate, but at least $\infty$ is a valid albeit useless upper bound. Consider again the dual function \begin{align*} g(\lambda) = -\lambda + \sup\{\langle x, z \rangle - u + \lambda t\} = -\lambda + \sup_{(z,t) \in K_B} \left\{\sup_{(x,u) \in K_A} \{\langle x, z \rangle - u \} + \lambda t \right\}. \end{align*} As I mentioned in my question, the inner supremum is unbounded unless $(z,-1)$ is in the polar cone of $K_A$. However, I made the mistake of using this condition as an additional constraint in the outer supremum. Instead, consider the following representation of the dual function: \begin{align*} g(\lambda) = -\lambda + \sup_{(z,t) \in K_B} \left\{\lambda t + \iota_{\{x : \|x\|_A^* \leq 1\}}(z) \right\} \end{align*} where $\iota_C$ denotes the indicator function of a set $C$ with $\iota_C(x) = 0$ if $x \in C$ and $\iota_C(x) = \infty$ otherwise. This shows that no matter how $\lambda$ is chosen, we can always find a $z$ not in the dual norm ball of $\|\cdot\|_A$ which makes the supremum arbitrarily large. In other words, we have $g(\lambda) = \infty$ for all $\lambda \in \mathbb{R}$ which means the dual problem is unbounded above. This also applies to the actual problem I'm working on.

I wonder whether one could find an alternative dual formulation which gives a more meaningful bound along the lines of what is described on slide 6 of 1 where one adds valid but redundant constraints to improve the duality gap. Not sure whether that's all that promising though.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .