Skip to main content

Questions tagged [global-optimization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
23 views

How to prove the convergence of Gechberg-Saxton algorithm?

I just have a problem that Gerchberg-Saxton algortihm is no worse than the previous iteration but not sure whether it is convergent.
Jianqing Li's user avatar
0 votes
1 answer
70 views

Relations between non-negativity of multivariate polynomials and SOS over gradient ideal

We know there is a necessary condition for the non-negativity of multivariate polynomials in the paper "Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational ...
Werther's user avatar
  • 59
1 vote
1 answer
83 views

optimization over moving domains

Let $A, B$ be Banach spaces, and for any $a\in A$, $B_a\in B$ is a measurable subset. Consider the following optimization problem: $$L(a)=\inf_{b\in B_a}\ell(b),$$ where $\ell(b)$ is a infinite-times ...
Jeff 's user avatar
  • 87
3 votes
1 answer
229 views

Min problem on integers

Let $n$ be any integer greater than $2^{10^6}$. Given any $s\le (\log_2 n)/1000$ integers $1=q_1\le q_2\le \cdots q_{s-1}\le q_s=n$. Prove that $$\min_\ell\left(\sum_{i=1}^\ell q_i\right)\left(\sum_{i=...
Nader Bshouty's user avatar
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}^...
lzzz's user avatar
  • 1
0 votes
0 answers
82 views

Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points

Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$ \begin{align} \max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
Boby's user avatar
  • 631
1 vote
1 answer
102 views

Optimization on non-convex set

Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem $$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$ where a minimum is ...
mlogm's user avatar
  • 11
0 votes
2 answers
374 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} {\...
Erik's user avatar
  • 21
1 vote
1 answer
63 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 ...
Naruto's user avatar
  • 63
1 vote
2 answers
119 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$. ...
user3750444's user avatar
2 votes
0 answers
97 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 ...
alhal's user avatar
  • 419
1 vote
0 answers
97 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}...
Goga's user avatar
  • 47
3 votes
1 answer
180 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 ...
Lieutenant Zipp's user avatar
18 votes
1 answer
658 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 ...
Gro-Tsen's user avatar
  • 30.8k
3 votes
2 answers
235 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 ...
lotuspaperboy's user avatar
2 votes
0 answers
43 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)...
dohmatob's user avatar
  • 6,824
1 vote
0 answers
46 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 ...
Samin's user avatar
  • 11
3 votes
1 answer
292 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 ...
MO B's user avatar
  • 617
2 votes
1 answer
68 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 ...
Koukyosyumei's user avatar
0 votes
0 answers
125 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 ...
user111's user avatar
  • 3,924
2 votes
1 answer
98 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 + ...
bobuhito's user avatar
  • 1,547
0 votes
0 answers
208 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 $\...
RLip2's user avatar
  • 1
5 votes
2 answers
216 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$...
Weather Report's user avatar
1 vote
1 answer
190 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 ...
user550103's user avatar
3 votes
0 answers
536 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 ...
Kunal Marwaha's user avatar
1 vote
1 answer
261 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 ...
user550103's user avatar
3 votes
0 answers
91 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 ...
Shaun Han's user avatar
  • 141
0 votes
1 answer
128 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 ...
UnclePetros's user avatar
0 votes
0 answers
92 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 ∈ ...
Shaun Han's user avatar
  • 141
2 votes
0 answers
47 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 ...
fibon's user avatar
  • 21
1 vote
0 answers
53 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 ...
Sebastian K.'s user avatar
3 votes
0 answers
269 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 ...
Bogdan's user avatar
  • 781
0 votes
1 answer
198 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 ...
Tal Galili's user avatar
1 vote
0 answers
155 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^...
hichem hb's user avatar
  • 377
4 votes
1 answer
90 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) ...
0xbadf00d's user avatar
  • 157
0 votes
1 answer
145 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 ...
Slava Rychkov's user avatar
5 votes
1 answer
228 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 ...
hichem hb's user avatar
  • 377
16 votes
1 answer
492 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/...
Alex Meiburg's user avatar
  • 1,203
0 votes
1 answer
301 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-...
ABIM's user avatar
  • 5,079
0 votes
1 answer
153 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} \...
Silvester's user avatar
0 votes
1 answer
439 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 ...
Hepdrey's user avatar
  • 90
2 votes
0 answers
47 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 ...
dohmatob's user avatar
  • 6,824
4 votes
0 answers
218 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 \...
dohmatob's user avatar
  • 6,824
0 votes
0 answers
36 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 $...
ABIM's user avatar
  • 5,079
0 votes
0 answers
234 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 ...
Athere's user avatar
  • 93
3 votes
1 answer
239 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 ...
ABIM's user avatar
  • 5,079
1 vote
1 answer
145 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 ...
dalex1's user avatar
  • 21
3 votes
0 answers
136 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 ...
Shijie Pan's user avatar
3 votes
1 answer
260 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 ...
Asaf Shachar's user avatar
  • 6,651
7 votes
1 answer
401 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 ...
Alexander Chervov's user avatar

1
2 3 4 5