0

Consider the following optimization problem, where $t_i$ is known

$$ \max_{0\leq a_1,\cdots,a_k\leq 1} \sum_{i=1}^k a_it_i $$

I want to ensure that the following inequality holds after optimization is completed

$$ a_1\leq a_2\leq \cdots \leq a_k $$

So how should I add constraints to the original objective function?

Some thoughts: I tried to add this item in the objective function to achieve my purpose

$$ M\cdot \sum_{i=2}^k (a_{i}-a_{i-1}), \quad M >>0 $$

But I soon discovered that this constraint does not guarantee that $a_i$ is increasing. Because only one of the sum terms is required to be large and the other terms are less than 0, it can also be guaranteed that the sum is a large integer. In addition, even if this constraint is correct, I still need to balance it with the original objective function through a hyperparameter.

So is there a better solution?

korangar leo
  • 1
  • Maybe you need to write more context about why you require to force this into the objective, because the natural approach would be to add these inequalities as constraints (your problem is already constrained by the bounds on $a_i$). – Michal Adamaszek Jan 30 '24 at 08:21
  • @MichalAdamaszek Sorry, maybe I didn't express it clearly. It does not necessarily need to be forced to be added to the objective function, as long as it ensures that the final result is increasing. – korangar leo Jan 30 '24 at 08:32
  • These are $k-1$ linear constraints $a_i-a_{i-1}\geq 0$, so you just add them as such. – Michal Adamaszek Jan 30 '24 at 08:35
  • I wonder if thinking about the a's as a vector living in a wedge of $R^k$, and looking for the vector that is most parallel to $t$ might give some insight – user619894 Jan 30 '24 at 08:49

1 Answers1

1

I think the following works:

Set $p_1=a_1, p_2=a_2-a_1,\ldots, p_k=a_k-a_{k-1}$ and $w_n = \sum_{i=n}^k t_i$ for $n=1,\ldots, k$. Then your objective function becomes

$$\sum_{i=1}^k p_iw_i,$$

with all the $w_i$ known (they just depend on the known $t_i$). You can check that for a given index $i$, $t_i$ only occurs in $w_1,\ldots,w_i$ and that the factors $p_n, n=1,\ldots,i$ sum up to $a_i$.

So how do the constrains transform? $a_1 \le a_2 \le \ldots \le a_k$ is equivalent to $p_2,p_3,\ldots,p_k \ge 0$. The condition $0 \le a_1$ becomes $p_1 \ge 0$ and $a_k \le 1$ becomes $\sum_{i=1}^kp_i \le 1$. So to summarize, we have as equivalent constraints

$$0 \le p_1,\ldots,p_k;\;\sum_{i=1}^kp_i \le 1$$

So it looks to me the following is true: If any $w_i$ are positive, take the largest one (say $w_m$), set the corresponding $p_m=1$ and all other $p_i=0$. Than your objective function becomes equal to $w_m$, and you can't do better. That's because having a a positive $p_i$ for a negative $w_i$ decreases your sum, and having any positive you $p_i$ on a postive or zero $w_i$ would be better spent on $w_m$, as it is the largest positive $w_i$.

However, if all $w_i$ are negative or zero then your objective function can be at most $0$, and you can achieve that by choosing $p_1=p_2=\ldots=p_k=0$.

Ingix
  • 14,494