Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

471 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
22 views

need difficult 2-3dim objective functions to optimize, by algorithm

for teaching purposes, I am looking for continuous compact functions defined over one or two variables that are deliberately chosen to illustrate how optimization algorithms can run into difficulties, ...
2
votes
0answers
23 views

Numerical analysis: Chebyshev coefficient representation error.

I am unsure if numerical analysis questions are suitable for this forum, but I have nowhere else to ask, so if this question is inappropriate, tell me and I will delete it. If $x_k$ are the Chebyshev ...
2
votes
1answer
226 views

Momentum in gradient descent

I often read about the importance of momentum in machine learning, namely, in neural networks. And as the partial derivative of the cost function w.r.t. to the weights gives us gradient descent, ...
2
votes
0answers
84 views

Confusion about Optimization partial derivative

I am confuse about maximization of a smooth, well behaved objective function $f(x,y, z)$ subject to the constraint that: $0\leq x \leq 1$ $y+z \leq 200$ $y,z$ are positive. The function $f(x,y,z)$...
2
votes
0answers
37 views

B-spline surfaces fitting references

I am looking for reference papers / publications regarding b-spline / NURBS surfaces fitting (I think I have noticed NURBS fitting is not very widespread so I guess most references will be related to ...
2
votes
0answers
215 views

Stochastic optimization vs stochastic programming

How should I think about the differences between stochastic optimization (SO) and stochastic programming (SP)? From Wikipedia, it seems that SO is a framework that uses randomness to solve a pre-...
2
votes
2answers
78 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?
2
votes
0answers
95 views

or Minimizing a sum of a product

I am trying to minimize a function and I was hoping that someone can point me in the right direction. I have tried using Lagrangian multipliers and experimenting with simple cases, but nothing has ...
2
votes
0answers
51 views

How does one solve non-linear systems of equations with only finite degree polynomial terms over the reals?

Consider a general polynomial non-linear system of equations as follows over the reals: $$ \begin{array}{c} f_1(x_1, \cdots, x_D) = 0 \\ \vdots \\ f_N(x_1, \cdots, x_D) = 0 \\ \end{array} $$ note ...
2
votes
0answers
62 views

Reducing sensitivity to initial guess for this nonconvex optimization problem

I'll start by formulating my problem. I am given a point and a plane. I am allowed to apply gains to the point such that it touches the plane, and is closest in 2 norm to the original point. The gains ...
2
votes
0answers
164 views

SVM classifier manual implementation differs from scikit

I'm trying to manually implement the scikit learn basic SVM classifier using the Gram kernel matrix $K$. The mathematic formulation is the following: \begin{align} \min_{\alpha\in\mathbb{R}^n} \...
2
votes
0answers
64 views

optimal orthogonal matrix in L1 sense

I want to find an orthogonal matrix $O\in SO(n)$ such that $\|Y - OX \|_1$ is minimized, where X and Y are matrices (of appropriate sizes). I know that there is a solution to this problem using SVD ...
2
votes
0answers
87 views

$\ell_1$ minimization with quadratic constraint

Is there a tractable solution to the optimization problem $$\min \|Ax\|_1 \mbox{ such that } \|x\|_2^2 = 1?$$ Because of the non-convexity of the equality constraint, it seems like this is hard. (In ...
2
votes
1answer
72 views

Explicit least-squares method for horizontal shifts of a function

I have a sequence of $N$ strictly positive real values $y_n$. They form some kind of peak; for simplicity, let's assume $f(x, \mu) = A \exp^{-(x-\mu)^2}$ is the shape, with $A$ and $\mu$ real (in the ...
2
votes
1answer
892 views

Does converting an inequality constraint to an equality one have any major impact on an optimization solver?

In an optimization problem, I have an inequality constraint, say $\begin{array}{c} {\min\limits_x~} c(x)\\ {s.t.~}g(x)\le 0 \end{array}$ The function $g(x)$ in general is unknown. So, numerical ...
2
votes
0answers
110 views

Index of a stationary point of constrained optimization

For an unconstrained optimization problem with objective function $F(x,y,z)$ the index of a stationary point is well-defined: If $(x^*, y^*, z^*)$ is a point where the gradient of $F(x,y,z)$ vanishes, ...
2
votes
0answers
77 views

Isotonic regression like

I have 2 ordered sets $$X=\{X_1<\dots<X_n\}$$ and $$Y=\{Y_1<\dots<Y_m\}$$ with $X_1<Y_1$ and and $X_n<Y_m$. I wish to approximate an increasing continuous function $g$ by piecewise ...
2
votes
1answer
2k views

Gradient descent: L2 norm regularization

So I've worked out Stochastic Gradient Descent to be the following formula approximately for Logistic Regression to be: $ w_{t+1} = w_t - \eta((\sigma({w_t}^Tx_i) - y_t)x_t) $ $p(\mathbf{y} = 1 | \...
2
votes
4answers
450 views

Linear Least Squares with Linear Equality Constraints - Iterative Solver

I am looking for iterative procedures for solution of the linear least squares problems with linear equality constraints. The Problem: $$ \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2}, \...
2
votes
0answers
44 views

What is the logic behind the given optimization problem?

I am following a book which has a part on numerical optimization techniques. In order to elaborate Karush-Kuhn-Tucker theorem, they gave the following example: When the unconstrained solution $x=A^+ ...
2
votes
0answers
151 views

Optimization Problem Involving an Integral Equation

I have an integral equation for a probability current $j(t)$ given by: $$ \large\frac{1}{\sqrt{t}} e^{-\frac{\bar{x}(t)^2}{4 t}} = \int_0^t \frac{j(t')}{\sqrt{t-t'}} e^{-\frac{\left[\bar{x}(t)-\bar{x}(...
2
votes
0answers
794 views

references: L-BFGS rate of convergence

I was trying to find results about the rate of convergence for the L-BFGS algorithm (in the nonlinear case). What I end up with so far is that the BFGS-Algorithm converges Q-superlinearly this 50 ...
2
votes
0answers
67 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and $|\cdot|_{BV}...
2
votes
1answer
303 views

Good convergence criterion for stochastic optimization?

This is a question that has bothered me quite long, as I have faced it many different optimization and equation solving problems. The basic idea is that one wishes to minimize $F(x)$ and has one ...
2
votes
1answer
110 views

why not handle box-constraints with a transformation

I have a question that I've always wondered about concerning the "L-BFGS-B" algorithm. I am not familar with the details of the algorithm except for the fact that it optimizes a non-linear function ...
2
votes
0answers
43 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving $...
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 ...
2
votes
0answers
50 views

Quantitatively comparing event trains of different lengths for Poissonness

I have a parameterized, effectively black box process that generates a series of events (simulated action potentials). Different parameter values often lead to different numbers of events. How can I ...
2
votes
1answer
396 views

Scale-invariance of Simpson's rule approximations to log

If I was trapped on a desert island and needed to compute $\log(2)$, the natural logaritm of $2$, one thing I could do is use the equality $$\log(2) = \int_1^2 \frac{1}{x} \ dx$$ and approximate the ...
2
votes
0answers
169 views

Optimization - show that linearized feasible set is empty.

I need help in the following problem: Consider the following optimization problem $$ \min_{x_1,x_2}-x_1-x_2\quad\text{s.t.}\quad x_1^2+x_ 2^2-1=0,\quad x_1,x_2\geqslant 0.$$ Show that the ...
2
votes
0answers
121 views

Levenberg-Marquardt stalling

I am trying to solve an optimization problem of the form $$\min_q E(q) = \min_q \frac{1}{2}f(q)\cdot f(q),$$ for $f:\mathbb{R}^n \to \mathbb{R}^m$, using Levenberg-Marquardt, i.e. starting from an ...
2
votes
0answers
99 views

Estimate the number of Local Minima

I am asking this question about local minima, but actually I started by trying to find the global maximum/minimum over a compact set, of a smooth function (the objective). The function has a random ...
2
votes
0answers
126 views

Steepest Descent/Newton

Suppose these over-determined system of equations: $$ |\mathbf{x}^T\mathbf{v_n}| = A, \qquad n = 1,2,\cdots,N-1 $$ $$ \mathbf{v_n}= [1 \quad w^n \quad w^{2n} \quad \cdots \quad w^{(N-1)n}]^T , \...
2
votes
0answers
146 views

Divergence of Gradient Method

Is there any example of a continuous differentiable function out there, in which the gradient method with Armijo's stepsize-rule doesn't converge? I found it pretty hard to create one myself because ...
2
votes
1answer
165 views

Formulate optimization problem

My research area has "nothing to do with mathematics" but I still find it full of optimization problems. Therefore, I would like to learn to formulate and solve such problems, even though I am not ...
2
votes
0answers
73 views

Customising force-directed graph layout

I would like to implement a variant of the force-directed graph layout where some nodes are constrained to moving only along a predefined curve (e. g. circle). I looked at some implementations using ...
1
vote
0answers
17 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{...
1
vote
0answers
28 views

Optimization with convex cost and bilinear constraint

What algorithms with proven convergence to the global optimum are there for the following problem? $$ \begin{array}{cl} \min \limits_{x \in \mathbb R^n,y \in \mathbb R^m} & J(x,y) \\ \text{s.t.} &...
1
vote
0answers
29 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 ...
1
vote
1answer
37 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}...
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^\...
1
vote
0answers
20 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 ...
1
vote
0answers
40 views

$\lambda_{max}$ in trust region method: Leveberg-Marquardt algorithm

I am learning levenberg-marquardt algorithm and in the process implementing the same. I am comfortable with the $Jacobian$, $Hessian$ and step size computation. For trust region implementation, I have ...
1
vote
0answers
35 views

Understanding/Proving a theorem in Numerical Optimization by Nocedal

I was reading this book specially theorem 8.4 on page 210. Suppose that a method in the Broyden class is applied to a strongly convex quadratic function $f : R^n \rightarrow R$, where $x_0$ is the ...
1
vote
1answer
26 views

How to use Finite Difference Method solving ODE with Boundary Value Problems?

Using these formulas, it is clear how to solve the problem: For node 1, we have the boundary value on the left side, for ex. $u(0) = 0$ and for node 2, we use the formula replacing $u''$ with $u_{i-1}...
1
vote
0answers
31 views

Derive Hessian inverse update using Sherman-Morrison in Quasi Newton Method

From Nocedal's Numerical Optimization book, the Hessian approximation equation is given using Symmetric Rank 1 (SR1) formula as follows: $$B_{k+1} = B_k + \frac{(y_k - B_ks_k)(y_k - B_ks_k)}{(y_k - ...
1
vote
0answers
24 views

How to implement Finite Difference Method ODE Boundary Value Problem in Python?

I implemented the Finite Differences Method for an ODE with Boundary Value Problem. Here is the approximations I used for the FDM: And here is the balk problem: with u(0) = u(L) = 0 (attached on ...
1
vote
0answers
25 views

Convergence Rates of Stochastic Gradient Descent with different sample size

Given a convex function $F(x)$ to be optimized with $F(x^*)$ being the optimal value at $x^*\in\mathbb{R}^n$. The difference $|F(x)-F(x^*)|$ is called the excess error. Using Stochastic Gradient ...
1
vote
1answer
67 views

Newton step for ${\min}_{x \in \mathbb{R}^n} \ \sum_{i=1}^n -\ln(1 + \eta_i x_i) \ $ s.t. $A x \leq b$; $-x \leq 0$ to be used in primal-dual

I have a following problem on hand. P1: \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & \sum_{i=1}^n -\ln(1 + \eta_i x_i) \equiv -e^T \ln(e + \eta \odot x) \\ \text{subject to }\quad &...