Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
0answers
28 views

In-exact line search

In my class notes, the author says: "If $f:\mathbb{R}^n \to \mathbb{R}$ is bounded below and $p_k$ is a descent direction and the $\alpha-\beta$ also known as Armijo-Goldstein condition is met then ...
-1
votes
0answers
17 views

How to model a hysteresis behavior using MILP on CPLEX?

The question is below: 1: y[t]=10,if x[t]>=2; 2: y[t]=-1,if x[t]<1; 3: y[t]=y[t-1],if 1<=x[t]<2. How to model the function in cplex using c++? Thank you very much! My model is added as "...
0
votes
1answer
61 views

Is this a knapsack problem?

I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
0
votes
0answers
21 views

Is this a form of stochastic gradient descent?

I want to minimize the following with respect to parameters $B$. $$\sum_{k = 1}^{K} f(A_{k}, B)$$ where $A_k$ are $K$ different data-sets and $B$ is a matrix of parameters. Can I do this by a ...
8
votes
2answers
895 views

Minimum path on known potential surface

I'm searching for the minimum path between the minima of a potential surface that is already known on a grid. (source: http://www.math.nus.edu.sg/~matrw/string/) Any point on the path is at an ...
0
votes
1answer
276 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
23 views

Gradient ascent method with a constant step size?

I'm trying to use the gradient ascent method on a convex function like the multivariate-Normal density function with respect to its parameters (the original is a bit more complicated), something ...
2
votes
2answers
144 views

Best software to do big number calculations quickly

I am trying to do some work on some math conjecture. I am testing the conjecture numbers using very large math numbers (100+ digits ). I am currently using python to test these numbers. In the ...
0
votes
1answer
43 views

Minimize cost with Levenberg-Marquart method

I want to minimize a cost function of the form, $$ \min_{q,t}\left(q^T\left(\mathcal A + \mathcal B\right)q + t^T\mathcal C t+\delta t+\varepsilon Q(q)^TW(q)t+\lambda\left(1-q^Tq\right)^2\right) $$ ...
2
votes
1answer
41 views

Question about strange outputs from the CVXPY solver

I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem: ...
3
votes
0answers
56 views

Given a list of intervals, find region that is contained by the largest number of those intervals

Start with 1d case. Say I have lots of 1d intervals $[s_i, e_i]$ and I want to find an interval $[s^*, e^*]$ to maximise the count of interval $i$ such that $[s_i, e_i]\supseteq [s^*, e^*]$. 1d case ...
0
votes
1answer
56 views

How to derive the optimal bayesian solution to a model of two normal distributed populations

In the "Introduction" section of the paper Support-Vector Networks, it mentioned Fisher's solution to a model of two normal distributed populations: My questions are: How to derive equation (1)? I ...
0
votes
1answer
66 views

Particle Collision to Static paticles

I have a system of particles with equal distance with each other and another at random positions which is moving with time. I want to know: a) The method by which I can reduce the number of particles ...
2
votes
1answer
45 views

Techniques to remove a function from Levenberg-Marquardt when it is against box constraints

I have a somewhat large (20+ dimensional) root finding problem that I'm solving with Levenberg-Marquardt. One of the functions has box constraints on [0, 2]. When it is against those bounds it will ...
12
votes
2answers
10k views

Confusion about Armijo rule

I have this confusion about Armijo rule used in line search. I was reading back tracking line search but didn't get what this Armijo rule is all about. Can anyone elaborate what Armijo rule is? The ...
3
votes
0answers
58 views

Nonlinear least squares and regularization

Consider the nonlinear least-squares minimization of a vector of $n$ residuals $\mathbf{f}$ in $p$ parameters $\mathbf{x}$: $$ \min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2 $$ This can be done with ...
2
votes
1answer
78 views

Some proof that linear translations and rotations of a bound-constrained function are equivalent

For example, I have a function to optimize: $$f_1(x,y) = x^2+y^2, \quad x_{lb}\le x\le x_{ub},\quad y_{lb}\le y\le y_{ub}$$ Then I apply rotation by $\theta$ plus translation by $x_0$ and $y_0$: $$f_2(...
2
votes
3answers
182 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
1answer
50 views

sum of absolute difference constraint in optimization problem

I am writing a model for an optimization problem. I need to write the following constraint: $$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$$ How to write this constraint (or linearize)? ...
1
vote
2answers
113 views

Method to find PDE equation coefficient satisfying mean solution?

What is the best approach to go about solving a PDE problem of the type \begin{equation} k^3\Delta u - k(\mathbf{1}\cdot\nabla u) = 0\, ,\\ u=g\; \text{on}\; \Gamma_D\, ,\\ mean(u) = u_\text{...
-1
votes
1answer
22 views

R function or package for carrying out maximum likelihood techniques in random effect models

I am applying optim() function in R to obtain maximum likelihood estimates of the fixed effects and random effects in a model with bivariate random effects. The ...
6
votes
1answer
357 views

Matching/Assignment Problem

I'm not sure how I can represent and solve the following problem. I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
-1
votes
1answer
62 views

Compute affine transformation between two sets of points

Consider two sets of points $P = (P_1, ...,P_n), \ Q = (Q_1, ..., Q_m) $ included in $\mathbb{R}^3$. I'm looking to compute an optimal affine transformation that "maps" $Q$ to $P$, although the sets ...
1
vote
1answer
42 views

Nature of stationary points of a Lagrangian fuction

I would like to extremize a certain function $f$ with respect to a parameter $x$, under constraints $g_1(x) = 0, ..., g_m(x)=0$. In order to achieve this, I consider the Lagrangian function $L(x, \...
14
votes
6answers
17k views

Constraints involving $\max$ in a linear program?

Suppose $$\begin{align*} \min A &\mathrm{vec}(U) \\ &\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n \end{align*}$$ where $U$ is a symmetric $n\times ...
3
votes
1answer
68 views

Nonlinear least squares when some parameters are linear

Consider the least squares problem, $$ \min_{\mathbf{a},\mathbf{b}} || \mathbf{f}(\mathbf{a},\mathbf{b})||^2 $$ where $\mathbf{a},\mathbf{b}$ represent the unknown parameters to be found. In my ...
1
vote
0answers
153 views

Good C++ optimization library for BFGS

To implement maximum likelihood estimators, I am looking for a good C++ optimization library that plays nicely with Eigen's matrix objects. Eigen has some capability of interfacing of its own but if ...
1
vote
1answer
69 views

Why does Newton's method with Linear Equality Constraints use KKT condition?

Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint. The problem only has equality constraint. Why ...
2
votes
0answers
24 views

Where can I find sample data for large linear programming optimization problems?

I am doing a comparison of different algebraic modeling langues (AMPL, AIMMS, GAMS, Pyomo) in both theoretical and practical terms. As a practical experiment I am trying to measure problem model ...
1
vote
0answers
45 views

Order of a principal term

In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a bound for the total number of iterations for some process. See page 109: $$\left[\frac{1}{\ln(2(1-\kappa))} \ln\frac{t_0-t^...
1
vote
0answers
29 views

Logging vs outputs in iterative optimisation

I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
3
votes
0answers
47 views

Nonlinear functional optimization in radial coordinates

I am currently implementing classical density functional theory for a radially symmetric system. In mathematical terms, I am searching for a function $f(r)$ that minimizes a functional $\Omega[f]$. ...
10
votes
4answers
3k views

Nonlinear least squares with box constraints

What are recommended ways of doing nonlinear least squares, min $\sum err_i(p)^2$, with box constraints $lo_j <= p_j <= hi_j$ ? It seems to me (fools rush in) that one could make the box ...
2
votes
0answers
72 views

How to numerically optimize affine transformations?

I need to optimize affine transformations for of a set of triangles using energy function based on the connectivity. The energy of an edge $e_j$ between triangles $T_a, T_b$ is given by $$ E_j = \...
8
votes
3answers
3k views

fmincg implementation in Python

I'm trying to re-implement Neural Networks in Python. I implemented the cost function and the backpropagation algorithm correctly. I have checked them by executing its Octave equivalent code. But ...
0
votes
1answer
408 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
97 views

Difference between Dishonest Newton method and Very Dishonest Newton method

What is the difference between the Dishonest Newton method and the Very Dishonest Newton method? Is there a difference or do they mean the same thing? I have tried searching for this on the internet ...
1
vote
0answers
31 views

Efficient numerical optimization of an “almost separable” function

I have come across an optimization problem with the following objective function: $$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
2
votes
1answer
52 views

Convergence rate and complexity for convex minimization problem

In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization ...
12
votes
3answers
498 views

Confusion about compressed sensing problem

I read some references including this. I am kind of confused what optimization problem compressed sensing builds and tries to solve. Is it $$\begin{array}{ll} \text{minimize} & \|x\|_1\\ \text{...
2
votes
1answer
30 views

Log-transformation of decision variables in parameter estimation

I am trying to find the diffusion coefficient ($D$) and the partition coefficient ($KLP$) using experimental data of desorption of a pollutant from a film into a liquid. This process can be modelled, ...
3
votes
0answers
31 views

Stochastic conjugate directions to improve convergence in narrow valleys

My question concerns a specific statement in this paper: N. N. Schraudolph and T. Graepel, "Conjugate Directions for Stochastic Gradient Descent," in Int. Conf. Artificial Neural Networks, Berlin, ...
5
votes
2answers
904 views

Interpolation by Solving a Minimization Problem (Optimization)

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - $M \times N$ Matrix). Someone marks some pixels as anchors. Now, you need to ...
13
votes
5answers
11k views

Minimizing the Sum of Absolute Deviation ($ {L}_{1} $ Distance)

I have a data set $x_{1}, x_{2}, \ldots, x_{k}$ and want to find the parameter $m$ such that it minimizes the sum $$\sum_{i=1}^{k}\big|m-x_i\big|.$$ that is $$\min_{m}\sum_{i=1}^{k}\big|m-x_i\big|.$$...
3
votes
1answer
64 views

What is a “good enough” method of assigning values to n variables subject to basic bounding constraints while maintaining relative weights?

Given triples of $n$ floating point values $$(\min_1, \max_1, w_1), \dots, (\min_n, \max_n, w_n)$$ and a value $V$, what is a good algorithhm to assign values $v_i$ to each of the triples such that ...
4
votes
1answer
172 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 ...
1
vote
1answer
244 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}...
3
votes
1answer
233 views

How does fmincon in MATLAB calculate gradients?

I am trying to solve numerically a constrained optimisation problem in MATLAB, and I am wondering how the fmincon function calculates gradients when one isn't ...
2
votes
1answer
119 views

Can the Power Method be used here?

Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected ...