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

learn more… | top users | synonyms (1)

6
votes
0answers
65 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
81 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 ...
5
votes
0answers
178 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 ...
5
votes
0answers
276 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
63 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 ...
4
votes
0answers
177 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
171 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 ...
4
votes
0answers
47 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 ...
4
votes
0answers
160 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: ...
4
votes
0answers
433 views

An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking. These subgradients are (assume $x \in$ ...
3
votes
0answers
153 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}}$ ...
3
votes
0answers
44 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 ...
3
votes
0answers
104 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, ...
3
votes
0answers
131 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
27 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
62 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 ...
2
votes
0answers
53 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 ...
2
votes
0answers
71 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 ...
2
votes
0answers
121 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}\| $$ $$ ...
2
votes
0answers
76 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 ...
2
votes
0answers
68 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, ...
2
votes
0answers
136 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) ...
2
votes
0answers
70 views

Sequence transformations that are entropy invariant

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Define entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$ by ...
2
votes
0answers
99 views

Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...
2
votes
0answers
84 views

Techniques for proving that a set of constraints over the integers are inconsistent

I have a problem which boils down to showing that a set of constraints has no solutions. A simplified version of this constraint system would be the following system: $$ \left\{ \begin{array}{l} ...
2
votes
0answers
171 views

Quadratic optimization with parameter in constraint

Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum. Question: Given a function $q: \mathbb R^{N\times N}\mapsto ...
2
votes
0answers
249 views

Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin

Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them? Background: Thanks to Will Jagy ...
1
vote
0answers
27 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
0answers
32 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 ...
1
vote
0answers
18 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) ...
1
vote
0answers
35 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\} $$ $$ ...
1
vote
0answers
31 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
0answers
169 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 ...
1
vote
0answers
108 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 ...
1
vote
0answers
73 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 = ...
1
vote
0answers
75 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 ...
1
vote
0answers
40 views

Frobenius nearest non-negative Gram matrix of balanced row-sums

Let $W \in \mathbb{R}^{n \times n}$ be any non-negative real symmetric matrix. For $k \leq n$, let $\mathcal{F} := \{X \in \mathbb{R}^{n \times k} \ | \ X \geq 0, X \mathbf{1} = \alpha \mathbf{1}, ...
1
vote
0answers
32 views

Minimizing sum of functions, while keeping their values non-negative

Suppose we have data $\mathbf{x}_i$, $i\in \{1, \ldots, K\}$, and we're trying to find parameters $\hat{\mathbf{\theta}}$ such that $$\hat{\mathbf{\theta}} = \underset{\mathbf{\theta}} ...
1
vote
0answers
113 views

Likelihood convexification

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form: $$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log ...
1
vote
0answers
78 views

modern exposition of exact ground state of classical XY model or Ising model

What is the state of art technique in solving exact ground state of Heisenberg model, meaning minimization of the H terms (hamiltonian) provided infinite spin space? ...
1
vote
0answers
64 views

Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...
1
vote
0answers
44 views

Limiting Entropy of deterministic sequences - 2

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Given $\{a_i\}_{i=1}^m$, let $\mathcal{P}_a$ be limiting distribution ...
1
vote
0answers
47 views

Changing a nonlinear equality constraint into some conic inequality plus rank constraint

If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
1
vote
0answers
68 views

Estimation of part of parameters from an ODE

Suppose, we have an ODE $$ \frac{dy}{dt}= f(t,y;p',a)$$ or alternatively $$ \frac{dy}{dt}= f(t,y;p)$$ where the set of all parameters $p = (p',a)$. We only need to estimate part of parameter set ...
1
vote
0answers
471 views

Subtour Elimination in Travelling Salesman Problem using MTZ

I am trying to formulation a problem similar to a Traveling Salesman with Time Window constraints. To eliminate subtours, I need to use some constraint similar to a generalization of MTZ constraints ...
1
vote
0answers
166 views

Constructing an $\epsilon$-net for a Lipschitz subspace of $L^2$

Let $X$ be a subset of $L^2([0,1])$ which contains only Lipschitz function. Also, the member of $X$ are uniformly bounded $$ |x(t)| < M, \text{ for all $x \in X$ and $t \in [0,1]$}. $$ Let $F: X ...
1
vote
0answers
142 views

Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...
1
vote
0answers
567 views

Solving a system of complex non-linear equations

I have a set of five equations which can be described as follows: $m_{i}=\frac{k_{1}}{(x+a)^{i}} + \frac{k_{2}}{(b+d)^{i}}+ \frac{k_{3}}{c^{i}}$ for i=1 to 5 where $$\eqalign{ ...
1
vote
0answers
233 views

Multiobjective semidefinite programming

Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$. There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is ...
0
votes
0answers
30 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 ...