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
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 ...
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 ...
-3
votes
1answer
50 views
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 ...
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 ...
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 ...
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
1answer
42 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
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 ...
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
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, \...
-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 ...
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 ...
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 ...
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
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 ...
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]$.
...
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 = \...
-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 ...
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 ...
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, ...
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 ...
1
vote
1answer
37 views
What is a good way to select a small subset (say 50) of items from a large pool of items (say 5 million) while minimizing an objective function?
I have 5 million items that have 10 features (all continuous and not categorical) each and would like to select a small subset of these items. Ideally, I want to manually specify 10 features of my own ...
-1
votes
1answer
75 views
Simulation-based Optimization vs PDE-constrained Optimization
What is the difference between Simulation-based Optimization and PDE-constrained Optimization?
Would studying a text on Simulation-based optimization be sufficient to understand and apply both?
0
votes
0answers
55 views
Artificial Neural Network for nonconvex optimization
I want to use artificial neural network(ANN) for solving non-convex optimisation problems. How do I map the constraints and the objective functions in the ANN architecture?
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 ...
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 ...
4
votes
0answers
76 views
What Derivative-free optimization method should I use when my initial guess is very good?
I am trying to minimize a function where my initial guess is quite close to the minimum.
I'm trying to minimize
$$f(q) = \text{angle}(qw_1q*, v_1) + \text{angle}(qw_2q*, v_2) + \text{angle}(qw_3q*, ...
5
votes
0answers
86 views
conjugate gradient for Newton's method with non positive definite Hessian matrix
I want to minimize a non-linear function $f(x)$ using Newton's method. At each optimization step, I compute a descent direction $d$ to update $x$ using a second-order approximation of $f(x)$:
$$ \...
3
votes
0answers
73 views
Inconsistency in optimize.minimize
I am trying to fit a time-dependent curve at each time step. I do so in minimizing along $x_c$ the quadratic error between the curve and a reference solution $ 1/(1 + \exp\left(\sqrt{S}(x-x_c)\right) $...
3
votes
1answer
34 views
Software for finding a minimum vertex cover for a hypergraph
A hypergraph $H = (V,E)$ consists of a finite set of vertices, say $V=\{1, \dots, n\}$ and a set of hyperedges $E \subseteq \mathcal{P}(V)$. We call $H$ a $k$-hypergraph if all $|e| = k$ for all $e\in ...
0
votes
0answers
41 views
Metric selection and scale-based preconditioning in quadratic optimization problem
I'm going to use scale-based preconditioning in a quadratic optimization problem: minimize $ x^T Q x + p^T x$ such that $ A x + b = 0$ and $D x + E \leq 0$, I want to speed up finding the optimal $x$ (...
0
votes
0answers
29 views
Converting logit coefficients into probabilities through the inverse multinomial logit
I am trying to come up with the transition intensities of a parameterized Markov model, i.e, the elements of the transition matrix weighted by the covariates through the inverse Logit relation:
$$\...
5
votes
1answer
122 views
Generate approximately semi-orthogonal tall matrix approximately satisfying constraints
I have a set of matrices $\{(A_i,D_i)\}$ for $i\in\{1,\ldots,n\}$, where:
Each $D_j\in\mathbb{R}^{S\times S}$ is diagonal, and every entry on the main diagonal is non-negative.
Each $A_j\in\mathbb{R}^...
5
votes
1answer
102 views
Solvers for Quadratically Constrained Quadratic Programs (QCQP) with complex variables
I'd like to know whether there are any publicly available tools for solving QCQP with complex variables (and constraints therefore expressed through Hermitian matrices). What I have found so far is ...
4
votes
1answer
184 views
How to solve the following Frobenius norm-minimization problem?
Background
We know how to solve the following minimization problem
$$
\min_{X} \lVert AX - B \rVert_F^2
$$
But what about the extended version?
$$
\min_{X} \lVert A
\begin{bmatrix}
X & X^2
\...
3
votes
1answer
169 views
How to solve the inverse problem of least-squares?
Focusing on following least squares problem:
$$\min\limits_{V} \lVert Z - WV \rVert _{_F}^2$$
$$Z∈{R}^{m\times n},\quad W∈{R}^{m\times k},\quad V∈{R}^{k\times n},\quad k\lt m\lt n $$
This problem ...
1
vote
1answer
181 views
How to use CSDP to express a semidefinite program?
I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program
$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
1
vote
1answer
199 views
FMINCON Step Size Tolerance
I get following error after implementing the attached code.
Error Message
"fmincon stopped because the size of the current step is less than
the default value of the step size tolerance but ...
1
vote
0answers
103 views
How to prevent BFGS from getting stuck on astronomically large gradient?
I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, ...
