Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

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

3
votes
1answer
178 views

Minimizing linear objective on intersection of convex sets

Suppose I wish to solve the following optimization problem: $$ \begin{array}{rl} \min_{\mu\in\mathbb{R}^n} &\mu^\top c\\ \textrm{subject to} & \mu\in C_1\cap C_2\cap\cdots\cap C_k, \end{array} ...
2
votes
2answers
91 views

Question concerning accumulation point

Suppose that we have to find an optimal solution $x^*$ to an optimization problem involving some function $f$, such that $0\in\partial f(x^*)$ where $\partial$ denotes the subdifferential. Let $(x_n)...
3
votes
1answer
136 views

Why are Hamiltonian dynamics used in MCMC?

In Hamiltonian Monte Carlo, Hamiltonian dynamics are used to generate new proposals from the current state. I understand why these dynamics are used as opposed to random walk behavior to generate ...
0
votes
1answer
279 views

Nonlinear integer program with linear constraints

I'm trying to perform inference over a subset of the latent variables of a hierarchical hidden Markov model I built. I've derived the relevant optimization problem, but it's a pretty nasty piece of ...
0
votes
1answer
128 views

Optimization with Yalmip [closed]

I would like to solve in Matlab the following optimization problem $$\begin{array}{ll} \text{maximize} & \bigg\| \displaystyle\sum_{l=1}^{2}\alpha_l \int_{\tau_{m+l-1}}^{\alpha_1\tau_m+\alpha_2\...
1
vote
0answers
71 views

vectorizing optimization or root finding [closed]

I need to find the roots of a function. I am currently using scipy.optimize.fsolve ...
5
votes
0answers
438 views

Precision of ratio constraint in a linear program [closed]

I am trying to solve a LP in which one of my constraints is of the form $$\frac{A(x)}{B(x)} = 1$$ I transform this constraint into a linear one $$A(x) - B(x) = 0$$ However when CPLEX solves the ...
1
vote
1answer
30 views

Parameter identification for regression model

Consider the following regression model : Y = AX + BU where the size of Y is $N \times n$, A is $N \times n$, X is $n \times n$, B is $N \times n$ and U is $n \times 1$. The matrices X,Y and U are ...
4
votes
3answers
2k views

Beating typical BLAS libraries matrix multiplication performance

A dull matrix multiplication algorithm where we use the formula $$C_{ij}=\sum_{k}A_{ik}B_{kj}$$ By literally following this in 3 loops we'll get a very slow program, because we don't utilize ...
3
votes
2answers
309 views

optimization problem. Monte Carlo stochastic method or another one?

I have the following problem, there is an objective function f() depending on 7 variables x=(x1,x2,...x7), so f(x)=f((x1,x2,...x7)) and I want to find the combination of variables that minimize the ...
0
votes
3answers
114 views

Choice of solver/software for global optimisation of cheap black-box function with known derivatives

I am trying to estimate a few unknown parameters of my continuous non-linear PDAE model (simulated through finite-volume method spatial discretisation, and time-stepping through method-of-lines). I am ...
2
votes
2answers
110 views

How to support or contradict a hypothesis on unconditional stability using numerical optimization

The main motivation behind my next question is that I think I derived a higher order numerical scheme for linear advection equation that is unconditionally stable using Von Neumann stability analysis. ...
1
vote
1answer
74 views

Can software remove all distortion from image taken with 180-degree lens?

If this isn't the right SE site, please suggest the right one? Can software remove all distortion from a 180-degree lens? In other words, if the goal is to optimize for distortion-free images, would ...
3
votes
0answers
64 views

“Solution path” for quadratic program as regularizer changes

I am solving a quadratic program with regularization parameter $\alpha\geq0$ to get the solution to a problem of the form $$ p(\alpha):= \arg\min_{p\in\mathbb{R}^n}\ [\alpha(v^\top p)+f(p)], $$ where $...
5
votes
2answers
212 views

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

I'm sorry for this silly question. Several times I faced with optimization problems which can be expressed as $$\begin{array}{ll} \text{minimize} & \mathrm x^T \mathrm A \mathrm x\\ \text{subject ...
1
vote
0answers
174 views

Open Source Quadratic Programming with Piecewise Linear Objective

I am looking for an open source solver to solve the a quadratic programming problem with an additional piecewise linear objective, as show below. The problem is fairly small ($\mathbf{x}$ is a vector ...
1
vote
0answers
441 views

Are linear programming algorithms faster than quadratic programming algorithms?

I have an objective function that I can write either in quadratic programming (QP) such as $$\sum_{i=1}^N \sum_{j=1}^N C_{ij}^2$$ or as an LP problem $$\sum_{i=1}^N \sum_{j=1}^N |C_{ij}|$$ which can ...
7
votes
1answer
176 views

What would be a good approach to solving this large data non-linear least squares optimisation

Introduction to Problem I'm using a Truncated Signed Distance Function to perform 3D reconstruction from depth images. Essentially I have a large voxel grid where each voxel contains the signed ...
3
votes
2answers
404 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 ...
8
votes
2answers
811 views

Why are convex problems easy to optimize?

Motivated by this top answer to the question: Why is convexity more important than quasi-convexity in optimization?, I am now hoping to understand why convex problems are easy to optimize (or at least ...
0
votes
1answer
68 views

Loooking for name of this geometrical optimization technique

From my knowledge if you fit geometrical objects into point clouds you want in general minimize the squared distances of the point cloud to your fitted objects. I do so with the downhill simplex ...
2
votes
1answer
58 views

Doubt regarding principled approach towards approximating the Hessian

In my optimization problem, the hessian has a structure such that it can be written as the sum of two matrices. Populating the first of the matrices is efficient. Populating the second one is ...
0
votes
1answer
197 views

How to code gradient descent-based Tikhonov denoising that exactly matches LSQ Tikhonov denoise?

(Note: Corrected code is posted below the original code.) For an exercise in optimization, I am interested in coding a simple example from scratch: a Tikhonov denoising routine using gradient descent,...
2
votes
1answer
151 views

Optimize custom probability distribution in Python [closed]

Consider random variables $X$ and $Y$, their distributions are given. $Z = f_a(X, Y)$ where $f(\cdot, \cdot)$ is a deterministic, not random function $f_a: \mathbb{R}^2 \to \mathbb{R}$ depending on a ...
1
vote
1answer
106 views

Non-linear optimization package that allows an user-defined Hessian

Our current lab uses SNOPT as an optimizer for aerodynamic shape optimization. I am currently working on building an approximate Hessian for the sake of improving the convergence speed and limits. ...
2
votes
0answers
104 views

Quasi-Newton Optimization with parallel function evaluation

I have a function of many variables (~200-2000) which I am optimizing with some success using L-BFGS. While the function is expensive to evaluate, the gradient can be computed with not much additional ...
3
votes
1answer
92 views

Enforcing bounds and equality constraints for convex optimization

In this JCP paper, the authors simultaneously enforce the discrete maximum principles and element-wise mass balance for advection-diffusion equations through convex optimization. The least-squares ...
2
votes
0answers
37 views

$(max(0, f(x)))^2$ or $(max(0, exp(f(x))))^2$ for soft constraints with Gauss-Newton

I need some kind of inequality constraint in my optimization problems (rude version of SVM for example or skeleton based mesh fitting). However hard constraints is not suitable for me because ...
4
votes
2answers
124 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 ...
6
votes
2answers
292 views

Can floating point error (in FFTW3) cause non-deterministic behavior?

I am solving a numerical optimization problem with my own L-BFGS (implemented in c++). The problem has $\approx 10^6$ optimization parameters. To find the objective function gradient, I am taking a ...
1
vote
0answers
58 views

Efficiently computing the properties of a Chebyshev series

Suppose we have some function $f(x)$ defined as a Chebyshev series up to order $M$: $$ f(x) = \sum_{n=0}^{M} c_n T_n(x). $$ For a given coefficients vector $\mathbf{c}$, and $x \in [-1,1]$ I'm ...
6
votes
1answer
354 views

Global convergence in trust region algorithm

I was reading about TR methods and there are some terms, which are confusing for me. It says, method is globaly convergent. What does it really mean? Converges to global minima, or converges for ...
3
votes
1answer
101 views

Looking for saddle point in scalar function with multiple parameters

I have a real valued function, let's call it $f(\mathbf{x}, \mathbf{y})$, which I would like to maximise with respect to $\mathbf{x}\in\mathrm{R}^d$ and minimise it with respect to $\mathbf{y}\in\...
7
votes
3answers
1k views

Approximating rotation matrix of arbitrary objective function

I want to approximate the rotation in SO(3) (ie. 3D rotation) that minimizes some objective function. I'm looking for a SO(3) rotation representation that lends itself to energy minimization. I'm ...
10
votes
3answers
2k views

Is providing approximate gradients to a gradient based optimizer useless?

Is it pointless to use gradient based optimization algorithms if you can only provide a numerical gradient? If not, why provide a numerical gradient in the first place if it is trivial to perform ...
8
votes
1answer
201 views

Methods to Estimate Optimal Distance Measure for Multidimensional Data Set

My problem at hand pertains to choosing a distance measure for use in locally weighted regression. In my particular problem, I have a data set that is upwards of 10 dimensions, where the variables ...
1
vote
1answer
97 views

Vectorizing list of different functions for Gradient Descent

I am new to machine learning and statistical analysis and am having trouble figuring how I should go about a problem I have. I believe that I understand the gradient descent algorithm and how it ...
10
votes
1answer
961 views

Adaptive gradient descent step size when you can't do a line search

I have an objective function $E$ dependent on a value $\phi(x, t = 1.0)$, where $\phi(x, t)$ is the solution to a PDE. I am optimizing $E$ by gradient descent on the initial condition of the PDE: $\...
1
vote
0answers
29 views

Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$. We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree ...
2
votes
0answers
544 views

Weighted Frobenius norm in BFGS

In what sense is the weighted Frobenius norm "adimensional"/"scale-invariant" for any symmetric positive definite weight matrix $W$? If we plug in a positive diagonal matrix into $W$ wee see that $||A|...
1
vote
1answer
183 views

imposing “measured data” to Dirichlet boundary conditions in fenics

I'm relatively new to fenics and I just looked through all questions related to Dirichlet boundary conditions. I don't seem to find a well-described question or answer about what I'm about to ask. I'...
3
votes
1answer
58 views

From deterministic to stochastic LP formulations

I am having a hard time understanding the very first example in "A Tutorial on Stochastic Programming". More specifically the authors show that one can formulate the stochastic variant of (1.2) ...
3
votes
2answers
83 views

Finding quick solution to a collection of systems of fairly simple but nonlinear equations

So I have a collection of systems of equations, basically $n$ systems of equations, each composed of $k$ equations: $$\frac{a_1x_{1j}}{a_1x_{1j} + \cdots + a_kx_{kj}} + \log x_{1j} + 1 - B_{1j} = 0$$ ...
1
vote
0answers
91 views

Choose of basis set [closed]

I am engaged with the syntheses and DFT calculations of coordination complexes. I wonder how can I set up the basis set for carried out using B3LYP method and mixed basis sets of LanL2DZ for Pd and 6-...
1
vote
0answers
95 views

Conservative Short Sales Portfolio Optimization with MatLab code help

I'm trying to solve the optimization problem below with MatLab, but I'm unsure of how to modify the constraints in the quadprog function (or how to add the constraints with the Portfolio object). In ...
1
vote
2answers
787 views

GSA Search Algorithm in C++

Is there any version of GSA (Gravitational Search Algorithm)[1] implemented with C++ or even C#? What I found was implemented using MATLAB which is not good for me. [1] Rashedi, Esmat, Hossein ...
0
votes
1answer
103 views

NONLINEAR ENERGY MINIMIZATION EXAMPLE

I am learning about FEM methods and nonlinear optimization. I would like to try my nonlinear trust region solver on some simple nonlinear problem. What would be good example to implement for ...
0
votes
1answer
167 views

Integer programming with Matlab

I'd like to know how to solve in MATLAB the following integer optimization problem : $\underset{B,D}{\arg\min} \Vert{Y-XDB}\Vert_{2}$ where $X,Y$ are given matrices. The constraint is the following ...
2
votes
2answers
411 views

Fitting rectangle to segments in image

I have the task to fit a rotated rectangle of known size into an image like This is a synthetic test case, in the real application, everything is rather blurred. The rectangle has to cover as much ...
2
votes
2answers
114 views

What kind of optimisation algorithm is suitable for a computationally expensive function?

I have a reference value $R$ and a modelled value $M$. $M$ is generated using a stochastic algorithm with parameters $a$ and $b$. The objective is to tune $a$ and $b$ so that $M$ is as close as $R$ ...