All Questions
Tagged with nonlinear-programming or nonlinear-optimization
640 questions
2
votes
1
answer
1k
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 ...
- 123
3
votes
1
answer
862
views
Nonconvex optimization problem
I have a nonconvex optimization problem with a linear objective function, a set of linear constraints and a set of nonlinear, non-convex constraints. Is this problem NP-hard? If so, how can I prove ...
- 221
3
votes
1
answer
602
views
Is the feasibility of a system of non-convex quadratic equations and inequations decidable?
I would like to know whether the following problem is decidable.
Given the following system in $x \in [0,1]^n$
$$x^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., k$$
$$x^T Q_j x + r_j \neq 0 \mbox{ ...
- 165
2
votes
0
answers
168
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
1
answer
655
views
A non-convex quadratically constrained quadratic program
$$\begin{array}{ll} \text{minimize} & \beta^{T} A \beta\\ \text{subject to} & \beta^{T} C \beta=1\\ & \beta \geqslant 0\end{array}$$
where $A, C\in \mathbb{R}^{M\times M}$ and $\beta \in ...
- 13
4
votes
1
answer
396
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 ...
- 185
0
votes
0
answers
104
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 |\lambda_2|(M)....
- 105
4
votes
1
answer
128
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 ...
- 489
2
votes
0
answers
242
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
3
answers
188
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 ...
- 251
3
votes
1
answer
2k
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 ...
- 43
5
votes
1
answer
3k
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
1
answer
654
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 ...
- 3
4
votes
1
answer
2k
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 ...
- 41
0
votes
0
answers
189
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 ...
- 221
7
votes
1
answer
422
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 ...
- 840
1
vote
1
answer
220
views
What kind of optimization problem is this?
I come across an optimization problem of the following form.
$$\max {\frac{1+v}{1-u}} \qquad \text{s.t.} \qquad ux^2+vy^2-xy \ge 0, \quad \forall x,y\in\mathbb{R}$$
I do not know much of optimization. ...
- 13
2
votes
0
answers
697
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 ...
- 21
6
votes
2
answers
2k
views
Find minimum-area ellipse which encloses two ellipses
I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...
- 61
0
votes
0
answers
67
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
1
answer
319
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 ...
2
votes
2
answers
293
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 ...
- 121
6
votes
1
answer
1k
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,\ldots,K$ are known, and are positive definite matrices. $\Omega$ also has to ...
- 173
0
votes
1
answer
272
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$ ...
- 1,421
12
votes
2
answers
1k
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 ...
- 23k
5
votes
2
answers
429
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 ...
- 1,421
0
votes
1
answer
165
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, \...
- 41
2
votes
1
answer
1k
views
Can one maximize the spectral norm of a matrix via semidefinite programming?
Consider the following optimization problem:
Maximize $\|X\|_2$, subject to $X$ being Hermitian (or symmetric) and a bunch of semidefinite constraints on $X$. Here, $\|X\|_2$ is the spectral norm of ...
- 1,332
1
vote
1
answer
2k
views
linear objective function, non-linear constraints involving square-root of variables
i am trying to solve a general linear objective function with non-linear constraints. Can someone help me solve this.
Here is an example of one problem i am trying to solve,
minimize $b$
subject ...
3
votes
1
answer
793
views
Does Quadratic Programming get easier when it's described by a diagonal matrix?
Generally, Quadratic Programming solves the problem
$$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$
In this form, Quadratic Programming is ...
- 693
2
votes
2
answers
1k
views
Minimizing product subject to linear constraints
I am looking for a solver that allows me to solve an optimization problem of the form
$$\begin{array}{ll} \text{minimize} & x_1 x_2 \cdots x_n\\ \text{subject to} & \color{gray}{\text{(some ...
- 23
1
vote
2
answers
242
views
what method can I employ to solve this optimization problem which involves \min?
The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\...
- 764
2
votes
1
answer
758
views
An algorithm for checking if a nonlinear function f is always positive
Is there an algorithm to check if a given (possibly nonlinear) function f is always positive?
The idea that I currently have is to find the roots of the function (using newton-raphson algorithm or ...
1
vote
0
answers
784
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{
k_{1}&=\frac{a(x+...
- 209
2
votes
2
answers
2k
views
Solving a system of equations/inequalities that have trigonometric functions on the left-hand side
Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...
- 23
1
vote
1
answer
370
views
A positive semidefinite programming problem
Dear all,
I've got a SDP problem as follows:
$\min_{{\bf H}\succeq0}\quad trace({\bf H}) - {\bf a}^{\top}{\bf H}{\bf b}$,
where ${\bf a}$ and ${\bf b}$ are two constant vectors. May somebody tell ...
- 145
1
vote
0
answers
266
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 ...
- 800
1
vote
2
answers
847
views
maximizing multivariate polynomial
Consider $J = \sum_{i=0}^{N}y_{i-1}x_{i}y_{i+1}$ where $+$ and $-$ in the indices are mod $N+1$. Let $x_{i} = 1 - y_{i} \in \{0,1\}$. What are some of the tools useful and relaxation techniques ...
- 13.9k
-1
votes
2
answers
487
views
Any efficient software/package/toolbox for nonlinear programming for MATLAB
I want to solve a nonlinear programming problem with the objective function being coded as a recursive function in Matlab. I have tried “fmincon”, but it could not get the solution due to large number ...
- 1
9
votes
5
answers
646
views
Software for rigorous optimization of real polynomials
I am looking for software that can find a global minimum of a polynomial function over a polyhedral domain (given by, say, some linear inequalities) in $\mathbb R^n$. The number of variables, $n$, is ...
- 7,836