Questions tagged [global-optimization]
The global-optimization tag has no usage guidance.
210
questions
0
votes
0
answers
21
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
- 21
1
vote
1
answer
46
views
Estimate of minimum of the Poisson integrals corresponding to a convergent Hausdorff sequence of smooth bounded domains from below
Let $\{\Omega_{j}\}_{j\in\mathbb{N}}$ be a sequence of smooth bounded domains in $\mathbb{C}^{n}$ such that $\Omega_{j}$ converges to a smooth bounded domain $\Omega$ in the sense that the defining ...
- 63
1
vote
2
answers
101
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
- 175
0
votes
0
answers
39
views
Ride sharing problem in GAMS
In this problem, we have a weighted and directed graph, where each node represents a certain place to determine the origin of the driver and the origin and destination of the passengers. In the real ...
0
votes
0
answers
101
views
Farkas' lemma for variables in the natural numbers
A lot of questions regarding the Farkas' lemma has already been done. Most of them seems to be related to consequences of the Farkas' lemma, for example, see [1, 2, 3]. This means that the problem of ...
- 203
2
votes
0
answers
65
views
Local behavior around critical points in high dimensions
I have asked this question on math.stackexchange.com but even though I gave a bounty, I was not able to receive any answers at all, so I'm posting it here again, hoping that the question is not too ...
- 387
1
vote
0
answers
93
views
How to solve the following optimization problem?
Let $G=(V,E)$ be a connected network with $|V|=n$. Consider the following optimization problem
I'm trying to know under which conditions the following minimization problem has solution :
$${\sum _{i=1}...
- 47
0
votes
0
answers
30
views
Matrix optimization to find ideal embedding
Basically, I am trying to find the embeddings so I can approximate $K \approx M(\vec{\phi})$. The embeddings are for each one of my samples $\vec{\phi}(x_i) \in \mathbb{R}^D$ so I thought it should ...
3
votes
1
answer
124
views
Minimize total area bounded by $N$ lines in general position
Suppose we have $N$ lines in general position (any two lines, but no three lines, meet at a point) ($N\geq 3$). Let the smallest bounded region have area $1$. Determine the minimum (or possibly ...
- 141
18
votes
1
answer
520
views
Known configurations maximizing the volume of the convex hull of n points on the unit sphere
For $n\geq 4$, let $V_n$ be the maximum volume of the convex hull of $n$ points on the unit sphere (in $\mathbb{R}^3$, although information on higher dimensions is welcome as well). I'm sure the ...
- 26.5k
3
votes
2
answers
134
views
Optimal Kelly criterion for process with N discrete outcomes
I am trying to come up with a generalisation of the Kelly formula for optimal fractional betting but and have hit a roadblock. The Kelly criterion is usually explained via a game that ends in 1 of 2 ...
2
votes
0
answers
35
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)...
- 6,338
1
vote
0
answers
40
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 ...
- 11
3
votes
1
answer
286
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 ...
- 487
2
votes
1
answer
64
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 ...
- 53
0
votes
0
answers
73
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 ...
- 3,596
2
votes
1
answer
88
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 + ...
- 1,527
0
votes
0
answers
143
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 $\...
- 1
5
votes
2
answers
147
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$...
- 319
1
vote
1
answer
182
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 ...
- 45
3
votes
0
answers
318
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
195
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 ...
- 45
3
votes
0
answers
81
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 ...
- 141
0
votes
1
answer
36
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 ...
- 61
0
votes
0
answers
91
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 ∈ ...
- 141
2
votes
0
answers
45
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 ...
- 21
1
vote
0
answers
49
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 ...
- 380
3
votes
0
answers
182
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 ...
- 751
0
votes
1
answer
143
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 ...
- 143
1
vote
0
answers
129
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^...
- 367
4
votes
1
answer
87
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) ...
- 131
0
votes
1
answer
137
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 ...
- 669
5
votes
1
answer
164
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 ...
- 367
15
votes
1
answer
442
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/...
- 1,123
0
votes
1
answer
245
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-...
- 4,928
0
votes
1
answer
126
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} \...
- 49
0
votes
1
answer
248
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 ...
- 70
2
votes
0
answers
46
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 ...
- 6,338
4
votes
0
answers
151
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 \...
- 6,338
0
votes
0
answers
33
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 $...
- 4,928
0
votes
0
answers
196
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 ...
- 93
3
votes
1
answer
176
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 ...
- 4,928
1
vote
1
answer
129
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 ...
- 21
3
votes
0
answers
128
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 ...
- 31
3
votes
1
answer
249
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 ...
- 6,499
7
votes
1
answer
365
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 ...
- 22.6k
9
votes
2
answers
201
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 ...
- 11.4k
1
vote
1
answer
166
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&...
- 6,499
2
votes
0
answers
300
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
532
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 ...
- 844