Questions tagged [global-optimization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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)...
user avatar
  • 5,580
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 ...
user avatar
  • 11
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 ...
user avatar
  • 477
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 ...
user avatar
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 ...
user avatar
  • 3,408
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 + ...
user avatar
  • 1,425
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 $\...
user avatar
  • 1
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$...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 141
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 ...
user avatar
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 ∈ ...
user avatar
  • 141
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 ...
user avatar
  • 21
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 ...
user avatar
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 ...
user avatar
  • 701
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 ...
user avatar
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^...
user avatar
  • 327
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) ...
user avatar
  • 383
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 ...
user avatar
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 ...
user avatar
  • 327
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/...
user avatar
  • 1,033
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-...
user avatar
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} \...
user avatar
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 ...
user avatar
  • 60
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 ...
user avatar
  • 5,580
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 \...
user avatar
  • 5,580
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 $...
user avatar
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 ...
user avatar
  • 73
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 ...
user avatar
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 ...
user avatar
  • 21
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 ...
user avatar
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 ...
user avatar
  • 6,286
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 ...
user avatar
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 ...
user avatar
  • 9,471
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&...
user avatar
  • 6,286
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 ...
user avatar
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 ...
user avatar
  • 825
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(\...
user avatar
  • 11
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)=\...
user avatar
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 ...
user avatar
  • 163
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\...
user avatar
  • 383
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,\...
user avatar
  • 383
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\...
user avatar
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{...
user avatar
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 ...
user avatar
  • 383
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 ...
user avatar
  • 547
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 ...
user avatar
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\...
user avatar
  • 383