# Questions tagged [global-optimization]

The global-optimization tag has no usage guidance.

**1**

vote

**0**answers

71 views

### When are quadratic integer programs “easy to solve”?

Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form
$$
f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...

**0**

votes

**0**answers

26 views

### symmetry preservation and symmetry breaking in optimization algorithms

Let $M$ be a Riemannian manifold, and $G$ be a group of isometries on $M$. If we have a $G$-invariant functional $F: M \rightarrow \mathbb{R}$, i.e. $F(g \cdot x) = F(x)$ for all $x \in M$ and $g \in ...

**0**

votes

**1**answer

82 views

### Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...

**0**

votes

**0**answers

59 views

### Is dynamic programming suitable for a specific optimization problem?

Let $c,\,\mathcal{P}_0,\,\mathcal{P}_1,\,\mathcal{P}_2,\ldots$ be a sequence of positive real numbers.
Let $N\in\{1,\,2,\,3,\ldots\}$ and let $t\in\{0,\,1,\,2,\ldots\}$, with $N$ and $t$ fixed.
...

**1**

vote

**1**answer

78 views

### Looking for a very particular kind of non-convex functions

I want some examples (hopefully parametric families!) of non-convex functions which satisfy the following properties simultaneously,
It should be at least twice differentiable.
It should have a ...

**0**

votes

**0**answers

30 views

### How can I solve a constrained optimization problem with a random number of decision variables?

Here is my problem. Let $A_t$ be a random variable with Poisson-Binomial distribution with set of success-probabilities $\{q_1^{(t)},\ldots,\,q_n^{(t)}\}$, with $t\in\{1,\,2,\,3,\ldots\}$, $n\in\...

**1**

vote

**0**answers

37 views

### Minimum Preserving Transformations [closed]

If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then
$$
\operatorname{argmin}_{x \in X} f(x)
=
\operatorname{argmin}_{x \in X} g\circ f(x) .
$$
X and Y ...

**0**

votes

**1**answer

104 views

### Properties of the argmin function (continuity, differentiability..) [closed]

Given vectors $x_1,\ldots,x_N \in \mathbb{R}^d$ and a function, say $\psi \colon \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$, one is interested in the properties of the function $$\Phi\colon (x_1,...

**1**

vote

**2**answers

205 views

### Maximizing a function that is sum of gaussians

Let $\mathbf{x}_1,\dots,\mathbf{x}_n$ be given $n$ vectors in $\mathbb{R}^d$. Define the function
\begin{align}
\mathcal{K}(\mathbf{x},\mathbf{y})=
\alpha\exp(-\frac{||\mathbf{x}-\mathbf{y}||^2}{2\...

**4**

votes

**2**answers

108 views

### Optimization problem on trace with both the positive semi definite and non positive semidefinite matrix

Given two $N \times N$ symmetric matrices $A, B$, where $A$ is positive semidefinite while $B$ is not positive semidefinite. I am interested in solving unitary constrained trace maximization problem:
...

**0**

votes

**0**answers

26 views

### Are Matérn class kernels universal kernels or not?

This is a question that I can't find the solution. I don't know it is a open question or it is a well-known result that can be attained from several lemmas.
Here are the definition of Matérn class ...

**15**

votes

**3**answers

808 views

### Is this lower bound for a norm of some complex matrices true?

Let $A = [a_{ij}]_{n\times n}$ be a Hermitian matrix, such that $|a_{ij}| =1$ for $i \neq j$, and $a_{ii} = 0$ for each $i$.
I am interested in a tight lower bound of $\|A\|_*:=\sum_{i=1}^n |\lambda_i(...

**0**

votes

**0**answers

31 views

### Nonlinear optimization problem better efficiency

I have a highly nonlinear optimization problem that I describre in the following lines:
$A$ is a $N \times N$ known matrix, $\vec{z},\vec{M},\vec{D}$ are known vectors of length $N$ and $R,T$ are ...

**0**

votes

**2**answers

94 views

### Maximizing a convex function with a convex constraint

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$, the objective is to find the farthest point in the level set $\left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1\right\rbrace$ (Assuming that ...

**0**

votes

**1**answer

48 views

### Linearly constrained saddle-point optimization

Let $f(x,y)$ be a smooth (twice differentiable) saddle function (convex in $x$ and concave in $y$), where $f \colon X \times Y \rightarrow \mathbb{R}$, and $X \subset \mathbb R^n$, $Y \subset \mathbb ...

**1**

vote

**0**answers

48 views

### On number of solutions by simplex and number of solutions in total in a linear optimization problem?

This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...

**0**

votes

**0**answers

45 views

### Optimization of generalized Fisher information over space of probability measures

Assume we already have $p(\theta)$ apriori desnsity function about unknown parameter $\theta$, and we consider an optimization problem as follows:
\begin{equation} \max_{P \in \mathcal{M}} \int_{\...

**3**

votes

**1**answer

165 views

### Does there exist energy-minimizing immersions?

This is a cross-post.
Let $M,N$ be $d$-dimensional oriented Riemannian manifolds, possibly with boundary, $M$ compact. Let $E_d:C^{\infty}(M,N) \to \mathbb{R}$ be the $d$-energy, i.e.
$$ E_d(f)=\...

**9**

votes

**2**answers

210 views

### A (reverse)-Minkowski type inequality for symmetric sums

Let $(u_1, u_2, u_3, u_4)$ and $(v_1, v_2, v_3, v_4)$ be vectors in $\mathbb R_+^4$. Is the following inequality true?
\begin{align*}
\left(\sum_{{[4] \choose 3}} \sqrt{u_i u_j u_k}\right)^{2/3} + \...

**0**

votes

**0**answers

20 views

### Quality indicator for two-objective Pareto fronts

What quality indicator can be used for two-objective cases when computing a Pareto front? One that I identified is a hypervolume indicator, but most of the articles and examples show for d > 2 ...

**3**

votes

**1**answer

58 views

### Maximizing the $\alpha$-moment of a distributution

Given $\alpha$ and constant $\mu$,
$$\begin{array}{ll} \text{maximize} & \displaystyle\int_0^\infty p(x)x^\alpha \,\mathrm d x\\ \text{subject to} & \displaystyle\int_0^\infty p(x)\,\mathrm d ...

**0**

votes

**1**answer

104 views

### QUBO formulation of a discrete-variable Genetic Algorithm optimization problem

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic real-valued function $f$ depending on a set of parameters $ \theta\...

**1**

vote

**0**answers

51 views

### Where does the expected value in the restatement of the pseudoregret come from?

Given stochastic payoff functions $X_{1}(t) \dots X_{K}(t)$, each having a different probability distribution on $[0,1]$, denote the expected value of $X_i(t)$ by $\mu_i$, and define $\mu^* = \max_{i \...

**1**

vote

**0**answers

42 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 ...

**6**

votes

**3**answers

220 views

### Solve $\inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] $

I want to solve the following optimization problem
\begin{align}
\inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right]
\end{align}
where $X^\prime$ is an independent copy ...

**0**

votes

**0**answers

48 views

### Dense set of functions on manifold with no local optima

Given a smooth manifold $M$ and another $S$, consider a smooth function $\psi: S \times M \rightarrow \mathbb{R}$, and use this to define $\psi_s:M\rightarrow \mathbb{R}$ by $\phi_s(p):= \psi(s,p)$.
...

**0**

votes

**1**answer

78 views

### Maximizing sum of a product of logs

I came across the following note in a paper I'm reading and don't understand how it was derived.
$\max_{\alpha_\ell}\sum_\ell^L\beta_\ell\log\alpha_\ell$ such that $\sum_\ell^L\alpha_\ell=1$ and $\...

**1**

vote

**1**answer

992 views

### minimum of convex function in different variables [closed]

Let $g_1,g_2$ be convex functions defined over $[0,1]$, and let $f:[0,1]^2 \rightarrow\mathbb R$ such that
$$f(x,y)=\min(g_1(x),g_2(y)). $$
I wish to know whether $f$ is convex. I do suspect that $f$ ...

**1**

vote

**0**answers

34 views

### Linear cost traveling salesman heuristic

I have a sequence of points $y_1,\ldots,y_n\in \mathbb{R}^3$ and want to approximately minimise
$$
\sum_{i=1}^{n-1}|y_{\pi(i)}-y_{\pi(i+1)}|
$$
by choosing a permutation $\pi$ of $\{1,\ldots,n\}$.
I ...

**1**

vote

**1**answer

145 views

### Name for functions with local=global minimum

I have a simple question. We know that functions where every stationary point is a global minimum are invex functions. Is there a name for functions where every local minimum is a global minimum?
And ...

**1**

vote

**0**answers

117 views

### linear relaxation of an optimization problem

I'm reading an article lately, and there is one point which confuses me.
So, we have the following constrained binary quadratic problem.
min $x^{T}Qx$
with the constraints that $Ax\leq b$ and $x\in ...

**-2**

votes

**1**answer

31 views

### global or local solver for constrained pseudo concave problem [closed]

Is there a good Matlab solver that can help with the problem:
$\max_{\boldsymbol{s}\in\mathbb{R}^{n}}\frac{\sqrt{\boldsymbol{a}^{T}\boldsymbol{s}+\epsilon^{2}}}{\boldsymbol{b}^{T}\boldsymbol{s}+\...

**2**

votes

**1**answer

126 views

### equality between the ratio trace and the determinant ratio

I have encountered the following equality
$\arg\max_{\text{tr}\left(\boldsymbol{S}^{H}\boldsymbol{S}\right)=1}\text{tr}\left(\boldsymbol{S}^{H}\boldsymbol{A}\boldsymbol{S}\left(\boldsymbol{S}^{H}\...

**4**

votes

**3**answers

134 views

### Maximizing a pseudoconcave function in a box

I am trying to solve the problem:
$\max_{\boldsymbol{s}\in\mathbb{R}^{n}} \frac{\sqrt{\boldsymbol{a}^{T}\boldsymbol{s}+\alpha}}{\boldsymbol{b}^{T}\boldsymbol{s}+\beta}\\
\text{s.t} \;\;0\leq s_{i}\...

**3**

votes

**0**answers

182 views

### Constrained optimization with a Proportional-Integral-Derivative (PID) controller

My engineering colleagues have devised an interesting approach to equality-constrained optimization. I.e. they wish to solve the problem $\min_x f(x)$ subject to the constraint $g(x) = 0$ where $f, g ...

**1**

vote

**0**answers

59 views

### Nonconvex Optimization of inner product objective

Does there exist any result on the following minimization,
$$\min_{x\in P} \langle x, F(x)\rangle\equiv \sum_i x_i F_i(x), $$ where $P$ is a convex polytope and $F_i(\cdot)$s are convex functions of $...

**0**

votes

**2**answers

60 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**

vote

**1**answer

111 views

### Optimization problem restricted to a smaller field?

Let $c:\mathbb R^2\to\mathbb R$ be a Lipschitz and bounded function (which can be supposed as "nice" as possible). Let $\mu$ and $\nu$ be two probability measures on $\mathbb R$ with finite first ...

**4**

votes

**1**answer

2k views

### Can you give me good examples of non-convex functions that are problematic for optimization?

I want to test my extended gradient descent algorithm, whose aim is to handle non-convex problems better. Can you give me some examples of non-convex functions that are hard to minimize via gradient ...

**4**

votes

**1**answer

256 views

### Maximum entropy distribution with constrained quantiles

Suppose we have a continuous probability distribution with density function $f$ whose support is $[a,b]$ and we know that for some finite set of values $\{ v_i \}_{i=1}^n$ between $a$ and $b$ that the ...

**0**

votes

**0**answers

39 views

### What (analytical or numerical) method can I use to solve scalar optimal problem?

I got the following optimization problem in mind and I am looking for some (analytic or numerical) methods to solve it. Can anyone have any ideas? Here is problem
\begin{aligned}
& {\text{...

**0**

votes

**0**answers

100 views

### eigenvalues of matrix multiplication

Let $W_{a},W_{b}\in R^{n\times n}$ and $A \in R^{n \times n}$. What can we say about the sign of eigenvalues of the matrix $D$? Are they always positive or negative?
$D= [\begin{matrix}
W_{a} &...

**0**

votes

**1**answer

73 views

### Differences between the convex discrete maximization and minimization problems? [closed]

Would you tell me some main distinctions between the convex discrete minimization and maximization optimization problems?
In the case of the feasible are bounded then we only need to transform one ...

**1**

vote

**0**answers

81 views

### What is optimal distance between inverse of convolution operator?

I am looking for a measure to find the optimal distance measure between inverse of an convolution operator $A$ and say another convolution operator $B$. I want my measure to be sharp that mean when $B$...

**1**

vote

**0**answers

126 views

### Semi-convex problem and almost convex problem

I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...

**27**

votes

**0**answers

860 views

### Sofa in a snaky 3D corridor

What is the largest volume object that can pass though a
$1 \times 1 \times L$ "snaky" corridor, where $L$ is large
enough to be irrelvant, say $L > 6$.
...

**4**

votes

**1**answer

363 views

### Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...

**1**

vote

**0**answers

74 views

### About a particular definition of a Hessian of a function of tuples of matrices

Say I have a function $L : (W_1,..,W_{H+1}) \rightarrow \mathbb{R}$ i.e it takes a tuple of $n$ matrices of different dimensions and computes a number from them.
Then I see being defined a ...

**2**

votes

**0**answers

111 views

### Characterizing the optimimum over the space of probability measures

Consider the following optimization problem:
\begin{equation}
\max_{\mu \in \mathcal{M}} \int \log\left( \int e^{\alpha U(x,y)} d\mu(y) \right) d\nu(x)
\end{equation}
where $\mathcal{M}$ is the space ...

**1**

vote

**1**answer

211 views

### Limits of argmin ratios and sums

In my research on convergence properties of certain Bayesian methods I have encountered $\mathop{\mathrm{arg\,min}}$ limits of the forms
\begin{equation}
\lim_{n\to\infty} \mathop{\mathrm{arg\,min}}_{\...