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
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
61 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
131 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
164 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
205 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
86 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
110 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
368 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
172 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
87 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
90 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
84 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
979 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
228 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
324 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
102 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
486 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
79 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
66 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
442 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
71 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
378 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
481 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. ...
1
vote
0answers
53 views

energy computation for BVP with Dirichlet boundary conditions

I am solving quadratic minimization problem \begin{align} \min_{x}\ \frac{1}{2} x^T A x -b^T x, \end{align} where matrix A results from discretization of Laplacian by FEM method, subjected to ...
7
votes
1answer
3k views

What are the differences between the different gradient-based numerical optimization methods?

I am interested in the specific differences of the following methods: The conjugate gradient method (CGM) is an algorithm for the numerical solution of particular systems of linear equations. The ...
0
votes
1answer
53 views

Efficient search strategy in a monotonic boolean function wherein the probability of solution location is known apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
3
votes
1answer
60 views

Linear programming with stochasticity?

Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution. Now, I would like to solve the same problem but with stochasticity ...
2
votes
1answer
81 views

Is a B-spline curve uniquely defined by one set of coefficients?

Let $C(u)$ be a B-spline curve depending on the parameter $u\in[0,1]$ $C(u) = \sum_{i=0}^n c_i \, B_i(u)$ with $n+1$ coefficients $\{c_i\}$ and B-spline basis functions $\{B_i(u)\}$. Edited based ...
1
vote
0answers
59 views

Optimal synthesis of crank–rocker linkages

I need help programming a script, in MATLAB, that for assigned values compute the optimal transmission angle of a crank-rocker mechanism. The parameters are: $L$: crank's angle of oscillation, for ...
1
vote
0answers
186 views

Constrained optimization: Stationary point vs. Nash point

1s question: definition of stationary point for constrained optimization As far as I know, a stationary point of a constrained optimization problem is a stationary point of the Lagrangian (that has ...
1
vote
1answer
159 views

Computing preconditioner for a non-linear conjugate gradient implementation

Consider the following steps for the $i$-th non-linear conjugate gradient iteration, in the context of 3D electromagnetic inversion, and as discussed in (Newman and Boggs, 2004): (1) set $i = 1$, ...
1
vote
1answer
1k views

How Jacobian matrix helps optimization faster?

I tried some python optimization functions and some of them needed Jacobian matrix prior for faster convergence. I understand Jacobians are basically transformation matrices that data from one space ...
6
votes
1answer
92 views

Intersections of supports constraint

Let $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ and $\text{supp}(\mathbf{x}) \subset \{1,2,...,n\}$ denote the set of indices such that $\mathbf{x}$ is non-zero. What type of optimization problem can ...
10
votes
2answers
399 views

Eigenvectors of a small norm adjustment

I have a dataset that is slowly changing, and I need to keep track of eigenvectors/eigenvalues of its covariance matrix. I've been using scipy.linalg.eigh, but it'...
1
vote
0answers
121 views

Solve scalar quadratic equation

I am implementing a Trust-Region method using Dogleg for the search direction defined as $\tau p^U$ for $0 \leq \tau \leq 1$ and $p^U + (\tau -1)(p^B-p^U)$ if $1 \leq \tau \leq 2$. To compute $\tau$ ...
1
vote
3answers
106 views

Is it possible to use both the absolute value and the actual value of a variable in a linear objective function?

I have an optimization problem that I'm trying to cast as a linear program. However, I have an objective function of the form $$\begin{array}{ll} \text{maximize} & a_1 x_1 - a_2 \lvert x_1\rvert\\...
1
vote
0answers
149 views

Search direction for CG method

I am studying optimization methods and I was able to understand and derive the search direction $$ p_k = r_{k-1} + \beta p_{k-1} $$ for Conjugate Gradient Method, with $$ \beta = -\frac{p_{k-1}^...
1
vote
1answer
184 views

Trouble getting steady-state solution by solving system of nonlinear algebraic equations in MATLAB

Background I have a stiff system of 6 ODEs, represented in MATLAB as follows: ...
4
votes
1answer
159 views

zero terminal value of the adjoint based optimal control

I have been pondering about this issue for some time... Say, I want to minimize a costfunctional $$ \tilde J(u) = J(v(u),u) = \frac 12 \int_0^T (v-v_0)^2 + \alpha u^2 dt $$ subject to $$ \dot v = v^2 ...
0
votes
1answer
244 views

Decrease execution time using openMP

I have this method which computes the Fibonacci function: ...
1
vote
1answer
271 views

Compressed sensing: $\ell_0$ “norm” vs $\ell_1$ norm

Suppose we have a very efficient way to perform $\ell_0$ "norm" compressed vs $\ell_1$ norm compressed sensing. Specifically, $\ell_0$ "norm" compressed sensing is $$\eqalign{ & \min \quad {x^T}...
0
votes
1answer
283 views

Line search bracketing for proximal gradient. Is it good idea?

Maybe my question is obvious but i cannot find any good source which answers it I trying to learn about proximal gradient. One thing which is not clear for me is particular algorithm for line search. ...
1
vote
1answer
146 views

Gaussian geometry optimisation: molecule is getting dissociated into sub group?

I was trying to optimise CdSe (Cysteine) molecule using a semi-empirical method in Gaussian 09 (and gaussView) for a preliminary study of quantum dots. But it seems as the number of iterations ...