Questions tagged [nonlinear-optimization]

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

233 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
274 views

$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan

There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....
8
votes
0answers
184 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 ...
7
votes
0answers
166 views

Concavity of product and ratio of sums

Apologies if this question is not appropriate for MathOverflow. I have asked at Math.StackExchange without success. Consider the function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ defined as $$ f(x)=\...
7
votes
0answers
389 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
210 views

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
6
votes
0answers
238 views

Concavity of a function implicitly defined by a polynomial

Consider the following system of $n$ equations: \begin{equation}f_j^2 = x_j^2\sum_{i=1}^n A_{ij} f_i \tag{$\star$} \end{equation} where $A_{ij}\geq 0$ are known constants and where $x_j>0$ for ...
6
votes
0answers
71 views

Bounding volume of cell in complement of zero set

I am given an integer polynomial $f \in \mathbb{Z}[X_1, \ldots, X_n]$ of bounded degree and bounded coefficient size. The polynomial's zero set partitions $\mathbb{R}^n$ into cells. What I am looking ...
5
votes
0answers
144 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 ...
5
votes
0answers
384 views

Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty). For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$. Given some $1\leq s < d$, consider ...
4
votes
0answers
74 views

Minimizing the largest eigenvalue of matrix product

Let $A\in\mathbb{C}^{m\times n}$, $B\in\mathbb{C}^{n\times k}$, $C\in\mathbb{C}^{k\times m}$ be given complex matrices. The objective of the optimization problem is \begin{equation} \mathop {\arg \min ...
4
votes
0answers
221 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 ...
4
votes
0answers
263 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)=\...
4
votes
0answers
212 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; $...
4
votes
0answers
205 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 ...
4
votes
0answers
213 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 ...
4
votes
1answer
491 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 ...
4
votes
0answers
609 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-...
4
votes
0answers
244 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
0answers
364 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}...
4
votes
0answers
220 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.,...
4
votes
0answers
188 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,\...
3
votes
1answer
50 views

Numerical scheme for convex optimization

Given $(e_n)_{-N\le n\le N}\in\mathbb R^{2N+1}$ and $-1<x<1$, solve \begin{eqnarray} &&\max_{(q_n)_{-N\le n\le N}\in\mathbb R^{2N+1}_+}~ \sum_{n=-N}^N (e_n-\log(q_n))q_n \\ \mbox{s.t.} &...
3
votes
0answers
97 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. ...
3
votes
0answers
85 views

Convex optimization upper bound for a non-linear optimization

Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem? \begin{align} \max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
3
votes
0answers
45 views

Convergence of iteration of a convex program

Let $\mathbf{V} \in \mathbb{R}_{+}^{n \times m}, \ \ \mathbf{E} \in \mathbb{R}_{+}^{n \times m}$, with $\mathbf{V} \mathbf{1}_{m} = \mathbf{1}_{n}$ and $\mathbf{E}^{T} \mathbf{1}_{n} = \mathbf{1}_{m}$...
3
votes
0answers
239 views

How can we solve this kind of saddle point problem?

I'm trying to solve a saddle point problem of the following form: Let $(E,\mathcal E,\lambda)$ be a measure space; $p$ be a probability density on $(E,\mathcal E,\lambda)$ and $\mu:=p\lambda$ $W$ be ...
3
votes
0answers
197 views

Maximize an $L^p$-functional subject to a set of constraints

Let $(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces $f\in L^2(\lambda)$ $I$ be a finite nonempty set $\varphi_i:E'\to E$ be bijective $(\mathcal E',\mathcal E)$-measurable ...
3
votes
2answers
221 views

Looking for a very particular kind of non-convex functions

I want some examples (hopefully parametric families!) of non-convex functions which satisfy the following properties simultaneously, It should be at least twice differentiable. It should have a ...
3
votes
0answers
97 views

Dependency of the Wasserstein distance on the parameter: a differential perspective

Let $\mu(dx)=\sum_{i=1}^np_i\delta_{x_i}(dx)$ and $\nu(dy)=\rho(y)dy$ be two probability measures on $\mathbb R^d$. Consider the $2-$Wasserstein distance below: $$W_2(\mu,\nu)^2 \quad := \quad \inf_{\...
3
votes
0answers
116 views

Finding a mixture of 1st and 0'th order Markov models that is closest to an empirical distribution

I am interested in finding the distribution "$p^*$" closest to an empirical distribution $\hat{p}$ where $p^*$ is a mixture of first and zeroth order Markov models. That is, I want to find $$ p^* = \...
3
votes
0answers
494 views

Can a quadratic matrix inequality constraint be convex?

I have an optimization problem with a semi-definiteness constraint: $$ N \preceq 0 $$ where the entries $N^{AB}$ of the matrix $N$ are defined through $$ N^{AB} = \sum_{i,j} x^i M_{ij}^{AB} x^j $$ The ...
3
votes
0answers
88 views

Are there scenarios under which feasibility bilinear programming is easy?

Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
3
votes
0answers
202 views

Constrained optimization with a Proportional-Integral-Derivative (PID) controller

My engineering colleagues have devised an interesting approach to equality-constrained optimization. I.e. they wish to solve the problem $\min_x f(x)$ subject to the constraint $g(x) = 0$ where $f, g ...
3
votes
0answers
91 views

The complexity of an optimization problem involving sum of binomial coefficients

I'm just new to this community. So please forgive me if the question is not properly asked. I would like to get the natural number e such that the following function can be minimized: $f(e)=\frac{b}{...
3
votes
0answers
198 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{...
3
votes
0answers
794 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}\| $$ $$ \...
3
votes
0answers
199 views

existence of optimal control

I'm looking for an existential result in optimal control for the following class of problems: Given $T > 0$, $\bar x, \hat x\in\mathbb R^d$, an instantaneous cost function $c:\mathbb R^d\times \...
2
votes
0answers
97 views

Existence and uniqueness of solution of a nonlinear system

I need a proof of the following result to calculate a Nash equilibrium in the Showcase Showdown game. For all $n>1$, the system of equations $$\left\{ \begin{aligned} (1+e^{x}(-1+x))^{n-2}&=\...
2
votes
0answers
44 views

Continuum of Lagrange multipliers, duality gap, and minimax theorem

Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
2
votes
0answers
105 views

Optimization of functionals with constraints

I have a minimization problem as follows: $\min\left( \int_0^1\int_0^1\beta(t)\beta(s)G_1(t, s)dtds\right)^{1/2}+\left( \int_0^1\int_0^1\beta(t)\beta(s)G_2(t, s)dtds\right)^{1/2} $ $\texttt{s.t.}\;\;\;...
2
votes
0answers
105 views

Condition under which the Clarke's subdifferential is locally Lipschitzian

Given a locally Lipschitz continuous function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ and closed set $$\Omega =\left\lbrace x \in\mathbb{R}^n \ |\ f(x) \leq 0 \right\rbrace$$ such that f is semi-...
2
votes
1answer
67 views

Does this non-negative function, with No stationary points, have only descend directions close to a constraint set?

Suppose $P: \mathbb{R}^n \rightarrow \mathbb{R}_{\ge 0} $ is differentiable map, with $P(x) = 0 \ \forall x \in \mathcal{X}$ and $P(x) > 0 \ \forall x \in \mathcal{X}^c$. Further, suppose $P$ has ...
2
votes
0answers
62 views

Monotone rearrangements of function, constrained optimization in $\mathcal{L}^p$

By $\mathcal{S}$ let us denote the set of such step functions $f:[0,1]\to [0,1]$ that additionally satisfy: $$\forall_{ x>\frac{1}{2}} \ \ \lambda\Big(f=x\Big) \ = \ x\cdot \Big[\lambda\Big(f=x\Big)...
2
votes
0answers
60 views

Global minimum of sum of a non-convex and convex function, where minima of the non-convex function can be found

I'm interested in finding $\arg\min_{x \in X} (f(x) + \lVert x\rVert_2^2)$ where $X$ is a $[0,1]^n$, $f$ is Lipschitz but non-convex and we already have a procedure to find some $x^* \in \arg\min_{x\...
2
votes
0answers
54 views

Minimizing a certain norm of the identity operator on $\mathbb R^2$

$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
2
votes
0answers
45 views

Which algorithm to optimize this problem?

I do need to find coefficients of a parametric model given observations, and I was wondering which algorithm I should use. The problem is as follows. I have a set of values $\mathbf x_i = (x_{i,1},\...
2
votes
0answers
39 views

A question about strong slopes (nonsmooth analysis)

Context. I'm reading the manuscrip "Nonlinear Error Bounds via a Change of Function" by Dominique Azé and Jean-Noël Corvellec (J Optim Theory Appl 2016), and I'm having a hard time ...
2
votes
0answers
67 views

Sparse signal recovery (nonlinear case)

Let $K \subset \mathbb{R}^n$, it may be that $K$ is "very thin" (e.g. $K$ is a $k$-dimensional affine subset of $\mathbb{R}^n$, with $k \ll n$). I'm interested in the case where $K$ is ...
2
votes
0answers
25 views

Numerical algorithms for geodesically convex optimization

I want to solve a minimization problem of the form $\inf_{x \in M} f(x)$ where $M$ is a Hadamard manifold and $f$ is geodesically convex (but not differentiable). Since I know that in general a ...
2
votes
0answers
164 views

How to sweep the leaves efficiently?

A cleaner, denoted by $P$, aims to sweep $n\ge 1$ leaves that appear one by one in a courtyard modeled by a compact set $D\subset \mathbb R^2$. Denote by $x_0$ the initial position of $P$ and by $v>...

1
2 3 4 5