Let $c_1,\dots,c_n$ be $n$ positive numbers and so be $a_1,\dots, a_n$. For some $r$ such that $1\leq r\leq n$, consider the optimization problem \begin{align} \max_{x_i\in\mathbb{R}}&~~\sum_{i=1}^{r}c_ix_i - \sum_{i=r+1}^{n}c_ix_i \\ & \sum_{i=1}^{r}a_ix_i - \sum_{i=r+1}^{n}a_ix_i \leq b \\ & 0\leq x_i \leq 1~,~\forall i \end{align} I understand that I can use a linear solver for this, however I am interested in finding a separate algorithm for this. I am using the following approach to solve it. First I initialize all $x_i$ as \begin{align} x_i \, = \, \begin{cases}1 ~~\text{if}~i\in\{1,\dots,r\}\\ 0 ~~\text{if}~i\in\{r+1,\dots,n\}\end{cases} \end{align} Note that this is the objective value at the optimum for the unconstrained problem which will be always larger (or equal) than the objective value at optimum of the constrained one. At this point, if this point is feasible, then we are done. Else, note that $\{c_i\}_{r+1}^{n}$ all have a decreasing effect on both objective and LHS of constraint (making it more likely to satisfy the constraint). Thus, I pick the smallest among these $c_i$ and increases its $x_i$ in $[0,1]$ to see if the constraint becomes feasible while decreasing the objective. If not, set $x_i=1$ and pick the second smallest in $\{x_i\}_{i=r+1}^{n}$ and continue in this fashion till I exhaust all in that set. Then I move on to the set $\{c_i\}_{1}^{r}$ and do similar operations there. My question is whether this will find the true solution?

  • $\begingroup$ I believe that constructing a one-dimensional Lagrangian dual problem is your way to construct a specialized algorithm. Construct a Lagrangian with a multiplier $\lambda > 0$ for the first inequality constraint, and minimize it subject to $x_i \in [0, 1]$. You can maximize it any one-dimensional method you like, such as Golden Section search, and then extract the primal optimal by substiuting $\lambda^*$ into the Lagrangian minimization problem. $\endgroup$ – Alex Shtof Mar 17 '19 at 8:09
  • $\begingroup$ Please clear this doubt. Is skipping the multipliers corresponding to $x_i\in [0,1]$ is ok? because they are also constraints, right? $\endgroup$ – dineshdileep Mar 17 '19 at 12:04
  • $\begingroup$ Yes. Duality works for convex problems of the form $\min~f(x)~\text{s.t.}~ g_i(x) \leq 0~ x \in C$. The dual function is $q(\lambda) = \min_{x \in C} \{ f(x) + \sum_{i} \lambda_i g_i(x) \}$. It is our choice which constraints we treat as $g_i$ and which constraints we treat as $C$. I chose to treat $x_i \in [0, 1]$ as the set $C$, and left with only one constraint which has a multiplier. $\endgroup$ – Alex Shtof Mar 17 '19 at 12:13
  • $\begingroup$ Got, it. Thanks!. $\endgroup$ – dineshdileep Mar 17 '19 at 12:34
  • $\begingroup$ @AlexShtof how are KKT conditions satisfied here? $\endgroup$ – dineshdileep Mar 17 '19 at 21:57

This algorithm is suboptimal. Suppose $a_i=0$ then you change $x_i$ unnecessarily. If you consider the ratio of $c_i$ and $a_i$, you almost mimicked the simplex method.

  • $\begingroup$ Can you explain the part on simplex method more? $\endgroup$ – dineshdileep Mar 16 '19 at 13:54
  • $\begingroup$ @dineshdileep I would need some time to work out the details and I am not 100% certain it boils down to the same result, but the ratio test in the dual problem considers the same ratios. $\endgroup$ – LinAlg Mar 16 '19 at 14:20

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.