Considering the following optimization program:
$$ maximize \ \ \ \log \left( \|x\|_\infty \right) $$
$$ subject \ to \ \ Ax\leq b, \ x \geq 0 $$
can we rewrite this program as a convex equivalence?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ What is $x$? Why maximizing something is any different from maximizing its logarithm $\endgroup$– Pietro MajerCommented Aug 24, 2019 at 16:18
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
No, because this could easily have several local maxima.
answered Sep 28, 2018 at 4:05
-
$\begingroup$ is -$log(\|x\|_\infty)$ convex? $\endgroup$ Commented Sep 28, 2018 at 6:44
-
$\begingroup$ No, it is not. $-\|x\|_\infty$ is concave. $\endgroup$ Commented Sep 28, 2018 at 7:20
-
$\begingroup$ $-\log(x)$ is convex and $\|x\|_\infty$ is convex, how about the composite of them. If not, i am thinking of approximating it using its convex envelope. Is there a function serving as a lower convex approximation of it? $\endgroup$ Commented Sep 28, 2018 at 7:22
-
$\begingroup$ Certainly not near $0$. Or on any domain that contains a line segment whose midpoint is closer to $0$ than its endpoints. $\endgroup$ Commented Sep 28, 2018 at 7:39
-
$\begingroup$ sorry that i forgot to add $x \geq 0$ and i updated my question. $\endgroup$ Commented Sep 28, 2018 at 13:10
$\begingroup$
$\endgroup$
Consider solving $n$ linear programs ($n$ being the dimension of the vector $x$), where the $i^{\rm{th}}$ LP is given by: $$ \max_x ~~~x_i\\ \mbox{subject to}\\ \hspace{3cm}Ax\leq b, x\geq 0\\ \hspace{3cm} x_j\leq x_i, ~\forall j\neq i. $$ Note that $\log$ can be removed its a monotonic function. It's clear that these LP's are the only possible cases. Finally choose the best among the solutions of the LPs (which ever exist), and take log of its inf-norm for the optimal value. Also, if any of the LP's is unbounded, the original problem is also unbounded.
$\begingroup$
$\endgroup$
Adding to the answer by @Robert Israel (which I'm sure he knows, but didn't mention):
Because log is strictly monotonically increasing, this problem is equivalent to $maximize \left( \|x\|_\infty \right)$ subject to the same constraints.
That is a concave programming problem, i.e., the minimization of a concave function ($ -\|x\|_\infty$) subject to convex constraints. If the constraints are compact, there is a global optimum at an extreme of the constraints, although there may be additional global optima not at an extreme. There may also be one or more local optima which are not global optima.
Presuming an upper bound can be placed on $x$, then by introduction of binary variables, this can be converted to a Mixed-Integer Linear Programming (MILP) problem, and solved to global optimality by any off the shelf MILP solver, such as Gurobi or CPLEX, among many others. It is NP hard, so it might take a while (and require some memory), but the business model of the companies which develop and sell MILP solvers is predicated on the ability of their customers to routinely solve NP hard problems using their solvers.
answered Apr 21, 2020 at 0:03