Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
613
questions
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 ...
4
votes
0
answers
688
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-...
0
votes
1
answer
515
views
a sum of ratios of quadratic forms
I have the following function that I would like to optimize over the value A
$$f(A)=\sum_k \frac{\mathbf{y}_k^H\left[\begin{array}{cc} 1&0\\ 0& A \end{array} \right]\mathbf{x}_k\mathbf{x}_k^H\...
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) +...
2
votes
0
answers
164
views
Conditions under which the dual function is self-concordant
Consider the following optimization problem
\begin{align}
\min_{x}&\quad f(x)\\
\nonumber \text{subject to } \quad&h_i(x) = 0,\,i=1,\ldots,m\\
\nonumber \quad&x\in X\subseteq\...
5
votes
0
answers
182
views
measure of an image under an argmax function
I am trying to find any techniques to analyze the measure of an image of a set under an argmax function.
For example, let $\Omega\subset\mathbb{R}^n$ be compact and $\phi:\Omega\to\mathbb{R}$ be ...
2
votes
1
answer
155
views
A graph assignment problem
Consider bipartite graph with vertex set $V_1\cup V_2$ where $|V_1|=\frac{n(n-1)}2$ and $|V_2|=n$. The vertices in $V_1$ all have degree $2$ and connected to two vertices in $V_2$. The vertices in $...
1
vote
1
answer
411
views
Generalized Lax-Milgram for Weak Formulation of 1D Linear Schrodinger
I am interested in the variational formulation of the 1D Schrodinger equation:
$i u_t- \beta u_{xx} = 0 $ and $u(x,0)=u_0(x)$ which upon integration by parts yields:
$i(u_t,v) + \beta (u_x,v_x) = 0$ ...
2
votes
0
answers
360
views
What's the advantage of majorization-minimization (MM) algorithm [closed]
The majorization-minimization (MM) algorithm is a framework for convex and nonconvex optimization. When applied to nonconvex optimization, the MM algorithm solves a sequence of convex problems to ...
-1
votes
2
answers
713
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
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) ...
2
votes
1
answer
220
views
A bound on the number of bilinear functions needed in order to obtain the minmax
For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$.
Is there a function $m:\mathbb N\to\mathbb N$ such that for any ...
0
votes
0
answers
172
views
Question on solving an optimization problem using Variable splitting and ADMM
Tell me if I have found the right approach to the following optimization problem:
$$
min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2
\\
s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0
$$
$A$ and $\Phi$ ...
1
vote
1
answer
1k
views
Envelope theorem for second derivative
I am maximizing a function $f(x,z)$ on $x$ ($z$ is treated a parameter in the maximization). The function $f$ is strictly concave on both variables.
I know how to use the envelope theorem for the ...
1
vote
0
answers
389
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{...
2
votes
1
answer
187
views
$0/1$ programming multiple quadratic constraints
If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time.
If we have an $n$-variable degree $2$ system how many constraints ...
1
vote
0
answers
88
views
solution of an infinite horizon optimization problem
Give the following formulation:
$\min_{\{x_s(t):\forall s,t\}} \sum_{s \in \mathcal{S}} \mathbf{1}\left(\lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=1}^T \frac{y_s(t)}{x_s(t)}\leq 1\right)$
$s.t. ...
1
vote
0
answers
117
views
Finding the Lagrangian dual problem for a quadratic programm [closed]
I've problems to find the Lagrangian dual problem to
\begin{align*}
\min \limits_{x \in \mathbb{R}^n} \; \frac{1}{2} x^{ T} Q x + q^{T} x \\
\text{s.t.} \quad
Ax &=b \\
x &\geq 0
\end{...
0
votes
1
answer
72
views
Solving a nonlinear optimisation problem
I have the following nonlinear optimisation problem arising in my model.
$$\min \sum_{k=0}^{N-1} (\tau-t_k)^+\quad \text{ s.t. } {\mathbf{x}^\top\mathbf{w}\le W,\ \mathbf{x}\ge0}, t_k=t_{k-1}+x_k \...
2
votes
0
answers
100
views
Solve non-linear Optimization Problem [closed]
I have to find $x$ that minimizes: $$ \sum_{k}(x^H\textbf A_kx - b_k)^2$$ where $A_k$ are 4 x 4 positive definite matrices ($A_1, A_2,...A_k$), $x$ is 4 x 1 vector and $b_k$ are scalars ($b_1,b_2,......
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 ...
6
votes
1
answer
5k
views
max-min optimization problem
I'm curious if there is any nice way to approach solving the following kind of optimization problem. Given a $n \times m$ matrix $A = (a_{ij})$, I want to solve
\begin{align*}
& \max_{c}\min_{1 \...
0
votes
1
answer
536
views
Convert general optimization problem to LP problem
I am trying to convert the following problem into a linear programming problem:
There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
2
votes
0
answers
127
views
How to approximate higher-degree multivariate polynomial in space of lower-degree multivariate polynomials with some constraints?
For a polynomial $P_{1}(x)$, $x\in {\mathbb R}^n$ with a higher-degree, how to find a lower-degree polynomial $P_{2}(x)$ with determined structure or bounded degree to approximate it with the ...
1
vote
1
answer
77
views
Quadrature formula for singular integrals over rectangular cuboids
A)Find the maximum of the following :
$$\int_{\Omega_{a,b,c}}\int_{\Omega_{a,b,c}}\frac{dV(X)dV(Y)}{\|X-Y\|^2}$$
where ${\Omega_{a,b,c}}=[0,a]\times[0,b]\times[0,c]$, given $abc=1$ with $a,b,c>0$.
...
1
vote
0
answers
129
views
Lower bound on the value $\textbf{1}^Tx$ such as $Ax\geq b$
The problem may be formulated as follows:
We are given a set of $m$ positive numbers $\{b_1,...,b_m\}$ and a set of $n$ positive numbers $\{v_1,...,v_n\}$. We have $v_j\leq K$, $j=1,...,n$, for a ...
2
votes
1
answer
151
views
Learning rule for recurrent neural network with flexible time steps
Summary: I want to train a recurrent network to output some answers, but the recurrent network is allowed to re-iterate through itself a flexible number of times for each input-output pair.
Why this ...
3
votes
1
answer
241
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 ...
3
votes
1
answer
681
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{...
3
votes
0
answers
937
views
Minimize L-infinity norm with restrictions
I need to minimize the following L-infinity norm with respective to $\tau$. L-infinity norm of a matrix $A$ is defined as $\|A\| = max_{i,j}|a_{i,j}|$.
$$
min_{\tau} \| I -S(S+\tau)^{-1}\|
$$
$$
\...
1
vote
0
answers
83
views
reconstructing a linear order corrupted by noise
Suppose we have a partial order (efficiently computable), $\leq$, on $\mathbb{R}^n$, a set $S \subset \mathbb{R}^n$, and let $\rho$ be the standard Euclidean metric. We want to find a set $S^\prime = ...
2
votes
0
answers
104
views
A (non-convex) minimization quadratic programming problem with d constraints
Minimize $0<\omega_{dd}<2$ subject to
$$\sum_{j=1}^{d}(\omega_{dj} - \omega_{ij})^{2} \geq 4, i=0,1,...,d-1,$$
where $-2<\omega_{ij}<2$ is known for $0 \leq i \leq d-1$ and $1 \leq j \leq ...
5
votes
1
answer
211
views
Bounding function of norms in constrained vector space
$v$ is a vector of length $n$, where $v_1 = 1$ and every element $v_i \in [0,1]$
$w = \| v \|_1^1 = \sum_i |v_i| = \sum_i v_i$
$x = \| v \|_2^2 = \sum_i |v_i|^2 = \sum_i v_i^2$
$y = \| v \|_3^3 = \...
2
votes
0
answers
282
views
Maximizing a convex bounded function of a PSD matrix
Let $f(X)$ be convex and continuous function , with $X$ a PSD matrix.
Assume that under the affine set of constraints $\mathcal{A}(X)=b$ and the convex constraint $f(X)\le1$ there is an optimal, ...
4
votes
0
answers
400
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}...
1
vote
0
answers
234
views
Asymptotics to Taylor expansions?
I posted a question on MSE about approximating Taylor series but Despite a bounty I did not receive any answers or comments.
Maybe you guys can help.
https://math.stackexchange.com/questions/1440931/...
0
votes
1
answer
117
views
How to compute the direction of slowest ascent from the minimum of a strongly convex function?
Consider a twice differentiable strongly convex function $f:\mathbb{R}^n \rightarrow \mathbb{R^+}$ that attains its minimum value at the point $x^*$. I am wondering if one can compute a direction of ...
2
votes
1
answer
82
views
Calculating the Upper Bound on the Sphere Radius of Knotted Channel Surfaces
This question is motivated by trying to determine the upper bound on the thickness of a rope of fixed length (w.l.o.g. $2\pi$), with which a knot of given topology can be realized under the further ...
5
votes
1
answer
140
views
How does one go from convexity to submodularity?
If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...
5
votes
2
answers
457
views
convert a special case of nonlinear fractional programming into a convex problem
Is it possible to convert a fractional problem (maximization) with objective function equal to the ratio of a concave function and convex function ? This question sound impossible but I have read this ...
1
vote
0
answers
129
views
Optimization question: maximize quadratic objective with semidefinite constraints
I recently encountered the following optimization problem:
$\max \|AX\|_F^2$
subject to: $X\succeq0$ and $Xb_i\leq c_i$ for a collection of $T$ conditions: $i=1,\ldots,T$.
Matrices $A$ and $X$ are ...
7
votes
2
answers
3k
views
Quadratically constrained linear program (QCLP) over $x$ with the linear constraint $x = Az$
I have a problem that looks very much like a norm-constrained linear program, but with an extra constraint that is unusual for me. The problem is the following. Given a matrix $A$ and a vector $w$,
$$...
5
votes
1
answer
180
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
2
votes
2
answers
257
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 ...
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) ...
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.,...
5
votes
2
answers
349
views
Discrete optimization problem
Suppose you had $N$ many fixed points $X_1, X_2, ..., X_N$ in some Euclidean space $R^d$ and from these coordinates you had to choose $n$ many of them ($n \leq N$ also being fixed) to form a subset $S$...
2
votes
0
answers
175
views
Why hexagons? The maximal minimum of a sum of cosines on the plane with frequencies on the unit circle
We wish to maximize the minimum of a weighted sum of cosines in the plane, when the frequency components are on the unit circle. Formally:
$$\max_{\{ a_i,\theta_i,\phi_i \}_{i=1}^{N} } \min_{(x,y) \...
4
votes
1
answer
817
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 + \...
2
votes
1
answer
573
views
Maximal minimum for a sum of two (or more) cosines
Please prove (or disprove, and give the correct answer):
$$2 =\mathrm{argmax}_{r\geq 1}\min_{x\in \mathbb{R}}\left[\cos\left(x\right)+\cos\left(rx\right)\right]
$$
In other words, find $r \geq 1$, ...