Questions tagged [nonlinear-optimization]

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

202 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
269 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
177 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
158 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
357 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
205 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
99 views

another extremal property of regular polygons

$\newcommand{\R}{\mathbb{R}}\newcommand{\D}[1]{\Delta_{#1}}\newcommand{\set}[1]{\{#1\}}\newcommand{\abs}[1]{\lvert#1\rvert}\newcommand{\E}{\mathbb{1}}$ In 1984 S.D.Berman, a Soviet mathematician, ...
6
votes
0answers
227 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
188 views

Solving a linear program, but over the unit sphere

I want to solve a linear program but with a subset of the variables taken from a unit sphere. That is, given fixed $\textbf{c} \in \mathbb{R}^{n}$, $\textbf{A} \in \mathbb{R}^{m \times (n+k)}$, I want ...
5
votes
0answers
380 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
184 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
25 views

Criterion for optimality in two-step optimization procedure

Fix $n\in \mathbb{N}$ with $n>1$, let $X$ be an infinite-dimensional topological vector space and suppose that one is given: continuous functions $F_0,\dots,F_n:X\rightarrow [0,\infty)$ for which $...
4
votes
0answers
257 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
209 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
165 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
193 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
443 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
572 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
135 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 ...
4
votes
0answers
239 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
358 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
207 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
186 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
0answers
235 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
194 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
0answers
87 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
336 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
86 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
192 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
85 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
196 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
743 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
191 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
1answer
115 views

Optimal function existence? what is it?

It's a problem abstracted from a real engineering project. I want to find the best curve $y=y(x)$, $x \in [0,1]$: $y$ doesn't have to be a continuous function. The constraint is $$ L=\int_{0}^{1} \...
2
votes
0answers
44 views

Zeroth order method with near-optimal rate that works in practice?

I want to find a ZO (zeroth-order, i.e. no access to gradient) algorithm to minimize a strongly-convex deterministic objective (say, as a sum of smooth and nonsmooth proximable functions). I want such ...
2
votes
0answers
45 views

Convergence of Quasi-Newton method with fixed derivative

Consider the Newton iteration $x^{(k+1)} = x^{(k)} - DF( x^{(k)} )^{-1} \cdot F( x^{(k)} )$ to find a zero of a function $F : \mathbb R^k \rightarrow \mathbb R^k$. If we freeze the first derivative,...
2
votes
0answers
125 views

Can we conclude $\sup_g\int f_1g\le\sup_g\int f_2g$ from $\int f_1\le\int f_2$ in this situation?

Disclaimer: Please bear with me, the question isn't as complicated as it looks like, but I wasn't able to find any simplification for which no counterexample comes to my find. Let $(E,\mathcal E,\...
2
votes
0answers
94 views

Maximization of an integral functional over a closed convex set

I want to maximize $$F(w):=\sum_{1\le i,\:j\le2}\int\lambda^{\otimes2}({\rm d}(x,y))\left(w_i(x)f_j(x,y)\wedge w_j(y)f_i(y,x)\right)g_{ij}(x,y)$$ over the closed convex set $$S:=\left\{w\in{\mathcal L^...
2
votes
0answers
90 views

Continuity of a constrained parameterized convex optimization problem

Consider the parameterized optimization problem: \begin{align} \boldsymbol{s}(p)= &\arg \min_{ \boldsymbol{x}} \quad g( \boldsymbol{x})\\ \text{s.t. } & \boldsymbol{A}(p) \textbf{x} = \...
2
votes
0answers
50 views

Solving Mixed-Integer Non-Linear Optimization Problem

I would like to solve the following optimization problem: \begin{array}{ll} \underset{x_{i}\geq0,\, \pi_{i}\in\{0,1\}}{\text{minimize}} & \displaystyle\sum_{i=1}^n x_i\\ \text{subject to} & ...
2
votes
2answers
160 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 ...
2
votes
0answers
45 views

Optimization with bounds on the control and its derivative

I would like to understand the following optimization problem. Let $F(t,x)$ be a continuous function defined on $[0,1]\times [0,1]$, which is increasing in $t$ and convex in $x$ (I have in mind $F(t,x)...
2
votes
0answers
204 views

Multidimensional Newton-Raphson

I have a system of $n$ rational functions of degree $d$, $f_1, \ldots, f_n$ in variables $x_1, \ldots, x_n$, i.e. $\forall i, f_i = p_i/q_i$ where $p_i, q_i$ are multivariate polynomials of degree at ...
2
votes
0answers
67 views

Gradient Descent with derivative constraints

tl;dr: I need bound results for the derivative of some big honking function. tfa: I am trying to solve an optimization problem: Find a parameter vector $\theta$ so that $\sum_x \log f(\theta, x) \...
2
votes
0answers
93 views

Fixed point of dynamic system

Let $F(\cdot, \cdot)\colon \mathbb{R}^n \times \mathbb{R}^n\rightarrow \mathbb{R}$ be a bivariate and nonnegative function. Suppose $F(x,y)$ is not convex with repect to $x$ or $y$. Moreover, asusme $...
2
votes
0answers
328 views

Matrix optimization of a random quadratic form

I am interested in maximizing a quadratic form which looks like $$f(\Sigma) = E(\operatorname{trace}(SJ)) = E(1^{\top} S 1)$$ where $J$ is a matrix of $1$'s, $S= \Sigma_{mm} - \Sigma_{mo} \Sigma_{oo}...
2
votes
0answers
80 views

steepest descent with upper bound on steplength

I want to minimize an unconstrained optimization problem using steepest descent algorithm. Now, I want to fix the upper bound (say $\delta$) on the step length of line search i.e. we aren't allowed to ...
2
votes
0answers
131 views

projection of a matrix to the the space such that the diagonal elements are the greatest

Suppose there is a symmetric matrix $A$ in $\mathcal{S}^n$. I would like to compute the nearest symmetric matrix $X \in \mathcal{S}^n$ such that $X_{ij} \le X_{ii}$, $i ,j \in \{1,...,n \}$. In other ...
2
votes
0answers
104 views

Maximization of product over primes

I have the following maximization problem. Let $f(p)$ be a real function on the primes, having values in $(0,1)$. Assume that $Y$ is a given (large) positive number, and that we have the bound $$\...

1
2 3 4 5