All Questions
7 questions
3
votes
2
answers
5k
views
Linear program to maximize the minimum absolute value of linear functions ?
I'd like to compute
$\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$.
where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.
Can this be solved with a linear ...
- 500
2
votes
4
answers
2k
views
Efficient algorithm for finding the minima of a piecewise linear function
Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:...
- 823
2
votes
2
answers
841
views
Finding the maximum of a multivariate polynomial of degree one
I need to find the global maximum of the function
\begin{align}
f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\
&+\ldots \\
&+ p_n ...
user24451
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
0
votes
2
answers
120
views
Reference request: dependence on linear constraints
Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:
$$P(...
- 1,835
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
101
views
How can we analytically solve this max-sum-min problem?
Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...
- 167