3
$\begingroup$

I am dealing with the following problem:

$\Pi = \inf\, \int v(w(x))dF(x)$

$s.t. \int x w(x)dF(x)\ge 1 $

$w(x)\ge0$

where F(x) is a probability distribution with support on $\mathbb{R}$ and $v(\cdot)$ is a strictly convex function. In economics, this convex optimization problem is known as the principal-agent model.

This problem is typically solved by writing the Lagrangian

$L(\lambda) = \inf_{w(\cdot)\geq0}{ \int v(w(x)) - \lambda( x w(x) - \lambda) dF(x) }$

and solving it state-by-state; i.e., by solving for each x,

$ \inf_{w(x)\geq0}{ v(w(x)) - \lambda x w(x) }$

Obviously, for this approach to be meaningful, it must be the case that strong-duality holds; i.e., $\Pi = \sup_\lambda{ L(\lambda)}$. Otherwise, there is no guarantee that the solution to the dual corresponds to a solution for the primal.

My question is how to show that strong duality holds.

As the objective is convex and the constraints are linear, if Slater's inequality is applicable, then strong duality follows immediately, provided that a feasible solution exists. But most of the textbook results on optimization theory that I know of (including those on Slater's inequality) apply to finite dimensional variables, whereas $w(\cdot)$ is infinite-dimensional.

Thank you! :)

$\endgroup$
  • 1
    $\begingroup$ Seems to me you have strict feasibility here. That is: surely you can find a point satisfying $w(x)>0$ and $\int xw(x)dF(x) > 1$? I don't know if that's enough in the infinite dimensional case but it likely is---just need to find a proof. $\endgroup$ – Michael Grant Oct 17 '17 at 1:03
  • 1
    $\begingroup$ Google a paper called "The Slater Conundrum: Duality and Pricing in Infinite Dimensional Optimization"... that might help $\endgroup$ – Michael Grant Oct 17 '17 at 1:07
  • $\begingroup$ @George Georgiadis can you provide a reference for this problem? $\endgroup$ – mcpca Oct 19 '17 at 18:44
  • 1
    $\begingroup$ @mcpca - dklevine.com/archive/refs41205.pdf - Eq. (4) and (6), assuming that G is convex and U is linear, and making the following transformation: the distribution dF above corresponds to the distribution of $f_a / f$ in the reference. $\endgroup$ – George Georgiadis Oct 19 '17 at 18:48
2
$\begingroup$

Here is the infinite dimensional version of the Lagrange multiplier theorem for convex problems with inequality constraints.

From Luenberger, Optimization by Vector Space Methods, Chapter 8, Section 3, Theorem 1, we have that for strong duality to hold in the problem $$ \text{minimize} \ f(x) \\ \text{subject to} \ x \in \Omega, G(x) \leq_P 0 $$

it is sufficient that

  1. $f: \Omega \to \mathbf{R}$ is convex, where $\Omega \subset X$ is a convex set in a linear space $X$;
  2. $G: \Omega \to Z$, where $Z$ is a normed space, is convex with respect to the convex cone $P \subset Z$;
  3. The convex cone $P$ has nonempty interior;
  4. (Slater's condition) There exists a point $x_1 \in \Omega$ such that $G(x_1) <_P 0$, i.e., $G(x_1)$ is an interior point of $-P$;
  5. The optimal value is finite.

In this case one has $$ \underset{x \in \Omega}{\inf_{G(x) \leq_P 0}} f(x) = \max_{z^* \geq_{P^*} 0}\inf_{x\in \Omega}{ \left[f(x) + \left<G(x), z^*\right>\right]} $$

where $z^* \in Z^*$, the dual space of $Z$, and $P^*$ is the positive conjugate cone of $P$. The maximum on the right-hand side is attained by some $z_0^* \geq_{P^*} 0$, and if the minimum on the left-hand side is attained by $x_0 \in \Omega$, $G(x) \leq_P 0$ then $$ \underset{x \in \Omega}{\inf_{G(x) \leq_P 0}} f(x) = f(x_0) = f(x_0) + \left<G(x_0), z_0^*\right> $$

If you don't know some of these definitions, they are all in the reference, but I will now specialize to your problem to derive the conditions in your case. Since you mentioned that you've only seen the conditions in the finite-dimensional setting, I thought it would be best to explain where they came from. Note that the condition is essentially the same (in the finite-dimensional case the cone $P$ is typically the nonnegative orthant $\mathbf{R}^n_+$).

To apply these conditions you must formulate the problem in the form above. A first step would be to choose the class of functions the solution will belong to, i.e. the space $X$. It is important to choose $X$ such that the dual of $Z$ is simple to work with, for instance $X =$ the space of continuous functions. I see that you are interpreting $x(t) \geq 0$ not as a constraint per se but as defining the domain $\Omega$ of $f$ (i.e., what Luenberger calls an 'explicit' (set) constraint as opposed to an 'implicit' (e.g. inequality) constraint). If you are considering solutions which are supported on $\mathbf{R}$ (which I understand is the case) this helps because the dual of the space of continuous functions on a noncompact interval will be a complicated space (and if you were to take this to be a constraint it would have to be 'incorporated into' $Z$).

So, if we take $X$ to be the space of bounded continuous functions on $\mathbf{R}$, we define $$ \Omega = \{ x \in X: x(t) \geq 0 \text{ for all } t \in \mathbf{R}\} \\ Z = \mathbf{R} \\ G(x) = 1 - \int_\mathbf{R}{tx(t)dF(t)} \\ P = \{t \in \mathbf{R}: t \geq 0\}. $$

The reason I am restricting to bounded functions is to avoid the issue of $G$ not being defined for all $x \in \Omega$ (I am assuming that $\int_\mathbf{R}{|t|dF(t)}$ is finite).

Clearly $P$ has nonempty interior, and Slater's condition is satisfied if there is an everywhere nonnegative bounded continuous function $x$ such that $G(x) < 0$, or $$ \int_\mathbf{R}{tx(t)dF(t)} > 1. $$

This is satisfied for instance by a constant function if $\int_\mathbf{R}{tdF(t)} \neq 0$. We also need to assume that the optimal value is finite, this is the case if for instance $v(t) \geq 0$ for all $t \geq 0$.

The dual of $Z$ is just $Z$, so the corresponding Lagrangian is $$ L(x, \lambda) = f(x) + \lambda G(x) = \int_\mathbf{R}{\left[v(x(t)) + \lambda (1 - tx(t)) \right]dF(t)}. $$

Since the conjugate of $P$ is $P$ itself, strong duality means that $$ \underset{x \in \Omega}{\inf_{G(x) \leq 0}} \int_\mathbf{R}{v(x(t))dF(t)} = \max_{\lambda \geq 0}\inf_{x\in \Omega}{ \int_\mathbf{R}{\left[v(x(t)) + \lambda (1 - tx(t)) \right]dF(t)} }. $$

I guess that by "solving state-by-state" you mean applying some kind of differential condition for the minimization of the Lagrangian w.r.t. $x$. This would require $L$ to be Gateaux differentiable in $x$. Luenberger presents a condition of this sort applicable when $\Omega$ is a convex cone (which it is in your case) and the Gateaux differential of $L$ w.r.t. $x$ is linear. This is Lemma 1 of Section 7, Chapter 8.

If you were to consider a problem where $F$ is supported on a compact interval, then you could take $x(t) \geq 0$ to be an explicit constraint, take $X$ to be the space of continuous functions on that interval with the supremum norm, and $\Omega = X$, $Z = \mathbf{R} \times X$. In this case the minimization of the Lagrangian w.r.t. $x$ would be unconstrained. The Lagrange multiplier in that case would be a pair $(\lambda, x^*)$ where $x^*$ is a function of bounded variation on the interval we are considering.

$\endgroup$

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.