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

learn more… | top users | synonyms (1)

6
votes
0answers
61 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
163 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
185 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
151 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: ...
3
votes
0answers
105 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 ...
3
votes
0answers
82 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 ...
3
votes
0answers
273 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$ ...
2
votes
0answers
47 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
83 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
152 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
197 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
28 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
72 views

Minimize Product of Sums of Squared Distances

The Question Given two sets of vectors $S_1$ and $S_2$,we want to find a unit vector $s$ such that $$\{\sum_{u\in S_1}(\|u\|^2-\langle u, s \rangle^2)\} \cdot \{\sum_{v\in S_2}(\|v\|^2 - \langle v, ...
1
vote
0answers
37 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
48 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
32 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
42 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
72 views

Maximizing the “uniformity” of a probability measure, with constraints, via path length minimization

Background I want to find a probability measure for a continuous random variable, subject to moment constraints, that is maximally "uniform", as defined below: Definition: Maximally Uniform ...
1
vote
0answers
38 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
65 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
272 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
145 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
132 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
442 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
227 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
20 views

Interior point V.S sqp algorithm for large scale optimization

I have an large scale optimization problem that works with fmincon solver within sqp algorithm. But it is so slow. However, ...
0
votes
0answers
78 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Constrained Optimization Problem Is is possible to describe, and locate efficiently, the maxima of the function $f$, as described below in the parameters $\mathbf{x} = (x_1,...,x_m)$. The constraints ...
0
votes
0answers
58 views

Can this equation have an explicit solution?

Given $n > 0$, $0 \leq i \leq n$ is an integer, $D = diag(d_1, \dots, d_n)$ is positive definite, $e_i$ is the $i$th column of a $n \times n$ identity matrix, $u \in R^n$ such that $B = D + u * ...
0
votes
0answers
17 views

Is it possible to design an algorithm an optimization problem with non-convex and coupled constraints, using decomposition methods?

Recently, I am working on an optimization problem in wireless networks. I formulate the problem to be an optimization problem with non-convex and coupled non-linear constraints. And I want to design a ...
0
votes
0answers
20 views

Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...
0
votes
0answers
100 views

How to decide a value of learning rate for Stochastic Gradient Descent?

I'd like to know how to decide a value of learning rate for Stochastic Gradient Descent (SGD), such as $\eta$ on the following parameter update iteration equation, $w_{i+1} = w_i + -\eta \nabla ...
0
votes
0answers
64 views

Specific optimization problem solution procedures

Is there a standard procedure to solve following two optimization problems? $$\mathsf{Problem\mbox{ }I}:\mbox{ }\min_{A\in\{0,1\}^{n\times n}:rk(A)=r}\mbox{ }\max_{R,S\in\Bbb R^{n\times ...
0
votes
0answers
28 views

non-coherent estimation problem

I have the following signals $$\left[\begin{array}{c} y_{mn} \\ y_{nm}\end{array}\right] =\left[\begin{array}{c} x_{n} \\ x_{m}\end{array}\right]h_{nm} +\left[\begin{array}{c} e_{mn} \\ ...
0
votes
0answers
60 views

Best s-term approximation and unit balls in weak $\ell^p$ norm

In the book "A Mathematical Introduction to Compressive Sensing" by Foucart and Rauhut there is the following asymptotic estimate at page 332, equation (11.1): $$\sup_{\mathbf{x}\in B^N_{r,\infty}} ...
0
votes
0answers
34 views

How can be a conservative field constraint be efficiently implemented in a continuous optimization problem?

Suppose we have the following continuous optimization problem: $$ \underset{x}{\mathrm{minimize}}f\left(x\right) $$ subject to $$ \exists X:\nabla X=Jac\left(X\right)=x $$ where $f$ is a function ...
0
votes
0answers
27 views

Optimization problem involving an entrywise function

Let $X$ a $n\times p$ real-valued matrix and $Y$ a $p\times q$ real-valued matrix. Let $\phi:\mathbb{R} \to \mathbb{R}$ a function. What is the appropriate way to deal with the following optimization ...
0
votes
0answers
56 views

Convergence of Coordinate Descent / Alternating directions

My question regards this method http://en.wikipedia.org/wiki/Coordinate_descent, where at each step a function $f$ is minimized along one coordinate axis (or block of coordinates). Assume that $f: ...
0
votes
0answers
46 views

minimizing concave function

I am interested in using the algorithm of Harold Benson described in his 1991 paper: "A Branch and Bound-Outer Approximation Algorithm for Concave Minimization over a Convex Set". In the paper, he ...
0
votes
0answers
25 views

Recursively calculate Tikhonov regularizer in b-spline objective function

I'm trying to write a program to calculate cubic b-spline based on set of inputs. But I can't figure out how to calculate value of Tikhonov regularizer. My b-spline function is this: I have ...
0
votes
0answers
54 views

Finding gradient of an optimization

I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me? Assume that we have an optimization ...
0
votes
0answers
53 views

Solution of a nonlinear system of two equations

Given the matrix $A_{M,N}$ with $N\gt M$, the vector $y$, I have to find the vectors $x$ and $u$, satisfying the following equations: $$D(x)x=A^Tu$$ $$y=Ax$$ where: $$D(x) = \left| \begin{array}{ccc} ...
0
votes
0answers
43 views

A Optimization problem using co-ordinates of joint numerical range.

Let $\mathbf{A}_1,\dots,\mathbf{A}_L$ be $N\times N$ hermitian matrices. Define the mapping from the $N-$dimensional unit sphere to $\mathbb{R}^L$ as \begin{align} ...
0
votes
0answers
77 views

Complexity of turning a d-degree polynomial to 2-degree polynomial

For a very simple example, $(1+x)^4=x^4+4x^3+6x^2+4x+1$ is a 4 degree polynomial, and I want to change it to a 2-degree polynomial by add more variables, for this example, we can simply let $y=x^2$, ...
0
votes
0answers
103 views

Modifying a QP to incorporate more constraints

Consider the following problem: $$\min \sum_{i=1}^n (Y_i - Z^{(i)})^2 \\ \text{subjected to}~ \epsilon_k^{\top}(X_j-X_k) \leq Z^{(j)}-Z^{(k)} ~ \forall k,j = 1 \ldots n. $$ where $\epsilon_1, ...
0
votes
0answers
71 views

Big eigenvalues of a special stochastic matrix

Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq ...
0
votes
0answers
58 views

functional maximization

Define a functional space of functions of the form $F(t)=p_1 exp^{-\mu_1(\delta-t)}+p'_1 (1-exp^{-\mu_1(\delta-t)}))$. $p_1,p'_1,\delta,\mu$ are parameters in [0,1] and trivially, variation of these ...
0
votes
0answers
55 views

Minimizing inside a spherical uncertainty region

I am trying to figure out how to solve: $\min_U r_{p}$ where $r_{p}=\alpha^\intercal\omega$ and $U$ is a sphere centered at $\alpha$ with radius equal to $\chi|\alpha|$ . ( $\omega$ is a vector or ...
0
votes
0answers
120 views

Question on non-linear parametric mixed integer program

I am trying to solve a mixed integer minimization problem, where there are a number of parameters, and there are products of parameters with variables appearing in the objective function. I assume ...