Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
893
questions
0
votes
0answers
10 views
Stochastic Optimization with Piecewise Function
I have a stochastic optimization problem where my objective is a piecewise function:
$$ \underset{x}{\text{min}} \: \sum_{i=1}^{N} E(g(Y, x_{i})) $$
where $Y \sim N(\mu, \sigma^2)$ is a random ...
1
vote
0answers
19 views
How to numerically solving a spectral optimisation problem?
Consider the following one-dimensional eigenvalue problem
\begin{align*}
-\frac{d}{dx}\left(\sigma(x)\frac{du}{dx}\right) & = \lambda u \ \ \textrm{ in $(0,L)$} \\
u(0) = u(L) & = 0,
\end{...
0
votes
0answers
10 views
Comparisons of Solving Speed of QP & SOCP
For two same scale optimization problem, quadratic programming (QP) and second-order cone programming (SOCP), which one is faster to solve? As far as I know, the computational complexity of QP and ...
3
votes
0answers
48 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 ...
0
votes
0answers
12 views
Specific number of Halton Points
I'm starting to study many article about numerical calculus and I see the definition of Halton Points (HP). But in this article sometimes one author use 289 HP, and sometimes another author use 1089 ...
0
votes
0answers
37 views
What is the arithmetic cost (computational complexity) of an SDP with nonlinear matrix inequality constraint
In the book ''Interior-Point Polynomial Algorithms in Convex Programming'' (Nesterov and Nemirovskii) section 6.4, there is a computational complexity result for the general positive semi-definite ...
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 $$...
3
votes
0answers
56 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 ...
1
vote
0answers
29 views
Extracting diagonal of $J^TJ$ via automatic differentiation like techniques
First of all please, let me know if this question is more suited for scicomp.stackexchange.com or or.stackexchange.com, and ...
0
votes
0answers
28 views
Can we always find a proper step size?
In convex optimization, if we know the gradient of a function $f(x)$, then is it true that we could always find a way to determine a proper step size in the gradient descent method? When I say "proper"...
0
votes
1answer
14 views
Optimal approximation of nonlinear probability density function by piecewise constant density
Given a nonlinear probability density function F, the problem is to estimate F using histogram over a partition with N intervals.
I have tried to realise this with MATLAB function fmincon, but it ...
3
votes
0answers
35 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 ...
1
vote
1answer
39 views
Positive semidefinite inequality
Let $\mathbf{A}\in\mathbb{C}^{m\times m}$, and $\mathbf{B}\in\mathbb{H}^{m\times m}$ be an $m$-dimension Hermitian matrix, solve $\theta$ that satisfies the condition
\begin{equation*}
e^{\jmath\theta}...
5
votes
1answer
48 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 ...
0
votes
1answer
100 views
Quadratic programming on a small embedded device — can I do the hard work on my PC first?
I have the following constrained quadratic program in $x$
$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^TQx + x^Tc\\ \text{subject to} & b_{\min} \leq Ax \leq b_{\max}\\ & x_{\min} \...
0
votes
0answers
18 views
Optimizing a system of equations to minimize purchasing cost
I am new to this (posting on stack exchange and higher level math in general) so please correct me where I am in error. I am trying to minimize the cost to my company for purchasing a certain product. ...
1
vote
0answers
17 views
Formula for Area of a Triangle - nodal basis function
Let T be a triangle with corners $P_1, P_2, P_3$ and the nodal basis function $\lambda_1, \lambda_2, \lambda_3$ and $\alpha, \beta, \in \mathbb{N}_0$. I want to show that
$$
\int_{T}^{} \lambda_1^\...
0
votes
1answer
38 views
Why is this inequality true in the proof of the convergence of Newton's method?
From Convex Optimization by Boyd & Vandenberghe:
Let $f$ be a twice continuously differentiable convex function that is strongly convex with constant $m$, i.e., $\nabla^2 f(x) \succeq m I$ for $...
1
vote
0answers
20 views
What are possible ways to update the Hessian if the calculated gradient is negative in BFGS algorithm (Quasi-Newton method)?
When applying the globalized BFGS algorithm (Quasi-Newton Method, optimization, minimization) to approximate the minimum of a function using the Quasi-Newton-Method, sometimes one can get a negative ...
3
votes
0answers
135 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 ...
1
vote
0answers
46 views
When is the simplex method slower than the ellipsoid algorithm?
In an undergrad class on linear programming, we learned about the simplex and ellipsoid methods for solving linear programs (LPs). I know that the simplex method is generally faster than the ellipsoid ...
0
votes
0answers
12 views
multi-objective optimization test function explanation
i took this image from a paper that describes a multi-objective optimization algorithm where UF1 is a multi-objective function to optimize. can you explain to me what J1, J2 variables and the second ...
1
vote
0answers
41 views
$\lambda_{max}$ in trust region method: Leveberg-Marquardt algorithm
I am learning levenberg-marquardt algorithm and in the process implementing the same. I am comfortable with the $Jacobian$, $Hessian$ and step size computation. For trust region implementation, I have ...
0
votes
0answers
51 views
Block Separability in ADMM
I am reading Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, where Boyd claimed that
ADMM is an algorithm that is intended to blend the ...
0
votes
1answer
31 views
Find a suitable zero equation to solve the optimization problem $\min_{x \in \mathbb{R}^N} f(x)$
Suppose we have an optimization problem for this general form of $f: \mathbb{R}^N \rightarrow \mathbb{R}$
$$\min_{x \in \mathbb{R}^N} f(x)$$
and this problem is solvable. How could I construct a ...
0
votes
1answer
24 views
Minimizing $\ell_p$ norm on a flat - what type of convex programming subproblem is this?
Suppose that we are in a finite-dimensional real vector space $\Bbb R^n$, and we are on a flat $F \subset \Bbb R^n$ (aka, an affine translation of a subspace of $\Bbb R^n$). We want to minimize some $\...
0
votes
0answers
44 views
Understanding the steps of Karmarkar's algorithm
I am working through Karmarkar's seminal paper [0] and came across something I didn't quite understand. In section 2.3, Description of the Algorithm, he explains how to calculate the next point. The ...
0
votes
0answers
24 views
Estimiate Fourier transform coefficients of optimial $L1$ function?
Let there be a loss function $h$ that takes an $L1$ function as input. Assume that $h$ has a finite global minima reached by a single $L1$ function $f^\ast$. In other words...
$$f^\ast = \...
1
vote
1answer
22 views
Gradient-based interpretation of the simplex algorithm
The simplex algorithm iterates from vertex to vertex of the convex polytope that bounds the feasible region of the constrained optimization problem, such that each iteration of the algorithm moves ...
1
vote
1answer
22 views
Showing a Chebyshev set
I want to show that $\{1,e^{ix},...,e^{(n-1)x} \}$ is a Chebyshev Set on $(0,2\pi]$. Now I know that $\{1,x,...,x^n \}$ is one and that $e^{ix}$ is injective on $(0,2\pi]$. But how do I show that if I ...
0
votes
0answers
79 views
Computation of function with sup
I am trying to compute the value of the following function $R:\mathbb{R}^m\mapsto\mathbb{R}$
$$R_n(\theta)=\sup_{\lambda\in\mathbb{R}^m}\left\{-\frac{1}{n}\sum_{i=1}^{n}\sup_{x\in\mathbb{R}^m}\lbrace ...
0
votes
1answer
28 views
Divergence criteria of Secant method on $\arctan(x)$?
I want to make sure I understand when the secant method will not converge as compared to the Newton's method.
When I look at $\arctan(x)$ and try to determine the initial guesses for which it will ...
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 ...
3
votes
1answer
47 views
“Rectangular” Cholesky decomposition of lower dimension
Given a symmetric PSD matrix $A \in \mathbb R^{n \times n}$, we can Cholesky-decompose it into $LL^T$, where $L \in \mathbb R^{n \times n}$ is lower triangular. However, we can also consider ...
0
votes
0answers
59 views
Computational complexity of solving an SDP in CVX
I have solved an SDP by the MOSEK solver of the CVX toolbox. I need to calculate the computational complexity of my algorithm. Can you help me in this regard? I would appreciate it if you can give me ...
1
vote
0answers
35 views
Understanding/Proving a theorem in Numerical Optimization by Nocedal
I was reading this book specially theorem 8.4 on page 210.
Suppose that a method in the Broyden class is applied to a strongly convex quadratic function $f : R^n \rightarrow R$, where $x_0$ is the ...
0
votes
0answers
23 views
constraint optimization using penalty function
Let say you have following constraint optimization problem and you want to optimize it using penalty function method:
$$
\min f(\mathbf{x}), \mathbf{x} \in R^{2} \\
s.t. \mathbf{a(x) = 0}, \\
\mathbf{...
0
votes
0answers
31 views
Active set method for a simple problem
In my computetional methods course we recently had an algorithm for solving
$(P)$ : $\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^THx + c^Tx $
subject to $a_i \leq x_i \leq b_i$ for $i \in \...
0
votes
2answers
64 views
How to show equivalence between two programs?
Let
$$A := \left\{ (x_1,x_2,x_3) \in \mathbb{R}^3 \mid x_1+x_2+x_3 = 1 \right\}$$
and suppose that we want to minimize a function $J : \mathbb{R}^{3} \to \mathbb{R}$ subject to the constraint $y \...
3
votes
1answer
46 views
Optimise allocation to minimise variance
Background
I am trying to allocate customers $C_i$ to financial advisers $P_j$. Each customer has a policy value $x_i$. I'm assuming that the number of customers ($n$) allocated to each adviser is ...
0
votes
0answers
19 views
How can I prove $\lambda_k^* = \frac{-g_k^T u_k}{u^T_k A u_k}$ in the conjugate gradient method?
To break down the formula,
This only applies to quadratic functions, $q(x) = \frac12 x^TAx+bx+c$
$g_k$ is the first derivative at the point $x_k$
$A$ is found from the quadratic function, or, I think,...
0
votes
0answers
33 views
Online Non-convex optimization
Can stochastic gradient descent be used for online non-convex optimization? If not, what are the suitable algorithms?
0
votes
0answers
10 views
What is the advantage of using KKT-CQ over LI-CQ for first-order KKT necessary condition
In the notes I follow, the author uses the KKT-CQ for the first-order necessary KKT conditions, then impose an additional constraint qualification which is the LICQ for the second-order conditions.
...
0
votes
0answers
20 views
What is the fault with Fritz John necessary condition for finding a local minimum for a general NLPP
The author says:
It is also possible that, at some feasible point $x$, the
FJ conditions are satisfied with Lagrange multiplier
associated with the objective function $u_0 = 0$.
In those ...
0
votes
1answer
41 views
Finding minimum of penalty-approximated quadratic problem
Find the minimum of the following quadratic function
$$ f_{\alpha}(x) := \frac{1}{2} x^T H x + c^T x + \frac{\alpha}{2}(b^Tx)^2 $$
where matrix $H$ is symmetric and positive definite, and $\...
1
vote
1answer
26 views
How to use Finite Difference Method solving ODE with Boundary Value Problems?
Using these formulas, it is clear how to solve the problem:
For node 1, we have the boundary value on the left side, for ex. $u(0) = 0$ and for node 2, we use the formula replacing $u''$ with $u_{i-1}...
1
vote
0answers
31 views
Derive Hessian inverse update using Sherman-Morrison in Quasi Newton Method
From Nocedal's Numerical Optimization book, the Hessian approximation equation is given using Symmetric Rank 1 (SR1) formula as follows:
$$B_{k+1} = B_k + \frac{(y_k - B_ks_k)(y_k - B_ks_k)}{(y_k - ...
1
vote
0answers
24 views
How to implement Finite Difference Method ODE Boundary Value Problem in Python?
I implemented the Finite Differences Method for an ODE with Boundary Value Problem. Here is the approximations I used for the FDM:
And here is the balk problem:
with u(0) = u(L) = 0 (attached on ...
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) $$
...
0
votes
0answers
14 views
The notion of conflicting objective functions in multi-objective optimization
In a paper by Carlos A. Coello titled
A Comprehensive Survey of Evolutionary-Based
Multiobjective Optimization Techniques
he states:
"Multiobjective optimization (also called multicriteria ...
