Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
287 questions with no upvoted or accepted answers
1
vote
0
answers
29
views
Gradient descent to estimate the ground truth pdf
I have a function $I_d(x)$ which defined over a plane. I could simulate the values of this function at different points. I have a ground truth probability density vector $p({\bf x})=(p_1(x),...,p_d(x))...
- 113
1
vote
0
answers
81
views
Solve optimal control problem whose associated system is nonlinear
Solve the optimal control problem of the LQR kind
$$
\min_u \int_0^{+\infty} x_1^2+x_2^2+\gamma(u_1^2+u_2^2) \, dt \quad\text{such that}\quad \begin{cases}\dot x_1=\alpha(x_2-x_1)+u_1,& x_1(0)...
- 207
1
vote
0
answers
150
views
Minimax optimization of diagonal entries of function of matrix
Let $\mathbf{A}$ and $\mathbf{U}$ be arbitrary complex $M\times N$ and $N\times M$ matrices, respectively. Let denote superscript $(\cdot)^{\dagger}$ and $(\cdot)^{\mathrm{H}}$ as pseudo-inverse and ...
- 287
1
vote
0
answers
116
views
Showing existence of a solution to an underdetermined system of equations with non-negativity constraints
Let $K$ be a positive integer, let $p\in (0,1)$, and let $\{W(k,i),W^B(k,i), \varphi_k(i)\}_{1\leq i\leq k\leq K}$ be variables.
I need to prove that there exists a solution to the following system ...
- 63
1
vote
0
answers
73
views
Reduce the asymptotic variance for a class of Metropolis-Hasting estimates
I'm running the Metropolis-Hastings algorithm with state space $E$, target distribution $\mu=p\lambda$ and proposal kernel $Q$ to estimate $\mu(hf)$ for a fixed function $f:E\to[0,\infty)^3$ and a ...
- 167
1
vote
0
answers
240
views
Maximize a smooth integral functional by pointwise maximization of the integrand
Let $(E,\mathcal E,\lambda),(E',\mathcal E',\lambda')$ be measure spaces, $I$ be a finite nonempty set, $p,q_i$ be probability densities on $(E,\mathcal E,\lambda)$, $\varphi_i:E'\to E$ be bijective ...
- 167
1
vote
0
answers
79
views
Minimization of a smooth integral functional over a closed convex set
Let $(E,\mathcal E,\mu)$ be a probability space, $I$ be a finite nonempty set, $\gamma:(E\times I)^2\to[0,\infty)$ be measurable, $$F_1(g,w):=\sum_{i\in I}\int\mu({\rm d}x)w_i(x)g(x)\sum_{j\in I}\int\...
- 167
1
vote
0
answers
106
views
Show a Poincaré inequality for a Markov kernel and minimize the Poincaré constant
Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$ (see definitions ...
- 167
1
vote
0
answers
152
views
solving a non-linear Matrix equation
I am working on a problem of optimization of wireless sensor networks in order to achieve the optimal power allocation in the network. I find an equality matrix problem that can be written as ...
- 377
1
vote
0
answers
543
views
Variational derivative of Wasserstein distance using Benaumou-Brenier formulation
I learned from the gradient flow theory in Wasserstein space that an equation of gradient flow type
$$\partial_t \rho + \nabla \cdot (\rho \nabla \frac{\delta F}{\delta \rho})=0,$$
can be derived as ...
- 429
1
vote
0
answers
99
views
Minimize $\langle(1-\kappa)^{-1}f,f\rangle$ for a parameter-dependent integral operator $\kappa$
I've got a contractive self-adjoint linear integral operator $\kappa$ of the form $$(\kappa g)(x):=g(x)+\int\lambda({\rm d}y)k(x,y)(g(y)-g(x))\;\;\;\text{for }g\in L^2(\mu),$$ where $k$ depends on the ...
- 167
1
vote
0
answers
311
views
Computing the nearest hermitian positive semi-definite matrix
The real case of finding the nearest semi-definite matrix in terms of the Frobenius norm was solved by Higham in 1988.
But is there any work on computing the nearest
hermitian positive semi-...
- 43
1
vote
0
answers
44
views
Finding a distribution satisfying uncountably many constraints: a follow up in a more restrictive setting
Recently, I posted the question Finding a distribution satisfying uncountably many constraints. Any relevant references?. Bjørn Kjos-Hanssen quickly and astutely pointed out that without further ...
- 33
1
vote
0
answers
167
views
Gradient formula for Clarke's generalized gradient on a general Banach space
In Theorem 10.27 of the book Functional Analysis, Calculus of Variations and Optimal Control, there is the following gradient formula:
($\operatorname{co}$ deotes the convex hull).
Is there an ...
- 167
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
1
vote
0
answers
116
views
look for differentiable symmetric functions whose global minimizer has all distinct components
For symmetric functions, people ask Do symmetric problems have symmetric solutions?, e.g., [3] and [4].
The answer is no in general. However, solutions of symmetric problems often exhibit certain ...
- 1,053
1
vote
0
answers
188
views
Solution to a Strongly Convex Non-smooth Minimization Problem involving an L1 Norm
Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1\}^{n}, \alpha \in [0,1], \lambda \in \mathbb{R}$. I have an expression that looks as follows
$\frac{1}{2}\|Xw -y \|_{2}^2 + \...
- 11
1
vote
0
answers
760
views
Matrix trace minimization of quadratic and linear terms under orthogonal manifold constraints
How would one solve the following orthogonal manifold problem?
$$\begin{array}{ll} \text{maximize} & \mbox{tr}(X^\top A X - X^\top B)\\ \text{subject to} & X^\top X = I\end{array}$$
where $A ...
- 21
1
vote
0
answers
59
views
Sum of squared nearest-neighbor distances between points on the sides of a rectangle
For positive real numbers $a,b$, let $R$ denote the $a\times b$ rectangle $[0,a]\times[0,b]$. Let $A_1,\dots,A_4$ be points on the sides of $R$, one point on each side. For each $j=1,\dots,4$, let $...
- 128k
1
vote
0
answers
67
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/...
1
vote
0
answers
68
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$$...
- 141
1
vote
0
answers
138
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$ ...
- 13.9k
1
vote
0
answers
101
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\...
- 1,982
1
vote
0
answers
229
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 ...
- 11
1
vote
0
answers
45
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 ...
- 1,503
1
vote
0
answers
51
views
A Pathwise Optimization Problem
Suppose $X$ is a nonnegative semimartingale that is progressively measurable with respect to a given filtration $\{\mathcal F_t\}_{t\ge 0}$. Let $c:\mathbb R_+ \mapsto \mathbb R_+$ be a strictly ...
- 622
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
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 ...
- 393
1
vote
0
answers
149
views
Coordinate descent conditions
The following is quoted from "Bertsekas, D. P. (1999). Nonlinear programming (p. 794). Belmont: Athena scientific".
Convergence of Coordinate Descent: Suppose a function $f$ is continuously ...
- 133
1
vote
0
answers
89
views
Optimization problem with non linear objective and non linear constraint (or upper bounding)
I am tackling the following optimization problem where ideally I would like to maximize (analytically, over $\alpha$) these sorts of quantities, where $n \ll d$ and $d \in \mathbb{N}, \epsilon \in \...
- 141
1
vote
0
answers
82
views
Gradient descent with gradient evaluated at transformed coordinates
Let $f:\mathbb{R}^n\to\mathbb{R}$ be a given function and let us consider the unconstrained problem, $$\min_{x\in\mathbb{R}^n}f(x)$$ The standard iterative method for this is the gradient descent ...
1
vote
0
answers
55
views
Does Sion minimax require choice?
Is the axiom of choice (or equivalent) required to establish Sion's minimax theorem?
H. Komiya's elementary
proof
does not seem not to use any transfinite induction or choice axiom. Is this really ...
- 6,541
1
vote
0
answers
49
views
Minimization of convex functions on dense subspaces
I want to consider the Moreau envelope $\psi_j$ of a proper, convex, lower semicontinuous function $\psi$ over a Banach space $V$ on dense (finite dimensional) monotonically increasing subspaces $V_m$,...
- 187
1
vote
0
answers
63
views
On solving non-linear equations of this type
I would like to attempt to solve the given problem below. I am sorry that I dont know whether such a question is solvable at all, even for just one specific example. If the solution set is empty, I am ...
- 359
1
vote
0
answers
190
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
69
views
Soft: Lagrange Multiplier and Intersection of Thickened Sets
Suppose I have an optimization problem of the form
$$
\inf_{\{x \in \mathbb{R}^d: g(x)=0\}} f(x),
$$
for some convex function $f$ and non-convex l.s.c. function $g$.
Can we reinterpret the ...
- 5,405
1
vote
0
answers
83
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
63
views
Does the equation $\mathbf{I} = \sum_{k=1}^{m} \mathbf{U} \mathbf{B}_k \mathbf{U}^T\mathbf{A}_k$ have a special name or solution?
I have encountered the equation $\mathbf{I} = \sum_{k=1}^{m} \mathbf{X} \mathbf{B}_k \mathbf{X}^T\mathbf{A}_k$, recently.
All matrices are of dimension $n \times n$.
Is it assigned a special name?
...
- 39
1
vote
0
answers
483
views
minimize norm of matrix product
I have the matrix Product $PAP^H$ and I need to minimize $\|(PAP^H)^{-1}\|^2$ (over $P$ and Frobenius norm).
$A$ is a positive definite Hermitian matrix and $P$ has the structure
$$P=\left[\begin{...
- 129
1
vote
0
answers
355
views
Solution to a system of nonlinear equations using convex conjugate of log sum exp
I need to prove the following result:
There exists a unique solution to the system of equations
$$\alpha = \frac{I^T(\gamma e^{I\beta})}{\sum_{i=1}^{n}\gamma_ie^{(I\beta)_i}}$$
if and only if $\...
- 11
1
vote
0
answers
232
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
94
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,246
1
vote
0
answers
64
views
Posterior consistency of non linear model
This is possibly a reference request. Let $G$ : $\mathbb{R}^p \to \mathbb{R}^q$ be a continuous injective/bijective function. Let $\mu$(we may also assume this to be a non degenerate Gaussian) be ...
- 157
1
vote
0
answers
947
views
max min of ratio of quadratic forms
Consider the optimization over two vectors $x$ and $y$
$$\max_{x,y} \min\left(\frac{x^TAx}{y^TAy},\frac{y^TBy}{x^TBx}\right)$$
for two positive definite matrices $A$ and $B$.
This problem can be ...
1
vote
0
answers
52
views
Which algorithm is most efficient for a specific QP problem
I have a QP problem of the following kind:
$\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$
s.t. $l\leq \alpha \leq u$
The matrix $M$ is symmetric and positive definite and of ...
- 11
1
vote
0
answers
68
views
Characterization of eigenvector
Let's say we have the following optimization problem. (All the $\Sigma_{ii}$'s are positive definite.)
$\max u^\top \Sigma_{12} v\quad$
$\text{subject to}\quad u^\top \Sigma_{11} u = 1\quad and\quad ...
- 515
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
32
views
$\min \sum_i f(w^i) +\sum_j g(w_j)$ wrt col and rows of a matrix
I've got an unconstrained optimization problem, and all function involved can be regarded as differentiable as you like.
The variable is a rectangular matrix $M$.
Target Function is $\sum_i f(w^i) +...
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
421
views
Is this QCQP convex or nonconvex?
\begin{equation}
\begin{split}
\min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x
\end{split}
\end{equation}
s.t.
$$
g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\}
$$
$$
g_i(x)=\frac{...
- 11