Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

471 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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 ...
5
votes
1answer
46 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 ...
4
votes
0answers
487 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
286 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
726 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
43 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 ...
3
votes
0answers
55 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 ...
3
votes
0answers
34 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 ...
3
votes
0answers
134 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 ...
3
votes
0answers
37 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
1answer
255 views

A good book on programming for numerical optimization

I was hoping someone could recommend a good book on programming for numerical optimization--including lots of code examples. I am reading Nocedal and Wright, which is great. One of the recommendations ...
3
votes
0answers
80 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
80 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
415 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
167 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
346 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
148 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
219 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
2answers
913 views

Maximizing “log det + log sum exp” function

I'm trying to find a numerical solution to the following optimization problem $$ \text{maximize } f(M) = \frac{1}{2} \log \det(M) + \log \sum_{i=1}^n \exp \left\{ - \frac{1}{2} x_i^T M x_i + a_i \...
3
votes
0answers
94 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
1answer
154 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
3
votes
1answer
406 views

Initialization of Limited-memory BFGS (using libLBFGS)

I am using the package libLBFGS in order to minimize an objective function, for which the first derivative (with respect to the optimization variable) is known and computable. I use the default ...
3
votes
1answer
273 views

Rewrite constrained optimization objective

I wanted to ask, under which conditions can one rewrite the optimization objective $\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$ as $\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$ I have particular interest ...
3
votes
0answers
242 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
2answers
123 views

Numerical optimization question

I need to solve the following optimization problem. \begin{aligned} \min_{\lambda_0,\lambda_1} & \sum_{t=1}^T\sum_{n\in\{4,8,12,16\}} \left(\frac{1}{n}A_n + \frac{1}{n}B_n^\top X_t + y_t^{(n)}...
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....
3
votes
1answer
61 views

How can I check for the accuracy of numerical result to optimization problem?

How can I check for the accuracy of numerical result to optimization problem? Or when is this possible? Intuitively it could be possible at least to some extent, when one knows how to find analytic ...
2
votes
1answer
47 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 $$...
2
votes
0answers
25 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
47 views

A “divide-and-conquer” iterative procedure for minimizing a sum of convex functions

For simplicity, let's assume $f_i: \mathbb{R} \to \mathbb{R}$ is convex and define $$ g(x) := \sum_{i=1}^{n}f_i(x) $$ Suppose we want to compute $$ x^* := \arg\min_{x \in \mathbb{R}} g(x) $$ ...
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
63 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
40 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
23 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
64 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
40 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
1answer
99 views

Maximize the modulus of a sum of complex exponentials on a given interval

I am trying to find $$\hat{t}=\underset{t \in [a,b]}{\text{argmax}}\,\left|\sum_{j=1}^n e^{i x_j t}\right|$$ where $t$ is a real number, $[a,b]$ is a given interval, $i$ is $\sqrt{-1}$, and $x_j$ are ...
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
57 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
64 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 ...