Solving the problem through KKT condition

35 Views Asked by At

This is my optimization problem where $n$ is the only decision variable of the problem:

\begin{align} \min_{n} \quad &c n \\ \text{subject to:}\quad &\sum_{i \in I} D_{i}x_i \lambda_i < n \\ &\frac{nD_{i}x_i}{n - \sum_{i' \in I}D_{i'}x_{i'} \lambda_{i'}} \leq \overline{LR}_i \quad \forall i \in I \\ & n \leq N \\ & n \in \mathbb N \end{align}

Can I use KKT condition to solve this problem? If so, since I have multiple constraints (one for each i $\in I$), How I can solve it and obtain optimal $n$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

The problem is trivial. You don't need KKT. Your first inequality has the form

$$\alpha < n$$

for some known constant $\alpha$, since $\sum_{i \in I} D_i x_i \lambda^i$ is a constant. Your second inequality has the form

$${\beta_i n \over n - \alpha} \le \gamma_i,$$

for some known constants $\beta_i,\gamma_i$, since $D_i x_i$ is a constant. This inequality is equivalent to

$$\beta_i n \le \gamma_i n - \alpha \gamma_i,$$

which is in turn equivalent to

$$n \ge {-\alpha \gamma_i \over \gamma_i - \beta_i}$$

if $\beta_i < \gamma_i$; or equivalent to

$$n \le {-\alpha \gamma_i \over \beta_i - \gamma_i}$$

if $\beta_i > \gamma_i$.

Therefore, your "subject to" constraints are all of the form $n \le d_i$ or $n \ge e_i$ for some constants $d_i,e_i$. It follows that they are equivalent to

$$\max_i e_i \le n \le \min_i d_i.$$

You can compute the constants $d_i,e_i$, find their min/max, and thereby find the allowable range for $n$. Now, assuming $c>0$, the minimum possible value of $cn$ over this range will happen when $n$ is at its minimal allowable value, i.e., $n = \max_i e_i$. It follows that it is trivial to solve your constraint system.