Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
126 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
35 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
97 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
36 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, ...
4
votes
0answers
34 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, ...
4
votes
1answer
1k 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 ...
3
votes
2answers
64 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 ...
0
votes
1answer
92 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?
3
votes
1answer
83 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
154 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
83 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
206 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
84 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
40 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 ...
5
votes
1answer
131 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}^...
6
votes
1answer
322 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
191 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
194 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
200 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
503 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 ...
2
votes
0answers
156 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, ...
1
vote
0answers
33 views

Best Possible Convex bounds for optimization problems

Suppose we have a primal problem $$ p^{*}=\min_x f(x), \\\text{s.t.}~~ h_i(x) \leq 0, $$ where $f(.)$ and $h_i(.)$ are possibly non-convex. Then its Lagrangian is $$\mathcal{L}(x,z_i)= f(x) + \...
1
vote
0answers
67 views

Nonlinear least square optimization

Problem description Given data at many time instance $t$, $$\min _{\alpha, \Lambda, \beta} \lVert y(t) - \alpha e^{\Lambda t} \beta \rVert_F$$ with $$ \lVert \alpha \rVert_2^F = 1 $$ where $y(t) \...
1
vote
0answers
44 views

Space covering optimization

I have the following problem: In the space $E=\{1, 2, \dots, N_x\} \times \{1, 2, \dots, N_y\}$, I want to define $N_R$ rectangles $R_k=\{x_k^0, \dots, x_k^1\}\times\{y_k^0, \dots, y_k^1\}$ which ...
2
votes
1answer
106 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(...
0
votes
1answer
104 views

ill-conditioning

I am struggling with the following exercise from the book of Nocedal, Numerical optimization, chapter 2, exercise 2.12: Suppose that a function $f$ of two variables is poorly scaled at the solution $...
3
votes
2answers
167 views

How do I check if a loss function can achieve its minimum?

For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its ...
0
votes
1answer
131 views

Can I convert CUDA core to CPU core and use it as cpu core while running any program?

I was using Metatrader5 and have designed a strategy for trading using MQL5 programming language. While I was running a Strategy Optimization process, I saw the it will need 10,00= iterations or ...
0
votes
1answer
47 views

Conflicting definition of limit point

This question was raised at a different place without sufficient answers. Definition 1: We say that a vector $x \in R^n$ is a limit point of a sequence $\{x_k\}$ in $R^n$ if there exists a ...
6
votes
1answer
257 views

What is required of the objective function in order to use Gauss Newton method?

From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method. In addition to that, are the following ...
1
vote
1answer
41 views

How to decide on what techniques to adopt in Genetic Algorithm optimization

Does it really matter which techniques we use in the process of GA optimization? For instance, if I use the Roulette Wheel Technique instead of Tournament Method for selection, two-point crossover ...
0
votes
1answer
345 views

I've developed a derivative-free optimization method, looking for comments

Here is the URL: https://github.com/avaneev/biteopt I've tested it on numerous global optimization benchmarking functions (included), and on real-world hyperparameter optimization problems I have. ...
3
votes
1answer
187 views

How to numerically minimize a functional?

How to numerically minimize a functional, for example, $$J[y]=\int_{x_1}^{x_2}L(x,y(x),y'(x))dx$$ An equivalent problem is to solve the Euler equation for this functional as a differential equation. ...
1
vote
1answer
42 views

Distribute sources among destinations

There are $n$ sources with the following positive volumes: $p_1, ..., p_n$ and there are $m$ destinations with the following positive volumes: $q_1, ..., q_m$. It is known that $p_1+ ...+ p_n=q_1+ ...+...
7
votes
3answers
775 views

Finding the first N roots of transcendental equation

I need to find the first $n$ roots of the transcendental equation \begin{equation} F(k) = J_m'(kr)Y_m'(k)-J'_m(k)Y'_m(kr) \end{equation} for integer values of $m$ and any $r \in [0,1)$ where $J'$ ...
0
votes
1answer
546 views

Defining a soft constraint in cvxpy

I am using cvxpy to do a simple portfolio optimization. I implemented the following dummy code ...
4
votes
1answer
116 views

Nonlinear least-squares solvers vs. generic minimization

A nonlinear least-squares problem with $F:\mathbb{R}^m\to\mathbb{R}^n$, $$ F(x) \to \min_x \quad (\text{in the least-squares sense}) $$ really means minimizing $$ \frac{1}{2} \|F(x)\|^2 \to \min_x. $$ ...
2
votes
1answer
107 views

What is the fastest way to solve Ax=b (subject to constraints and an absolute term)

I am trying to solve/optimize $Ax=b$ in the least squares sense subject to box constraints; a few (less than 5) equality/inequality constraints; and an absolute function penalty (or some other ...
1
vote
0answers
19 views

How does the MADS algorithm work in practice

Mesh Adaptive Direct Search (MASH) is an algorithm for black box optimization I want to understand an implement this method to solve some 2D multivariate blackbox function $f(x,y)$, but am having ...
6
votes
2answers
948 views

What is the most appropriate derivative free optimization algorithm

We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$. If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
3
votes
1answer
319 views

Linear constraints for L-BFGS-B

I know L-BFGS-B only supports simple box constrains of the form: $l_i \leq x_i \leq u_i$, where $l_i$ and $u_i$ are constants. For my specific optimization problem, I need to specify some simple ...
0
votes
1answer
805 views

How to define the derivative for Scipy.Optimize.Minimize

I am trying to use scipy.optimize.minimize to minimise a quadratic objective function: $f(x) =x^\top Q x$. As a start, I have successfully implemented this using the built-in Nelder-Mead Simplex ...
0
votes
1answer
181 views

CPU and GPU influence on task parallel execution performance

This question is mainly about hardware, but also about software. In my current work I have approximately 68 millions of combinations that I am iterating through, in parallel. For each of those ...
1
vote
0answers
42 views

Genetic Algorithm: Need some clarification on selection and what to do when crossover doesn't happen

I'm writing a genetic algorithm to minimize a function. I have two questions, one in regards to selection and the other with regards to crossover and what to do when it doesn't happen. Here's an ...
1
vote
0answers
178 views

Levenberg-Marquardt for root-finding: just square the function?

This question might be so obvious and trivial that I'm having a hard time googling it. I have a multivariate root finding problem that I'm trying to solve in C# and the library that I'm trying to use ...
0
votes
1answer
57 views

reduced system: primal-dual interior point method for nonconvex constrained problem

When solving a reduced KKT system of a nonlinear (and nonconvex) constrained program after eliminating slack and dual variables, how do we actually take the next step in a primal-dual method? For ...
1
vote
0answers
16 views

Procedure to identify characteristic properties of unknown functions in a DAE model

I have a system of 1st order odes given by $$ \dot{x_1}(t) = \alpha_1 f_1(x_1,t) + \beta_1 u(t) \\ \dot{x_2}(t) = \alpha_2 f_2(x_2,t) + \beta_2 u(t) $$ They are constrained by an algebraic equation ...
1
vote
0answers
64 views

overlapping additive schwarz [closed]

I am solving 1D laplace problem discretized with finite differences (3-point stencil). I would like to use additive Schwarz method in classical form: $U_{k+1}=U_{k}+M^{−1} r_k,$ where $r_k=F−A U_k$...
3
votes
1answer
118 views

Obtaining a feasible solution for underdetermined system of linear equations satisfying inequality constraints

I would like to obtain a feasible solution for an under-determined system of linear equations, $$Ax=b$$ where, $A \in \mathbb{R}^{7\times9}, \, x \in \mathbb{R}^{9\times1}\text{and } b\in\mathbb{R}^...
4
votes
1answer
403 views

Optimization of a blackbox function with an equality constraint?

I believe this would be an interesting problem. I have a blackbox function which can take 2-60 input variables $(X_1,X_2,...X_n)$ which are to be optimized. I'm calling this objective function as a ...