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

learn more… | top users | synonyms

0
votes
0answers
24 views

Fitting high frequency trading model

I have a high frequency time series of the bid and ask prices of a stock recorded on every tick. For each data point I also have a certain indicators that predict the future movement of the price. The ...
4
votes
1answer
52 views

Selecting most scattered points from a set of points

Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)? I assume the points ...
2
votes
1answer
82 views

Solve $AX = B$ where $X^T X = C$

Is there a natural way to find the solution to $$AX = B, X^TX = C \enspace \text{?}$$ $X$ is a matrix and has a small number of rows, and $A$ is sparse. An approximate solution would be fine.
3
votes
1answer
73 views

Trust-region Newton: implementation issue with Conjugate Gradient calculations

UPDATE: The problem turned out to be the step (refer penultimate paragraph below) where I was factoring out a small value from the vectors of the numerator and denominator and then computed dot ...
0
votes
1answer
27 views

Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$ We can in theory convert the constraints to the convex hull ...
1
vote
0answers
55 views

Simple MCMC Algorithm in Matlab

I would be really glad to get some specific advise on how to implement a simple MCMC algorithm (in Matlab, if possible). I'm not yet too familiar with optimization methods. My problem goes as follows: ...
1
vote
2answers
49 views

Solving absolute value quadratic optimization problem

would you please help me to solve following problem $$x^*= \text{argmin}\ xLx^T+ |P^Tx|$$ $x$ is binary $P$ is a known vector (with positive and negative values) $L$ is Laplacian matrix I have ...
0
votes
0answers
23 views

Cyclic Coordinate Descent Optimization for Bayes Logistic Regression (Code Problem?)

I am trying to reproduce the CLG algorithm for the Laplace prior given in Genkin et al to find the MAP estimates for a logistic regression model. I am using Python (Anaconda 2.2) with Numpy to ...
1
vote
2answers
108 views

Ideas on how to search nearby geospatial data fast

I am looking at a very simple problem, but can't quite find the best solution. I need to accept a lat/lon coordinate and based on that coordinate find all the points within roughly ~1km (accuracy is ...
4
votes
2answers
122 views

Python solvers for mixed-integer nonlinear constrained optimization

I want to minimize a black box function $f(x)$, which takes a 8$\times$3 matrix of non-negative integers as input. Each row specifies a variable, whereas each column specifies a certain time period so ...
2
votes
1answer
33 views

scaling and preconditioning for trust region Newton methods

Geometrically, scaling and preconditioning seem to address similar challenges in optimization. However, these two concepts are implemented very differently. Take trust region Newton method, as an ...
3
votes
2answers
74 views

Derivative-free optimization of function with a flat region

I'm attempting derivative-free minimization of, essentially, a black-box function in one dimension. Up to now I've been using BOBYQA as implemented in NLopt. The shape of the function looks like this: ...
3
votes
0answers
25 views

Python trust region optimization code that allows ellipsoid-shaped trust regions

Are there any high quality trust region optimization implementations that allow nonspherical ellipsoid trust regions, and are written in Python, or are easy to call from python? By nonspherical ...
3
votes
2answers
64 views

non-convex quadratic with only one quadratic constraint?

I have a non-convex optimization problem in the form: \begin{align} \min_{b,\xi,\eta} \sum_{i=1}^{n} b_i \xi_i + \gamma \Vert \eta \Vert \cr \text{s.t.} b\geq 0, b^\mathsf{T} 1 = 1,b_i \leq ...
3
votes
0answers
56 views

Combinatorial algorithm problem of a symmetric matrix [migrated]

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
0
votes
1answer
52 views

Converting smooth $L1$ norm approximation into SOCP

I am approximating the expression $\left\|Ax-b\right\|_1$ by the expression $$\text{minimize}\;\;\sum_i\sqrt{(a_i^Tx-b_i)^2+\varepsilon}$$ where $a_i$ is the $i^{th}$ row of $A$. This function is ...
0
votes
1answer
39 views

What are open source codes for interior point optimization to modify?

I am working on a modified interior point algori thm for semidefinite for my special problem. I don't have enough skills and knowledge about interior point for semidefinite to code it from scratch. ...
3
votes
2answers
114 views

Solution to the optimization problem in “Blessing of Dimensionality High … the face verification”

I am reading the work "Blessing of Dimensionality High dimensional feature and its efficient compression for the face verification" CVPR 2013. One of the key contributes is the authors propose a new ...
1
vote
1answer
23 views

Approach to determining most likely integer factors of a noisy measurement?

I have a quantity which is estimated from a number of noisy measurements. I know that the real underlying value must be some integer multiple of two quantities, e.g. $M = I_1C_1 + I_2C_2$ where $C_1$ ...
1
vote
1answer
31 views

How to nest 2 simple CVX problems? Is it possible at all?

I have the underdetermined outer optimization problem $$\text{min}_{x\geq 0}\quad \|Ax-b_1\|_2^2+\|AT(x)-b_2\|_2^2$$ with $A\in\mathbb{R}^{m\times n}$ and $m<<n=64^2$ or in corresponding CVX ...
1
vote
2answers
125 views

Find $\min \sum_{1\le i\le n} x_i\mathbf{z}^T\mathbf{A}\mathbf{y}_i +\mathbf{b}^T\mathbf{x} +\cdots$

I have been stuck at this problem for a while :( Given $\mathbf{A}\in\mathbb{R}^{p\times p}, \mathbf{A}\ge 0,\mathbf{A} \text{ symmetric}, \mathbf{b}\in\mathbb{R}^n,\mathbf{c}_i\in\mathbb{R}^p\forall ...
2
votes
1answer
62 views

Hessian-free and Truncated Newton methods

In this paper on Deep Learning for Machine Learning, the approach is referred to as Hessian-free method. That is because the Hessian is never computed explicitly. Instead, the product of the Hessian ...
0
votes
1answer
76 views

Use line segments to approximate a function

I need to use line segments to approximate a function, f = 1/x. The range of x is from 1 to 2048 with an interval of 1. I will pick 10 locations for x and interpolate y between two adjacent x using ...
0
votes
0answers
33 views

Optimization of nonlocal stencil-like operator on subset of regular grid

I am trying to optimize the execution time for this particular piece of fortran code. Details: i_gc is a (ngpts, 3) array of containing (i,j,k) indices for each grid point. This is a subset of the ...
1
vote
0answers
37 views

Numerical Implementation of “integrates to some values” type constraint in convex solvers?

I am maximizing a linear functional subject to an integrates to one constraint. More explicitly, my problem is $$\begin{align} &\max_{x \in \mathbb{R}^n}\quad c \cdot x\\ &\text{subject to} ...
1
vote
0answers
40 views

Is there a convergence proof for ADMM applied to biconvex/bilinear problems?

Ok, I've already asked this question in math.stackexchange, but I feel it is more appropriate to ask here (hopefully I am not violating any rules by repeating!). So here it is: I wonder if there ...
1
vote
1answer
55 views

Gradient Descent

I am working with an objective function that is convex globally, but the path downward is lined (if you will) with quartz crystals. In this case, the update vector (gradient solution) of partial ...
0
votes
0answers
34 views

How to scale variables for optimization if one of them is an exponential

I do use scipy`s leastsqare function for data fitting. My function looks like: $$ \frac{dy_i}{dt} = K_{kin} *x_i* (K_2 * (K_2 - a*y_i - b*y_i)^c) - y_*cs^c ) $$ The variables are ...
1
vote
3answers
100 views

Dealing with errors in non-linear least square problem

I am currently working with a optimization problem involving a non-linear least square problem. I have chosen to use lsqnonlin in Matlab. What follows is a ...
0
votes
0answers
73 views

Frank Wolfe algorithm in matlab

I'm trying to solve the following question : $$ maximize \ x^{2}-5\cdot x + y^{2}-3\cdot y $$ $$ x+y\leq 8 $$ $$ x\leq2 $$ $$ x,y\geqslant 0 $$ By using Frank Wolf algorithm ( according to ...
1
vote
1answer
41 views

Solving nonlinear optimization problem with combinational constraints

I have to minimize a nonlinear objective function $f(x_0, x_1, x_2, x_3, x_4, x_5)$ with 6 variables. The constraints governing these these variables are a mix of nonlinear inequality constraints, ...
0
votes
1answer
56 views

Is there general algorithms to solve such 3D cutting problems?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
0
votes
0answers
26 views

Softly bounded linear regression

I am looking into implementing (in C++) a linear regression of few parameters (5-ish) to find moderate amount of data (2000-ish data points). Implementing least-square fit is straightforward; however, ...
0
votes
1answer
117 views

How to speed up fmincon in MATLAB when there are many variables? Alternatives to MATLAB optimization toolbox?

I need to solve an optimization problem with two nonlinear equality constraints. My function evaluation is very fast (less than a second) and I also provide fmincon ...
0
votes
0answers
24 views

Genetic Algorithm in linear cut optimization with reuse

As stated in the title i have a problem of linear cut optimization that i need to solve with a genetic algorithm. No problem if i have all the possible pieces to cut that are stically defined when ...
1
vote
1answer
88 views

Maximum translation distance between piecewise functions that satisfy a condition

The description: I have a number of similar piecewise functions, where $d$ is the translation distance lets assume this is the function (where a and b are known constants): $$f(x-d) = \left\{ ...
0
votes
0answers
44 views

how to compute Lagrangian multipliers for this case?

I have seen in the Pang book of data mining the following example: ...
2
votes
1answer
64 views

Constraint containing 'max' in linear program unnecessary?

The problem that I'm trying to solve is as follows. A server has at its disposal a pool of video encoders (each encoder has different settings and causes a different load on the server) that can be ...
6
votes
4answers
290 views

Levenberg-Marquardt - What is preferable (A + mu.I) or (A + mu.diag[A])?

The step size is computed by solving $$ (A + \mu I) h = -g $$ I could find in some literature that one can compute the step size by solving $$ (A + \mu \operatorname{diag}(A) ) h = -g $$ It is said ...
0
votes
1answer
37 views

Algorithms for searching in high-dimensional binary data spaces

Is there any algorithm that can learn/search efficiently the best sequence of 1's and 0's of length $n$ to fulfill certain performance? The search is performed in a high-dimensional binary data space. ...
2
votes
1answer
57 views

optimize vertices using a cost function on triangles

I want to optimize the vertex positions in a mesh, with a given cost function on the associated triangles. The paper gives a cost function, which evaluates to an real number by using a sum over the ...
0
votes
1answer
113 views

Doubt regarding stopping criterion for Newton method

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
0
votes
1answer
70 views

Unconstrained minimization of unbounded function with SciPy

It seems that scipy.minimize can find the minimum of an unbounded function. ...
0
votes
0answers
44 views

stochastic optimization with unknown distribution

I have a stochastic optimization problem in which I have expectation in constraints. we do not have any any information about distribution function of the random variable a prior. I know in cases you ...
4
votes
2answers
148 views

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

So I have a symmetric matrix $A$ and I would like to solve the optimization problem: $$\text{Minimize}\;\; ||A-S||_2$$ $$\hspace{-5mm}\text{Subject to}\;\; S\geq0$$ $A$ is given and $S$ is the ...
1
vote
2answers
70 views

Optimization: Providing gradients by autodifferentiation e.g PyAutoDiff

What is the difference (in terms of e.g robustness and speed) between proving a gradient obtained by an AD package (like PyAutoDiff) and let the solver (e.g BSGS) calculate the gradient ? It seems so ...
2
votes
1answer
137 views

optimization (using python) how to find the most suitable solver?

I have a fitting routine set up. It works, but pretty slow. I was wondering if there is a better method to use. I checked my (forward) code against some literature data and at least I do have no bugs ...
0
votes
0answers
33 views

Dynamic programming as final value problem?

I refer to the note "Stochastic systems" by Geering, Dondi, Herzog, Keel (freely available as a pdf ); We consider a stochastic optimal control problem, i.e. given a dynamical system with state ...
2
votes
1answer
75 views

Generalized linear-fractional program [closed]

Given the generalized linear-fractional program: $$\text{Minimize}\;\; \max_{i}\Big|\frac{c_i^Tx+d_i}{e_i^Tx+f_i}\Big|$$ $$\hspace{-5mm}\text{Subject to}\;\; e_i^Tx+f_i>0$$ I convert this into the ...
0
votes
0answers
80 views

Help with the definition of constraints for a joint optimization problem

A trajectory is piecewise defined by the following polynomial form: $$ f(t) = a + bt+ct^{2}+dt^{3}+et^{4}+ft^{5}+gt^{6}+ht^{7}+it^{8}+jt^{9} $$ for every single segment composing the trajectory (the ...