3

Is there a known algorithm ( similar to simplex algorithm) that solves the following problem: Maximize $c^Tx$ subject to the constraints $Ax\leq b$ and $c^Tx\leq \alpha$. It would be nice if you can provide a link to an article or software implementation of such problems.

Thanks

Mary Star
  • 13,956
YoelZ
  • 41

1 Answers1

1

Well of course, all you do is add $c^T$ as a row to your $A$ matrix, and $\alpha$ to your $b$ vector. That is, $$\bar{A}\triangleq \begin{bmatrix} A \\ c^T \end{bmatrix} \quad \bar{b}\triangleq \begin{bmatrix} b \\ \alpha \end{bmatrix}$$ And then you solve using any preferred algorithm: $$\begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to} & \bar{A} x \leq \bar{b} \end{array}$$ Here's how this works: let $\alpha_{\max}$ be the solution to the original problem (without the extra $c^Tx\leq\alpha$ constraint), and let $\alpha_{\min}$ be the solution to the minimization $$\begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x \leq b \end{array}$$ (Note: it's possible one of these extremes will be infinite.) Now select any value $\alpha\in[\alpha_{\min},\alpha_{\max}]$ and add your extra constraint $c^Tx\leq \alpha$ as I've shown above. When you solve this modified model, the optimal point $x^*$ will achieve exactly $c^Tx^*=\alpha$.

Again, I'm sorry for misreading the problem earlier! I hope this clarifies matters.

Michael Grant
  • 19,450
  • because sometimes you don't care about global maximums but only about local ones. I am not interested in any maximum but only maximum in a certain region. – YoelZ Feb 17 '14 at 22:23
  • Why must the modified program be unfeasible if $c^Tx^>\alpha$? Clearly $x^$ cannot be optimal, as it is not feasible, but there could exist a different optimal solution for the modified program. – Daryl Feb 17 '14 at 22:27
  • so what you're saying that with your modification if there is no solution to the original model there will be no solution to your modification? – YoelZ Feb 17 '14 at 22:28
  • Of course I am asking about it but you solved my problem so for that I am very thankful and I am giving you all the credit! But suppose that we found $x$ in the original problem such $c^Tx^{}>\alpha$ does it mean that if I will use the new set up (with \bar(A) it will give me a point $x_0$ and the maximum will be exactly $\alpha?$ This exactly what I am looking for! – YoelZ Feb 17 '14 at 22:36
  • I'm afraid I misread your problem as a minimization, not a maximization. My approach to adding a row to $A$ and $b$ still works, but most of what I said before is irrelevant. I'm sorry for leading you astray; I'm deleting many of my comments above. @Daryl, now I understand your confusion too. – Michael Grant Feb 17 '14 at 22:38
  • No that's fine. I am happy with your trick. I didn't realize that I can add constraints satisfied by the cost function itself. The trick you suggested should do the job. – YoelZ Feb 17 '14 at 22:45
  • Great. I've modified my answer accordingly. – Michael Grant Feb 17 '14 at 22:45
  • 1
    This problem arises naturally in financial planning. You have an existent portfolio with certain weights and projected returns for each of these weights. You like to achieve a maximal certain return below a certain return threshold while keeping control of how you change the weights ( not too much trading). So I hope you can see that the restriction I introduced is natural ( total return of the portfolio is just the weighted average of the projected returns) – YoelZ Feb 17 '14 at 22:48