Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
2
votes
1answer
48 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}|...
1
vote
1answer
46 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\...
0
votes
2answers
40 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\\ ...
6
votes
1answer
4k views

Jacobian of exponential mapping in SO3/SE3

Following this post Jacobian matrix of the Rodrigues' formula (exponential map) What if I really need the Jacobian of the exponential mapping function in $\omega \neq 0$? Basically, I want to ...
4
votes
1answer
51 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
51 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 ...
0
votes
0answers
15 views

What does “reduced-Hessian” mean? [closed]

What does "reduced-Hessian" mean? I came across this concept in the book named "numerical optimization". Thanks a lot.
2
votes
0answers
23 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....
3
votes
2answers
114 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 ...
2
votes
0answers
40 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
11 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
19 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 ...
0
votes
1answer
73 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: $$\...
1
vote
1answer
47 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{ ...
1
vote
1answer
37 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
1answer
830 views

Difference between gradient and Jacobian in gradient descent

What is the difference between the computation of gradient (the partial derivative of error w.r.t. weight) in gradient descent and the computation of the Jacobian in Levenberg-Marquardt algorithm?
0
votes
1answer
12 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}{...
4
votes
1answer
132 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 ...
1
vote
2answers
127 views

Solving a One Dimensional Problem with Interpolation of Vectors

I have the following optimization problem. $$\operatorname*{argmax}_{w} \|(1-w)\boldsymbol{X} -w\boldsymbol{Y}\|^2 \\ s.t. \quad 0<w<1 $$ How can I find the solution of this problem? May be ...
1
vote
0answers
17 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 ...
2
votes
2answers
609 views

Why Does the Projected Gradient Descent Method Work?

Consider the problem \begin{align*} \min_{x \in \mathbb{R}^n} &\quad f(x) \\ s.t.: &\quad x \in C, \end{align*} where $C$ is a convex set. As $C$ is convex, the projection onto $C$, $P_C$, is ...
8
votes
2answers
2k views

What Numerical Methods Are Known to Solve $ {L}_{1} $ Regularized Quadratic Programming Problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
0
votes
2answers
50 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+(...
0
votes
1answer
777 views

Can the Dinkelbach method solve nonlinear fractional programming problems?

Can the Dinkelbach method solve nonlinear fractional programming problems, where the functions in the numerator and denominator are not necessarily quadratic and not convex either? If not is there a ...
0
votes
0answers
13 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 ...
0
votes
1answer
698 views

Gradient descent and penalty method

I am seeking a minimum of a function under an inequality constraint. How can I set stop condition? The problem is that $\nabla f_p$ never goes to zero. The function: $$f(x_1, x_2)=\left(x_1 - 1\right)...
1
vote
0answers
25 views

How to numerically solving a spectral optimisation problem?

Consider the following one-dimensional eigenvalue problem \begin{align*} -\frac{d}{dx}\left(\sigma(x)\frac{du}{dx}\right) & = \lambda u \ \ \textrm{ in $(0,L)$} \\ u(0) = u(L) & = 0, \end{...
0
votes
0answers
21 views

Comparisons of Solving Speed of QP & SOCP

For two same scale optimization problem, quadratic programming (QP) and second-order cone programming (SOCP), which one is faster to solve? As far as I know, the computational complexity of QP and ...
3
votes
0answers
57 views

How can I apply backpropagation with matrix algebra? - Deep learning

Deep learning and backpropagation is taught out very badly and is often looks like a mess, according to me. So I want to start with a simple example about how to use backpropagation: Assume that we ...
0
votes
0answers
43 views

What is the arithmetic cost (computational complexity) of an SDP with nonlinear matrix inequality constraint

In the book ''Interior-Point Polynomial Algorithms in Convex Programming'' (Nesterov and Nemirovskii) section 6.4, there is a computational complexity result for the general positive semi-definite ...
0
votes
0answers
111 views

How to take derivative of log loss function in gradient descent?

I know the gradient descent about $z=wx+b$. But how to implement the derivative values of $w$ and $b$ in Python? I see some example like ...
0
votes
0answers
13 views

Specific number of Halton Points

I'm starting to study many article about numerical calculus and I see the definition of Halton Points (HP). But in this article sometimes one author use 289 HP, and sometimes another author use 1089 ...
2
votes
1answer
50 views

Why the solution does not converge in this optimization problem?

I want to use the "projected Gradient decent algorithm" to solve this optimization problem but I do not know why it does not converge. I appreciate if anybody can help me to find the mistake. Given $$...
3
votes
0answers
61 views

Adding identity to invert matrix

I'm looking into algorithm implementation which is essentially linear regression: $$\|Ax - b\| \rightarrow \min$$ Matrix A and vector b are estimated using data, then we do $A^{-1}b$ to find x. But ...
1
vote
0answers
30 views

Extracting diagonal of $J^TJ$ via automatic differentiation like techniques

First of all please, let me know if this question is more suited for scicomp.stackexchange.com or or.stackexchange.com, and ...
0
votes
0answers
28 views

Can we always find a proper step size?

In convex optimization, if we know the gradient of a function $f(x)$, then is it true that we could always find a way to determine a proper step size in the gradient descent method? When I say "proper"...
3
votes
0answers
37 views

LMI-based versus standard form semidefinite programs

In the context of semidefinite programming (SDP), under what conditions is it preferable to formulate and solve an LMI-based SDP rather than an equivalent standard form SDP? I have been told that ...
2
votes
1answer
1k views

Direct multiple shooting (numerical optimal control)

please, Iam currently implementing direct multiple shooting method* and I need one simple but fundamental concept answered: When I want to provide not only objective funtion value (result of ODE ...
1
vote
1answer
44 views

Positive semidefinite inequality

Let $\mathbf{A}\in\mathbb{C}^{m\times m}$, and $\mathbf{B}\in\mathbb{H}^{m\times m}$ be an $m$-dimension Hermitian matrix, solve $\theta$ that satisfies the condition \begin{equation*} e^{\jmath\theta}...
0
votes
1answer
17 views

Optimal approximation of nonlinear probability density function by piecewise constant density

Given a nonlinear probability density function F, the problem is to estimate F using histogram over a partition with N intervals. I have tried to realise this with MATLAB function fmincon, but it ...
5
votes
1answer
52 views

What is known about optimizing a function whose evaluation cost is variable?

Let's imagine I have a function $f(x)$ whose evaluation cost (monetary or in time) is not constant: for instance, evaluating $f(x)$ costs $c(x)\in\mathbb{R}$ for a known function $c$. I am not ...
3
votes
0answers
136 views

Verify if my idea is correct

Hi guys I have been reading Numerical optimization by Nocedal. While I was on the chapter on quasi- Newton methods it was mentioned that $g_{k+1}^Ts_k=0$ where $g_k = Ax_k -b^Tx_k$ if we use exact ...
0
votes
1answer
100 views

Quadratic programming on a small embedded device — can I do the hard work on my PC first?

I have the following constrained quadratic program in $x$ $$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^TQx + x^Tc\\ \text{subject to} & b_{\min} \leq Ax \leq b_{\max}\\ & x_{\min} \...
0
votes
0answers
18 views

Optimizing a system of equations to minimize purchasing cost

I am new to this (posting on stack exchange and higher level math in general) so please correct me where I am in error. I am trying to minimize the cost to my company for purchasing a certain product. ...
2
votes
2answers
82 views

How to choose two diagonal matrices minimizing the condition number

I have a matrix $A \in R^{n×n}$. I would like to choose two diagonal matrices $D_1,D_2 \in R^{n×n}$ such that $\text{cond}(D_1AD_2)$ should be minimal. How to provide such diagonal matrices?
1
vote
0answers
17 views

Formula for Area of a Triangle - nodal basis function

Let T be a triangle with corners $P_1, P_2, P_3$ and the nodal basis function $\lambda_1, \lambda_2, \lambda_3$ and $\alpha, \beta, \in \mathbb{N}_0$. I want to show that $$ \int_{T}^{} \lambda_1^\...
0
votes
1answer
39 views

Why is this inequality true in the proof of the convergence of Newton's method?

From Convex Optimization by Boyd & Vandenberghe: Let $f$ be a twice continuously differentiable convex function that is strongly convex with constant $m$, i.e., $\nabla^2 f(x) \succeq m I$ for $...
1
vote
1answer
23 views

Showing a Chebyshev set

I want to show that $\{1,e^{ix},...,e^{(n-1)x} \}$ is a Chebyshev Set on $(0,2\pi]$. Now I know that $\{1,x,...,x^n \}$ is one and that $e^{ix}$ is injective on $(0,2\pi]$. But how do I show that if I ...
1
vote
0answers
25 views

What are possible ways to update the Hessian if the calculated gradient is negative in BFGS algorithm (Quasi-Newton method)?

When applying the globalized BFGS algorithm (Quasi-Newton Method, optimization, minimization) to approximate the minimum of a function using the Quasi-Newton-Method, sometimes one can get a negative ...
1
vote
0answers
46 views

When is the simplex method slower than the ellipsoid algorithm?

In an undergrad class on linear programming, we learned about the simplex and ellipsoid methods for solving linear programs (LPs). I know that the simplex method is generally faster than the ellipsoid ...