Consider the following constrained optimization with the integral objective function $$ \min_{x_i\in D} \int_{t_1}^{t_2} \frac 1 {t - \sum\limits_{i = 1}^N x_i f_i (t)} \, dt $$ where $t - \sum\limits_{i = 1}^N x_i f_i(t) > 0 $ and $f_i(t)$ are polynomial functions. $D$ is a convex set. Is there any numerical method to solve the problem?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This looks like a convex optimization problem. Fix a convex set $D \subseteq \mathbb{R}^N$. Fix parameters $t_1<t_2$. Let $x=(x_1, \ldots, x_N)$. Define the set $\mathcal{A}$ and function $g:\mathcal{A}\rightarrow \mathbb{R}$ by: \begin{align} \mathcal{A} &= \left\{x \in D : t - \sum_{i=1}^N x_i f_i(t)>0 \quad \forall t \in [t_1, t_2]\right\} \\ g(x) &= \int_{t_1}^{t_2} \frac{1}{t - \sum_{i=1}^N x_i f_i(t)}dt \end{align} Assume the set $\mathcal{A}$ is nonempty.
Claim: The set $\mathcal{A}$ is a convex set, and the function $g(x)$ is a convex function over $x \in \mathcal{A}$.
Proof: The set $\mathcal{A}$ is the (infinite) intersection of convex constraints, and so it is a convex set. Now Let $X$ be a random vector in $\mathcal{A}$ that takes two possible values with probabilities $\theta$ and $1-\theta$. It remains to prove that $E[g(X)] \geq g(E[X])$. We have: \begin{align} E[g(X)] &= \int_{t_1}^{t_2} E\left[ \frac{1}{t - \sum_{i=1}^N X_i f_i(t)}\right] dt \\ &\geq \int_{t_1}^{t_2} \frac{1}{t-\sum_{i=1}^N E[X_i] f_i(t)} dt \\ &= g(E[X]) \end{align} where the inequality holds by convexity of the function $1/y$ for $y>0$. $\Box$
If you want, you can compute a gradient $\nabla g(x)$ via: $$ \frac{\partial g}{\partial x_i} = -\int_{t_1}^{t_2} \frac{f_i(t)}{\left(t - \sum_{i=1}^Nx_i f_i(t)\right)^2} dt $$ and then use a gradient projection method, although projecting a vector onto the set $\mathcal{A}$ may not be easy. You might approximate this set by a discretization of $[t_1, t_2]$ to a finite set of times $\{\tau_1, \ldots, \tau_K\}$, and then the approximated set $\tilde{\mathcal{A}}$ is defined by $k$ linear inequality constraints: $$ \tilde{\mathcal{A}} = \left\{x \in D : \tau_k - \sum_{i=1}^N x_i f_i(\tau_k) > 0 \quad \forall k \in \{1, ..., K\} \right\} $$
Alternatively, you can use an interior point approach: Each iteration, go in a direction of the optimal change (as determined by the gradient), but go only an amount $\eta>0$. So if we are at a current interior point $x$, we find the direction vector $d$ and find $\eta>0$ so that $x + \eta d $ is still inside our constraint set, and $g(x+\eta d)$ is a nicely improved value. If the gradient is zero then we know we are optimal.
To avoid the case where the denominator goes to zero, you can fix a value $\theta>0$ and change the constraint to:
$$ t - \sum_{i=1}^N x_i f_i(t) \geq \theta \quad \forall t \in [t_1, t_2] $$
Assuming $\{\tau_1, ..., \tau_K\}$ are equally spaced over $[t_1, t_2]$, you can approximate the entire problem via the discretization $\{\tau_1, \ldots, \tau_K\} \subset [t_1, t_2]$ by:
\begin{align*}
\mbox{Minimize:} & \quad \sum_{k=1}^K \frac{1}{\tau_k - \sum_{i=1}^Nx_if_i(\tau_k)} \\
\mbox{Subject to:} & \quad \tau_k - \sum_{i=1}^Nx_i f_i(\tau_k) \geq \theta \quad \forall k \in \{1, \ldots, K\} \\
& \quad x \in D
\end{align*}
and this is itself a convex optimization problem. A potentially interesting way of making this into a separable problem is this: If you assume $D$ is a compact set and define $y_k^{max}$ as maximum values of $\tau_k - \sum_{i=1}^Nx_i f_i(\tau_k)$ over $x \in D$, then the above problem is equivalent to the following (which introduces additional decision variables $y_k$):
\begin{align*}
\mbox{Minimize:} & \quad \sum_{k=1}^K \frac{1}{y_k} \\
\mbox{Subject to:} & \quad \tau_k - \sum_{i=1}^Nx_i f_i(\tau_k) \geq y_k \quad \forall k \in \{1, \ldots, K\} \\
& \quad y_k \in [\theta, y_k^{max}] \quad \forall k \in \{1, \ldots, K\} \\
&\quad x \in D
\end{align*}
A "drift-plus-penalty" method (related to classic dual-subgradient methods) would be to define "virtual queues" (related to Lagrange multiplier estimates) for each $k \in \{1, ..., K\}$ and iterations $t\in\{0,1,2,...\}$:
$$ Q_k(t+1) = \max\left[Q_k(t) + y_k(t) - \tau_k + \sum_{i=1}^Nx_i(t)f_i(\tau_k), 0\right] \quad \forall k \in \{1, ..., K\} \quad (Equation *) $$
The algorithm is then defined by a positive parameter $V$ and is the following: Initialize $Q_k(0)=0$ for all $k \in \{1, ..., K\}$. Every step $t \in \{0, 1, 2, ...\}$ do:
1) For each $k \in \{1, ..., K\}$, choose $y_k(t)$ to solve: \begin{align} \mbox{Minimize:} & \quad \frac{V}{y_k} + Q_k(t)y_k(t) \\ \mbox{Subject to:} & \quad y_k(t) \in [\theta, y_k^{max}] \end{align} which reduces to $y_k(t) = \left[ \sqrt{V/Q_k(t)}\right]_0^{y_k^{max}}$, with $[a]_0^{y_{max}}$ denoting the projection to the interval $[0, y_k^{max}]$.
2) Choose $x(t) = (x_1(t), ..., x_K(t))$ to solve: \begin{align} \mbox{Minimize:} & \quad \sum_{i=1}^N x_i(t)\left[\sum_{k=1}^KQ_k(t)f_i(\tau_k)\right]\\ \mbox{Subject to:} & \quad x(t) \in D \end{align}
3) If $t>0$, form the averages: $$ \overline{x}_i(t) = \frac{1}{t}\sum_{\tau=0}^{t-1} x_i(\tau) $$
4) Update the $Q_k(t)$ values via (Equation *).
The nice thing about this algorithm is that it reduces the steps to finding a vector $x(t) \in D$ to minimize a linear function on each iteration $t$. The averages $(\overline{x}_1(t), ..., \overline{x}_N(t))$ converge to an answer within $O(1/V)$ of optimality within $O(V^2)$ steps. http://arxiv.org/abs/1412.0791
Defining $\epsilon = 1/V$ means it gets an $O(\epsilon)$ approximation with convergence time $O(1/\epsilon^2)$. Not necessarily the fastest alg, but one with simple steps.
