Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

475 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
63 views

Finding a point with maximum distance from a given point in a polyhedron

We are given the polyhedron $X=\{x:Ax\le b,x\ge 0\}$ and the point $y\in X$. We want to find a point $x \in X$ such that $d(x,y)$ is maximized. The function $d(x,y)$ represents the distance between ...
2
votes
0answers
46 views

Monge Ampere Numerical Analysis

This is an example of the Monge-Ampere equation from "C0 penalty methods for the fully nonlinear Monge-Ampere equation, Mathematics of Computation, 80:1979-1995, 2011." by S.C. Brenner, T. Gudi, M. ...
2
votes
0answers
66 views

Optimality guarantees of SGD convergence in Geometric Programming

What guarantees of optimality do we get when minimizing with Stochastic Gradient Descent a problem in its original formulation, after showing that it is a Geometric Programming instance (i.e. can be ...
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
248 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
85 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
237 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
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?
2
votes
0answers
98 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
63 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
169 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
75 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
909 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
476 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
153 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
805 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
69 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
310 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
113 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
45 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
51 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
398 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
170 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
124 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
106 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
166 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
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 ...
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 ...
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{...
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 ...
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
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 ...
1
vote
0answers
43 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
37 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
27 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
40 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 - ...