Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
0answers
23 views

How can I solve a constrained optimization problem with a random number of decision variables?

Here is my problem. Let $A_t$ be a random variable with Poisson-Binomial distribution with set of success-probabilities $\{q_1^{(t)},\ldots,\,q_n^{(t)}\}$, with $t\in\{1,\,2,\,3,\ldots\}$, $n\in\...
1
vote
0answers
34 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 ...
0
votes
1answer
88 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
152 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
103 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: ...
0
votes
0answers
26 views

Are Matérn class kernels universal kernels or not?

This is a question that I can't find the solution. I don't know it is a open question or it is a well-known result that can be attained from several lemmas. Here are the definition of Matérn class ...
15
votes
3answers
777 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(...
0
votes
0answers
31 views

Nonlinear optimization problem better efficiency

I have a highly nonlinear optimization problem that I describre in the following lines: $A$ is a $N \times N$ known matrix, $\vec{z},\vec{M},\vec{D}$ are known vectors of length $N$ and $R,T$ are ...
0
votes
2answers
87 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 ...
0
votes
1answer
46 views

Linearly constrained saddle-point optimization

Let $f(x,y)$ be a smooth (twice differentiable) saddle function (convex in $x$ and concave in $y$), where $f \colon X \times Y \rightarrow \mathbb{R}$, and $X \subset \mathbb R^n$, $Y \subset \mathbb ...
1
vote
0answers
47 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\...
0
votes
0answers
45 views

Optimization of generalized Fisher information over space of probability measures

Assume we already have $p(\theta)$ apriori desnsity function about unknown parameter $\theta$, and we consider an optimization problem as follows: \begin{equation} \max_{P \in \mathcal{M}} \int_{\...
3
votes
1answer
162 views

Does there exist energy-minimizing immersions?

This is a cross-post. Let $M,N$ be $d$-dimensional oriented Riemannian manifolds, possibly with boundary, $M$ compact. Let $E_d:C^{\infty}(M,N) \to \mathbb{R}$ be the $d$-energy, i.e. $$ E_d(f)=\...
9
votes
2answers
208 views

A (reverse)-Minkowski type inequality for symmetric sums

Let $(u_1, u_2, u_3, u_4)$ and $(v_1, v_2, v_3, v_4)$ be vectors in $\mathbb R_+^4$. Is the following inequality true? \begin{align*} \left(\sum_{{[4] \choose 3}} \sqrt{u_i u_j u_k}\right)^{2/3} + \...
0
votes
0answers
20 views

Quality indicator for two-objective Pareto fronts

What quality indicator can be used for two-objective cases when computing a Pareto front? One that I identified is a hypervolume indicator, but most of the articles and examples show for d > 2 ...
3
votes
1answer
57 views

Maximizing the $\alpha$-moment of a distributution

Given $\alpha$ and constant $\mu$, $$\begin{array}{ll} \text{maximize} & \displaystyle\int_0^\infty p(x)x^\alpha \,\mathrm d x\\ \text{subject to} & \displaystyle\int_0^\infty p(x)\,\mathrm d ...
0
votes
1answer
89 views

QUBO formulation of a discrete-variable Genetic Algorithm optimization problem

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic real-valued function $f$ depending on a set of parameters $ \theta\...
1
vote
0answers
47 views

Where does the expected value in the restatement of the pseudoregret come from?

Given stochastic payoff functions $X_{1}(t) \dots X_{K}(t)$, each having a different probability distribution on $[0,1]$, denote the expected value of $X_i(t)$ by $\mu_i$, and define $\mu^* = \max_{i \...
1
vote
0answers
40 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 ...
6
votes
3answers
220 views

Solve $\inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] $

I want to solve the following optimization problem \begin{align} \inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] \end{align} where $X^\prime$ is an independent copy ...
0
votes
0answers
47 views

Dense set of functions on manifold with no local optima

Given a smooth manifold $M$ and another $S$, consider a smooth function $\psi: S \times M \rightarrow \mathbb{R}$, and use this to define $\psi_s:M\rightarrow \mathbb{R}$ by $\phi_s(p):= \psi(s,p)$. ...
0
votes
1answer
77 views

Maximizing sum of a product of logs

I came across the following note in a paper I'm reading and don't understand how it was derived. $\max_{\alpha_\ell}\sum_\ell^L\beta_\ell\log\alpha_\ell$ such that $\sum_\ell^L\alpha_\ell=1$ and $\...
1
vote
1answer
888 views

minimum of convex function in different variables [closed]

Let $g_1,g_2$ be convex functions defined over $[0,1]$, and let $f:[0,1]^2 \rightarrow\mathbb R$ such that $$f(x,y)=\min(g_1(x),g_2(y)). $$ I wish to know whether $f$ is convex. I do suspect that $f$ ...
1
vote
0answers
33 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 ...
1
vote
1answer
105 views

Name for functions with local=global minimum

I have a simple question. We know that functions where every stationary point is a global minimum are invex functions. Is there a name for functions where every local minimum is a global minimum? And ...
1
vote
0answers
98 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 ...
-2
votes
1answer
28 views

global or local solver for constrained pseudo concave problem [closed]

Is there a good Matlab solver that can help with the problem: $\max_{\boldsymbol{s}\in\mathbb{R}^{n}}\frac{\sqrt{\boldsymbol{a}^{T}\boldsymbol{s}+\epsilon^{2}}}{\boldsymbol{b}^{T}\boldsymbol{s}+\...
2
votes
1answer
117 views

equality between the ratio trace and the determinant ratio

I have encountered the following equality $\arg\max_{\text{tr}\left(\boldsymbol{S}^{H}\boldsymbol{S}\right)=1}\text{tr}\left(\boldsymbol{S}^{H}\boldsymbol{A}\boldsymbol{S}\left(\boldsymbol{S}^{H}\...
4
votes
3answers
131 views

Maximizing a pseudoconcave function in a box

I am trying to solve the problem: $\max_{\boldsymbol{s}\in\mathbb{R}^{n}} \frac{\sqrt{\boldsymbol{a}^{T}\boldsymbol{s}+\alpha}}{\boldsymbol{b}^{T}\boldsymbol{s}+\beta}\\ \text{s.t} \;\;0\leq s_{i}\...
3
votes
0answers
182 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 ...
1
vote
0answers
57 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 $...
0
votes
2answers
59 views

Reference request: dependence on linear constraints

Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem: $$P(...
1
vote
1answer
111 views

Optimization problem restricted to a smaller field?

Let $c:\mathbb R^2\to\mathbb R$ be a Lipschitz and bounded function (which can be supposed as "nice" as possible). Let $\mu$ and $\nu$ be two probability measures on $\mathbb R$ with finite first ...
4
votes
1answer
1k views

Can you give me good examples of non-convex functions that are problematic for optimization?

I want to test my extended gradient descent algorithm, whose aim is to handle non-convex problems better. Can you give me some examples of non-convex functions that are hard to minimize via gradient ...
4
votes
1answer
238 views

Maximum entropy distribution with constrained quantiles

Suppose we have a continuous probability distribution with density function $f$ whose support is $[a,b]$ and we know that for some finite set of values $\{ v_i \}_{i=1}^n$ between $a$ and $b$ that the ...
0
votes
0answers
39 views

What (analytical or numerical) method can I use to solve scalar optimal problem?

I got the following optimization problem in mind and I am looking for some (analytic or numerical) methods to solve it. Can anyone have any ideas? Here is problem \begin{aligned} & {\text{...
0
votes
0answers
99 views

eigenvalues of matrix multiplication

Let $W_{a},W_{b}\in R^{n\times n}$ and $A \in R^{n \times n}$. What can we say about the sign of eigenvalues of the matrix $D$? Are they always positive or negative? $D= [\begin{matrix} W_{a} &...
0
votes
1answer
69 views

Differences between the convex discrete maximization and minimization problems? [closed]

Would you tell me some main distinctions between the convex discrete minimization and maximization optimization problems? In the case of the feasible are bounded then we only need to transform one ...
1
vote
0answers
80 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
0answers
121 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 ...
27
votes
0answers
827 views

Sofa in a snaky 3D corridor

What is the largest volume object that can pass though a $1 \times 1 \times L$ "snaky" corridor, where $L$ is large enough to be irrelvant, say $L > 6$.           ...
4
votes
1answer
339 views

Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$. We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree ...
1
vote
0answers
72 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
votes
0answers
109 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 ...
1
vote
1answer
208 views

Limits of argmin ratios and sums

In my research on convergence properties of certain Bayesian methods I have encountered $\mathop{\mathrm{arg\,min}}$ limits of the forms \begin{equation} \lim_{n\to\infty} \mathop{\mathrm{arg\,min}}_{\...
0
votes
0answers
118 views

Limit of argmin of sum

Suppose that I know $f_n\rightarrow f$ and $g_n\rightarrow g$ are both continuous maps from a Complete Riemmanian Manifold $X$ to $\mathbb{R}$ which converge pointwise almost everywhere. Then is it ...
1
vote
0answers
79 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 ...
5
votes
1answer
324 views

Optimization of a function of a positive definite matrix and its inverse

This question is a little ill-posed, but I've been playing with some equations and am just wondering if this resembles any known problems that have been solved. Suppose I have two real, positive ...
-1
votes
2answers
275 views

Is finding a local minimizer of a NP-hard optimization problem is still NP-hard [closed]

I was wondering if for a NP-hard optimization problem, I only want to find its local minimizer, is it still NP-hard or NP-hard is only true when trying to find a global minimizer?
1
vote
0answers
29 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) ...