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

learn more… | top users | synonyms (1)

-3
votes
1answer
73 views

Convert constraint to do convex optimization or use Lagrange multiplier method [closed]

$w_1, w_2, w_3 ... w_n$ are the weights I need to find I have the following constraint: $|w_1| + |w_2| + .. |w_n| <= 5$ That is the sum of the absolute values of the weights has to be less than ...
4
votes
2answers
279 views

Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...
3
votes
0answers
83 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 ...
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
64 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: ...
1
vote
0answers
73 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 ...
0
votes
0answers
49 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 ...
7
votes
2answers
441 views

How to solve such an optimization problem

I encounter the following optimization problem, but I can't solve it. Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find ...
1
vote
1answer
351 views

Levenberg's original article “A method for the solution of certain problems in least squares”

Does there exist any digital copy of the original article (or a transcript) K. Levenberg, A method for the solution of certain problems in least-squares, Quart. Appl. Math. 2 (1944): 164-168? It is ...
2
votes
2answers
306 views

How to fit the parameters of differential equations with known data?

I have the following data from chemical kinetics research to fit the parameters of ordinary differential equations: $$ \left[ \begin{array}{ccccccc} \text{No.}& t & y_1(t)&y_2(t) & ...
1
vote
0answers
39 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 ...
0
votes
0answers
55 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 ...
5
votes
1answer
187 views

optimization problem, any solution?

The objective is as follows: $\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$ $s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$ ...
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
2answers
147 views

Approximate solution to large mixed integer programming problem

What are the available approaches to find an approximate solution to a large mixed integer programming problem? I ran my problem in the Gurobi MIP solver. It can find a feasible solution in ...
2
votes
3answers
357 views

Solving a quadratic matrix equation with non-squared matrix

I was trying to solve the problem of finding the value of a non-squared matrix $T$ ($n \times m$) which solves $$ T^T T = X$$ where $X$ is a symmetric and positive semidefinite $m \times m$ matrix, ...
6
votes
1answer
273 views

Finding a point maximizing the minimal distance to a set of points

Given a set of of $N$ points $\{\mathbf x_i \in \mathcal{S}^d\}_{i = 1, \ldots, N}$, where $\mathcal{S}$ is a set of possible values, how can I find the point $\mathbf x^*$ that maximizes the minimum ...
1
vote
2answers
58 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
144 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
237 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
152 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
255 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
78 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
173 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
307 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$, ...
1
vote
1answer
159 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
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} ...
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
230 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
170 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 ...
1
vote
0answers
278 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 ...
2
votes
2answers
276 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
2answers
159 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
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 ...
3
votes
2answers
1k 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
286 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
196 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 ...
3
votes
0answers
289 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
244 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
418 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
369 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 ...
2
votes
1answer
151 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
136 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
286 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
218 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
73 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
78 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 ...