Suppose we have the following linear program (LP1), $$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{\mathbb{R}} \cos(2\pi x t) f(t)dt \geq 0 \text{ ,}$$

Where $\mathcal{C}$ is some "nice" family of functions (which I am not sure what it is. In the comments it was mentioned that $f$ has to be an analytic function with bounded spectrum). Now define for all $n \in \mathbb{N}$ the following "approximate" linear program (LP2):

$$\min \sum_{i=0}^n a_i \cos(2 \pi x_0i) \\ \text{subject to } \sum_{i=0}^n a_i = 1 \\\forall k \in \{1/n, 2/n, \ldots, 1\} : \sum_{i=0}^n \cos(2\pi i k)a_i \geq 0.$$

Let $f^*$ be the optimal function for (LP1), and let $f_n$ be the optimal function for (LP2) (i.e. $f_n(x) = \sum_{i=0}^n a^*_ig(x)$, for $a_i^*$ optimizing the linear program).

My question is: under what conditions (if any) we can prove that $\lim_{n\rightarrow \infty} f_n$ converges and $f_{\infty} = f^*$? What can we say about the rate of convergence (obviously by the way the question is phrased this is impossible to answer, but are there examples where the answer is known)? Are there known results for the case where the linear program has many constraints?

  • $\begingroup$ As posed, LP1 is not even bounded unless $g$ is a linear combination of $c1,c2$, so there is nothing to talk about as long as the convergence is concerned. Also, the summation over integers is a too poor approximation to the integral to ensure anything unless you restrict your function space to analytic functions with bounded spectrum. So the answer to the question as currently posed seems to be "pretty much never". However, if you impose some additional restrictions, it may become meaningful, so I abstain from voting to close :-) $\endgroup$ – fedja Aug 24 '20 at 16:35
  • $\begingroup$ @fedja - thank you. I know that as phrased the question is almost meaningless - but part of my question is what conditions I should pose for convergence of the two programs. I will add your conditions, as well as more clarifications. $\endgroup$ – Ernie Aug 24 '20 at 18:38

Your Answer

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

Browse other questions tagged or ask your own question.