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
0answers
110 views

Stochastic gradient descent for large deterministic optimization problems

The Wikipedia page for SGD describes optimizing a function $f = \sum f_i(\theta;x_i)$ by successively approximating gradients from random subsets of the data, while most literature poses the problem ...
1
vote
0answers
171 views

First approximation to the TSP in a non-complete Graph

I'm trying to solve the Travelling Salesman Problem in a non-complete graph $(G,E)$ using genetic algorithms. My problem is that I can't find a good first approximation by the usual greedy algorithms,...
1
vote
1answer
115 views

GAMS Optimization

I am writing a GAMS program where I am interested in using the value of a variable as a condition inside an another equation. Let's say I have two equations with two variables, $g_1(t)$ and $g_2(t)$, ...
1
vote
0answers
147 views

How to test for convergence (smoothness of Pareto front) in DEAP

In the DEAP algorithms (see documentation here), I notice that we need to specify the the number of generations (NGEN). I was advised that convergence has been achieved if the Pareto curve is smooth. ...
4
votes
1answer
147 views

Optimization of non-smooth, non-convex, locally Lipschitz functions of type exp(-abs(x))

What would be the numerical method of choice to find minima in a non-smooth, non-convex, locally Lipschitz function $f: \mathbb{R}^n\rightarrow \mathbb{R}$. The function $f$ is mostly smooth but ...
2
votes
0answers
57 views

Comparing the solutions to a multi-objective optimization problem

Suppose I have a multi-objective optimization problem, and I wish to find solutions using two different methods/algorithms. The result of each algorithms is a Pareto front. Comparing two different ...
1
vote
0answers
74 views

How does this Constrained Minimization algorithm work?

I don't fully understand the subsection 3.2 Constrained minimization of this paper. In particular, I don't understand the first step "Register active set" and the definition of projection $P(x)$. ...
2
votes
0answers
94 views

Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
0
votes
1answer
199 views

What penalty function produces optimization-based Gaussian smoothing?

I have just read yet another introduction to image processing, which describes Gaussian smoothing from a convolution perspective and least-squares smoothing from an optimization perspective. It would ...
1
vote
2answers
632 views

LU decomposition of large dense matrices

I wanted to generate LU decomposition of large size dense matrices ($N>10^7$), the LU decomposition I'm currently using is based on Adaptive Cross Approximation and is taking very long time to ...
1
vote
0answers
179 views

Variable elimination in linear programming

I have a linear program of the form $$\underset{P,\;g}{\text{Minimize}}\hspace{3mm}c^Tg$$ \begin{align} \hspace{17mm}\text{Subject to}\hspace{3mm}AP_{\cdot,j}&=\begin{bmatrix} -g\\ d \end{...
2
votes
0answers
93 views

A least square problem with a fixed mean constraint and a subspace constraint

Let $V_1,\ldots,V_n$ be $n$ vector subspaces of a Hilbert space, $y_i\in V_i$ for each $i$ and $\overline{x}$ be a fixed vector. I want to solve the optimization problem: \begin{equation*} \begin{...
3
votes
0answers
60 views

Relaxing a variable in MIP

I have this MIP optimization problem, with couple of binary variables; however when I relax one of the binary variables the optimal solution of the objective does not change. But the solving time ...
3
votes
0answers
1k views

Understanding MATLAB's `fmincg` optimization function

I'm researching numerical optimization. Recently I've come across a variant of a conjugate gradient method named fmincg. The function is written in MATLAB and is ...
2
votes
0answers
62 views

Global optimization with known distributions of some variables

I'm solving simple single-objective multidimensional global optimization problem using various stochastic algorithms like Monte-Carlo, GA and other evolutionary approaches. The task is formulated as ...
2
votes
2answers
183 views

Approach to handle a quadratic constraint xy <= z

I have non-linear constraints like $ x_1x_2\leq x_3 $ where $ x_1,x_2,x_3\geq 0 $. The objective is linear, and all other constraints are linear, too. I know that I can transform the product as $ ...
3
votes
0answers
94 views

Finite difference method for coupled PDEs: optimizing performance (time step, iterations per step)

I'm solving coupled PDEs using finite difference method: Incompressible Navier-Stokes and the divergence-free induction equation (Maxwell's equations) with non-uniform electrical conductivity. The ...
5
votes
0answers
127 views

How to optimally choose points for multivariable Hermite interpolation?

I have a multi-variate, continuous function $f$ from $R^n$ to $R$, which I can query for its output for any input. I would like to create interpolation polynomial for it. In one-dimensional case ...
1
vote
0answers
110 views

preconditioning LBFGS?

I want to minimize an energy of the form $$V_1(\mathbf{x}) + V_2(\mathbf{x})$$ where $V_1$ is much stiffer than $V_2$. When I try to use LBFGS, convergence is extremely slow, as the solution ...
3
votes
3answers
233 views

How to debug a constrained optimization algorithm?

I have implemented a saddle point optimization problem based on the algorithm by Prof. Nesterov, primal-dual[1]. Unfortunately, it doesn't work. It seems it is converging. But unfortunately, not to ...
7
votes
1answer
118 views

reformulating inverse problem as multi-objective optimization

I'm working on an inverse problem for my Ph.D. research, for which I'll write the objective functional as $J(\theta) = E(G(\theta) - u^o)$, where $\theta$ are the parameters, $G$ is the forward map ...
1
vote
1answer
21 views

Break a set of numbers to minimum groups with each having a common divider

I have a set of numbers, all positive, integers obviously, and what I want to do is divide them in the least possible groups with each group having a GCD bigger than 1. The biggest possible number is ...
3
votes
2answers
172 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(...
0
votes
2answers
422 views

Optimization using Python/MATLAB

Given the following optimization problem: Given positive integers $n_1, n_2, \dots, n_m$ and real numbers $P_1, P_2, \dots P_m$. Besides these, given positive real numbers $a_{i,j,l}$ for $1 \leq i \...
1
vote
1answer
102 views

SOCP: Recovering primal from dual

Consider the following second-order cone program (SOCP): $$ \begin{array}{rl} \min_x & c^\top x\\ \mathrm{s.t.} & \|A_ix+b_i\|_2 \leq c_i^\top x+d_i \ \forall i \end{array} $$ Suppose I solve ...
2
votes
1answer
190 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
92 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
141 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
291 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
133 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
77 views

vectorizing optimization or root finding [closed]

I need to find the roots of a function. I am currently using scipy.optimize.fsolve ...
4
votes
0answers
474 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
32 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 ...
3
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 ...
2
votes
2answers
332 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
118 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
75 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 ...
2
votes
0answers
65 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 $...
4
votes
2answers
214 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
182 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
466 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 ...
6
votes
1answer
179 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
435 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
924 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
59 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
210 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
159 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
112 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. ...