I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I see the issue here. $\|x\|_\infty$ is a convex function. Only when you do minimization, it is a convex problem. If you do maximization, the problem itself won't be convex one. Linear programming is a special convex problem. I feel you won't be able to convert it to single linear-programming problem. $\endgroup$– Yan ZhuCommented Mar 30, 2022 at 4:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Perhaps, the easiest approach is just to solve $2n$ problems with objectives: $x_i\to \min$ and $x_i\to\max$ for $i=1,2 \dots,n$, where $n$ is the size of $x$, and then pick the solution that delivers overall maximum of $|x_i|$.
answered Mar 29, 2022 at 23:44
-
$\begingroup$ You could detail the how-to construct such $2n$ problems, I think. Could you? $\endgroup$ Commented Jun 25, 2022 at 5:18
-
$\begingroup$ What exactly is not clear in my answer? $\endgroup$ Commented Jun 25, 2022 at 11:24
-
$\begingroup$ First, I dont know such notation for minimization. Second, how to know what you've done works? Where is the proof? $\endgroup$ Commented Jun 25, 2022 at 16:04
-
1$\begingroup$ @R.W.Prado: For example, $x_i\to\max$ denotes the objective function $f(x) = f(x_1,\dots,x_n) = x_i$ subject to maximization. The proof is straightforward: $$\max_x |x|_\infty = \max_x \max \left\{ |x_1|, \dots, |x_n|\right\} = \max_x \max \left\{ x_1, -x_1, \dots, x_n, -x_n \right\}$$ $$=\max \left\{ \max_x x_1, -\min_x x_1, \dots, \max_x x_n, -\min_x x_n \right\},$$ where maximization/minimization over $x$ is done under the given constraints $Ax\leq b$. $\endgroup$ Commented Jun 25, 2022 at 17:29
-
$\begingroup$ I see it. Thank you. Makes total sense now. =) Despite being $2n$ problems, storing the largest gotten value, it's possible to reduce the cost comparing with the last values obtained before. $\endgroup$ Commented Jun 25, 2022 at 17:40