0
$\begingroup$

I am trying to find the dual of the following linear program. The primal LP's purpose is to find the lowest possible L1 (sum of absolute values of coefficients) of a degree $d$ polynomial such that (1) the polynomial is bounded between -1 and 1 for all points $x\in X$ and that (2), the polynomial has slope $\mathcal{S}$ at $x=1$. Note that the variables $c$ represent the coefficients of the polynomial, and the $s$ variables are used to look at their absolute values. (As a side note, realize that if $X$ is set to be the Chebyshev nodes, and constant $\mathcal{S}$ is set to $d^2$, then the only feasible polynomial for this LP is the degree $d$ Chebyshev polynomial.)

$\min_{s,c} s_0+...+s_d$
s.t. $\forall i=0,...,d$
$c_i-s_i\leq 0$
$-c_i-s_i\leq 0$
$c_1+2c_2+...+dc_d=\mathcal{S}$
$|c_0+c_1x+c_2x^2+...+c_dx^d|\leq 1\forall x\in X$

I have taken what I think is the dual of this program, and attained the following. Note that the $j$th value in the set $X$ is denoted $x_j$. (I presume $X$ has $n+1$ elements ordered in increasing order.)
$\max_{a,\lambda,\psi}\sum_{i=0}^na_i-\mathcal{S}\psi$
s.t. $\forall i=0,...,d$
$0\leq\lambda_i\leq 1$
$2\lambda_i+i\psi-\sum_{j=0}^na_jx_j^i=1$

I believe that some mistake must have been made, as evaluating this dual LP via computer results in the program saying that it is unbounded (ie the primal is infeasible). But this makes no sense, as clearly the primal is feasible. Can someone check whether I correctly took the dual? I have checked several times, but not found an error in my derivation or in my program.

$\endgroup$

1 Answer 1

0
$\begingroup$

It turns out that there was a sign flipped somewhere. The correct dual is:
$\max -\sum_{i=0}^n(\alpha_i+\beta_i)-\psi\mathcal{S}$
st $\forall i=0,...,d$
$\lambda_i+\gamma_i=1$
$\lambda_i-\gamma_i+i\psi+\sum_{j=0}^n(\alpha_j-\beta_j)x_j^i=0$.
Where $\psi$ is a free variable and all other variables are nonnegative.

$\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.