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

learn more… | top users | synonyms (1)

1
vote
2answers
54 views

Linear Programm with matrix [closed]

Is there a name for problems like this min norm(Cx) Ax = b where C is a matrix and norm is the maximum norm. This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
3
votes
2answers
135 views

QR-Decomposition of matrix valued function

Suppose I have a matrix valued function $$ F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T $$ where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, ...
2
votes
1answer
235 views

How to minimize $-\sum p_b \ln{p_b}$?

Consider multisets of the form $A = \{a_1,\dots,a_n\}$ of integers. Let $q = P(a_i = a_j)$ when $i$ and $j$ are chosen independently and uniformly from $\{1,\dots, n\}$. Let $B$ be the set of ...
4
votes
0answers
150 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: ...
2
votes
5answers
245 views

Distance between two sets

Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem. $$ \min ...
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$, ...
2
votes
2answers
144 views

How to minimize the Bregman divergence on a convex hull spanned from a set of vectors?

everyone. It has been well known that the following minimization problem of a Bregman divergence with linear inequality can be solved by successively projecting the current point to each constraint ...
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
2answers
294 views

Can we decompose a polynomial into difference of convex polynomials?

Given a multivariate polynomial $p(x_1, ..., x_n)$ on $\mathbb{R}^n$, can we always decompose it into the difference of two convex polynomials? i.e., is there a pair of convex polynomials $f$ and $g$, ...
0
votes
0answers
125 views

No Strong Duality In Spite of Slater's Condition

I was reading some course notes here. On Page 8, it says: Note that strong duality holds here (Slater's condition), but the optimal value of the last problem is not necessarily the optimal ...
2
votes
0answers
82 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} ...
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
1answer
195 views

How to find the necessary and sufficient conditions for a non-convex function to be locally convex?

Let $f(X)\geq 0$ be a nonconvex $C^\infty$ function: $\mathbb R^3\to \mathbb R$. Give any fixed $X_0$ such that $f(X_0)=\epsilon^+$, and the level set: ${L}=\{X\in \mathbb R^3:f(X)\leq \epsilon^+\}$ ...
1
vote
1answer
154 views

Lagrange multiplier and semidefinite programming

suppose we have a primal semidefinite programming. for finding its dual we use Lagrange multiplier $w_i$ for each semidefinite constraint. If the Lagrange multiplier be zero for one constraint what we ...
2
votes
0answers
240 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 ...
3
votes
2answers
248 views

Why eigenvectors optimize this orthogonally constrained nonlinear minimization problem?

Given a $p \times p$ positive definite matrix $\Sigma$, why eigenvectors of $\Sigma$, stacked as columns of a matrix $R \equiv [r_1 \, r_2 \, \ldots \, r_p]$, optimize the following orthogonally ...
3
votes
1answer
125 views

Decomposition of a semi-definite matrix into sums of sparse semi-definite matrices

I'll first provide the background. Let $x\in\mathbb{R}^N$ be decomposed into $n$ non-overlapping blocks of variables $x^{(1)},\ldots,x^{(n)}$. We say that $f:\mathbb{R}^N\rightarrow\mathbb{R}$ is ...
1
vote
0answers
141 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 ...
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, ...
3
votes
2answers
990 views

Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
4
votes
1answer
270 views

Finding all local maximum points of a function?

Let ${\boldsymbol \theta}=(\theta_1,\theta_2,\ldots,\theta_n) \in{\mathbb T}^n$ and $P:{\mathbb T}^n\rightarrow {\mathbb R}$ be a function defined on $n$-torus as $$ P({\boldsymbol \theta}) = ...
3
votes
1answer
195 views

Intuition on a certain class of quadratic optimization problems

Let $\mathcal{X} = \{\mathbf{X}\in\mathbb{C}^{d\times d}:\|\mathbf{X}\|\leq 1\}$, where $\|\cdot\|$ is the Frobenius norm. Let $\mathbf{y}\in\mathbb{C}^{d\times 1}$. We are familiar with the following ...
2
votes
0answers
191 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
1answer
240 views

Non-linear 1st order difference equation

I have been trying to solve the following difference equation for some time now : $$u^3(n+1) = a - b\cdot u^2(n) + u^3(n), \qquad a \ne 0 \ne b$$ I have tried various substitutions, simplifications ...
2
votes
1answer
376 views

Finding zeros of a multi-variable nonlinear trigonometric function

I am trying to calculate analytic solution (or locus) of zeros of a very large multi-variable function which is consisted of thousands of nonlinear trigonometric terms. All the variables are real ...
0
votes
1answer
358 views

Nonconvex optimization problem

I have a nonconvex optimization problem. It is actually optimizing a linear objective function over a set of linear constraints and a set of nonlinear, non convex constraints. Is this problem ...
1
vote
1answer
131 views

Is the feasibility of a system of nonlinear, non-convex equations (inequalities) decidable?

I would like to know whether the following problem is decidable. Is the system $x^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., k$ $x^T Q_j x + r_j \neq 0 \mbox{ for } j = k+1, ..., t$ feasible, ...
1
vote
0answers
129 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 ...
0
votes
1answer
256 views

solve non-convex quadratic constrained quadratic programming

$\min_{\beta}\beta^{T} A \beta$ $s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$ Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$ I saw in one paper saying that it could be ...
3
votes
1answer
210 views

Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint

I am wondering what is known about optimization problems of the following type. Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities $$Az≥b,$$ and we ...
0
votes
0answers
70 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 ...
3
votes
1answer
76 views

Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...
2
votes
0answers
149 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
3answers
155 views

Constraint optimization problem for any dimensionality $n>1$.

I am going to post a particular example for the sake of clarity. One needs to maximize a real function $F = a_1a_2 + a_2a_3 + \cdots + a_{n - > 1}a_n + a_na_1;$ with active ...
3
votes
1answer
491 views

The average number of people that can sit on a bench of a given length.

Let me explain what I mean: The width of the average person varies, perhaps with a normal distribution. Given a specific variance, how many people (on average) can sit side-by-side on a bench of a ...
2
votes
1answer
425 views

Maximizing supermodular functions

I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k . I am wondering if anyone can give me more information about a ...
0
votes
1answer
255 views

minimization of a function when the feasible set is an unbounded cone

I have the following semi-infinite programming problem: I need to minimize a strictly convex real-valued function $f:\mathbb R^n\to\mathbb R$ subject to infinite linear constraints. I know in advance ...
2
votes
1answer
326 views

lipschitz constant of a multivariate function

I have a function $f:\mathbb{R}^{50} \rightarrow \mathbb{R}$ and I need to compute the Lipschitz constant of $f$ to solve an optimization problem using a specific algorithm. Does any one have ...
0
votes
0answers
57 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 ...
6
votes
1answer
244 views

Generalization of the equilateral triangle?

I consider points in the two-dimensional plane. An equilateral triangle is a set of three points in the plane which are equidistant. Suppose now I have $n$ points $x_1,...,x_n$. What is the ...
1
vote
1answer
134 views

What kind is this optimization problem

I come across a problem like $\max {\frac{1+v}{1-u}}$ $s.t.~$ $ux^2+vy^2-xy\ge0$ $\forall x,y\in\mathbb{R}$ I do not know much of optimization. What I have done is that $ux^2+vy^2\ge ...
0
votes
0answers
54 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
1answer
168 views

Can one always Decide whether a Systems of Nonlinear Equations with Bilinear terms is Feasible?

I have come to a point in my PhD research were i need to prove that a particular decision procedure is decidable or not. And if i can solve the sub-problem described below, i shall have proved it. The ...
1
vote
2answers
178 views

Convex optimization problem to QPP

Briefly, have the following problem: \begin{equation} \sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\ s.t.\\\\ A \bar x \leq b \end{equation} where $ F( \bar x ) $ is a ...
5
votes
1answer
310 views

Solve equation with matrix variable

I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1...K$ are known, and are positive definite matrices. $\Omega$ also has to be ...
0
votes
1answer
176 views

A certain type of quadratic problem.

I am interested in solving the following equality constrained quadratic (?) problem. \begin{align} \min_{u^{H}u=1}~(u^{H}A_1u) \\\ s.t.~ u^{H}A_2u=0 \end{align} $A_1$ and $A_2$ are $N\times N$ ...
11
votes
2answers
559 views

Quadratic Farkas' Lemma?

The Farkas Lemma says that if a system of linear inequalities implies yet another linear inequality, then this last inequality can be obtained by taking a positive linear combination of the ...
5
votes
2answers
268 views

Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

Consider hermitian positive semi-definite matrices $A_1$ and $A_2$. Consider also positive definite matrices $B_1$ and $B_2$. I want to maximize the minimum of the two Generalized Rayleigh Ritz ratios ...
0
votes
1answer
129 views

Nonlinear matrix equation 2

Solve the following nonlinear equations for $v$ and $w$ $Avv^TAw+Bvv^TBw=\lambda_1v+\lambda_2w$ $Aww^TAv+Bww^TBv=\lambda_1w+\lambda_2v$ $v^Tw=w^Tv=0$ $v^Tv=w^Tw=1$ where $\lambda_1, \lambda_2, ...
1
vote
1answer
325 views

Can you maximize the spectral norm of a matrix in a semidefinite program?

Consider the following optimization problem: Maximize $||X||$, subject to $X$ being Hermitian (or symmetric, if you prefer) and a bunch of semidefinite constraints on $X$. I want to know if this can ...