Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
934
questions
1
vote
0answers
16 views
Does this adaptive time-step algorithm have a name?
I'm using a somewhat unconventional technique to iteratively minimize a high-dimensional function $E(\vec\theta)$, and have proposed a simple routine to dynamically adapt its time-step. I am seeking ...
2
votes
1answer
32 views
Does this iterative optimization method have a name? (problem and method described here)
I will describe an iterative optimization problem and method, and I am interested in if this method has a specific name.
Problem: Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}^3$. (In general, $f:\...
0
votes
0answers
22 views
How to explain that one optimization problem formulation gives a faster solution than another?
I have a relaxed convex problem (Conic) that can be expressed using two formulations. When solved using CPLEX, I obtained the same global solution. However, one formulation yielded the global solution ...
1
vote
1answer
47 views
How to find if this minimization problem is solvable
Given $x_i,y_i,z_i \in \mathbb{R}$, I want to find $a_0, a_1, a_2$ that minimize the following
$$\sum_{i=1}^n(a_0\times\text{max}[a_1x_i-1,a_2y_i-1]-z_i)^2$$
Is this convex optimization problem and ...
1
vote
0answers
14 views
How can we solve this nonlinar, nonsmooth optimization problem arising in the variance minimization of an MCMC estimator?
I want to maximize $$F(w):=\sum_{i\in I}\sum_{j\in I}\int\lambda({\rm d}x)\int\lambda({\rm d}y)\left(w_i(x)p(x)q_j(y)\wedge w_j(y)p(y)q_i(x)\right)\sigma_{ij}(x,y)|g(x)-g(y)|^2$$ subject to $$\sum_{i\...
0
votes
0answers
33 views
non-smooth convex optimization
I want to solve an optimization of the form $$\underset{x}{\min}f(x) + g(x),$$ where $f(x)$ is $\mu$-strongly convex and differentiable with a Lipschitz continuous gradient (with Lipschitz constant $L$...
2
votes
0answers
32 views
Efficient algorithm to search minimum of function with noise
Assume I want to find the mimimum of some function $f(x)$
but I can only compute $$f(x) + \varepsilon,$$ where $\varepsilon$ is some random variable with mean 0. With enough computation power I can ...
1
vote
1answer
39 views
In maximum likelihood estimation, why is it hard to directly optimize the likelihood function?
In Boyd's Chapter 7, it writes
I am just wondering what is the reason we do not maximize the likelihood function directly and instead construts the log-likelihood function?
What is the fundamental ...
0
votes
0answers
61 views
Can linear programing be used in Model Predictive Control?
I'm trying to implement Model Predictive Control onto a small micro controller. I know that is not "possible", but I want to minimize the "unnecessary" tools that are avaiable inside "regular" Model ...
1
vote
0answers
61 views
What is the simplest method to solve an inequality-constrained convex quadratic program?
I am going to create a simple QP-solver in C programming language to solve the following inequality-constrained convex quadratic program
$$\text{minimize} \quad\frac{1}{2}x^TQx + c^Tx $$
subject to:
...
2
votes
0answers
48 views
How is the sequence generated via gradient descent uniformly bounded?
Consider a function $f\in\mathcal{C}^2$ with Lipschitz continuous gradient (with constant $L$)- we also assume the function is lowerbounded and has at least one minimum. Let $\{x^k\}_k$ be the ...
0
votes
1answer
56 views
Absolute Error Versus Relative Error. More suitable?
I understand the differences between relative and absolute error. I can think of examples when relative error is a more suitable error measure but not when absolute error is more suitable than ...
0
votes
0answers
12 views
Naming continuous-time random walks
Is there a standard notation for naming continuous-time random walks according to their probability distributions?
For example, Lévy flights as Cauchy-based random walk, Rayleigh walk as Gaussian-...
1
vote
0answers
40 views
Initilize BFGS optimization with negative definite matrix
In http://apmath.spbu.ru/cnsa/pdf/monograf/Numerical_Optimization2006.pdf on page 151, we are told that approximations of the Hessian matrix with the BFGS formula are always symmetric and positive ...
0
votes
1answer
34 views
Basic numerical Optimization/approximation question
can someone help me out with this question? I am at a complete loss...
define these two functions:
\begin{align}
f(x, \delta) &= \cos \left(x + \delta\right) - \cos(x)
\\[.5em]
g(x, \delta) &...
0
votes
0answers
70 views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\Phi_g(w):=\sum_{i\...
1
vote
1answer
50 views
How can we solve this simple linear program?
Let $$a:=\begin{pmatrix}.2&.1\\.7&.05\end{pmatrix}$$ and $$b:=\begin{pmatrix}.01&.9\\.4&.3\end{pmatrix}.$$ I want to maximize $$\sum_{ij}a_{ij}\min(x_i,b_{ij}y_j)$$ subject to $x_1,x_2,...
1
vote
1answer
34 views
Where can I find a (well-documented) simple solver for linear optimization problems with both equality and inequality constraints?
I need to solve a linear optimization problem subject to both equality and inequality constraints in C++ (using MSVC 15). Mathematically, this can be solved by the simplex algorithm. Since I don't ...
0
votes
1answer
48 views
Equality constrained non-negative linear least squares
I have the following constrained linear least-squares problem:
$$\min_{x \in \mathbb{R}^n} \frac{1}{2}||Ax-b||_2^2,$$
$$\text{subject to } \sum_{i=1}^n x_i = 1 \text{ and } x_i \geq 0, \text{ for } ...
0
votes
0answers
10 views
Efficient line search algorithm to guarantee prescribed condition
Suppose $f : \mathbb R^n \to \mathbb R$ is a $C^2$-smooth function with $L$-Lipschtiz continuous gradient, i.e., $\|\nabla f(x) - \nabla f(y)\|_2 \le L \|x-y\|_2$. There is no assumption of convexity ...
1
vote
0answers
16 views
Trace-inequality on triangle
I need to show that for $f\in C^1(T)$ on a triangle $T$ with corner points $P$ and edges $E$ with $D=\max \{|P-x|:x\in E \}$
$$
\parallel f \parallel_{L^2(E)}^2 \leq \frac{|E|}{|T|}\parallel f \...
0
votes
0answers
12 views
Sobolev constant Inequality
For $-\infty<\alpha<\beta<+\infty$ the Sobolev constant is called
$$
C_S:=\sup_{g\in C^1[\alpha,\beta]\setminus\{0\};g(\alpha)=0=g(\beta)}\frac{\parallel g\parallel_{L^\infty(\alpha,\beta)}}{...
0
votes
0answers
8 views
Cost function for an optimization (Conjugate Gradient)
I am dealing with a nonlinear problem that I have defined such as the minimization of:
Error_function=integral(weight*(f(x)-mask)^2)
I have minimized it with the ...
1
vote
1answer
82 views
Gradient Descent inequality lemma
Does anybody know how could i prove this inequality?
Consider a sequence of vectors $v_1,v_2...v_T$ and an update equation of the form $w^{t+1}= w^t - \eta \cdot v_t$ with $w^1=0$.
Show that:
$$\...
0
votes
1answer
25 views
Find max vectors of a function numerically
I have a function $f(\vec{x})$ that converts a vector to a scalar. $f$ is relatively complex and thus this needs to be solved numerically. Maybe something like gradient descent.
I want to find the ...
0
votes
0answers
21 views
Maximizing 3 separate scenarios
I need help with the following business scenario. I’ve tried looking up the math myself, but I realize I was limited on the set up. I believe this will require second order differential equations, ...
0
votes
0answers
18 views
Right algorithm to minimize a function $f(x)$ over grid points $\{x_i\}_{i=1}^{N^n}\subset\mathbb{R}^n$
I want to minimize a uni-modal function (or want to do local-optimization)$f(x)$ over grid points $\{x_i\}_{i=1}^{N^n}\subset \mathbb{R}^n$ when gradient $\nabla f$ cannot be computed. In this case, ...
0
votes
0answers
15 views
Chebyshev System and Trigonometric polynomials
For $j\in\mathbb{N}_0$ let $\sin_j(x)=\sin(jx)$ and $\cos_j(x)=\cos(jx)$ for all $x\in\mathbb{R}$. How do I prove that the finite series of functions
$$
(1,\cos_1,\sin_1, \cos_2, \sin_2,...,\cos_m,\...
0
votes
0answers
18 views
Penalty-Approximated solution to quadratic program
Find the minimum of the following quadratic function
$U(x) = \frac{1}{2}x'Qx -qx'R +\frac{\alpha}{2}(x'd -b)^2$
Where Q is a positive semi-definite symmetric matrix, $x,R,d$ are $Nx1$ vectors, and $...
0
votes
1answer
50 views
Find maximum of a function when its integral is known
A very open question: have people considered a problem where the integral of a function is known (or we know a bound on it), and the goal is to find the location of its maximum?
Does this pop up in ...
0
votes
0answers
48 views
Convergence Rate of Projected Gradient Descent with Simplex Constraints
I'm trying to study the convergence rate, which is defined as
$$ \lim_{k \to \infty} \frac{f(x_{k+1}) - f(x_*)}{(f(x_k) - f(x_*))^p} = R$$ (where $x_k$ is the $k$-th iterate while $x_*$ is the ...
1
vote
1answer
52 views
Problem with finding the expected value of a trajectory under a constraint
I have a problem with trajectories $x(t)$ where $x(0) = x(T) = 0$ and $x > 0$ for all $t \in [0, T]$.
I know the joint probability $P(x, t)$ and can find the expected $\left\langle x(t) \right\...
2
votes
1answer
64 views
Vector subderivatives and “simple algebra” which turn out not to be so simple
In Friedman, Hastie and Simon (2013) an algorithm is proposed for a group-LASSO penalized regression possibly involving many variables. The problem is as follows:
$\underset{\beta}{min}\{ \frac{1}{2}|...
0
votes
2answers
44 views
A global optima: $\text{max}_{x} \frac{1}{2}\left\| X (a + b) \right\|_2^2 \ \text{s.t.} \ a^T X b \leq \delta; 0 < x \leq 1$,$X := {\rm Diag}(x)$
How to find (using any software) a global optimum for such a (non-convex) problem
\begin{align}
\text{maximize}_{x \in \mathbb{R}^{n \times 1}} \quad & \frac{1}{2}\left\| X (a + b) \right\|_2^2\\
...
4
votes
1answer
55 views
Generalizing the conjugate gradient like this works?
Given $A \in \mathbb{R}^{n \times n}$, a SPD matrix, and a vector $b \in \mathbb{R}^n$, it is possible to solve the problem
$$\min_x \| Ax - b\|$$
with the conjugate gradient method. Its algorithm ...
1
vote
1answer
55 views
How to optimize a function with the following constraints by using gradient descent?
I am not currently unfamiliar with a numerical optimization, so I am studying them. What I am wondering is that I'd like to optimize a certain function with the following constraints by using gradient ...
1
vote
0answers
68 views
Max-min and min-max equivalence for the optimization problem
I have the following max-min problem:
$\underset{{\bf X}}{\max} \underset{k}{\min} \|{\bf A}_k{\bf x}_k\|^2_2 $
where ${\bf X} = [{\bf x}_1, \dots, {\bf x}_K]\in \mathbb{C}^{N \times P}$ and ${\bf ...
2
votes
0answers
28 views
Prove that superlinear convergence of gradients implies superlinear convergence of sequence itself
I'm stuck on proving a result that is not specifically proven in a research paper.
https://people.maths.ox.ac.uk/cartis/papers/ARCpI.pdf
It is the proof of Corollary 4.8. I'm trying to show that $(4....
2
votes
0answers
43 views
Convergence of complex sequence with gradient descent
I am looking to solve the following otimization:
$\underset{{{{\bf x} \in \mathcal{X}}}}{\text{min}} \; f({\bf x})$
where ${\bf x} \in \mathbb{C}^N$ and $f({\bf x}) \in \mathbb{R}$, $f(x)$ is a ...
1
vote
0answers
13 views
Stopping criterion
I've seen this stopping criterion for iterative optimization algorithms such as Newton-Ralphson, Gradient Descent, etc. However, I do not remember its name nor where I saw it. It seems that this ...
0
votes
0answers
20 views
Proof of the convergence of a convex function with newton method
I need to prove the following:
Assuming that $f$ is convex, under the assumption that $f$ is convex and $x^{(0)} \geq x_\star$, the algorithm always delivers a converging sequence:
Theorem:
Let's ...
1
vote
1answer
51 views
Maximize constrained log-sum
Given constants $c>0$ and $\beta_i \in [0, \infty)^d$, for $i=1,..,n$, I want to (numerically?) solve the following problem:
$\max_{x \in [0, \infty)^d} \sum_{i=1}^n \log(\beta_i^T x), \text{ ...
0
votes
1answer
13 views
Initial feasible solution for barrier method
From this example page 9 It said set initial feasible solution at 2
here's barrier function:
$$T(x)=\frac{100}{x}+\frac{1}{r}(\frac{-1}{x-5})$$
after derivative:
$$\frac{\delta T}{\delta x}=\frac{1}{...
0
votes
1answer
74 views
Semi-infinite programming discretization theorem from the book ,,Theory, Methods, and Applications'
I think this theorem from Kortanek and Hettich book ,,Semi-Infinite Programming: Theory, Methods, and Applications'' is false.
(P) is a semi-infinite programming problem in the following manner:
$$\...
2
votes
1answer
47 views
Variational inference: Does the natural gradient follow geodesics locally?
Amari's natural gradient descent is a well-known optimisation algorithm from information geometry that is well-suited for finding optima of functionals on statistical manifolds. It consists of ...
0
votes
2answers
52 views
How to solve this quadratic program using the penalty method?
example:
$$\min\frac{1}{2}((x_1-3)^2+(x_2-2)^2)$$
s.t.$$-x_1+x_2{\le}0$$
$$x_1+x_2{\le}1$$
$$-x_2{\le}0$$
and we start with $~x^0=[3,2]^T~$ its violate the condition :
$$q(x,c)=\frac{1}{2}((x_1-3)^2+(...
3
votes
2answers
119 views
Efficient algorithm for determining whether value of convex optimization program is below some value?
Let $X$ be a convex subset of $\mathbb{R}^N$, let $c \in \mathbb{R}^N$.
I want to know whether
$$
\min_{x \in X} x^\top c < 0.
$$
Obviously, I can (efficiently, with standard software) evaluate ...
1
vote
0answers
21 views
Is there a way to identify singular points in a spectrahedron without finding the entire set?
I'm a physicist working in a non-linear optimization problem that reduces to a semidefinite program (SDP). In the simple low dimensional cases we workout in the research we could identify singular ...
4
votes
1answer
133 views
finding a solution to a matrix inequality
I would like to find a 19x19 matrix V such that the following inequality holds:
$$V^TAV<K$$
and where all entries of V are positive and the sum of entires in a row of V are equal to 1.
Also < is ...
0
votes
0answers
17 views
Stochastic Optimization with Piecewise Function
I have a stochastic optimization problem where my objective is a piecewise function:
$$ \underset{x}{\text{min}} \: \sum_{i=1}^{N} E(g(Y, x_{i})) $$
where $Y \sim N(\mu, \sigma^2)$ is a random ...
