Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

460 questions
91 views

Recommendation for intro to geometric integrators?

Explicit Request Looking for book or lecture note recommendations on numerical optimization that (ideally) have the following: Emphasis on geometric and physical intuition Emphasis on symplectic ...
476 views

I am curious about divergence conditions of the Gradient Descent method. In the reading that I have done I have only ever seen it mentioned that this method diverges when $\alpha$ is too large. It ...
67 views

Let $f(x)$ be a function on $[0,+\infty)$. I want to solve the following functional problem: $\min L(f)=\int_0^{\infty} (f'(x))^2\mathrm dx$ subject to $f(0)=a$ $f(x)\ge 0,\forall x$ $\int_0^\... 0answers 284 views Is there a name for this modified Newton method, and prove the convergence. I can't seem to find the name of this method anywhere in literature, but it has appeared in my assignment. Modified Newton Method. Let$f\in C^2$, convex,$\mathbb{R}^n\to\mathbb{R}$. The ... 0answers 174 views Qualities of Projected Gradient Methods Consider the following constrained minimization problem:$ min_{x \in X} \ f(x) $where$ X \subset \Bbb{R}^{n} $is a nonempty closed convex set and f is continuously diferentiable. I'm ... 0answers 722 views Real-time linear programming I'm going to implement in C a light-weight embedded LP solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programs with ~6-60 variables and ... 0answers 34 views Optimizing intervals in piecewise function I am not sure what the relevant tags are (or how to best described the problem). I have a piecewise function where for a particular interval element there is a known functional form (e.g. for ... 0answers 73 views Infinite dimensional convex linear optimisation problem I have the following problem: The functions$a_i(x) > 0$and$b_i(x) > 0$for$x\in I \subset \mathbb{R}$,$I$compact, and$i=1,\ldots,n$are given. The objective is to find functions$f_i(x)$... 0answers 78 views Maximize rank of Gramian kernel matrix Suppose we have a data matrix$X \in \mathbb{R}^{m\times n}$, where$m\gg n$. This matrix represents a series of measurements of a physical system, where each column represent a single measurement. ... 0answers 407 views Gradient descent with box constraints and possible non-convex function. Hope you are well. I am working on an optimization problem, quadratic (see below). Of the 4 variables there are but 2 that have a negativity constraint. Am I correct to say that gradient descent is ... 0answers 161 views ADMM fails to converge on convex problem. Are there any tricks of trade for application? Convex Problem I am trying to solve the semidefinite program:$\min y$(Objective, 0) subject to$y\geq0$(Nonnegative, 1)$y I + \Sigma_0 = \sum^{n}_{i=1} x_i \Sigma_i + Z$(Linear Equality,2) ... 0answers 342 views Generalized gradient descent with constraints In order to find the local minima of a scalar function$f(x)$, where$x \in \mathbb{R}^N$, I know we can use the projected gradient descent method if I want to ensure a constraint$x\in C$: $$y_{k+1}=... 0answers 147 views Efficient algorithm for lower-bound least squares. We have: A \in \mathbb{R}^{n \times m} with independent columns, y \in \mathbb{R}^n. Moreover, n \gg m. Consider the following problem, where the inequality is elementwise:$$x^{\star} := \arg\... 0answers 38 views Numerical “helper solver” to solve polynomial matrix equation system? I have noticed that when solving the following matrix-polynomial: $$\sum_{k=0}^N{\bf C}_k{\bf T}^k = {\bf 0} \hspace{0.6cm} \text{ s.t. } \hspace{0.6cm} {\bf C}_k,{\bf T} \in\mathbb{R}^{{M\times M}}$$... 0answers 103 views how to find the the maximum of an implicit function I have an implicit function and I would like to find the value of$h$that maximizes$R$, i.e, I want to find$h$that satisfies$\frac{\partial R}{\partial h} = 0$. The function is,$C=\frac{A}{1+\...
216 views

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has $O(1/T^2)$...
92 views

Software tools for medium-scale systems of polynomial equations

I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real ...
239 views

Does convexity of a function guarantee tractability of finding its minimum?

Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not. ...
1k views

Optimization over function spaces

There are many methods to solve optimization over standard spaces such as real and complex numbers or vector spaces of these. In my case I have a vector space of functions of a real value to find. e....
24 views

Globalized BFGS (Quasi-Newton method) condition

I didn't find any information on the internet about the globalized $\textit{BFGS}$ method. Wikipedia only talks about the normal BFGS, without this ...
11 views

Finding the domain shape, where the fundamental Helmholtz Eigenmode has certain properties at a boundary

The following is a problem about finding the shape of a domain such that the fundamental Helmholtz eigenmode has certain properties at the boundary of the domain. I search for an analytical or ...
61 views

How do I pack 2D objects into an arbitrary shape?

I've heard of packing problems in general, and I've seen a couple questions on this site that address specific cases (e.g. how to pack 45-45-90 triangles into an arbitrary shape), but after a search I ...
88 views

Using Coordinate Descent on Projected Space

My goal is to maximize an objective function using coordinate descent over a 3-dimensional vector. In the simple case the domain over which I am maximizing is defined as follows: $X \in \mathcal{X}$ ...
59 views

How to solve a large scale convex optimization problem?

Consider the following convex optimization problem in vectors $x$ and $y$ $$\begin{array}{ll} \text{minimize} & f(x,y)\\ \text{subject to} & g_1 (x)\le 0\\ & g_2 (y)\le 0\end{array}$$ ...
37 views

I am looking for a way how to prove/show that one problem is easier to optimize(more robust to starting guesses) than another. Suppose I have two non-convex functions from $L_1,L_2:\mathbb{R_+}^8\... 0answers 21 views Gradient of function with index operation First of all, please let me know if anything is off with my notation. I am a computer scientist and as such I am not that strict about notation. In my problem I want to optimize an objective function ... 0answers 60 views How to show convergence of Frank-Wolfe algorithm ( or conditional gradient method)? Let$g(w)$be a differentiable convex function. Frank-Wolfe algorithm over a convex set$C \in \mathbb{R}^n$is defined so as to find the local minimum of the function: $$s_{t+1}=\arg\min_{s \in C} ... 0answers 23 views Numerical Integration Schemes for a Hemispherical Region I am struggling with a problem that requires me to numerical integrate a function within a hemisphere. While the function is smooth, it is pretty nasty, extremely oscillatory and I have to calculate ... 0answers 39 views Self-study - Numerical Optimization Is there any available online course on Numerical Optimization other than NPTEL courses? I'm also looking for lecture notes or textbooks that are suitable for self-study with lots of examples and ... 0answers 24 views Methods for numerically solving field shapes for multiple permanent magnets. I am trying to optimize an engineering setup which involves an arrangement of permanent neodymium magnets in 3d space. I am planning on using Houdini to solve the optimization as a simulation, which ... 0answers 58 views Is there an equivalence between subgradient and stochastic gradient? Consider the optimization problem$$\min_x \; f(x) := \sum_{i=1}^m f_i(x).$$A subgradient method at each iteration takes a subgradeint descent step$$ x^+ = x - \alpha g, \quad g\in \partial f(x)... 0answers 56 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 ... 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. ... 0answers 62 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 ... 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, ... 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 ... 0answers 81 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 1y+z \leq 200y,z$are positive. The function$f(x,y,z)$... 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 ... 0answers 192 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-... 0answers 94 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 ... 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 ... 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 ... 0answers 162 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} \... 0answers 64 views optimal orthogonal matrix in L1 sense I want to find an orthogonal matrixO\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 ... 0answers 86 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 ... 0answers 108 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, ... 0answers 75 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 ... 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^+ ...
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}(...