Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
1
vote
1answer
23 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 ...
1
vote
0answers
26 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 ...
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 ...
8
votes
4answers
1k views

Finding good approximation for $x^{1/2.4}$

I would like to a good (8 bits accuracy) approximation for $x^{1/2.4}$ in the range $[0, 1]$. This transform is used for converting linear intensities to SRGB compressed values, so it's important that ...
1
vote
0answers
43 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
13 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 ...
0
votes
0answers
54 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 ...
1
vote
1answer
405 views

What is the standard SDP form of this eigenvalue optimization?

The following are two pictures in a lecture note: I know how to formulate this problem into the second to last problem, but I am confused about how to write this problem into the standard SDP problem....
0
votes
1answer
25 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
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
0answers
25 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
25 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 ...
0
votes
0answers
47 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 ...
2
votes
1answer
909 views

Does converting an inequality constraint to an equality one have any major impact on an optimization solver?

In an optimization problem, I have an inequality constraint, say $\begin{array}{c} {\min\limits_x~} c(x)\\ {s.t.~}g(x)\le 0 \end{array}$ The function $g(x)$ in general is unknown. So, numerical ...
2
votes
1answer
2k views

Gradient descent: L2 norm regularization

So I've worked out Stochastic Gradient Descent to be the following formula approximately for Logistic Regression to be: $ w_{t+1} = w_t - \eta((\sigma({w_t}^Tx_i) - y_t)x_t) $ $p(\mathbf{y} = 1 | \...
1
vote
1answer
28 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}...
0
votes
1answer
33 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 ...
3
votes
2answers
925 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 \...
0
votes
1answer
20 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 ...
3
votes
1answer
49 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 ...
2
votes
0answers
29 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 ...
0
votes
2answers
65 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 \...
0
votes
0answers
82 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
37 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
24 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
32 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
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
37 views

Online Non-convex optimization

Can stochastic gradient descent be used for online non-convex optimization? If not, what are the suitable algorithms?
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
11 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
21 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
45 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 $\...
2
votes
0answers
49 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
47 views

Linear Program is Surprisngly Infeasible - Trying to Write the Dual

I need to solve the following linear program: $$\displaystyle{\min_{\bar{X},t}} \hspace{0.1in}t$$ such that: $$A\bar{X}=\tilde{x} + td$$ where $A$ is $N\times N$ and known, $t$ is scalar, $\tilde{...
1
vote
0answers
40 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
30 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 ...
3
votes
2answers
3k views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in \mathbb{...
0
votes
0answers
15 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 ...
0
votes
0answers
26 views

Difference between augmented Lagrangian and penalty method

1.what is an auxiliary variable? 2.when should we use the augmented Lagrangian (AL) instead of Lagrangian multiplier? 3.when should we use the penalty function instead of augmented Lagrangian (AL) ? ...
0
votes
2answers
38 views

Minimizing univariate quadratic via gradient descent — choosing the step size

I'm learning gradient descent method and I saw different (and opposite) things on my referrals. I have the following function $$f(x) = 2x^2 - 5x$$ and I have to calculate some iterations of ...
1
vote
0answers
26 views

Convergence Rates of Stochastic Gradient Descent with different sample size

Given a convex function $F(x)$ to be optimized with $F(x^*)$ being the optimal value at $x^*\in\mathbb{R}^n$. The difference $|F(x)-F(x^*)|$ is called the excess error. Using Stochastic Gradient ...
129
votes
4answers
72k views

Partial derivative in gradient descent for two variables

I've started taking an online machine learning class, and the first learning algorithm that we are going to be using is a form of linear regression using gradient descent. I don't have much of a ...
1
vote
0answers
36 views

How to convert a semidefinite program to an optimization problem that can be solved by the ellipsoid method?

Suppose we have the following set of linear inequalities in $x \in \mathbb R^n$ $$\begin{aligned} a_1^T x &\leq b_1\\ a_2^T x &\leq b_2\\ &\vdots\\ a_k^T x &\leq b_k\end{aligned}$$ ...
0
votes
1answer
46 views

Quadratic convex objective with non-smooth constraint

I am currently in the situation where I have to find the $\arg\min$ of a convex objective function with a non-smooth convex constraint. More formally, this takes the following form $$\beta^* := \arg \...
0
votes
1answer
37 views

What point will ADMM converge to ? A feasible point or a stationary point or local optima or global optima?

In Boyd's great ADMM paper Section 3.2.1, ''Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers'', it says that as iteration index $k\to \infty$, ...
0
votes
1answer
38 views

Numerical methods for solving the inverse Weierstrass transform

I have a measurement technique that results in a frequency distribution of the results. Let's say x is the parameter of interest, the method gives you a distribution F(x). I have the idea that the ...
-1
votes
1answer
19 views

Analysis of optimization procedure for two equivalent optimization problems

I come up with this question. Assume the optimization problem is: $$argmin_w\|\hat{y}(w)-y\|^2$$ Now suppose there is a overcomplete set for the representation of $\hat{y}$ and $y$, this set has lots ...
0
votes
0answers
34 views

Algorithm to find minimum of a multivariate function

Problem: Find (numerically) minimum of a function $f=f(x_1,...,x_M)$, where $M \in \mathbb{N}$ - a fixed number (often large), and $x_i \in [a,b],\forall i$. Function $f$ is complicated, and to ...
0
votes
0answers
34 views

Globalized Newton method for minimizing a specific functional: Convergence?

I'm currently working on a generalized p-Laplace equation: \begin{align} \label{DP} \begin{cases} \text{div} (\sigma |\nabla u|^{p-2} \nabla u) = f &\quad \text{in } \Omega\\ u = g &\quad \...