Questions tagged [optimization]

This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.

Filter by
Sorted by
Tagged with
5
votes
2answers
908 views

minimization problem: sum of Rayleigh quotients

I would like to find $x$ which minimizes the following equation: $\frac{x^HAx}{x^HBx} + \frac{x^HCx}{x^HDx}$ where A, B, C, D are positive-definite. $x$ is not a very large vector (<1000 elements ...
4
votes
2answers
142 views

Maximization variant of semidefinite programming (SDP)

Consider the following program: $$\max_{\pmb a} \sum_i z_i\\ u.c. \pmb a \pmb P_i\pmb a^\top\geq z_i$$ where $\pmb a \in\mathbb{R}^p$ and the $\pmb P_i$ are all symmetric positive semidefinite ...
3
votes
2answers
2k views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial f(x^*).$ ...
3
votes
2answers
692 views

Low-rank updates in BFGS

I have read this and other threads on this site on BFGS, but I still don't have a clear understanding of what it's meant by low-rank updates. For example, I read the following in this book: The ...
3
votes
2answers
175 views

Optimization of known function with respect to two unknown function arguments

I have a data set, composed of points $(x_i, y_i)$ for $i=1,N$. I also have a known function $F$, which maps these points $x_i$ to $y_i$ as such $F(x_i, a(x_i),b(x_i)) = y_i$, where $a(x_i)$ and $b(...
3
votes
2answers
177 views

polynomial time solvability

Consider the following optimization problem: $Min \qquad C^TX$ S.t.: $\qquad AX=0;$ $x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$ $X=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; j=1,2,......
3
votes
2answers
181 views

Find $\min x^TAy$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$

In the following problem, $A$ is a given $\mathbb{R}^{m\times n}$ matrix: \begin{align} \mbox{minimize}\quad & x^TAy \\ \mbox{subject to}\quad & 1^Tx=1^Ty=1, \\ & x\ge 0,y\ge 0. \end{...
3
votes
2answers
362 views

Knapsack problem with fixed number of elements?

I am looking at an optimization problem that looks like this: $$ \text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\ \text{subject to}\;\; ||...
2
votes
3answers
3k views

How to avoid the round-off errors in the larger calculations?

Now I need to sum up more than one thousands of terms and then make the four-dimmensional integral in my Fortran program. I found that there are some numerical errors. Can you give me some suggestions ...
1
vote
2answers
392 views

What method do you suggest to solve this minimax, quadratic in both variables problem?

I have a problem of the form, \begin{align} minimize_{y} maximize_{x}&\quad x^T y - y^T (B\odot x x^T) y\\ s.t. &x\in [l,u]\\ &Ay=b \end{align} How to efficiently solve this problem? ...
1
vote
1answer
1k views

How to define the derivative for Scipy.Optimize.Minimize

I am trying to use scipy.optimize.minimize to minimise a quadratic objective function: $f(x) =x^\top Q x$. As a start, I have successfully implemented this using the built-in Nelder-Mead Simplex ...
1
vote
1answer
412 views

Feasibility checking

Consider the following optimization problem: $Min\;\;\; CX$ $AX\geq b$ $x_ix_j= x_s x_t\;\;\; i\neq j \neq s\neq t$ $x_j\geq 0;$ Where $A$ is the adjacency matrix and $C$ is a constant vector. ...
1
vote
3answers
177 views

Optimization of a blackbox function

Let's say that we have an objective function $f(\mathbf x,\mathbf y)$ which has the parameters $\mathbf x=[x_1\ldots x_n]$ and $\mathbf y=[y_1\ldots y_n]$. Here, $\mathbf y$ is a blackbox variable ...
0
votes
0answers
31 views

Minimizing the ratio of two specific non negative quadratic convex functions

$F$ is $m\times m$ diagonal, with real non negative elements $D$ is $n \times m$ complex $P$ is $n \times 1$ complex $A$ is $m \times 1$ complex. Minimize $\Gamma(A)$, with respect to $A$. $$\...
0
votes
1answer
95 views

Free access to Xeon Phi clusters

Apologies if this is not the right forum to ask, but there has been a somewhat related question here. I am working on a piece of software (nonlinear constrained optimisation, coded in C++11 and ...
-3
votes
1answer
104 views

1
2