All Questions
Tagged with nonlinear-programming or nonlinear-optimization
639 questions
4
votes
3
answers
948
views
Efficient algorithm for Wasserstein-1 distance in graph setting
I first asked this question on math.stackexchange, but I think this question is high-level enough that is better suited here.
I'm looking for an efficient algorithm to calculate the Wasserstein-1 ...
- 143
4
votes
3
answers
1k
views
Solving a quadratic matrix equation with fat matrix
I am trying to find an $n \times m$ fat (i.e., $m > n$) matrix $T$ that solves
$$T^T T = X$$
where $X$ is a given $m \times m$ symmetric, positive semidefinite matrix.
I saw this post, but ...
- 143
4
votes
2
answers
464
views
QR-Decomposition of matrix valued function
Suppose I have a matrix valued function
$$
F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T
$$
where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, $...
- 255
4
votes
1
answer
2k
views
lipschitz constant of a multivariate function
I have a function $f:\mathbb{R}^{50} \rightarrow \mathbb{R}$ and I need to compute the Lipschitz constant of $f$ to solve an optimization problem using a specific algorithm. Does any one have ...
- 41
4
votes
1
answer
242
views
Nonlinear system of integral equations
I have encountered a system of nonlinear integral equations in my work. They take the form
$$\int_{0}^{1} \frac{1}{g(y)}e^{f(x)/g(y)}(x+f(x)/g(y)-f(x))dy=0$$
$$\int_{0}^{1}\frac{f(x)}{g(y)^2} e^{f(x)/...
- 143
4
votes
1
answer
822
views
Nonlinear least square with quadratic equality constraint
I am looking for an appropriate method or hint to solve the following constrained nonlinear least square problem:
$\operatorname{argmin}_X \sum_{i\in I} \|\mathbf{X}_i - \mathbf{X}_{i+1}\|_2^2 + \...
- 41
4
votes
1
answer
128
views
Conjugate gradient algorithm where first search direction is not equal to residual
In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...
- 489
4
votes
1
answer
90
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) ...
- 167
4
votes
1
answer
889
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}
\...
- 101
4
votes
1
answer
445
views
Proving convergence of modified ALS for non-negative matrix factorization
The general Non-Negative Matrix Factorization (NMF) problem asks that for given a matrix $X \in \mathbb R^{m,n}_{0+}$ (with this notation meaning a matrix containing real numbers greater than or equal ...
4
votes
2
answers
672
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 ...
- 355
4
votes
1
answer
429
views
Finding all local maximum points of a function?
Let ${\boldsymbol \theta}=(\theta_1,\theta_2,\ldots,\theta_n) \in{\mathbb T}^n$ and $P:{\mathbb T}^n\rightarrow {\mathbb R}$ be a function defined on $n$-torus as
$$
P({\boldsymbol \theta}) = \sum_{i&...
4
votes
1
answer
396
views
Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint
I am wondering what is known about optimization problems of the following type.
Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities
$$Az≥b,$$
and we ...
- 185
4
votes
0
answers
235
views
What is the maximum tidal force between two objects with unit volumes and unit density?
Motivation for this problem
This problem arises from the fact that the derivative of the gravitational force (tidal force) in the $z$-direction between two objects $A$ and $B$, which have equal ...
- 273
4
votes
0
answers
121
views
$f(n) = \frac{n^2 + n + 4}{2}$, $g(f(n)) = f(g(n))$ such that $g(n)$ is an integer
Let $n$ be a strict positive integer and let's define an integer sequence $f(n)$ :
$$f(n) = \frac{n^2 + n + 4}{2}$$
so
$$
\begin{split}
f (\Bbb N)& \triangleq {3,5,8,12,17,23,30,38,47,\ldots}\\
f(...
- 763
4
votes
1
answer
287
views
Local maxima of the sum of Gaussian functions in *multiple dimensions* are always strict local maxima - prove/disprove/prove conditionally?
This is a follow up of the question in one dimension, that asked to show that the all the maxima of the sum of Gaussian
$$f_n(x):= \sum_{i=1}^{n}e^{-(x-x_i)^2}, x_1 < x_2 < \dots < x_n$$
are ...
- 1,467
4
votes
0
answers
146
views
An inequality for three iid random variables with a log-concave density
It was previously shown that
$$H\ge cG,\tag{1}$$
where $c:=1/14334$,
$$G:=E|X-Y|,\quad H:=E|X-Y|-\tfrac12\,E|X+Y-2Z|,$$
and $X,Y,Z$ are independent random variables with the same log-concave density.
...
- 128k
4
votes
0
answers
287
views
A conjecture about the barycenter of a polytope
Could someone help me with the following conjecture? Thanks a lot!
Suppose I have a polytope $\Delta$ in $\mathbb R^n (n\geq 2)$ with coordinates $(x_1,x_2,\cdots,x_n)$ defined by linear ...
- 1,121
4
votes
0
answers
275
views
Computing Bohr Radii
The Bohr radius $R$ for $\mathcal{H}(\mathbb{D})$ is defined as the radius $$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)=\...
- 3,209
4
votes
0
answers
228
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;
$...
- 359
4
votes
0
answers
234
views
Optimisation over $SO(3)$: is it safe to use a global parametrisation?
I am a functional analyst by training, but I am doing some numerical experiments which require me to minimise continuous functions $f:SO(3)\longrightarrow [0,+\infty)$ using a computer (I know that ...
- 778
4
votes
0
answers
241
views
Stochastic subgradient descent almost sure convergence
I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure ...
- 141
4
votes
0
answers
707
views
What does the Von Neumann's stability analysis tell us about non-linear finite difference equations?
I've asked this question on computation science stackexchange, but it did not receive any answers so I have decided to ask it here as well.
I am reading a paper [1] where they solve the following non-...
- 215
4
votes
0
answers
248
views
Comparison of Constrained Optimization Methods
I am trying to solve a constrained optimization problem using filter methods and came across two papers on the topic that I am having some problems with. The original filter method paper is the ...
4
votes
0
answers
405
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
233
views
Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same
I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e.,...
- 1,517
4
votes
0
answers
575
views
Programming workbooks in C++ and Research Math [closed]
I know the basics of C++ by taking a few courses and going through "C++ Primer" by Lippman. As a math graduate student, I would love to get my hands on some programming-math exercises geared towards ...
4
votes
0
answers
522
views
Solution of a linearly constrained quadratic programming problem [closed]
What is the solution of the following optimization problem:
\begin{align}
&\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\
&\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}.
\...
- 51
4
votes
0
answers
213
views
Optimization problem involving Multivariate Normal
I use $\phi(t)$ to describe the standard normal distribution density and $\Phi(t)$ as the normal distribution CDF and would like to prove that for all
$n\geq3$, the function:
$$h(\mu_{1},\ldots,\...
- 41
3
votes
2
answers
3k
views
Sparse approximation of the inverse of a sparse matrix
Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
- 2,205
3
votes
1
answer
233
views
Min problem on integers
Let $n$ be any integer greater than $2^{10^6}$. Given any $s\le (\log_2 n)/1000$ integers $1=q_1\le q_2\le \cdots q_{s-1}\le q_s=n$. Prove that
$$\min_\ell\left(\sum_{i=1}^\ell q_i\right)\left(\sum_{i=...
3
votes
1
answer
416
views
What's the best orthonormal matrix to align two matrices in the operator norm sense?
Let $A,B \in R^{n\times r}$ with $A^\top B $ invertible. It is known that
\begin{equation}
UV^\top :=\arg\min_{R \in \mathcal{O}^{r\times r}}\|AR-B\|_\mathrm{F},
\end{equation}
where $USV^\top$ is ...
- 515
3
votes
1
answer
2k
views
The average number of people that can sit on a bench of a given length.
Let me explain what I mean:
The width of the average person varies, perhaps with a normal distribution.
Given a specific variance, how many people (on average) can sit side-by-side on a bench of a ...
- 43
3
votes
2
answers
266
views
Fixed point iteration on symmetric biconvex function
Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...
- 705
3
votes
1
answer
205
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 ...
- 4,280
3
votes
1
answer
227
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} $ ...
- 2,283
3
votes
1
answer
730
views
Computational complexity of low rank SDP
Suppose we are given a general semidefinite program (SDP) of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{...
- 1,503
3
votes
1
answer
322
views
Special version of Tonelli’s theorem
I am trying to prove this theorem. I have not found anything similar to it on the internet.
Special version of Tonelli’s theorem
Assume that the functions $f(x,u): [a,b] \times \mathbb{R} \to \mathbb{...
- 159
3
votes
1
answer
862
views
Nonconvex optimization problem
I have a nonconvex optimization problem with a linear objective function, a set of linear constraints and a set of nonlinear, non-convex constraints. Is this problem NP-hard? If so, how can I prove ...
- 221
3
votes
1
answer
602
views
Is the feasibility of a system of non-convex quadratic equations and inequations decidable?
I would like to know whether the following problem is decidable.
Given the following system in $x \in [0,1]^n$
$$x^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., k$$
$$x^T Q_j x + r_j \neq 0 \mbox{ ...
- 165
3
votes
1
answer
189
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
3
votes
1
answer
133
views
Is the smallest root of this quartic always the closest point on the Hyperbola? [closed]
Let $a>b>0$.
Suppose we want to minimize
$$
f(x)=(x-a)^2+(1/x-b)^2,
$$
over $x>0$.
Equating $f'(x)=0$ leads to the quartic equation
$$
g(x)=x^4-ax^3+bx-1=0. \tag{1}
$$
Question:
Is the ...
- 6,741
3
votes
1
answer
217
views
Obtaining the "best possible" inequality by tuning hyper-parameters
I encountered the following problem in one of my research projects which can be encapsulated as follows. Let's say we have a set $\mathcal{C}$ of functions $f$ defined from $\mathbb R_+$ to $\mathbb R$...
- 730
3
votes
1
answer
702
views
Maximizing the distance sum of some points inside a circle
Consider $n$ points $\{p_i\}_{i=1}^n$ located inside or on a circle with radius $r$ in the plane. The question is: how to place the $n$ points so that the sum of inter-point distances,
$$J=\sum_{i=1}^...
- 133
3
votes
2
answers
97
views
Optimal covering of line subsegments using a given set of disks
Is there a way of picking a minimal set of disks that's still covering the same line subsegments as all the disks together? Any help or references highly appreciated. Below is just an illustrative ...
3
votes
1
answer
260
views
Better alternative to solve quadratic programming for large matrices
I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...
- 135
3
votes
1
answer
2k
views
Valid KKT Constraint Qualification? Linear constraints not full rank, Jacobian of nonlinear constraints full rank and independ. of linear constraints
For a nonlinear optimization problem having only linear constraints, by the Linearity Constraint Qualification, no further constraint qualification is required for the Karush-Kuhn-Tucker (KKT) ...
- 1,517
3
votes
1
answer
283
views
Eigenvectors of a tensor in $\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^2$
I want to find the critical point of tensor $f=a_0b_0c_0 + a_1b_1c_1$ in $\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^2$, and I followed this construction:
First, I take the following partial ...
- 309
3
votes
1
answer
413
views
Weird claims and conclusions in "Introduction to Shape Optimization"
I'm trying to understand the notions of Euler and Hadamard derivatives of shape functionals. All the lecture notes and papers on this topic that I've found seem to build up on the books Shapes and ...
- 167
3
votes
1
answer
261
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 ...
- 6,741