Questions tagged [nonlinear-optimization]

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

Filter by
Sorted by
Tagged with
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 ...
Max Hamper's user avatar
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-...
Hunter's user avatar
  • 215
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\...
Max Hamper's user avatar
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) +...
Zhongshi Jiang's user avatar
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\...
jonem's user avatar
  • 179
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 ...
Christopher Miller's user avatar
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 $...
user avatar
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$ ...
Sriram Nagaraj's user avatar
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 ...
mycal's user avatar
  • 61
-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?
sjtupuzhao's user avatar
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) ...
Moe's user avatar
  • 11
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 ...
Ron P's user avatar
  • 947
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$ ...
c.Parsi's user avatar
  • 109
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 ...
ccc's user avatar
  • 13
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{...
sjtupuzhao's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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. ...
Michael Fan Zhang's user avatar
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{...
Martin's user avatar
  • 11
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 \...
Bravo's user avatar
  • 519
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,......
zsha's user avatar
  • 121
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 ...
RustyStatistician's user avatar
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 \...
Mark Hubenthal's user avatar
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 ...
Math_manul's user avatar
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 ...
Jack's user avatar
  • 21
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$. ...
BigM's user avatar
  • 1,543
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 ...
user2370336's user avatar
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 ...
YKY's user avatar
  • 508
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 ...
neversaint's user avatar
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{...
gondolf's user avatar
  • 1,487
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}\| $$ $$ \...
phil wang's user avatar
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 = ...
antianticamper's user avatar
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 ...
Samuel Reid's user avatar
  • 1,401
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 = \...
user's user avatar
  • 181
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, ...
Yair Forchevsky's user avatar
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}...
mycal's user avatar
  • 61
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/...
mick's user avatar
  • 703
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 ...
Berk U.'s user avatar
  • 379
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
user6818's user avatar
  • 1,883
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 ...
behrad mahboobi's user avatar
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 ...
yuanz07's user avatar
  • 123
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$, $$...
redfly10's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Justin's user avatar
  • 695
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) ...
Mark L. Stone's user avatar
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.,...
Mark L. Stone's user avatar
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$...
Adam A Allan's user avatar
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) \...
Daniel Soudry's user avatar
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 + \...
the_max's user avatar
  • 41
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$, ...
Daniel Soudry's user avatar

1
9
10
11 12 13