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
0
votes
1answer
63 views

Adaptive gradient descent

I want to minimize some multivariable function $\Delta(\alpha, \beta)$. I know that this function has a zero point, $\Delta(5, 5) = 0$. Starting from some $(\alpha, \beta)$ close to $(5,5)$ (e.g. (4....
5
votes
1answer
474 views

Ways to speed up solving an LP with Google's ortools

I'm having an issue solving an LP of the form: $$\min z = c^Tx$$ $$\text{s.t.}$$ $$Ax \geq b$$ $$x\geq p$$ $1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$ The specific problems I'm running into ...
3
votes
0answers
102 views

Are the No Free Lunch Theorems Useful for Anything?

I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here,...
1
vote
3answers
166 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 ...
1
vote
0answers
37 views

Meaning of “points where the first- and second-order optimality conditions fail”

I am reading a paper that summarizes a set of simulations. Basically, the authors are trying to minimize some function using different optimization algorithms. They conclude: "Our findings point to ...
4
votes
1answer
75 views

Large-scale almost-linear optimization

I'm currently trying to minimize the following function: $$\min_{\mathbf x,\mathbf y,s} \|F\mathbf x-\mathbf a\|_2^2 + \|SF\mathbf y-\mathbf b\|_2^2 + \lambda \|\max(\mathbf x, \mathbf y)\|_1,$$ $$\...
1
vote
0answers
81 views

Sequential Quadratic Programming for Quadratically Constrained Quadratic Programs

A standard Quadratically Constrained Quadratic Program (QCQP) is of the form: $$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x $$ $$ subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{...
0
votes
1answer
94 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 ...
2
votes
2answers
72 views

Find combinations of variables with variable bounds to get summed up to a required value (using Python)

Let's say I have n variables. Each variable has lower and upper bounds. I want to find all suitable combinations of these variables to sum up to a required value. An example with two variables: $$ ...
3
votes
2answers
326 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}\;\; ||...
1
vote
0answers
74 views

Find a vector B that minimizes |W-A*B|

I want to find a candidate vector $B$ that $$\min|(W - A_i * B_i)|$$ $$ a_i > 0,\ A_i=\{a_0,...,a_i\},\ B_i=\{-1,0,1\}^i$$ For example, given $$W = 0.6,\quad A_4 = [0.1, 0.2, 0.4, 0.7] $$ one ...
1
vote
0answers
53 views

Obtaining the lagrangian multipliers in an optimization problem

Suppose we have this simple optimization problem \begin{align*} \underset{x\in V}{\text{min}} &~ f(x) \\ \text{s.t.}& ~x \leq \beta \end{align*} Using slack variables \begin{align*} ...
1
vote
0answers
72 views

Nonlinear global optimization algorithm that can use dynamic programming

I've asked this question on stackoverflow 2 weeks ago, but, judging by zero response, that probably was the wrong forum. Therefore copying it here: Let F0,...,Fn ...
1
vote
0answers
57 views

BFGS convergence problem

I would like first to state that it is beyond my capability to identify whether this is a BFGS issue or a R package problem. I've been doing some mixed logit regression using the R package "mlogit". ...
1
vote
1answer
408 views

Trajectory optimization for smoothness

I want to achieve the following in 2D (and without obstacles): Given start position A and end position B, generate the path between the two points that optimizes a cost function that depends on total ...
0
votes
1answer
125 views

pde-constrained optimization

I'm trying to solve a problem where I have a initial and final distribution of tumor, and my goal is to find the best map of parameters (diffusion and reaction terms) for a reaction-diffusion equation,...
1
vote
1answer
70 views

Solving for $C$ in $Q = YCZ$ using least squares in Matlab

I am trying to solve for the matrix $C$ in $Q = YCZ$ in matlab. I have preliminary results but they don't seem realistic. Here, $Q$ is $n \times m-1$, $Y$ is $n \times p$, $C$ is $p \times m$ and $Z$ ...
1
vote
0answers
49 views

Finding minimum of Wronskian determinant

If I have a partial differentail equation such as $\frac{\partial^2 u}{\partial t^2} + c^2 \frac{\partial^2 u}{\partial x^2}$, with boundary conditions $u(0,t) = 0$ and $u(1,t)=0$, I can solve this ...
2
votes
0answers
377 views

Using C/C++ for Markov chain Monte Carlo (MCMC) methods

I'm working on optimizing the parameters of a mathematical model to fit experimental data, using an existing formula for the likelihood of observing the data given a set of parameter values. At the ...
4
votes
3answers
202 views

How can I use Projected Gradient Descent for this optimization problem with constraint?

Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that $$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
1
vote
0answers
53 views

Algorithm design to filter on 5,000 stocks each of which has 4 months worth of data points

I want to filter on 5000 stocks, each of which has 4 month or more worth of data (>= 500 data points each). my filtering criteria will be based on 8 calculated values from the data points. for example,...
0
votes
1answer
62 views

Why can't we discretize continuous domains in distributed non-convex constraint optimization problems?

Consider a non-convex distributed optimization problem. We have $X$ = a set of $n$ decision variables: $x_i$ where $i=1..n$ and $x_i \in R$, the set of Reals. We have $F$ = a set of $m$ constraint ...
1
vote
0answers
150 views

Linear regression with inequality constraint in Java

I haven't been doing math in years and I'm facing the following problem. I'm trying to implement in Java a linear regression under a set of inequality constraints. Sorry in advance for all the ...
1
vote
1answer
165 views

Robust/Tested Solver for incompressible 2D Euler (Fluid dynamics) Equation

I am trying to locate suitable computational algorithms for a optimization problem that requires repeated solution of transient 2D incompressible Euler equation on a 2D domain (say rectangular). My ...
3
votes
1answer
224 views

Why do active set methods or the simplex method pivot only one variable at a time?

Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
1
vote
0answers
48 views

Selecting n points to have a given mean and covariance

I have a set $N$ points in $d$-dimensional space, $\mathbf{x}_i \in \mathbb{R}^d ~~ \forall i=\{1,2,...,N\}$. How to choose $n$ points from the set such that it maximises $$ f = |\mathbf{S}|^{-n/2} \...
3
votes
0answers
87 views

How to optimize for decay constant in exponential-like function?

I've got a data set of points $M_O .. M_N$ for time points $t_0 .. t_N$, where $N$ is approximately 10-20, and the spacing of time is not uniform (i.e., $t_{i+1}-t_i$ is not constant for all i). It is ...
1
vote
0answers
30 views

3-parameter optimization of a convex function

I am modeling the structure of a crystal and need to find what the "lowest energy structure" is. There are three free parameters (let's say, $a$, $b$, and $c$) to change, and the search space, $E(a,b,...
3
votes
0answers
113 views

Optimization Problem: Minimize the absolute value of a set of points

I have the following optimization problem: Given is a set of $n$ points $x_i, \ldots, x_n$ with $x_i \in \mathbb{C}, \|x_i\| < \infty$. Note that $n$ is usually not large, i.e. $n < 1000$. We ...
0
votes
1answer
71 views

Non linear programming solvers with API for MATLAB?

I'm facing a non-linear programming problem which currently I'm solving with fmincon function of MATLAB. However, I'm not very happy with computation times and solution convergence since it only ...
3
votes
1answer
382 views

Scaling/nondimensionalization for numerical optimization

I have a numerical optimization problem that I am trying to scale appropriately, in order to allow for the solver to achieve faster and more accurate results. I found a paper here that had a short ...
1
vote
2answers
122 views

Factoring a quadratic function

I have a quadratic binary optimization problem of the form \begin{align} &\max x^TQx \cr &\text{subject to }x\in\mathcal{X}\subseteq\{0,1\}^n, \end{align} where $\mathcal{X}$ is the feasible ...
4
votes
2answers
178 views

Literatures on numerical stability of optimisation algorithms

I am curious of whether optimisation algorithms (whatever simplex, active-set quadratic programming, interior point sequential etc.) can fail due to numerical errors and how to avoid them. But I ...
1
vote
2answers
89 views

How can i solve this non-convex multi-variable optimization problem?

I want to solve the following optimization problem: $$\min_{A,B,X} \|Y-AX\|_F^2 + \lambda_1 \|Z-BX\|_F^2+ \lambda_2 \|B\|_F^2$$ $$s.t ~~x_{ij}~ \geq 0$$ in which, $Y$ and $Z$ are data matrices and ...
3
votes
0answers
92 views

Minimize number of rectangles that cover all the points

I have a 2d distribution of moving points with known trajectories represented in a 640x480 image. Here is the initial state: I have to find the minimum number of rectangles with fixed dimensions (...
5
votes
1answer
89 views

$L_2$ projection with integer constraints and prescribed sum

Suppose I am given a vector $v^0\in\mathbb{R}^n$ and integers $k,\ell\in\mathbb{Z}$. Assuming $k$ is close to zero (e.g. $0\leq k\leq5$), is there an algorithm for solving the following integer ...
1
vote
1answer
1k views

Solve a set of multivariate linear inequalities with constraints in Python

I'm trying to implement Dinur-Nissim algorithm and am stuck at how to solve the set of linear inequalities with multiple unknowns and a large number of equations along with constraints. Example: \...
4
votes
4answers
256 views

Find representatives of vector-space in set of vectors?

Suppose I have a multi-dimensional vector space $X$, and a collection of $n$ vectors $\{x_i\}_{i=1}^n \subset X$, which are not evenly "spaced-out" in $X$. I am searching for $m<<n$ of these $...
1
vote
0answers
370 views

Optimizing an error function involving rotation vectors in Python

I'm prototyping a system that finds the 3D pose of a object in a video sequence. For this I minimize a error function involving the rotation and translation of the object as parameters and two sets of ...
0
votes
1answer
111 views

Mixed Integer Nonlinear Programming Problem

There is a problem I want to solve. The function is: \begin{align} &\underset{a,b,\textbf{vec}}{\text{minimize} \text{ }\text{ }\text{ }\text{ } } f=\sum_{i=1}^{b}(\textbf{vec}_i)^{a}\\ &\...
1
vote
1answer
580 views

Sieve of Eratosthenes with minimized memory usage [closed]

Originally sieve of Eratosthenes requires a lot of memory. This algorithm is my attempt to limit the memory usage. In fact it requires ln(N) memory (for each found prime number we keep last crossed ...
5
votes
0answers
81 views

Minimize interesting objective function with knowledge of gradient nonlinearity?

I plan on using a Quasi-Newton method (L-BFGS) to minimize a non-linear objective function. $$ f: \mathbb{R}^n \rightarrow \mathbb{R}$$ The gradient is kind of interesting: as the values of the ...
1
vote
0answers
68 views

Minimizing the products of variables

My problem Maximize $$\min_{i} \{\ c_i \cdot \prod_{j \in A(i)} {x_{j}} \prod_{j \in B(i)} {y_{j}} \} $$ Subject to \begin{align} &\sum_{j \in C(k)} x_{j} = 1,\ \forall k \\ &l \leq x_{j}...
0
votes
1answer
51 views

Maximize sum(AI) for matrix A and any permutation of identity matrix I

I have a random binary matrix $A$ $$ A=\left[\begin{array}{c c c c c}0&0&0&0&1\\0&1&0&1&0\\1&1&1&1&0\\0&1&1&0&0\\1&0&1&1&...
1
vote
1answer
153 views

How can I solve on a computer a large projection problem with redundant constraints?

This question is the essence of this one. After we remove all the cruft, we can recast it as follows: Problem: Given $b \in \mathbb{R}^n$, $C\in \mathbb{R}^{n\times m}$, and $g\in \mathrm{Range}(C^...
0
votes
1answer
451 views

Derivative chain rule

Define a sequence $(\mathbf{y})_{i=0}^N$ in $\mathbb{R}^n$ such that: $$\mathbf{y}_{k+1} = \mathbf{y}_{k} + \lambda \nabla_\mathbf{y} E(\mathbf{y}_k,\mathbf{w}), \quad k=0,1,\ldots,N-1,$$ where $\...
3
votes
0answers
199 views

Optimal Control using Dynamic Programming - Optimizing for Furthest Distance

So I have been investigating a problem to get a glider with control of its elevator to fly as far as possible from any given initial state. To keep this simple, we will view this in 2D space with the ...
3
votes
1answer
72 views

Solving multiple least-square problems with the same constraints

The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin): $$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$ where the parameters of the ...
2
votes
1answer
439 views

What is the most intuitive explanation for the concepts of weak local minimizer, strong local minimizer and isolated local minimizer?

Reading Nocedal's book on optimization, I came into the concept of local minimizer, which is a well-known concept in numerical optimization. However, I think I am having a rough time trying to come up ...
3
votes
2answers
556 views

Quadratic programs with rank deficient positive semidefinite matrices

Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...