I want to ask an optimization question, Consider x in Rn , such that Ax=b, we need to solve for minimum sum of positive components of x. which is an optimization over objective function f=1T (x+|x| ) such that, Ax=b, which is easily convertible to LP. We know some specific LPs have analytical solutions like min{ cT x } S.t. Ax=b, which the solution is bT(AAT)-1 Ac . So I was wondering if there exist a famous analytical solution for this optimization.
It is already analytic. You can get its exact solution in unique way, so you do need to make it complicate it any further. For more details such studies I would like to suggest you the work by Professor Stephen Boyd :::: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
what I mean is, I need a one step formula as the optimal value for 1T (x+|x|) without using linear programming, I am searching for a closed form solution.
Dear Navid, the problem is tricky. If the hyperplane Ax=b intersects the negative orthant, then all the points of the intersection are minima. Otherwise, reasoning in two dimensions for example, it seems that at least one of the minima should coincide with the point closest to the origin in 1-norm. I don't know whether it works in higher dimensions, but it remains hard to get a closed-form solution, since the function is nondifferentiable...
yes exactly , I agree, You know these days we are seeing many innovative methods that people are using change of variables and represent the non-differentiable functions in differentiable forms but using another variables, So I thought maybe there is some of those tricks for this one as well and this is why I asked this question here
- Badges
- Science topic
- Similar topics
- Mathematics