All Questions
10 questions
5
votes
1
answer
432
views
Optimizing a multivariate symmetric (permutation-invariant) function
Let $\ell$ and $d$ be two integers such that $\ell \le d$.
I would like to find the global maxima of the following symmetric function $f\colon (0,1]^n \to \mathbb{R}$,
$$f(x_1, \ldots, x_n) := \sum_{\...
- 381
4
votes
0
answers
539
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 391
3
votes
1
answer
886
views
Is the max of two supermodular functions supermodular?
A function $f: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ is supermodular if for every $x'>x$ and $y'>y$,
$$f(x',y') + f(x,y) > f(x',y) + f(x,y').$$
Suppose $f$ and $g$ are supermodular, ...
- 31
3
votes
1
answer
239
views
A difficult combinatorial optimization problem
Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.
(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. $\mid\...
- 1,421
2
votes
0
answers
56
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 2,772
2
votes
1
answer
240
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
- 21
1
vote
1
answer
94
views
Weak submodularity for consecutive indices
Let $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ be defined by $f(x,y) = \frac{x^2}{y}$. Let $X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$, $Y = \left\lbrace ...
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 193
0
votes
1
answer
236
views
Solving a 0-1 quadratic matrix inequality
I am working on a binary optimization problem. So far I have derived the following constraint functions.
\begin{align}
\begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^...
- 11
0
votes
0
answers
68
views
Under which conditions discrete versions of convex\concave function are submodular/supermodular?
I have $f(x)$ with $x \in [0,1]$ and $f(x)$ is convex, then, under which conditions discrete function which is defined as $f(x_h)$ on discrete subset of $[0,1]$, for example, $x_h \in \{0, h, 2h, \...
- 355