Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
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 ...