what is the dual of the following linear program over a convex set?

Question

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?

Answer 1

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.