# An upper bound for the norm of solution to linear optimization problem

I am looking for a practical method to find a valid upper bound for the infinity norm of the solution to a standard linear optimization problem: \begin{align}\min&\quad c^\top x \\ \text{s.t.}&\quad Ax = b\\ &\quad x \ge 0,\end{align}

where $$x,c \in \mathbb{R}^n$$, $$b\in\mathbb{R}^m$$ and $$A\in \mathbb{R}^{m\times n}$$. We can also assume that the final precision and optimality gap is $$\epsilon = 10^{-6}$$.

• At a higher level, what are you actually trying to accomplish? Aug 16, 2022 at 17:01
• I am coding an infeasible interior-point method for LO problems. There is a parameter in the algorithm that is affected by that norm. Aug 16, 2022 at 20:15
• But it can be any norm? Does the parameter determination take into account which norm it is? Do you need to bound the norm of all optimal solutions, or just ensure there is at least one optimal solution whose norm satisfies the bound? The methods I can think of are more computationally demanding than solving the LP you show - is that LP what you are trying to solve with the infeasible interior-point method? Is LO the same ad LP? Aug 16, 2022 at 20:55
• It is the infinity norm. We can derive an upper bound for it if we have different norms like l1 and l2. One solution is enough. By LO, I meant LP. I prefer to use the term optimization instead of programming. Aug 16, 2022 at 22:00
• Can you do better than $\sqrt{n}$ factor when converting norms, and is that o.k.? if not, just use infinity norm. Aug 16, 2022 at 22:22