Questions tagged [global-optimization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
25 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
1answer
65 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
0answers
25 views

Norm of vector components optimization of linear matrix combination

Given complex matrices $A_1, A_2, \dots, A_k\in\mathbb{C}^{m \times n}$, $B \in\mathbb{R}^{m \times n}$, the objective is to find a vector $x \in \mathbb{C}^k$ such that: $\max {||x_i||}$ , $i\in 1,2.....
0
votes
1answer
114 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 ...
4
votes
0answers
72 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
0answers
85 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
1answer
70 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
1answer
56 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
1answer
78 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 ...
0
votes
0answers
44 views

How do i get the $\Delta_a$ value that would maximize $(\Delta_d-\Delta_a)$

so this problem is derived from a real world problem i have so i'm unsure if it can be solved through maths or not. I'm currently "finding" the solution through tons of computer iteration ...
2
votes
0answers
38 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
0answers
64 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
0answers
18 views

Dealing with degeneracy in nonlinear programming by “small” perturbations of constraints

CONTEXT: Suppose you have the nonlinear program $$ \begin{aligned} &\min f(x)\\ \text{subject to: }\quad & h_1(x) = 0 \\ &\quad\quad\vdots\\ &h_m(x) = 0 \end{aligned} $$ where $x\in\...
0
votes
0answers
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
0answers
124 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
1answer
89 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
1answer
86 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
0answers
112 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
1answer
225 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
1answer
290 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
2answers
185 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
1answer
148 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&...
1
vote
0answers
62 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
1answer
288 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
0answers
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
0answers
61 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
0answers
36 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
0answers
59 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
0answers
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
0answers
62 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
0answers
71 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
0answers
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
0answers
65 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
1answer
106 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
0answers
70 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\...
1
vote
1answer
177 views

Maximize a Lebesgue integral subject to an equality constraint

I want to maximize $$\Phi_g(w):=\sum_{i\in I}\sum_{j\in I}\int\lambda({\rm d}x)\int\lambda({\rm d}y)\left(w_i(x)p(x)q_j(y)\wedge w_j(y)p(y)q_i(x)\right)\sigma_{ij}(x,y)|g(x)-g(y)|^2$$ over all choices ...
6
votes
4answers
2k views

Prove that this expression is greater than 1/2

Let $0<x < y < 1$ be given. Prove $$4x^{2}+4y^{2}-4xy-4y+1 + \frac{4}{\pi^2}\Big[ \sin^{2}(\pi x)+ \sin^{2}(\pi y) + \sin^{2}[\pi(y-x)] \Big] \geq \frac{1}{2}$$ I have been working on this ...
11
votes
1answer
600 views

Illustrating that universal optimality is stronger than sphere packing

I'm a physicist interested in the conformal bootstrap, one version of which was recently shown to have many similarities to the problem of sphere packing. Sphere packing in $\mathbf{R}^d$ has been ...
5
votes
1answer
175 views

An effective way for the minimization of $\left\|ABA^{-1}-C\right\|$

Supposing I have complex square matrices $B_i$ and $C_i$ ($i = 1,\dots,N$) of dimension $4 \times 4$. Is there an effective algorithm for solving the following problem? $$\begin{align} A=&\...
5
votes
1answer
82 views

On a maximum of a determinant with dependent variables

Let $x_1,\ldots,x_n\in [-1,1]^n$ and define the function $$f(x_1,\ldots,x_n):= \prod_{i=1}^n\prod_{j=i}^n\left(1-\prod_{k=i}^j x_k\right).$$ This is a positive function, and actually coincides with ...
1
vote
1answer
278 views

Minimizing sum of ratio of linear functions (Sum of Linear Ratios Problem)

Given constants $c_i \in \mathbb{R}$ and $d_i \in \mathbb{R}$ and variables $x_i \in \mathbb{R}$, where $c_i > 0, d_i > 0, x_i > 0$ can we easily solve the following optimization problem: $$...
1
vote
0answers
89 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)^...
1
vote
1answer
118 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$ ...
3
votes
2answers
220 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 ...
1
vote
0answers
129 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 ...
1
vote
1answer
596 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
2answers
387 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
2answers
324 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: ...
15
votes
3answers
957 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(...
1
vote
2answers
2k 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 ...