Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

474 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
130 views

Difficulty implementing logarithmic barrier in Matlab.

I'm trying to create a convex optimization code in Matlab , to deal with inequality constraints I'm using logarithmic barrier.Suppose we have inequality $g(x) =< 0$ to satisfy,so I define $\varphi ...
1
vote
0answers
84 views

Can Gauss-Newton algorithm give better optimization performances than Newton algorithm?

I am currently facing the problem of a robotic manipulator calibration: the goal is to find the best correction that must be applied to a set of kinematic parameters describing the robot model, in ...
1
vote
0answers
104 views

Solution to Primal-Dual Optimization Problems

I know that I must be wrong, but I'm hoping someone may be able to tell me where my understanding of the problem breaks down in the following question. If we consider the primal problem, $$\min c^{T}...
1
vote
0answers
185 views

The 2-norm of inverse of a Hessian matrix

This concerns the convergence of Newton's method in unconstrained optimization. But the question can be taken out of this context. Suppose $f$ is twice differentiable and that the Hessian $\...
1
vote
0answers
34 views

Numerically compact representation of high dimensional phase space maps

I am studying the behavior of a transmission electron microscope lens system numerically. The lens system has only one approximate mirror symmetry. Essentially, I am studying the function taking in 5 ...
1
vote
0answers
107 views

How to generate a large PSD matrix $A \in \mathbb{R}^{n \times n}$, where $\mathcal{O}(n) \sim 10^3$

I would like to generate a large PSD matrix, i.e., $A \in \mathbb{R}^{n \times n}$, where $\mathcal{O}(n) \sim 10^3$. The entries of the matrix should be randomly generated using a standard function ...
1
vote
2answers
67 views

Nesterov's momentum derivation

On page 75 in Sutskever's thesis http://www.cs.utoronto.ca/~ilya/pubs/ilya_sutskever_phd_thesis.pdf In equation (7.5) setting $a_0=1$, $a_{t+1} = (1+\sqrt{4 a_t^2 + 1})/2 $ The author said, "to ...
1
vote
1answer
41 views

What solver can I use to solve the following optimization problem?

Let $\xi_{1},\xi_{2},\ldots,\xi_{N}\in\mathbb{R}^{m}$, $\mu,\varepsilon\in\mathbb{R}$ with $\varepsilon>0$ (These are not variables, they are constant). We consider the following optimization ...
1
vote
0answers
329 views

How to solve this QCQP efficiently?

I'd like to solve the following quadratically constrained quadratic program (QCQP) \begin{equation}\label{bijective} \begin{split} \min_{x} \quad &x^{T}Ax\\ \mathrm{s.t.}\quad &...
1
vote
0answers
35 views

How to characterize objective function in order to choose optimization method?

What are some good quantitative metrics to describe an objective function that may help choose which optimization method will work best? E.g. if there are a lot of local minima we know that we ...
1
vote
0answers
78 views

Is there a stochastic analogue of Zangwill's global convergence theorem for deterministic descent algorithms?

Zangwill's well-known global convergence theorem (Zangwill, W. I. 1969. Nonlinear Programming: a Unified Approach. Englewood-Cliffs, N.J.: Prentice-Hall) provides sufficient conditions under which ...
1
vote
0answers
129 views

When does the nuclear norm fail to minimize rank?

Given $F$ and $G$, I'm solving the following problem: \begin{align} \min_{t} & \quad \mbox{rank}(A) \\ \text{s.t.}& \quad A = \text{diag}(t) F - G \\ \end{align} I used the nuclear norm, $\|...
1
vote
1answer
178 views

stochastic subgradient descent

When using stochastic subgradient descent, the solution $f_{best}(x_k)= \min \{f(x_1),f(x_2),....f(x_k) \}$, i.e., the best "point" over all the steps. As I understand, I should evaluate the function ...
1
vote
0answers
347 views

Learn Numerical methods in Python

Please suggest me some texts that I could use to learn Numerical Methods in Python (irrespective of 2.7 or 3.x). I would like to improve my coding skills with Python along with refreshing my math in ...
1
vote
0answers
60 views

Scaling/nondimensionalization for numerical optimization

I have a numerical optimization problem that I am trying to scale appropriately, in order to allow for the solver to achieve faster and more accurate results. I found a paper here that had a short ...
1
vote
0answers
395 views

Writing an accurate SDP solver in Matlab

As part of a research project I'm supposed to write an semidefinite programming solver in Matlab (similar to SDTP3, MOSEK, SEDUM, etc) except it needs to be able to solve to many significant digits ...
1
vote
1answer
112 views

How to solve this optimization problem analytically (parameter selection problem)?

My problem is as follows: \begin{align} \underset{\boldsymbol{x}}\max \quad & \boldsymbol r^T\boldsymbol x-\boldsymbol t^T\boldsymbol x \\ \text{s.t.} \quad & \boldsymbol1^T\boldsymbol x = N \...
1
vote
2answers
121 views

What is the best way to solve this QP?

I have been studying the following optimization problem in $x_0, \dots, x_{n-1}$ $$\begin{array}{ll} \text{minimize} & \frac{1}{2} \displaystyle\sum_{i=1}^{n-1} \left( x_{i-1} - x_i - y_i \right)^...
1
vote
0answers
401 views

Hessian of Euclidean norm of vector function

I'm not familiar with Matrix algebra. I'm trying to minimize an $\ell_2 $ (Euclidean) norm of vector function. I found out the gradient of the function, using the previous questions and answers in ...
1
vote
0answers
104 views

relation between L-BFGS and BFGS

In BFGS, we apply a rank-2 update to the approximate inverse Hessian ($H \in \mathbb{R}^{n \times n}$) at each iteration. This update adjusts for the curvature found from the change in gradient and ...
1
vote
1answer
64 views

Find $\alpha$ from the equations below.

I need to find $\alpha$ from the equations in below. Having the following constants: $C$, $K$, $N_k (1\le k \le K)$ and $\lambda_{k,i}(1\le k \le K, 1 \le i \le N_k)$. What would be $\alpha$ if: \...
1
vote
3answers
169 views

Algorithms For Lp Regression

So I know that L2 regression problems can be solved by simple autocorrelations and matrix inversions. Similarly, L1 and L$_{\infty}$ problems can be solved by linear programs. But what about Lp, ...
1
vote
0answers
43 views

Is there any method for gradient descent that achieves acceleration while moving always in the opposite direction of the gradient?

I'm studying gradient descent methods, in particular Nesterov's methods and others that achieve a better complexity (in terms of access to the gradient oracle) than regular gradient descent. In ...
1
vote
0answers
32 views

Optimization with probability constrain

Is there a clever way (analitically or nummerically) to minimize following objective function $$ L(W, W_{in}, W_1, W_2) = \sum_{t=0}^T (W + W_{in}W_{out})\vec{x}(t) \cdot (W_1+W_2 W_{out})\vec{x}(t) ...
1
vote
0answers
98 views

Find boundary of a set (interval), What to use?

So directly I will State my problem: Given $\epsilon >0$ and some function $f$, required to find $\epsilon_1, \epsilon_2 >0$ such that, for any $x_1, x_2 \in \mathbb{R}$ we have $$ |x_1|\leq \...
1
vote
0answers
32 views

Maximum likelihood of a non-injective transformation

Problem: Let $g(z|a,b,c,d) = a + bz + cz^2 + dz^3$ be a polynomial function of degree 3. Clearly, $g$ is not monotone increasing for all values of $a,b,c,d$. Suppose I observe data $Y_1, \cdots, Y_n$ ...
1
vote
0answers
24 views

Designing non-local polynomials for function approximation (spec. trig fun).

In the process of investigating this problem I encountered the following $\log_2$-plots of bitwise errors of the Taylor expressions of growing number of significant terms: By these plots it's quite ...
1
vote
1answer
45 views

Best approximation in the motivation of the GMRES method

Let $n\in\mathbb N$ $A\in\mathbb C^{n\times n}$ be invertible $b\in\mathbb C^n$ $x_0\in\mathbb C^n$ $r_0:=Ax_0-b$ Moreover, let $$\mathcal K_i:=\operatorname{span}\left\{A^0r_0,\ldots,A^{i-1}r_0\...
1
vote
0answers
480 views

Minimizing sum of two functions, minimize one and maximize the other.

I'm new in optimization and I have a problem involving minimizing the sum of two functions f(x) and g(x). The objective function must be in such a way that f(x) has to be minimized and g(x) maximized, ...
1
vote
0answers
39 views

A nonlinear optimization problem: numerical solution fails

I am working on a practical problem which requires a theoretical analysis. Specifically, the problem is: Given a list of items, each enclosed in a rectangular box and with a given weight, and given ...
1
vote
1answer
333 views

How to show that the method of steepest descent does not converge in a finite number of steps?

I have a function, $$f(\mathbf{x})=x_1^2+4x_2^2-4x_1-8x_2,$$ which can also be expressed as $$f(\mathbf{x})=(x_1-2)^2+4(x_2-1)^2-8.$$ I've deduced the minimizer $\mathbf{x^*}$ as $(2,1)$ with $f^*=-8$...
1
vote
0answers
192 views

numerical optimization algorithm with approximate Gradient and Hessian only!

Suppose I have a energy functional E depending on X, where X is a N-dimensional real value vector and N could be very large (~=2000). I assume that there exists (at least) a (local) minimizer for E. ...
1
vote
1answer
40 views

Understanding a bound in numerical optimization

I'm reading through the deepest descent method, and I'm struggling to understand a specific bound. I'll try to be as much clear as I can, but the notation used is a bit messy. It is basically ...
1
vote
0answers
384 views

Numerical - Optimization : Gauss-seidel implementation?

Reading through a book of numerical optimization the very first algorithm explained is the Gauss-Seidel one. Suppose we want to solve the problem $$ \min_{x \in \mathbb{R}^n} f(x) $$ Assume $f : \...
1
vote
1answer
81 views

Maximizing the logarithm of a rational function over a polytope

Which optimization technique/algorithm can be used to solve such problems? I want to know the name of a technique because some problems I need to solve are more complex than this one. \begin{align} \...
1
vote
0answers
26 views

H^1-Seminorm of nodal basis bounded

My question comes from the topic of Finite Elements (and domain-composition-algorithms). Consider the following setting: We have some domain $\Omega = (0,1)^2$ which is decomposed into rectangular ...
1
vote
0answers
63 views

Determine whether the nonconvex problem has a unique global minimum or not

The original optimization problem is in the constrained least square form as follows: $$\min\limits_{x_1,x_2,x_3,x_4,x_5,x_6\in \mathbb{R}} \left(\left(x_2^2+x_3^2+2 x_1-x_4+x_5-3 x_6\right)^2+\left(-...
1
vote
0answers
34 views

is this optimization formulation correct?

I define an optimization problem for the following scenario: Let $S={V_1,...,V_L}$ be a set of real valued variables, defined in domain $\ [0,1]$. I have constraints as follows. 1) I want sum of ...
1
vote
0answers
55 views

Minimize function over graph weights

I have given an absorbing Markov chain $P_t$ dependent on the transition probabilities $t:V \times V \rightarrow [0,1]$ for $V$ the states of the chain. Given is also a initial vector $x$ and a vector ...
1
vote
0answers
75 views

Minimization of a convex smooth function with implicit constraints

My goal is to minimize twice differentiable convex function $f(x):\mathbb{R}^n \to \mathbb{R}$ subject to constraints $x \in C_1$ and $x \in C_2$. However I have an issue with formulating $C_2$ as I ...
1
vote
1answer
659 views

Optimal Control/Runge-Kutta-4

I'm working through Lenhart and Workman's Optimal Control Applied to Biological Models, and I'm trying to apply the Forward-Backward Sweep Method w/ Runge-Kutta-4 as the DE solver to solve $$\max_{u}\...
1
vote
0answers
112 views

Is this algorithm for solving an inverse problem similar to any known algorithms?

The short version of my question is: I designed this algorithm for finding a solution for an inverse problem. Based on my research it is a new algorithm, does anyone know a similar algorithm? My ...
1
vote
0answers
191 views

Prove the steepest descent algorithm for solving $Ax = b$

Prove that the steepest descent algorithm for solving $Ax = b$, where $A$ is symmetric and positive definite, can be rewritten as follows: Compute the residual at the $k^{\text{th}}$ step: $r_k = b − ...
1
vote
0answers
56 views

Can this nonconvex optimization problem be tranformed into a convex problem?

I’m trying to solve the following optimization problem. Minimize M subject to $0=t_{1,1}\prec t_{1,2}=t_{2,1}\prec t_{1,3}\prec t_{2,2}=t_{3,1}\prec t_{3,2}\prec t_{2,3}\prec t_{3,3}=M$, $t_{j,k}=...
1
vote
1answer
160 views

Element-wise upper bound by rank-1 matrix

I would like to solve the following optimization problem for vectors $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, given a matrix $\mathbf{h} \in \mathbb{R}_{\geq 0}^{m \times n}$ ...
1
vote
0answers
435 views

Convergence of gradient descent method with non Lipschitz gradient

I would like to study the convergence of the gradient descent method applied to the function $$f(x)=|x-1|^3$$ In order to do that, I was thinking about using the following theorem: Assume that $...
1
vote
0answers
103 views

Numeric solution to summation with Hadamard product of vectors

I need to solve: $$\vec a_i\circ \vec b_i=\sum_{j}^n\alpha_{ij}\vec c_j\circ(\vec d_j-2\pi\tau_{ij})$$ For $\vec d_j$ and $\tau_{ij}$ when $\circ$ denotes the Hadamard product and $\vec a_i,\vec b_i,\...
1
vote
0answers
38 views

Optimisation problem: connectors

Suppose there are $n$ distinct points in the $\mathbb{R}^3$ space, namely $P_1,P_2,\ldots,P_n$. Define the distance matrix $M:=(d_{ij})_{n\times n}$, where $d_{ij}$ denotes the distance of line ...
1
vote
0answers
68 views

Finding zero of a matrix function via trust region subproblem

I have an issue with some steps carried out in a paper (https://arxiv.org/abs/1508.07497 sec 9.2.2) In order to perform a gradient descent step, we need to solve the following equation for the square ...
1
vote
0answers
98 views

Closed form solution to the Digamma recurrence relation?

The difference between two digamma function can be written using the following recurrence relation: $\psi(n+z) - \psi(z) = \sum_{i=0}^{n} \frac{1}{i + z}$ My question is, is there a closed form ...