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

learn more… | top users | synonyms (1)

1
vote
1answer
104 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 ...
-1
votes
1answer
47 views

About the critical points of quasi-convex functions

What do we know about the structure of critical points of quasi-convex functions? I am looking for statements like "the critical points of a quasi-convex function are always either a global minima ...
1
vote
1answer
102 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 ...
0
votes
1answer
53 views

Quadratically constrained quadratic programming/optimization involving piece-wise function

I have a quadratically constrained quadratic programming/optimization problem involving kind-of piece-wise quadratic functions $f_n (x_m)=a_{n,m} (x_m-\theta_n)^2$, if $|x_m-\theta_n|<c$; $c^2a_{n....
1
vote
0answers
27 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 ...
1
vote
0answers
28 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 ...
0
votes
1answer
30 views

Limits of argmin ratios and sums

In my research on convergence properties of certain Bayesian methods I have encountered $\mathop{\mathrm{arg\,min}}$ limits of the forms \begin{equation} \lim_{n\to\infty} \mathop{\mathrm{arg\,min}}_{\...
6
votes
0answers
157 views

Analytic expression for the Tsirelson bound of the I3322 inequality?

Finding Tsirelson bounds for Bell inequalities is a well-loved problem in quantum information theory. A famous case where it is still open is for the I3322 inequality. In this paper Pál and Vértesi ...
7
votes
0answers
115 views

Solving matrix equation $X^{-1}=\sum_{i=1}^n D_i X A_i$

Does anybody know an algorithm to solve the following matrix equation? $$X^{-1}=\sum_{i=1}^n D_i X A_i$$ where $D_i$s are diagonal and $A_i$s are symmetric matrices. It would be great to have an ...
0
votes
0answers
39 views

optimize a Quadratic Matrix Programming with multi-spherical constraints

I have got the following quadratic problem restricted on the Cartesian product of Euclidean spheres. $\underset{X \in \mathbb{R}^{n\times 3}}{\text{min}}$ $Q(X) = \frac{1}{2} Tr(X^TA X) + Tr(B^T X)$ ...
2
votes
2answers
99 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
54 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 ...
4
votes
2answers
78 views

About optimization with Renyi divergence

Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form or ...
0
votes
0answers
17 views

Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ...
0
votes
0answers
43 views

Largest instance of highly nonlinear benchmark functions (e.g. Rastrigin function)

What is the largest instance size (number of variables) ever numerically solved for highly nonlinear (continuous, not combinatorial) optimization benchmarks functions, such as Rastrigin, Schwefel or ...
0
votes
0answers
31 views

Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...
1
vote
0answers
31 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 ...
1
vote
1answer
102 views

Why polynomial $\psi^\top(t) A^{-1} \psi(t)$ attains maximum on $[-1, 1]$ at $t = \pm 1$, where $\psi_k(t) = t^k$?

Problem. Let $\psi(t) = (1, t, t^2, \ldots, t^{p-1})^\top$ - a polynomial basis. Suppose there is a matrix $$ A = \int_{-1}^1 \psi(t) \psi^\top(t) dt, \ \text{i.e. } \ A_{ij} = [2 \, | \, i+j] \...
1
vote
0answers
35 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 ...
0
votes
0answers
51 views

About identifying a few diagrams

Please have a look at these beautiful seminar slides, https://math.berkeley.edu/~bernd/coimbra1.pdf Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ...
1
vote
0answers
58 views

Hessian matrix positive definiteness (concavity test) [closed]

I have a rather simple scenario based optimization problem: Maximize $$ Q_1{_s}(A_1{_s}-Q_1{_s}-bQ_2{_s})+ Q_2{_s}(A_2{_s}-Q_2{_s}-bQ_1{_s})-[(Q_1{_s}-K_1)^+ + (Q_2{_s}-K_2)^+]c $$ subject to $Q_1{...
3
votes
1answer
137 views

Global minimum of nonlinear least square

We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem: Minimize $J(x)=\Vert f(x)-z\Vert^2$ subject to box ...
3
votes
0answers
154 views

Can the following system of equations be solved analytically/in a closed form?

From a constrained non-linear maximization problem I obtained the following system of equations: $a_1=\frac{1+a_3-\sqrt{a_2a_3}\sqrt{v_1}}{1+\sqrt{\frac{a_3}{a_2}}\sqrt{v_1}}$ $a_2=\frac{2-a_3-\sqrt{...
0
votes
0answers
175 views

A contractive mapping which I don't understand

Given a matrix $Y$ and a vector $c$ define the following iteration $\hat{c} = f(c)$, where each element of $\hat{c}$ is given by $$\hat{c}_{\ell} = \frac{\sum_k Y_{k,\ell}\frac{1}{|c_{\ell}|^2+|c_{k}|...
0
votes
1answer
112 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 ...
0
votes
0answers
52 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
0answers
130 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
1answer
76 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\...
2
votes
0answers
28 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
0answers
64 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\...
1
vote
0answers
172 views

Minimization of nonlinear integral operator

See also on MSE. For non-negative self-adjoint traceclass operators $0\leq T \leq 1$ with $\mathrm{tr}T^\alpha=N$ on the Hilbert space $L^2(\mathbb{R}^3)$ s.t. $\operatorname{tr}(-\Delta T^\alpha)=\...
3
votes
0answers
49 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
1answer
121 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 $...
0
votes
0answers
23 views

Maximizing modular function subject to supermodular constaint

I'm trying to solve a constrained optimization problem with submodular functions and get some nice properties of the solution. Unfortunately, I think I am in a setting where Topkis' theorem does not ...
0
votes
1answer
109 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
2answers
197 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$, ...
2
votes
0answers
63 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 ...
0
votes
0answers
45 views

Nuclear norm maximization

I am trying to solve a nuclear norm maximization problem: $$\arg \max_{Q \in O(n)} \|WQV^T\|_*$$ where $Q$ is an $n \times n$ orthogonal matrix and $W$ and $V$ are real $d \times n$ matrices. I've ...
-1
votes
2answers
99 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
0answers
21 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) ...
0
votes
0answers
50 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
1answer
87 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
0answers
42 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{...
4
votes
1answer
164 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 + \...
1
vote
0answers
33 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. ...
0
votes
1answer
58 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 \...
1
vote
0answers
30 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{...
2
votes
0answers
86 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
1answer
169 views

Constrained optimization (QCLP) over $x$ with the 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, given a matrix $A$ and a vector $w$, $$ \min_{x \...