0
$\begingroup$

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following optimization problem? \begin{align} \min_{\mathbf{x}\in\mathcal{S}}~&x_0 \\ l_i\,\leq\,x_i\,&\leq\,u_i,~~i=1,\dots,N \end{align} where $l_i$ and $u_i$ are given positive constants. What is the dual of the above linear program?

$\endgroup$
1
$\begingroup$

This is not, actually, a linear program, because you haven't specified S in LP form (and you haven't even said that it is polyhedral). It's convex though.

First, some preparation: let's define $x\triangleq (x_0,\bar{x})$, where $\bar{x}=(x_1,x_2,\dots,x_N)$, and let $I_\mathcal{S}$ be the indicator function for $\mathcal{S}$. That is: $$I_\mathcal{S}(x_0,\bar{x}) = \begin{cases} 0 & (x_0,\bar{x})\in\mathcal{S} \\ +\infty & (x_0,\bar{x})\not\in\mathcal{S} \end{cases}$$ The convex conjugate of this function is known as the support function for $\mathcal{S}$, defined over $z\triangleq(z_0,\bar{z})$: $$I^*_\mathcal{S}(z_0,\bar{z}) = \sup_{x_0,\bar{x}} z_0x_0+ \bar{z}^T\bar{x} - I_\mathcal{S}(x_0,\bar{x}) = \sup_{(x_0,\bar{x})\in\mathcal{S}} z_0 x_0 + \bar{z}^T\bar{x}=\phi_\mathcal{S}(z_0,\bar{z})$$ This function is convex and homogeneous, and since $\mathcal{S}$ is bounded, it is finite for all $z\in\mathbb{R}^{N+1}$.

Now let us write your problem in this form: \begin{array}{ll} \text{minimize} & x_0 + I_\mathcal{S}(x_0,\bar{x}) \\ \text{subject to} & \ell \preceq \bar{x} \preceq u \end{array} The Lagrangian of your problem is $$\begin{aligned} L(x_0,\bar{x},z_\ell,z_u) &= x_0+I_\mathcal{S}(x_0,\bar{x})-z_\ell^T(\bar{x}-\ell)-z_u^T(u-\bar{x}) \\ &=I_\mathcal{S}(x_0,\bar{x})-(-1)x_0-(z_\ell-z_u)^T\bar{x}+\ell^Tz_\ell+u^Tz_u\end{aligned}$$ The dual function is $$g(z_\ell,z_u)=\inf_{x_0,\bar{x}} L(x_0,\bar{x},z_\ell,z_u) = \ell^Tz_\ell+u^Tz_u-\phi_\mathcal{S}(-1,z_\ell-z_u)$$ So the dual problem is $$\begin{array}{ll} \text{maximize} & \ell^Tz_\ell+u^Tz_u-\phi_\mathcal{S}(-1,z_\ell-z_u) \\ \text{subject to} & z_\ell, z_u \succeq 0 \end{array}$$ In order to get more specific you will have to determine a more explicit expression for $\phi_\mathcal{S}(x)$. The task of doing so will look a lot like finding the dual function of a convex optimization problem, and will depend on how you express the set $\mathcal{S}$ in terms of constraints.

$\endgroup$
  • $\begingroup$ nice!!. can you suggest a good book to learn in depth about duality?? $\endgroup$ – dineshdileep Sep 2 '14 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.