# Questions tagged [global-optimization]

The global-optimization tag has no usage guidance.

199
questions

1
vote

0
answers

16
views

### Convergent algorithm for minimizing nonconvex smooth function

Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by
$$
\ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...

1
vote

0
answers

37
views

### Problems with known optimal solution [closed]

I am looking for some problems in which we know the value of optimal solution and should find just a vector of variables. For example in N-Queens problem we know the value of optimal solution (that is ...

2
votes

0
answers

117
views

### Trying to prove an inequality

I am working on a problem and for that purpose, I need to prove the following inequality. Let $t\in [0,1]$ and set
$$
z_0=1-4t(1-t)\sin^2(4x)\\
z_1=1-4z_0(1-z_0)\sin^2(3x)
$$
I need to show that for ...

2
votes

1
answer

58
views

### Optimize a function with not-full knowledge of gradient

I want to optimize the following function:
$$
argmin_{x} f(x) = g(x) + h(x)
$$
, where I can get $\nabla_xg(x)$, but cannot calculate $\nabla_xh(x)$.
The derivative-free method, such as the Hill ...

0
votes

0
answers

46
views

### Minimax problem : uniqueness of a solution

Let $n\geq2$. Is it true that the minimax problem:
$$
\min_{p\in\mathcal{P}}\max_{H\in\mathcal H}p^tH\bar{p},
$$
where
$\mathcal H\subset\mathcal{M}(n)$ is a strictly convex bounded subset of ...

0
votes

1
answer

58
views

### Maximizing a skew-symmetric 4D cross product

How do I find two orthonormal 4D vectors, $(x_0,x_1,x_2,x_3)$ and $(y_0,y_1,y_2,y_3)$, which maximize this function:
$-19x_1y_0 - 33x_2y_0 + 11x_3y_0 + 19x_0y_1 - 21x_2y_1 - 33x_3y_1 + 33x_0y_2 + ...

0
votes

0
answers

98
views

### Convergence of ODE solutions almost everywhere to a stable equilibrium point

Theorem: Suppose ${\bf g} :\mathbb{R}^n \mapsto \mathbb{R}^n$ is continuously differentiable, there exists a set $\mathcal{A} \subset \mathbb{R}^n$ such that $\bf g$ is uniformly Lipschitz on $\...

5
votes

2
answers

130
views

### Integrals can sometimes be computed through their saddle points. Are there examples of converse, when saddle points are found via integrals?

Under some reasonable assumptions integrals with large exponents can often be computed via saddle point approximations, e.g.
$$\int e^{-\lambda f(x)}\approx e^{-\lambda f(x_0)},\qquad \lambda\to\infty$...

1
vote

1
answer

174
views

### Proof of extended version of non-random "almost supermartingale"

In this question, a non-random version of "almost supermartingale" theorem is proved.
Here, I would like to extend/apply the non-random version to the slightly different situation. I wonder ...

2
votes

0
answers

154
views

### Proving an optimization problem from continuous input to binary is optimal

Suppose we have a function $f(x,y,z)$ where the inputs are uniform from 0 to 1. The output is either $+1$ or $-1$. And there is a partial symmetry $f(x,y,z) = f(z,y,x)$.
Tell me what the minimum of ...

1
vote

1
answer

162
views

### Can we invoke "almost supermartingale" Theorem for deterministic sequences?

Perhaps stupid question.
Question: Can "almost supermartingale" theorem be equally applicable to prove the convergence of some algorithms solving non-random optimization problems?
Attempt ...

3
votes

0
answers

74
views

### What is the name for this type of optimization problem?

As we all know, a classic optimization problem can be represented in the following way:
Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...

0
votes

1
answer

19
views

### Transformation of an unconstrained binary quadratic optimization problem into a constrained binary linear programming problem

I know that a constrained linear optimization problem can be transformed into an unconstrained binary quadratic optimization problem (UBQP). Does anyone know if the inverse result is solved in the ...

0
votes

0
answers

87
views

### Optimization problem where the objective function returns a function instead of a real number

As we all know, a classic optimization problem can be represented in the following way:
Given: a function $f: A \rightarrow \mathbb{R}$ from some set $A$ to the real numbers
Sought: an element $x_0 ∈ ...

2
votes

0
answers

44
views

### Why not use global optimization algorithms like PSO to solve decentralized control problems?

I do not see many works that use global optimization algorithms to solve decentralized control problems. Here the decentralized control problem means some entries of the feedback matrix are ...

1
vote

0
answers

48
views

### Nested, successive minimization solved by asympotic minimization?

I am curious about the general relation between nested, successive minimization (M1) and asymptotic minimization (M2) as defined in the following. What one wants is to implicitly minimize a sequence ...

2
votes

0
answers

114
views

### Continuum of Lagrange multipliers, duality gap, and minimax theorem

Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...

0
votes

1
answer

102
views

### How do you call a linear programming problem when the solution should be "constrained" to a norm?

(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...

1
vote

0
answers

78
views

### Optimization problem on trace of complex matrix product

Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...

4
votes

1
answer

74
views

### Do Pareto critical points of a multicriteria optimization problem form an attractor of the dynamical system induced by a descent algorithm?

Let $d\in\mathbb N$, $k\in\mathbb N$ and $f:\mathbb R^d\to\mathbb R^k$ be differentiable. Say that $v\in\mathbb R^d$ is a descent direction at $x\in\mathbb R^d$ if ${\rm D}f(x)v<0$ (component-wise) ...

0
votes

1
answer

124
views

### What to call a function that is negative on a set

Let $Y$ be a nonempty region in $\mathbb{R}^n$. I am designing an algorithm which given a point $x_0$ outside $Y$ in a finite number of steps lead to a point $x_n∈ Y$. The way I do it is that I have a ...

5
votes

1
answer

119
views

### Minimizing the largest eigenvalue of matrix product

Let $A\in\mathbb{C}^{m\times n}$, $B\in\mathbb{C}^{n\times k}$, $C\in\mathbb{C}^{k\times m}$ be given complex matrices. The objective of the optimization problem is
\begin{equation}
\mathop {\arg \min ...

8
votes

0
answers

101
views

### Can solutions to Thomson's problem have pentagons?

Thomson's problem asks for the minimum energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...

0
votes

1
answer

167
views

### Gradient-descent "type" Methods for non-convex and non-smooth functions

Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either:
lower semi-...

1
vote

1
answer

92
views

### Prove zero slope point is global maximum for constrained function with binomials. Without restriction, objective function is non-concave

How to prove the zero slope point is a global maximum in this non-concave program for a function with binomials?
I need to find the (global) maximum of the following constrained problem:
$$\max_{CAP} \...

0
votes

1
answer

118
views

### Properties of $l_q$-balls

For a given $q\in (0,1]$, define the $l_q$-ball as
$$\mathbb{B}_q(R_q)\mathrel{:=}\left\{\theta\in\mathbb{R}^d\,\middle\vert\,\sum_{j=1}^d \lvert\theta_j\rvert^q\leq R_q \right\}. $$
For a given ...

2
votes

0
answers

41
views

### A question about strong slopes (nonsmooth analysis)

Context. I'm reading the manuscrip "Nonlinear Error Bounds via a Change of Function" by Dominique Azé and Jean-Noël Corvellec (J Optim Theory Appl 2016), and I'm having a hard time ...

4
votes

0
answers

93
views

### Fréchet subdifferentiation on riemannian manifolds

Context. I'm looking for a "natural" definition of subdifferentials on riemannian manifolds.
Given a function $F:\mathbb R^m \to \mathbb R$, its Fréchet-subdifferential at a point $w \in \...

0
votes

0
answers

31
views

### Optimizing upper and lower bounds

Let $L_i:X\rightarrow [0,\infty)$ be continuous (objective) functions defined on a metric space $X$ and suppose that
$$
L_1(x)\leq L_2(x)\leq L_3(x)\qquad (\forall x \in X).
$$
Here, I imagine that $...

0
votes

0
answers

159
views

### Exponential map and optimization

Apologies in advance for being somewhat vague. I'm trying to get pointers to establish a connection between a common trick used in practice in optimization, and the exponential map in differential ...

3
votes

1
answer

127
views

### Measurable selection for argmin to distance

Let $Y$ be a Banach space and equip $Y$ with the weak topology. Now, let $X$ be a closed, bounded, and convex subset of $Y$ and suppose that the relative (weak) topology on $X$ is metrizable with ...

1
vote

1
answer

104
views

### K-means clustering benchmarks [closed]

What benchmarks do you use for evaluating clustering algorithms, especially for evaluating the performance of K-means vs. another algorithm?
I am especially interested in looking at the correctness of ...

3
votes

0
answers

116
views

### What is the convergence rate of the iterative optimization method?

For the following optimization problem:
$$
\mathrm{min}_{A,B} \|I-A^{T}XB\|^2 + \lambda\|B\|^2,
$$
where $A$ and $B$ are the two variables ($\|A\|^2 \le \rho$ where $\rho$ is a constant, e.g. 1), the ...

3
votes

1
answer

242
views

### When is the optimum of an optimization problem affine in the constraint parameter?

While working on a variational problem I have reached to the following question:
Let $f:(0,\infty) \to [0,\infty)$ be a $C^1$ function satisfying $f(1)=0$. Suppose that $f(x)$ is strictly increasing ...

7
votes

1
answer

331
views

### Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / "K-means") produce hexagonal clusters / hexagonal lattice?

"K-means" is the most simple and famous clustering algorithm, which has numerous applications.
For a given as an input number of clusters it segments set of points in R^n to that given number of ...

8
votes

2
answers

193
views

### Maximal distance of $2d+1$ points on a sphere

If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ as the vertices of the regular octahedron, then one can achieve a minimal spherical distance of $\pi/2$ between any two ...

1
vote

1
answer

156
views

### Is the minimum of a constraint optimization problem differentiable in the constraint parameter?

Let $h:\mathbb R^{>0}\to \mathbb R^{\ge 0}$ be a smooth function, satisfying $h(1)=0$, and suppose that $h(x)$ is strictly increasing on $[1,\infty)$, and strictly decreasing on $(0,1]$.
Let $s&...

2
votes

0
answers

201
views

### Pros and cons of using integer programming alone or combined integer and global optimization?

First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...

2
votes

1
answer

415
views

### When does $\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$ hold for a real function $f(x,y)$?

Let $f(x,y)$ be a real function of the variables $x,y$ (which can be real vectors). Under what conditions do we have the following equality:
$$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$$
For ...

1
vote

0
answers

73
views

### Joint optimization of the order 1 moment of a function and its Fourier transform

For the purpose of a quantum optics experiment, I come to the following problem :
Let $X,P \in \mathbf{R}^2$
\begin{equation}
J(\psi) = | \int_{-X}^{X} x |\psi^2(x) | dx + \int_{-P}^{P} p |Tf(\...

1
vote

0
answers

63
views

### Distance between value function of deterministic and stochastic control problems

Suppose that one wants to control a diffusion process
$$
dX_t^u = \mu(X_t^u,u)dt + \sigma dW_t; \qquad X_0^u=x
$$
in order to optimize a stochastic control problem with value function
$$
V_T(u)=\...

0
votes

0
answers

37
views

### Minimizing along independent directions, nonlinear programming

Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...

0
votes

0
answers

65
views

### Numerically solve a specific saddle-point problem

Let $(\Omega,\mathcal E,\mu)$ be a probability space, $k\in\mathbb N$, $$W:=\left\{w:E\to[0,\infty)^k:\sum_{i=1}^kw_i=1\;\mu\text{-almost surely}\right\},$$ $G$ be a finite nonempty set and $a^{(g)}:E\...

2
votes

0
answers

129
views

### Can we conclude $\sup_g\int f_1g\le\sup_g\int f_2g$ from $\int f_1\le\int f_2$ in this situation?

Disclaimer: Please bear with me, the question isn't as complicated as it looks like, but I wasn't able to find any simplification for which no counterexample comes to my find.
Let $(E,\mathcal E,\...

0
votes

0
answers

67
views

### How to maximum L1 norm problem?

I have met a problem these days.
\begin{equation}
\underset{\omega}{\max} \quad \Vert \text{diag}(\mathbf{h}^H)\mathbf{G}^H\mathbf{\omega}\Vert_1 \\
s.t.\quad\mathbf{\omega}^H\mathbf{G}\mathbf{G}^H\...

0
votes

0
answers

74
views

### A question about multivariable calculus and optimization

Consider the function $f(x) :\mathbb{R}\rightarrow \mathbb{R}$, such that $f(x)\geqslant 0\; \forall x\in \mathbb{R}$, and has a set of extremum points at $x_{j}$.
Consider the integral :
$$\int_{\bar{...

0
votes

0
answers

40
views

### Is there a multiplier rule for this minimization problem?

Let $(E,\mathcal E)$ be a measurable space, $W\subseteq\left\{w:E\to\mathbb R\mid w\text{ is }\mathcal E\text{-measurable}\right\}$ be a Banach space, $k\in\mathbb N$ and $f:W^k\to[0,\infty)$. I'm ...

1
vote

0
answers

70
views

### Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related?

I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy:
$$
\inf_{x\in\mathbb{R}^n}\quad p(x),
$$
where $p$ is a polynomial of even degree ...

1
vote

1
answer

136
views

### Fritz-John conditions: Equality-constrained case as special case of inequality constraints

In Chapter 4 of Nonlinear Programming: Theory and Algorithms by Bazarra, Sherali, and Shetty, the following claim is made after Theorem 4.3.2 (Fritz-John necessary conditions):
"Note also that these ...

0
votes

0
answers

74
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\...