Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

7
votes
0answers
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 ...
4
votes
0answers
476 views

Gradient Descent Divergence

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 ...
4
votes
0answers
67 views

Is there analytic solution to this functional problem?

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^\...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
3
votes
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 ...
3
votes
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)$ ...
3
votes
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. ...
3
votes
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 ...
3
votes
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) ...
3
votes
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}=...
3
votes
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\...
3
votes
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}}$$...
3
votes
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+\...
3
votes
0answers
216 views

Accelerated gradient descent versus nonlinear conjugate gradient descent

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)$...
3
votes
0answers
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 ...
3
votes
0answers
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. ...
3
votes
0answers
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....
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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}$ ...
2
votes
0answers
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}$$ ...
2
votes
0answers
37 views

Non-convex numerical optimization

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\...
2
votes
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 ...
2
votes
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} ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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)...
2
votes
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 ...
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
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 ...
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
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 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
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-...
2
votes
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 ...
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
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} \...
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
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 ...
2
votes
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, ...
2
votes
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 ...
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
148 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
784 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 ...