2
$\begingroup$

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}$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ At a higher level, what are you actually trying to accomplish? $\endgroup$
    – Mark L. Stone
    Commented Aug 16, 2022 at 17:01
  • $\begingroup$ I am coding an infeasible interior-point method for LO problems. There is a parameter in the algorithm that is affected by that norm. $\endgroup$
    – Ramin Fakhimi
    Commented Aug 16, 2022 at 20:15
  • 1
    $\begingroup$ 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? $\endgroup$
    – Mark L. Stone
    Commented Aug 16, 2022 at 20:55
  • $\begingroup$ 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. $\endgroup$
    – Ramin Fakhimi
    Commented Aug 16, 2022 at 22:00
  • 2
    $\begingroup$ Can you do better than $\sqrt{n}$ factor when converting norms, and is that o.k.? if not, just use infinity norm. $\endgroup$
    – Mark L. Stone
    Commented Aug 16, 2022 at 22:22

1 Answer 1

Reset to default
3
$\begingroup$

Unless I misunderstand your problem you can get a bound on the norm of x by finding upper bounds for each component of x.

You can use primal and dual bound tightening to get upper bounds on each x. This is not necessarily possible for all problems but will work in many cases. Even better if your optimization problem has upper bounds already (in your formulation, as part of the matrix).

One paper typically referenced is Savelsberg: "Preprocessing and probing techniques for mixed integer programming problems" in the context of MILP. Tobias Achterberg's thesis has both primal and dual bound tightening spelled out (called constraint propagation there) and more references, but also in the context of MILP.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.