Questions tagged [global-optimization]
The global-optimization tag has no usage guidance.
74
questions with no upvoted or accepted answers
7
votes
0
answers
2k
views
Optimization over space of probability measures
Consider an optimization problem as follows:
$$
\min\mathbb E_w[f_0(w)] \mathrm{\,\,\,\,\,\ s.t.\,\,\,\,} E_w[f_i(w)]\leq 0 ,\,\,\, i=1,\dots, k
$$
where the maximum is taken over $\mathscr M$, ...
- 722
7
votes
0
answers
342
views
An $L^{\infty}$ version of principal component analysis?
I have a $k$ by $n$ matrix $A$, with $k \ll n$. In case it helps, the $k$ rows are orthonormal.
I'm interested in finding a $k$ by $k$ orthogonal matrix $M$ so as to maximize the $L^{\infty}$ norms ...
- 193
7
votes
0
answers
882
views
Maximizing the matrix norm
Hi all,
I wish to find a 3x3 rotation (orthogonal) matrix $\mathbf{R}$ such that it maximizes the following matrix norm:
$||\mathbf{A} \mathbf{D}_r \mathbf{D}_b ||_2$
where $\mathbf{A}$ is a known $...
- 113
5
votes
0
answers
167
views
A specific case of the $p$-center problem
Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
- 125
4
votes
0
answers
207
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,726
4
votes
0
answers
400
views
maximize non-convex composite function
I want to maximize a composite function over a convex set
\begin{equation}
\begin{aligned}
& \underset{\mathbf{p}}{\text{maximize}}
& & f(\mathbf{p})-g(\mathbf{p})\\
& \text{subject to}...
- 61
4
votes
0
answers
195
views
Basin of Attraction
I have a function $F$ which is defined as follows:
$$
F(x) = \sum_{i=1}^N f(z_i^T x)
$$
where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \...
- 291
3
votes
0
answers
503
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 ...
3
votes
0
answers
87
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
3
votes
0
answers
257
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 ...
- 781
3
votes
0
answers
135
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
3
answers
455
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 ...
- 2,146
3
votes
0
answers
234
views
Constrained optimization with a Proportional-Integral-Derivative (PID) controller
My engineering colleagues have devised an interesting approach to equality-constrained optimization. I.e. they wish to solve the problem $\min_x f(x)$ subject to the constraint $g(x) = 0$ where $f, g ...
- 163
3
votes
0
answers
697
views
Minimum weight bipartite graph clique covering
I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be a bipartite graph, and $\forall u\in L\cup R$, let $c_u$ be a cost associated to ...
- 151
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
- 131
2
votes
0
answers
90
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 ...
- 419
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)...
- 6,726
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 ...
- 21
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 ...
- 6,726
2
votes
0
answers
378
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
0
answers
131
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,\...
- 161
2
votes
0
answers
224
views
Characterizing the optimimum over the space of probability measures
Consider the following optimization problem:
\begin{equation}
\max_{\mu \in \mathcal{M}} \int \log\left( \int e^{\alpha U(x,y)} d\mu(y) \right) d\nu(x)
\end{equation}
where $\mathcal{M}$ is the space ...
- 21
2
votes
0
answers
352
views
Likelihood convexification
I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form:
$$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log \...
2
votes
0
answers
182
views
numerical solver for stochastic optimal control problems
can any one recommend numerical solver (c/c++ library preferred) for stochastic optimal control problems? For deterministic optimal control I found something like that: http://abs-5.me.washington.edu/...
- 21
2
votes
0
answers
153
views
Maximizing an integral over a convex region
Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
- 21
2
votes
0
answers
169
views
modification of singlestart in global optimization
When minimizing a nonconvex function $f : \Omega \rightarrow \mathbb{R}$ that may have multiple minima, there are some very simple strategies to improve the odds of finding the global minimum point. ...
- 4,435
1
vote
0
answers
94
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
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 ...
- 390
1
vote
0
answers
151
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^...
- 377
1
vote
0
answers
75
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(\...
- 11
1
vote
0
answers
71
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)=\...
- 4,969
1
vote
0
answers
92
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 ...
- 607
1
vote
0
answers
102
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)^...
- 379
1
vote
0
answers
66
views
On number of solutions by simplex and number of solutions in total in a linear optimization problem?
This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...
- 13.7k
1
vote
0
answers
78
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 383
1
vote
0
answers
39
views
Linear cost traveling salesman heuristic
I have a sequence of points $y_1,\ldots,y_n\in \mathbb{R}^3$ and want to approximately minimise
$$
\sum_{i=1}^{n-1}|y_{\pi(i)}-y_{\pi(i+1)}|
$$
by choosing a permutation $\pi$ of $\{1,\ldots,n\}$.
I ...
- 435
1
vote
0
answers
186
views
linear relaxation of an optimization problem
I'm reading an article lately, and there is one point which confuses me.
So, we have the following constrained binary quadratic problem.
min $x^{T}Qx$
with the constraints that $Ax\leq b$ and $x\in ...
- 11
1
vote
0
answers
79
views
Nonconvex Optimization of inner product objective
Does there exist any result on the following minimization,
$$\min_{x\in P} \langle x, F(x)\rangle\equiv \sum_i x_i F_i(x), $$ where $P$ is a convex polytope and $F_i(\cdot)$s are convex functions of $...
- 133
1
vote
0
answers
83
views
What is optimal distance between inverse of convolution operator?
I am looking for a measure to find the optimal distance measure between inverse of an convolution operator $A$ and say another convolution operator $B$. I want my measure to be sharp that mean when $B$...
1
vote
0
answers
226
views
Semi-convex problem and almost convex problem
I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...
- 355
1
vote
0
answers
92
views
About a particular definition of a Hessian of a function of tuples of matrices
Say I have a function $L : (W_1,..,W_{H+1}) \rightarrow \mathbb{R}$ i.e it takes a tuple of $n$ matrices of different dimensions and computes a number from them.
Then I see being defined a ...
- 2,146
1
vote
0
answers
90
views
Separable Least squares - is there a notion of conjugate directions?
I have a general question.
Suppose I have the following to optimize
$$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$
where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
- 61
1
vote
0
answers
36
views
Deterministic global solution to find the Optimal-knot placements for continuous piecewise linear functions to fit nonlinear data
I have been searching lately for a deterministic global technique to linearize a nonlinear function with continuous piecewise linear regions.
I've a univariate nonlinear function y=f(x). where f(x) ...
- 11
1
vote
0
answers
88
views
solution of an infinite horizon optimization problem
Give the following formulation:
$\min_{\{x_s(t):\forall s,t\}} \sum_{s \in \mathcal{S}} \mathbf{1}\left(\lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=1}^T \frac{y_s(t)}{x_s(t)}\leq 1\right)$
$s.t. ...
1
vote
0
answers
100
views
Changing a nonlinear equality constraint into some conic inequality plus rank constraint
If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
- 33
1
vote
0
answers
214
views
range of the difference-of-two-qubit-$4 \times 4$-density-matrix-determinants
The determinant of a two-qubit $4 \times 4$ density matrix--that is, a Hermitian, nonnegative definite matrix with unit trace--lies between $0$ and $(\frac{1}{2})^8$. (A "pure state" has determinant ...
- 723
1
vote
0
answers
102
views
Trying to get an idea of the maths I could use for this optimization problem
Firstly, apologies if some of the notation or terminology is odd, or if I am defining functions that have standard notation associated with them already - I am not familiar with the concepts in this ...
- 11
1
vote
0
answers
266
views
On the convergence of a special fixed point iteration
The problem is actually a quadratically constrained quadratic program. And the formulation is:
$max: \frac{1}{2}x^TQx + d^Tx$
$s.t. x\in R^{n,+} ,\sum_{i\in I_p}x_i^2=1, p=1..k$
where $d\in R^{n,+}$,...
- 11
0
votes
1
answer
41
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 ...
- 59
0
votes
0
answers
54
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}^...
- 1