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.

0
votes
0answers
9 views

Reference on one iteration convergence of gradient projection algorithm (Bound constrained optimization)?

So for a bound constrained optimization problem of minimizing a continuously differential function f(x) with $x^*$ which is a non degenerate solution, I was interested in showing that if all bound ...
1
vote
0answers
13 views

Show convergence of an algorithm within $m$ steps

I am trying to show that the following algorithm with will converge within $m$ steps. Assumptions $A$ is symmetric positive definite with $m$ distinct Eigen values then \begin{align} \text{for } &...
0
votes
0answers
24 views

Characterizing class of functions from their gradient descent trajectory

Let $f : \mathbb R^d \to \mathbb R$ be a function with at least one minimum. Suppose that $f$ has the property that the gradient descent trajectory from any point of the function is a straight line to ...
-3
votes
0answers
18 views

how to prove equation 3.19 in page 40 of “numerical optimization” second edition, Jorge Nocedal [on hold]

how to prove equation 3.19 in page 40 of "numerical optimization" second edition, Jorge Nocedal enter image description here
2
votes
0answers
10 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 ...
1
vote
0answers
36 views

Find minimizer of mean values

i'd like to know if there is an analytical method to solve the following optimisation problem : $\forall i=1,..,n$ find $\omega_i^{}$ and $\alpha_i^{}$ such that: $\dfrac{1}{n} \displaystyle \sum_{i=...
0
votes
0answers
22 views

Is it possible to specify optimization algorithm in CVX? [closed]

I am using CVX as a bench mark to debug my MATLAB code for gradient descent algorithm. Although CVX gives me a good reference point, I was wondering if it is possible to ask cvx to solve optimization ...
0
votes
1answer
22 views

How to work around a nonconvex constraint?

My objective function is \begin{align} \text{minimize}_{\mathbf{x} \in \mathbb{R}^3} \quad & \mathbf{x}^T\mathbf{M}\mathbf{x} \\ \text{subject to }\quad & x_1 = 1\\ & x_3=x_1x_2=x_2 \...
0
votes
0answers
14 views

Superimpose an item of the chaotic sequence on vector

In the article "Improved Chaotic Gravitational Search Algorithms for Global Optimization" on page 1223, in step 6 of the pseudo-code "Chaotic Local Search Algorithm", the phrase "Superimpose an item ...
1
vote
3answers
92 views

Why do we need approximation methods when we have algorithms to find exact roots?

While I was studying numerical methods and optimizations recently, I observed that whenever we find a root to an equation or a system of linear equations, we always find approximate roots. However, we ...
1
vote
0answers
43 views

Optimisation under constraint of Wasserstein distance

Let $\mathcal P_n = \{P \in \mathbb R^n_{\geq 0}: P^T \mathbb I = 1 \}$, where $\mathbb I = (1,...,1)^T \in \mathbb R^n$ and $f: \mathcal P_n \to \mathbb R$ a convex and differentiable function (or ...
0
votes
0answers
24 views

Is there efficient Surface Walking method for optimization problems with equality constraint?

To my best knowledge, if we want to find the minimum of a function $f$ defined on a $d$-dimension manifold $M$ in $\mathbb{R}^n$, a.k.a an optimization problem with equality constraint, the most ...
0
votes
0answers
11 views

Roots of a n-variable non linear function with numerical methods

Currently I am working with finding the solutions for the following problem: I have a unit sphere in which I have n points defined by their polar and azimuthal angles: $\theta_n , \phi_n$. I then do ...
0
votes
0answers
11 views

Prove that $\xi_{k+1} = (-1)^{k+1}(\alpha_0 \times \alpha_1 \times \dots \times \alpha_k)$ is the (k+1) coefficient of $p_k$

I was given the following question as part of a homework assignment. Any help would be greatly appreciated! The following image shows the steps of a preliminary version of the conjugate gradient ...
0
votes
0answers
21 views

Optimization with difference equation constraint

I'm working on a problem where I have a (vector) linear recurrence relation of the form $$ a_{n+1} = \lambda \circ a_n+b_n $$ I need to solve the following optimization problem: $$ \min\limits_{b_n}...
1
vote
0answers
40 views

Use Conjugate Gradient to obtain the Eigenvalues

So I have been told that we can use CG to obtain an eigenvalue approximation to the true matrix. I am not sure how? (Connection to Lanczos) Furthermore I have been told that there is a deep ...
0
votes
0answers
21 views

Confused about Nesterov momentum gradient descent algorithm

I've found a variety of variations of writing Nesterov but I cannot understand why they cannot simply be expanded into a one liner. Here is one I found that can just be re-arranged, can someone ...
2
votes
2answers
84 views

Optimal Value of a Cost Function as a Function of the Constraining variable

Consider the optimization problem : $ \textrm{min } f(\mathbf{x}) $ $ \textrm{subject to } \sum_i b_ix_i \leq a $ Using duality and numerical methods (with subgradient method) i.e. $d = \...
1
vote
1answer
36 views

Iterative algorithm for a simple linear optimization problem

Let $c_1,\dots,c_n$ be $n$ positive numbers and so be $a_1,\dots, a_n$. For some $r$ such that $1\leq r\leq n$, consider the optimization problem \begin{align} \max_{x_i\in\mathbb{R}}&~~\sum_{i=1}^...
2
votes
0answers
55 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 ...
1
vote
2answers
53 views

Expanding $\frac{1}{1-x}$

Is there any kind of expansion of $f(x)=\frac{1}{1-x}$, possibly with polynomials, such that with only a few terms I can represent with an error smaller than $10\%$ the function over the interval $[0, ...
0
votes
0answers
15 views

General Chebyshev approximation

I am having trouble understanding it, first of all, what is x? Are x's coefficients of this polynomial we are looking for? This would mean that the polynomial is of degree $n-1$ because it has n ...
2
votes
0answers
85 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
1answer
37 views

Recovering a matrix from a linear ODE given observations

To make this simple, let's say we have $x: \mathbb{R} \rightarrow \mathbb{R}^2$ such that $$\frac{d}{dt}\vec{x}(t) = \begin{pmatrix} x_1'(t) \\ x_2'(t) \end{pmatrix} = A \vec{x}(t)$$ for some constant ...
0
votes
0answers
11 views

Minimize Error for Expansion of $1/(1-x)$ with fewer terms

Suppose you want to expand $f(x) = \frac{1}{(1-x)}$ around some point $x_0$ for $0<x<1$ Call the expansion of $f$ around $x_0$ as $Exp_{x_0}f$. I want to compare the performance of $Expf$ vs $...
0
votes
0answers
23 views

Zoutendijk's Lemma Using Goldstein Conditions

I am reading Numerical Optimization by Wright and Nocedal and in page 39, it says that a similar result to Zoutendijk's lemma (Theorem 3.2) can be proven using the Goldstein conditions instead of the ...
0
votes
1answer
36 views

Getting to the gradient descent algorithm

I understand that gradient descent comes from the (quite natural) idea that we might want to choose our next weight vector ($w^{t+1}$) as $$w^{t+1} = \arg \min_w \frac{1}{2} \|w-w^t\|^{2} + \eta f(w^...
0
votes
0answers
34 views

I am trying to find the maximum learning rate or stepping rate of steepest descent algorithm in 2 dimensions

Let $f(x,y) = (x-y)^4+2x^2+y^2-x+2y$. I am trying to numerically find the miniumum of $f$. We define a fixed-point iteration scheme \begin{align*} g(x, y) = \vec{x}_{n+1} = \vec{x}_{n} - a\nabla f \...
0
votes
1answer
33 views

Minimizer of a multivariable function and iteration through Newton's method

I got stuck on the following question. Find the minimizer for $$f (x_1,x_2) = \frac 12 (x_1^2 - x_2)^2 + \frac 12 (1-x_1)^2$$ and compute one iteration for minimizing $f$ from point $(2,2)$. Also, ...
1
vote
0answers
28 views

What methods can solve SOCP problems?

What methods can solve SOCP problems? I need at least few different. By: https://en.wikipedia.org/wiki/Second-order_cone_programming it seems that the problem "reduces" to simpler problems, but I'...
0
votes
1answer
69 views

Finding a global minimum

I seek the function $f$ which satisfies the 100 equations (i=1,2...100) $\sum_{j=1}^{2000} f(A_{ij},B_{ij},C_{ij})=Q_i$. Where $A,B,C$ are 100x2000 matrices and all entries are between 0 and 1. ...
1
vote
2answers
30 views

Differential equation: mixed boundary condition, how to solve numerically?

I have a differential equation (dot means derivative w.r.t time) $$(\dot x, \dot y) = f(x,y)$$ and I am given the initial condition for $x$, but a final condition for $y$: $$x(0),\qquad y(1)=g(x(1))$$ ...
0
votes
1answer
35 views

Applying a quasi newton (L-BFGS) method to a non differentiable cost function.

I'm reading through a paper which presents at some point an optimization step to a function of the form: $$ E = \sum_i \left|\alpha_i - \beta_i \right| $$ where $\alpha_i$ and $\beta_i$ are also ...
0
votes
0answers
17 views

Quadratic programming terms

Help me to understand the terms of this quadratic programming problem? $$ P{\left(U,Z,W\right)} = \sum_{p=1}^{k} \sum_{i=1}^{n} \sum_{j=1}^{m} U_{ip} W_{pj} ( X_{ij} - Z_{pj} )^{2} +{1 \over{2}}a \...
1
vote
1answer
39 views

Approximate $f''(x)$ given $f(x),f(x+h),f(x+3h),f(x-5h)$

Given $f(x),f(x+h),f(x+3h),f(x-5h)$, approximate $f''(x)$. Book's solution: From Taylor' series, $$ \\ f(x+h)=f(x)+f'(x)h+0.5f''(x)h^2+{1\over6}f'''(x)h^3+O(h^4) \\ f(x+3h)=f(x)+3f'(x)h+4.5f''(x)h^2+...
3
votes
1answer
117 views

Linear Least-Squares Problem with Inequality Constraints on Residual

I have an over-determined linear least-squares problem $$\min_{\vec{x}}\Vert\mathbf{A}\vec{x}-\vec{b}\Vert_2^2,$$ where $\mathbf{A}\in\mathbb{R}^{n\times m}$, $\vec{x}\in\mathbb{R}^m$, $\vec{b}\in\...
0
votes
0answers
23 views

Manifold Optimization in Human understandable language

I am coming across a project that involves with "manifold optimization". I don't know what that is. After Googling for a bit, my understanding is that we use a low dimensional surface to approximate ...
0
votes
0answers
19 views

Computing the element-wise logarithm of a matrix exponential more efficiently?

Is there any known way to compute the element-wise logarithm of a matrix exponential more efficiently? Motivation: I am trying to an optimization problem (basically finding a specific Markov ...
0
votes
1answer
20 views

Operational cost of vector and matrix multiplications

Find the computational cost of a column vector $x$ multiplied by a row vector $v$ I computed n multiplication operations and n - 1 addition operations, so would that make for $n(n-1)$ operations ...
0
votes
1answer
39 views

Inequality constraints and the max function

Let $g_i(x):\mathbb{R}^{n} \to \mathbb{R}$, for $i=1,\ldots,n$, be continuous convex functions. Define $g_{\rm max}$ as $g_{\rm max}(x) \triangleq \mbox{max}_{i=1,\ldots,n}\{g_i(x)\}$. Define also the ...
0
votes
1answer
34 views

$ \sum_{i = 1}^{m}\lambda_i v_i v_i^T$ for $v_1,v_2, \ldots,v_m \in \mathbb{R}^n$ linearly independent has rank $m$ $(\lambda_i \neq 0)$

I often see this formula used in the rank 1 or rank 2 cases for Quasi-Newton methods, but I am wondering how this can be proven in the general rank $m$ case. As a linear algebra problem, I would like ...
3
votes
0answers
33 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 ...
0
votes
1answer
33 views

How to solve a minimize problem with maximize a subproblem

I have a minimization problem $$\min_{x, y} \{f(x, y) + \max_{y} g(y)\}$$ which has a max subproblem inside it. How to solve it? Will alternating optimizing converge to the optimum?
0
votes
0answers
38 views

Are step sizes in quadratic programming solvers analytically exact?

In this paper (DOI link), Goldfarb and Idnani describe an algorithm for solving a certain subset of quadratic programs. This algorithm (or a very similar one) is implemented in the quadprogpp package ...
0
votes
1answer
17 views

What is a nontrivial minimizer?

I came across a statement that x is a nontrivial minimizer of some function, but couldn't find a definition of "nontrivial minimizer" on the Internet. Can anyone help point out some references for ...
3
votes
1answer
56 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 ...
1
vote
0answers
48 views

Reference request. Rigorous numerical optimization

I am looking for texts on Numerical optimization that are closer to Analysis definition-theorem-proof style texts. EDIT: This is my first acquaintance with numerical optimization. My institution ...
2
votes
0answers
56 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}$$ ...
0
votes
0answers
18 views

Do BFGS and L-BFGS methods converge when the matrix $H=B^{-1}$ is ill-conditioned?

I am using BFGS and L-BFGS to solve an unconstrained optimization problem. The objective function is the Mean Euclidean Error. The output is given by an Artificial Neural Network. The line search ...
0
votes
0answers
21 views

Minimum path distance from a source

Suppose I have a path-connected subset $I$ of $\mathbb{R}^n$ (not convex, but can be contained in a product of finite-measure closed intervals), and I define a "source point" $a \in \mathbb{R}^n$. ...