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.

0
votes
0answers
13 views

Possible application of Polya's urn on real data (for Portfolio optimization)

I wanted to find some more information of this topic, but I found very little. I might be interested in optimizing a stock investment portfolio. Maybe I could use beta or some other common risk ...
0
votes
1answer
32 views

Vehicle Route assignment with capacity constraint

Problem Background I'm trying to find a solution/model to the following problem: Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each ...
1
vote
0answers
21 views

Examples of problems that cannot be formulated as optimization problems

An optimization problem has 3 main components: decision variables, constraints and an objective function. Such a problem can be mathematically modelled and solved using an optimization solver. For ...
2
votes
2answers
183 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 ...
3
votes
2answers
73 views

Optimization techniques for expensive multi-variable functions

I'm working with a finite element model in which I'm interested to minimize the average temperature at a surface. I have 15 independent variables in my model, including geometry, materials, flows, ...
0
votes
1answer
50 views

Solve multi-dimensional optimization problem using basinhopping

I am searching for an optimization solution, which is a 8d vector representing 4 complex elements, where each element is within the complex circle with maximal radius 1.2. The objective function is: ...
1
vote
3answers
115 views

Find a solution of large system of inequalities

I have a large system of homogenous inequalities involving 33 real unknowns of the form $$ \vec{F}(z_i)^T \cdot \vec{X}>0\, $$ where $\vec{X} = \left(x_1,...,x_{24}\right)^T$ are the unknowns and ...
15
votes
4answers
5k views

Linear programming feasibility problem with strict positivity constraints

There is a system of linear constraints ${\bf Ax} \leq {\bf b}$ . I wish to find a strictly positive vector ${\bf x} > 0$ that satisfies these constraints. That means, $x_i > 0$ is required for ...
4
votes
1answer
59 views

What is the name for this type of constraint?

I have what would be a straightforward mixed-integer linear programming problem, except for the fact that some of the constraints are of the form $f(x_1,x_2,x_3,\ldots,x_n) < c$, where $f$ is 'take ...
2
votes
0answers
42 views

Non-parametric models as solutions to Partial Differential Equations

In the realm of scientific computing, there are a plethora of techniques developed to solve Partial Differential Equations (PDEs). Many of the popular methods are variants of common techniques such as ...
0
votes
0answers
12 views

Cost functions to judge time/memory/accuracy tradeoffs

I am working on an interesting algorithm: Its absolute error is exponential in a parameter $j \in \mathbb{N}$, and for a given $j$, I have complete freedom to choose between an $\mathcal{O}(1)$ time-...
0
votes
0answers
90 views

How to solve extremely large scale linear system

I have a extremely large scale liner system equation. It stems from the minimization of $$ E(\{\widetilde{C_{i}}\}) = \sum_{i}\left[ \left( 1-\psi _{i}\right) \left\| \widetilde{C_{i}}-\sum_{j\in{N_{i}...
0
votes
0answers
27 views

Minimizing the ratio of two specific non negative quadratic convex functions

$F$ is $m\times m$ diagonal, with real non negative elements $D$ is $n \times m$ complex $P$ is $n \times 1$ complex $A$ is $m \times 1$ complex. Minimize $\Gamma(A)$, with respect to $A$. $$\...
0
votes
1answer
16 views

Minimize squared error of linear function

Let $M$ be a $m \times n$ matrix, $x$ a $n$-vector, $y$ a $m$-vector, and $\|\cdot\|_2$ represent the $L_2$ norm (i.e., Euclidean norm). Given $M,y$, the goal is to find $x$ that minimizes the ...
2
votes
1answer
82 views

Is there an optimization scheme/algorithm that converges, for this non-convex scenario but with some special properties

I have a smooth function $f(x) = \frac{g(x)}{h(x)}$ that is the ratio of two smooth convex functions $g(x)$ and $h(x)$. It is known that $f(x)$ has a global minimum, achieved at the unique point $x_0$....
1
vote
0answers
45 views

Simplification of an optimization objective

Let $G(V,E)$ is a weighted simple graph, where $V$ and $E$ are the set of vertices and Edges. The graph is undirected. Let $A \in \{0,1\}^{n\times n}$ and $W \in R_+^{n\times n}$ be the adjacency ...
7
votes
1answer
183 views

Lack of quadratic convergence in Newton's method

It is well-known that Newton's method can converge quadratically, if initial guess is close enough and if the arising linear systems are solved accurately. I am applying Newton's method to highly ill-...
3
votes
1answer
71 views

Minimize a function with sparse Hessian

The problem I am trying to solve involves minimising a function with respect to a large number (probably 10,000+) of parameters. I can cheaply compute both its Jacobian and its Hessian. The Hessian is ...
0
votes
1answer
65 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) $$ ...
0
votes
0answers
32 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 ...
0
votes
1answer
64 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
30 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
939 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
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
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
1answer
47 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
58 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
60 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
47 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
71 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
79 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
186 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
59 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
114 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
26 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
359 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
68 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
50 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
70 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
351 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
82 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
25 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
46 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
32 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
48 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 ...