1
$\begingroup$

I am trying to solve an optimization problem which is probably reminiscent of optimal control theory but all of this is not exactly my field of expertize and I am a little bit lost in translation. If someone could please put me on the right tracks, it would most certainly save me a lifetime of useless wanderings.

In discrete time $t=[1,2,...,T]$, I would like to find the vector $\{b_t\}_{t \in T}$ such that $F(b_t):=\sum_{t=1}^{T} h(d_t-b_t)b_t$ is maximized, where:

  1. $\{d_t\}_{t \in T}$ is given and $d_t \geq0 \quad \forall t\in T$.
  2. $h(\cdot):\mathbb R^+ \to \mathbb R^+ $ is a strictly convex function.
  3. $d_t-b_t\geq0 \quad \forall t\in T$
  4. $\mid b_t \mid \leq \zeta \quad \zeta \in \mathbb R^+$
  5. $\sum_{t=1}^{t'} \big(\theta(b_t)+\eta\theta(-b_t)\big)\cdot b_t\leq 0 \quad \forall t'=[1,2,...,T]$ , where $0<\eta \leq1$ is fixed and $\theta(\cdot)$ is the Heaviside function.

I am pretty novice in optimization theory but from what I have understood this problem could maybe be solved using Karush-Khun-Tucker conditions, but then I don't clearly see how to proceed, notably with the heaviside's. Is there a better approach or is this problem simply unsolvable? Is there good (introductory) literature I should read about this?

Thank you for your help!

$\endgroup$
  • 2
    $\begingroup$ So you are trying to maximize a convex function, which means all solutions will be at an extreme points of your constraint set. I haven't thought about it more closely, but given that it is a convex maximization, it may be intractable. $\endgroup$ – Suvrit Jul 16 '15 at 22:43
  • $\begingroup$ Thanks Suvrit for your comment, I am not sure to understand your point (although h(a-x) is convex x.h(a-x) is not necessarily convex anymore). When relaxing constraint 5. it looks straightforward to find the optimal solution by differentiating x.h(a-x) with respect to x. But constraint 5. imposes a "chronological" limitation on solutions which I don't know how to handle properly. I surely miss some theoretical background here, any advice would be great. $\endgroup$ – Anna maredric Jul 20 '15 at 8:37
3
$\begingroup$

I assume that $\theta(y) = 1$ if $y\geq 0$, and $\theta(y)=0$ else. In that case you can "linearize" your constraint 5 as follows: Add new variables $y_t$ for $t \in T$. Replace constraint 5 with the following three linear constraints:

i) $y_t \geq b_t$ for all $t \in T$.

ii) $y_t \geq \eta b_t$ for all $t \in T$.

iii) $\sum_{t=1}^{t'} y_t \leq 0$ for all $t' \in \{1, ..., T\}$.

This works precisely because $0 < \eta \leq 1$. The entire problem would be a convex optimization problem if the functions $h(d_t-b_t)b_t$ were concave in $b_t$ for all $t$.


Without concavity of the objective function, general solutions seem hard. However, the above transformation at least maps it to a problem of maximizing a (nonconcave) objective function over a convex set defined by linear inequality constraints. And KKT conditions may be easier to state now.

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