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

Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.

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
65 views

Matrix completion in $2\times2$ case by nuclear norm minimization to guarantee rank $1$?

Does fixing diagonal entries and minimizing nuclear norm under weighted sum of entries conditions produce a rank $1$ matrix? I think the answer for this is no. At least could it be true in $2\times2$ ...
0
votes
0answers
23 views

Closed-form solution of quadratically constrained quadratic program in 2 unknowns

I am interested in a closed-form solution of the following problem in two unknowns: \begin{equation} (\bar x, \bar y) = \text{arg}\min_{(x, y) \in \mathbb R^2} \left\{ (x, y)^\top \begin{bmatrix} a ...
1
vote
1answer
59 views

Takahashi minimization theorem for lower pseudo-continuous functions on complete metric spaces

Takahashi minimization theorem says : Let $(X,d)$ is a complete metric space, $f:X\to \mathbb{R}\cup\{+\infty\}$ is a proper(not constantly +$\infty$) lower semi continuous function, which is bounded ...
1
vote
1answer
72 views

Closed Form Solution for Optimization Problem over the Space of Rigid Transforms

Is there a closed form solution to this constrained optimization problem: \begin{equation} \min_{R \in SO(3),\, \mathbf t \in \mathbb R^3} = \sum_{i = 1}^N \| M_i(R \mathbf p_i + \mathbf t) \|^2, \...
2
votes
1answer
41 views

Are the intersection of proximinal sets in a Hilbert Space proximinal?

Let $X$ be a real Hilbert Space and $C \subseteq X$. Let $d_C$ be the infimal distance function to $C$ and $P_C(x) = C \cap S[x; d_C(x)]$ be the metric projection. We say $C$ is proximinal if $P_C(x) \...
6
votes
1answer
137 views

Adding constraints as penalty with $\| \cdot \|_0$ norm

In the paper Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries (page 2), the authors rewrite the minimization problem \begin{align} \min_{\alpha \in \mathbb R^k} \| \...
6
votes
0answers
80 views

another extremal property of regular polygons

$\newcommand{\R}{\mathbb{R}}\newcommand{\D}[1]{\Delta_{#1}}\newcommand{\set}[1]{\{#1\}}\newcommand{\abs}[1]{\lvert#1\rvert}\newcommand{\E}{\mathbb{1}}$ In 1984 S.D.Berman, a Soviet mathematician, ...
0
votes
0answers
28 views

how to get this deterministic equivalent formulation of its original probabilistic counterpart by knapsack constraint?

I'm reading this article with title "a probabilistic model applied to emergency service vehicle location". https://www.sciencedirect.com/science/article/pii/S0377221708002336 This is a very good ...
3
votes
1answer
143 views

it's convex sequence inequality

A sequence $a_0,a_1,\dots,a_n$ of real numbers is called concave if $a_{0}=0$, and for each $0<i<n$, we have $a_i\geq\dfrac{a_{i-1}+a_{i+1}}{2}$. Find the largest $c(n)$ such that for every ...
0
votes
0answers
34 views

a game-theoretical / optimization problem

Does anyone know how to solve (or a good reference) for the following problem? Let n and m be two positive integers. Let z \mapsto G^{i,j}(z) be a real polynomial, for each i=1,...,n and j=1,...,m. ...
2
votes
1answer
91 views

Convergence of a stochastic sequence?

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...
0
votes
1answer
48 views

Quasiconvexity property of quasinorms

Schatten $p$ norm is convex when $p\geq1$ holds and if $p\in(0,1)$ it is quasinorm. If $p\in(0,1)$ then is Schatten $p$ norm quasi convex? I am interested in definition of quasi convexity here https:...
2
votes
0answers
49 views

How to solve such integer program problem?

Consider a $3$-tuple $(a,b,s)$ with $a,b\in\mathbb{Z}_+,s\in\mathbb{Q}_+$. Denote $ab-s$ by $\Delta$. Let $A$ be a positive number. What are the values of $A$ such that for any $(a,b,s)$ with $\Delta\...
0
votes
0answers
40 views

Sensitivity of Lagrangian solution: implicit constraint

just a question about a literature reference. I am writing a paper for engineers. Usually for the Lagrange multiplier problem ∇f(x)+λ∇g(x)=0 the sensitivity result that the multiplier λ gives the ...
0
votes
0answers
14 views

Efficient numerical optimization of an “almost separable” function

I have come across an optimization problem with the following objective function: $$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
0
votes
0answers
49 views

Using mollifiers (or some other idea) to solve constrained minimax problem

Sorry in advance if this sounds like a more SE question. Consider a continuously parametrized family of $L$-Lipschitz continuous $f_\theta: X \rightarrow \mathbb R_+$ on a metric space $X=(X,d)$. Let ...
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 ...
3
votes
0answers
50 views

Dependency of the Wasserstein distance on the parameter: a differential perspective

Let $\mu(dx)=\sum_{i=1}^np_i\delta_{x_i}(dx)$ and $\nu(dy)=\rho(y)dy$ be two probability measures on $\mathbb R^d$. Consider the $2-$Wasserstein distance below: $$W_2(\mu,\nu)^2 \quad := \quad \inf_{\...
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\...
8
votes
1answer
367 views

Higher dimensional scutoids?

The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...
0
votes
1answer
73 views

Subset optimization with composite aggregate functions

I have a finite set $P = \{1, 5, 3, 6, 4, ..., p_n\}$ of size $N$ and average $A$. I want to find the most efficient way to maximize the following function: $$ f(x, y) = \frac{1}{(1+e^{-6(x-2)})(1+e^...
0
votes
0answers
75 views

Minimizing Frobenius norm with sparsity constraints

I am trying to solve the following minimization problem \begin{equation*} \begin{aligned} & \underset{X,Y \in \mathbb{R}^{n\times k}}{\text{minimize}} & & \| X Y^\top A - B \|_{\text F}^2 ...
2
votes
1answer
114 views

Optimal-score partitions

The question about throwing darts asked on the MathOverflow page Sacred Geometry of Chance was not well received, apparently because of "[t]oo much noise around the actual math", as stated in a well-...
1
vote
0answers
52 views

Distance between quadric surface and point or Intersection of sphere and quadric surface

I asked a similar question on math.stackexchange, but the answer wasn't quite ideal for my application. Apparently analytic solutions are surprisingly rare for general quadric distances. Given a ...
2
votes
1answer
110 views

Non-negativity condition for special quartic

I know that a necessary and sufficient condition for the positivity of a quartic polynomial of many variables is in general difficult. I have a somewhat special case, maybe here more can be said. Let $...
3
votes
1answer
92 views

Is the level set of a product of affine linear functions comprised of convex curves?

Internet searches haven't helped. Can you? Let $\, f = \prod_{i=1}^n (a_i x + b_i y + c_i).$ Is each component of $\, f^{-1}(1)$ a convex curve? I expect so, and can prove it for $n=2,$ but I'm ...
2
votes
1answer
191 views

Minimizing the expectation of a functional of probability distribution subject to an entropy constraint

Consider a PDF $\pi(x)$ for $x\in[0,1]$, and the following functional $$ F(\pi) = \mathbb{E}_\pi |x-y| $$ It is minimized by any point mass, so to avoid such degeneracy I'd like to lower-bound the ...
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 ...
1
vote
1answer
104 views

Parametric constrained optimization

I'd like to find a way of determining if the distance from the origin of a parametric parabolic path falls below a certain value within a given range of the parameter. The parabola is expressed as: $$...
3
votes
1answer
159 views

A sum over a hyperplane in $\mathbb{Z}^4$

Fix $M \geq 2$. What is the smallest number $\tau = \tau(M)$ such that $$\sum_{a,b,c,d =1\\ a + b = c+ d}^M (x_a x_b x_c x_d)^{\tau/4} \leq 1,$$ for all $x , \ldots , x_M \in \mathbb{R}_{\geq 0} $ ...
0
votes
0answers
16 views

Finding Optimal Spheric Polyhedra with Given Convex Hull Topology

I want to draw finite planar graphs in certain canonical ways. My idea is to use a stereographic projection of the convex hull of points placed on the unit sphere in a way, that the graph induced ...
0
votes
0answers
95 views

L1 norm constraint on product of 2 matrix

I want to solve below minimization problem \begin{equation*} \begin{aligned} & \underset{A, B}{\text{minimize}} & & ||Y-AB^T -D||_F^2 \\ & \text{subject to} && |A_i|_1 \leq a,...
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 ...
2
votes
0answers
38 views

Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...
2
votes
1answer
73 views

Linear optimization with one positive definite quadratic equality condition in P?

I have the following minimization problem in $z \in \mathbb R^n$, which contains $x_1, \dots, x_t, y \in \mathbb R$. $$\begin{array}{ll} \text{minimize} & y\\ \text{subject to} & xQx'= y\\ &...
0
votes
0answers
57 views

non-convex optimization with constraint

I have a special non-convex optimization problem: $\min / \max \ f(x) + g(x) + h(x)$, subject to $| g(x) - h(x)| < \varepsilon$, where $f(x)$ is non-convex, but both $g(x)$ and $h(x)$ are ...
0
votes
1answer
73 views

On an error bound for matrix constraints

Given $A,B\in\mathbb R^{n\times n}$ such that there is an $U\in\mathbb R^{n\times n}$ with $UU'=I$ and $UAU'=B$. Suppose each entry of $V$ is within $\pm\epsilon$ of each entry of $U$ is there a way ...
2
votes
0answers
43 views

Optimization with bounds on the control and its derivative

I would like to understand the following optimization problem. Let $F(t,x)$ be a continuous function defined on $[0,1]\times [0,1]$, which is increasing in $t$ and convex in $x$ (I have in mind $F(t,x)...
0
votes
2answers
152 views

Lagrange Multipliers for two constraints, degenerate case

To optimize $f(x,y,z)$ subject to $g(x,y,z)=h(x,y,z)=0$, we use the Lagrange Multiplier method and solve \begin{equation*} \nabla f=\lambda \nabla g+\mu\nabla h,\quad g=0,\quad h=0. \end{equation*} ...
0
votes
1answer
87 views

1D functional equation: solve for function with given expected value w.r.t normal density

Given scalars $c_1, c_2 > 0$, how would one go about solving, for non-expansive (i.e 1-Lipschitz) $\phi: \mathbb R \rightarrow (-\infty,+\infty]$, the following equation $$ \begin{split} \mathbb ...
0
votes
0answers
9 views

Embedding Symmetric TSP Instances in Euclidean Spaces of Least Dimension

It is known, that the set $E_{opt}$ resembling the opitmal tour of a symmetric TSP, is invariant under the addition of so called vertex weights $w(v_i)$, i.e. to adding or subtracting the same ...
0
votes
0answers
54 views

Suggestions to solve an optimization problem that involves quadratic forms

I am in a crucial part of my research, I have arrived at an optimization problem that I can not solve, I need to solve it to be able to perform simulations and thus complete my research, due to this ...
0
votes
0answers
26 views

Functions of squares of gradients and the spectrum of the Hessian

This is a very ill-formed formed question but kindly indulge me! Say one has function $f : \mathbb{R}^d \rightarrow \mathbb{R}$ and a constant $a >0$. And let $g = \nabla f$ and $i \in 1,2..,d$. ...
6
votes
5answers
259 views

Nearest matrix orthogonally similar to a given matrix

Given $A,B\in\Bbb R^{n\times n}$ is there technique find $$\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_F\mbox{ or }\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_2$$ within additive approximation error in $\...
1
vote
0answers
121 views

Lagrange-Newton minimization and initial value for the Lagrange multipliers

Short version. How to choose the initial values for the Lagrange multipliers in the Lagrange-Newton equality-constraint minimization method? Introduction. The problem to solve is \begin{equation} \...
4
votes
0answers
204 views

Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables

Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest: $1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed; $...
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} + \...
1
vote
0answers
40 views

Rank Optimization over semi-definite constrains

Let $X$ and $Y$ be finite dimensional Hilbert spaces $\mathbb{C}^n$ and $\mathbb{C}^m$, $L(X)$ and $L(Y)$ be the sets of linear operators of $X$ and $Y$, $\text{Herm}(X)$ and $\text{Herm}(Y)$ be the ...