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

Questions tagged [nonlinear-optimization]

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

0
votes
0answers
37 views

A Quadratic Programming Problem

Let $d > 1$. I am looking to solve the following $$\max x \cdot x $$ subject to $$Ax \leq b , \ \ x \geq 0.$$ Here $A$ is the matrix with $d+1$ along the diagonal, $d$'s below the diagonal, $1$'s ...
1
vote
0answers
18 views

Bayesian parameter estimation

I am generally not that knowledgeable for math, so if my question is too broad or inaccurate, please let me know. I am currently reading a paragraph of one paper (https://www.fil.ion.ucl.ac.uk/spm/...
6
votes
2answers
180 views

Proving an infinite norm minimization problem has finite support (non-convex p-norms)

Consider an optimization problem over infinite variables: $$ \begin{align} \min_{x}~& {\left\lVert{x}\right\rVert }_p \\ \text{s.t}~& \left\langle x, a_n\right\rangle \ge 1~,~\forall n=1,\...
1
vote
0answers
39 views

Curvature of projection function onto a smooth curve

Suppose we have a smooth curve $C$ lying in $\mathbb{R}^2$, and let us consider the orthogonal projection function $P_C(x)$ onto the curve, described by $$P_C(x) = argmin_{y \in C} \Vert x - y \Vert$$...
11
votes
2answers
516 views

Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 1$

Suppose $f:\mathbf{N} \to [0,1]$ satisfies $$f(x)f(y) + f(x+y)\leq 1\qquad(1)$$ for all $x,y$. Let $$d_n = \frac{1}{n} \sum_{x=0}^{n-1} f(x).$$ It is easy to prove that $$\limsup d_n \leq 1/\varphi,$$ ...
4
votes
0answers
164 views

Computing Bohr Radii

The Bohr radius $R$ for $\mathcal{H}(\mathbb{D})$ is defined as $$R = \sup\limits_{0<r<1} \Bigl\{ r\ \Big|\ \sum\limits_{k=0}^{\infty}|a_k|r^k \leq |f|_\mathbb{D} \text{ for all }f(z)=\sum\...
0
votes
1answer
82 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$ ...
0
votes
0answers
59 views

Is dynamic programming suitable for a specific optimization problem?

Let $c,\,\mathcal{P}_0,\,\mathcal{P}_1,\,\mathcal{P}_2,\ldots$ be a sequence of positive real numbers. Let $N\in\{1,\,2,\,3,\ldots\}$ and let $t\in\{0,\,1,\,2,\ldots\}$, with $N$ and $t$ fixed. ...
0
votes
0answers
34 views

optimisation problem for unknown function

I have two variables function $z=f_{a,b}(x,y)$ ($a,b$ - some parameters), however I don't know its formula (I can compute its value for given $x,y$ and $a,b$). I would like to find minimum of this ...
0
votes
0answers
50 views

Optimizing a complex functional with respect to the Lexicographic Ordering?

I'm wondering if the following argument is correct: Consider optimizing a complex functional $S[x(t)]$. Since $S$ is complex, it only has an optimum with respect to the lexicographic order of the ...
1
vote
1answer
78 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 ...
0
votes
0answers
30 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
77 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
25 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
62 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
83 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
48 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
140 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
84 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
157 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 ...
2
votes
1answer
92 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
50 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:...
1
vote
0answers
85 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
42 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
53 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
37 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
55 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
205 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
376 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
75 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
92 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
115 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
58 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
112 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
93 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
199 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
94 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
105 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
160 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
111 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
48 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
1answer
49 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
75 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
71 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
74 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
157 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*} ...