Skip to main content

Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
1 vote
0 answers
12 views

How to formulate piecewise quadratic function optimization without introducing binary variables?

I have a problem with logical constraints (either-or constraints). I know that it can be solved by either big-M or complementary formulations. However, i do not want to convert it into mixed-integer ...
Surya Venkatesh's user avatar
1 vote
0 answers
10 views

bound for SR1 update

Suppose the exact hessian $H^\star$ as function of vector x (no need to further be specified) and the initial SR-1 approximation $H$ are globally bounded in some norm of your choice by some real ...
user23311233's user avatar
1 vote
0 answers
13 views

Challenges with a Multi-label Regression Problem in a Real Estate Dataset

I am currently conducting a research where I aim to predict the selling price and deal execution time of properties in NY. To do this, I have a dataset of various properties sold in NY, containing ...
Marco Di Giacomo's user avatar
0 votes
0 answers
19 views

a cool optimization problem involving cubes surfaces and volumes

Consider a codimension one surface of revolution $S$ and an embedding $e:S \hookrightarrow X^n$ for $X^n=[0,1]^n$ with points $p,q$ elements of $\partial X^n$ where $\partial X^n=X^n-(0,1)^n$ for $\...
zeta space's user avatar
1 vote
1 answer
64 views

Recommendations on numerical methods and numerical analysis books for machine learning? [duplicate]

I'm self studying maths for machine learning and I have read Introduction to Linear Algebra and Calculus, both by Gilbert Strang. Now I'm going to study optimization, but I also would like to study ...
Sharpe's user avatar
  • 13
0 votes
0 answers
56 views

A company is dedicated to the manufacture of three kinds of lenses: A, B and C.

A company is dedicated to the manufacture of three kinds of lenses: A, B and C. The production procedure involves three operations: lens formation, where molten glass is transformed into raw lenses; ...
isa.be's user avatar
  • 9
0 votes
1 answer
25 views

Minimal angle between Euclidean subspaces

Consider the following minimization problem. Let $U, V$ be $k$ and $l$ dimensional subspaces of $\mathbb{R}^n$, respectively, so that $k+l \leq n$, and $U \cap V = \{\textbf{0}\}$. Suppose $\mathbb{...
user918212's user avatar
-1 votes
1 answer
67 views

What's the purpose of the KKT condition when first-order optimality condition exists?

Given a convex optimization problem $$\min f(x), x \in D$$ $f, D$ convex. The first-order optimality condition says $x$ is the minimizer if and only if $\nabla f(x)^T (x-y) \geq 0, \forall y\in D.$ ...
Shamisen Expert's user avatar
1 vote
1 answer
64 views

Solving a convex problem with quasiconvexity with CVXPY?

I have a question regarding quasiconvexity and its usage in CVXPY. I have the following optimization problem. \begin{equation*} \begin{aligned} \min_{x} \quad & \sqrt x\\ \textrm{subject to:} \...
Michael's user avatar
  • 53
0 votes
0 answers
11 views

Brachistochrone involving gravitational changes dependent on x

as an extension to the normal brachistochrone problem: $$T[y]=F(y,y')= \tfrac{1}{\sqrt{2g}}\int_{0}^{x_{b}}\tfrac{\sqrt{1+(y'(x))^2}}{\sqrt{y(x)}}dx$$ I was asked to get the gravity dependent on x, so ...
Bastian Sommerfeld's user avatar
0 votes
0 answers
10 views

Gradient-based methods on quasi-convex problems?

In the book I am currently reading, it says Gradient-based methods are useful for one global optimum and no additional local optima: (quasi-)concave for maximums, (quasi-)convex for minimums. It is ...
Marlon Brando's user avatar
0 votes
0 answers
14 views

Show that to reduce the initial error by the factor $\varepsilon$ at most many iteration steps are required

Consider the CG method for the iterative solution of the system of equations $A \mathrm{x}=\mathrm{b}$ with a positive definite and symmetric matrix $A \in \mathbb{R}^{n \times n}$ and $b \in \...
Euler007's user avatar
  • 132
0 votes
1 answer
25 views

Show in terms of numerics for symmetric and positive definite matrix

Let $0<\lambda_{1} \leq \ldots \leq \lambda_{n}$ be the eigenvalues of the symmetric and positive definite matrix $A \in \mathbb{R}^{n \times > n}$ and $u_{1}, \ldots, u_{n} \in \mathbb{R}^{n}$ ...
Euler007's user avatar
  • 132
2 votes
1 answer
96 views

Is it true that a function is $c$-strongly convex if $f - c\|x\|^2_p$ is convex for ANY norm $\|x\|_p$?

It is a common knowledge that a function is $c$-strongly convex if $f - c\|x\|^2_2$ is convex. However, can we replace $\|x\|_2$ with any norm $\|x\|_p$? I strongly suspect this holds, but from ...
Shamisen Expert's user avatar
0 votes
1 answer
32 views

Why can I replace both sides of the interval in the bisection method for optimization?

In the bisection method for optimization, we look at the first derivative and then depending on whether it is positive or negative replace the boundary point a or b. I tried to implement it in python ...
Marlon Brando's user avatar
1 vote
0 answers
73 views

Does anyone have experience with this multidimensional optimization algorithm

I recently stumbled across what looks like a very interesting paper concerning a simplex-based bisection algorithm for multidimensional optimization. The authors provide results from their own MATLAB ...
m4r35n357's user avatar
  • 141
1 vote
0 answers
16 views

Maximum number of local minima in k-means

Suppose $\mathcal{Z} = \{z_1, \dots, z_n\}$ is the set of points in $d$-dimensional Euclidean space. The aim is to partition the dataset into $(K\leq n)$ distinct clusters $R_1,\dots, R_K$ where $R_i\...
entropy's user avatar
  • 147
1 vote
1 answer
52 views

Positive-semidefinite-constrained nuclear-norm-regularized optimization problem [closed]

I want to solve the following optimization problem: Let $S \in \mathbb{R}^{p \times p}$ be a symmetric matrix, and fix $n \in \mathbb{R}$ such that $n$ is significantly less than $p$ and the rank of $...
Eco-nometrician's user avatar
1 vote
2 answers
57 views

How to transform this expression to a numerically stable form?

I have this function $$f(x, t)=\frac{\left(1+x\right)^{1-t}-1}{1-t}$$ Where $x \ge 0$ and $t \ge 0$. I want to use it in neural network, and thus need it to be differentiable. While it has a ...
yuri kilochek's user avatar
0 votes
0 answers
28 views

Computing gradient over all examples in Gradient Descent

I am studying about Gradient Descent and Stochastic Gradient Descent, and the text says that one of the advantages of sgd over gd is, that gd can be computationally expensive for large datasets. In ...
WalaWizon's user avatar
1 vote
1 answer
28 views

Nocedal 3.25. Calculate $\frac{\partial \phi}{\partial \alpha}$ where $\phi(\alpha) = f(x - \alpha \nabla f)$ and $f(x) = \frac{1}{2} x^T Qx - b^T x$

I'm trying to understand the calculation of the following equation 3.25 in the textbook "Numerical Optimization by Nocedal and Wright": Here is my work: \begin{gather*} f: \mathbb{R}^n \...
clay's user avatar
  • 2,753
0 votes
1 answer
34 views

what are the generic methods to prove solution existence!?

Suppose we are in $\mathbb R^n$ and consider $$\min f(x) \qquad s.t. \qquad x\in P.$$ Under what conditions on $f$ and $P$, we can guarantee this problem obtains a solution? The most generic ...
Sam's user avatar
  • 348
0 votes
1 answer
26 views

Minimize an N-dimensional vector dot product with <N constraints

I have a list of N variables $\vec{x}=(x_1, x_2, \cdots, x_N)$ where in my situation N will be around 10 and all of these variables must be nonnegative real numbers. I also have three linear ...
slabi's user avatar
  • 1
0 votes
1 answer
69 views

Sensitivity of Newton's method initial vlaue

Can someone explain to me what sensitivty refers to when it comes to root finding? When we say it is sensitive to initial value for x, is because there are multiple roots, or because there might be a ...
Need_MathHelp's user avatar
0 votes
0 answers
27 views

Newton's convergence for systems of equation analysis

So I solved a question using Newton's Method for systems of equations. Then they asked: How can you ensure that Newton's method converges as it should? What convergence rate do you observe? My idea ...
Need_MathHelp's user avatar
0 votes
0 answers
22 views

Most efficient bounded maximum of high degree polynomial

Say I have identified a limit that approaches the bounded maximum value of a polynomial (with rational coefficients) to arbitrary precision. An example such limit is: $lim_{k->\infty} ((\int_a^b (f(...
dhakim's user avatar
  • 69
3 votes
0 answers
43 views

Minimizaiton of $f\mapsto\int\frac12\|f\|^2+\nabla\cdot f\:{\rm d}\mu$, when $\mu$ is only given by i.i.d. samples

I know this question is quite vague, but I need some indication. I have a problem where I have a probability distribution $\mu$ on $\mathbb R^d$ and I want to find a differentiable function $f:\mathbb ...
0xbadf00d's user avatar
  • 13.5k
1 vote
1 answer
39 views

Is there any method that can optimize the problem whose regularizer is kurtosis term?

I recently worked on an optimization problem, whose regularizer $g(x)$ is kurtosis. The overall optimization formula is as follows. $$\begin{align} \arg \min_x \frac12 \Vert Ax-b\Vert_2^2 + \lambda g(...
Leung Joe's user avatar
0 votes
0 answers
40 views

What does singular hessian in optimization tell me

I am doing optimization using maximum likelihood estimation, and when I am trying to get the standard errors of estimates using hessian matrix, I get non-invertible/singular hessian warning. After I ...
jasmine's user avatar
  • 123
2 votes
1 answer
37 views

Least squares regression with stable and non-negative constraint

I am trying to fit an auto-regressive model to a time-series where I have some constraints. We have the first order model, $$ X_{t+1} = AX_t + \xi_t, $$ which I can pose as a least-squares ...
citizenfour's user avatar
1 vote
1 answer
46 views

$L^1$-norm minimization using combinations and a scalar variable

Problem: I am given the vectors $\mathbf{a}\in\mathbb{R}^m$ and $\mathbf{b}\in\mathbb{R}^n$ with $m > n$ and an unknown $c\in\mathbb{R}$. I want to find a combination of values, in any order, from ...
Bulbasaur's user avatar
  • 157
0 votes
1 answer
89 views

Minimal optimization using a cost function

The above image is data that cannot be saved in a list because there's too much of it. This image is just a small snippet of what my real data looks like. The plot is created by some cost function $y=...
steveK's user avatar
  • 119
0 votes
0 answers
25 views

Fair Bandwidth Allocation

This is a question that sounds simple but I can't figure out a proper solution. The question is as follows. Say you have a binary tree of 3 levels(8 leaves). Let's say this represents a network where ...
oshan yalegama's user avatar
0 votes
1 answer
117 views

Numerical gradient calculation for optimal control of PDE

I have two related questions regarding the correct way to perform numerical gradient descent for an optimal control problem with a non-uniform mesh/grid. 1) Say I am solving a PDE-constrained ...
Frubiclé's user avatar
  • 603
1 vote
0 answers
53 views

Solving a matrix optimization problem

Consider the following optimization problem \begin{equation*} \min_{0\leq \sigma \leq 1} \lVert B(\sigma)\,B^{+}(\sigma)\,p -p \rVert^2 \end{equation*} where $\sigma\in \mathbb{R}^m$ is the decision ...
matteogost's user avatar
3 votes
1 answer
131 views

Minimum number of required function values to maximize a quadratic form

Consider a Rayleigh quotient $$f(\mathbf{x})=\frac{\mathbf{x}^H \mathbf{G}\mathbf{x}}{\mathbf{x}^H \mathbf{x}}$$ where all quantities are complex valued, $\mathbf{x}$ is an $N\times 1$ vector and $\...
TryingToLearn's user avatar
0 votes
0 answers
35 views

Optimization Models and the chicken-and-egg problem

I have started working with optimization models to minimize the total generation costs of electricity in a system. The basic idea in this model is to minimize the overall system cost given a certain ...
Eve Chanatasig's user avatar
0 votes
0 answers
38 views

Optimization of a function with only a few partial derivatives available

Suppose you want to minimize a multivariate function where partial derivatives are available only wrt some of the variables but not all. Are there numerical optimizers designed for this case? Two ...
Rosh's user avatar
  • 3
0 votes
0 answers
43 views

Prove a lemma of the conjugate gradient method

To me is given the following task in connection with the conjugate gradient method with a positive definite and symmetric matrix: $$ \begin{array}{l} \text { Let } g^{i} \neq 0, i \leq t \in > \...
Euler007's user avatar
  • 132
2 votes
1 answer
67 views

An idea for convex-concave saddle-point problem [closed]

For the following convex-concave problem $$ \min_{x\in\mathbb{R}^n}\max_{y\in\mathbb{R}^n} f(x)+\langle y,x\rangle-g(y) $$ Does the following algorithm achieve convergence? Under what conditions? $x_{...
Kamy's user avatar
  • 31
1 vote
0 answers
56 views

IN SVMs, why can't the Lagrange multipliers for support vectors be 0?

In hard margin SVMs, we have the primal optimization problem: \begin{align*} \min_{\vec{w}, b} \max_{\vec{\alpha}} \quad & \frac{||\vec{w}||^2}{2} + \sum_{i=1}^m \alpha_i \left( 1 - y_i (\vec{w} \...
Bob Smith's user avatar
0 votes
1 answer
83 views

Non linear optimization wrt to square matrix

Given vectors $\pmb{y}_0, \pmb{y}_1, \dots \pmb{y}_t \in \mathbb{R}^n$, let $F : \mathbb{R}^{n \times n} \to \mathbb{R}_0^+$ be defined by $$F(W) := \left\| \pmb{y}_1 - W \pmb{y}_0 \right\|^2 + \left\|...
Vladislav Bizin's user avatar
1 vote
2 answers
99 views

Minimising inconclusive range for binary classification with two thresholds

Background I have an optimisation problem related to a binary classification tasks. I have arrays of probabilistic predictions, $x$, and true binary labels, $y$, i.e. $x_i\in [0,\,1]$ and $y_i\in \{0,...
Filip's user avatar
  • 495
0 votes
0 answers
19 views

Existence of the minimum of bivariate function

This is related to a previous post, see here if needed. I have $x \in \mathbb{R}^{d\times 1}$ and $y\in \mathbb{R}^{p\times d}$ and I want to minimize the function $f(x,y) = g(x) + x^T y^T y x$ such ...
Ki Chao's user avatar
  • 43
2 votes
1 answer
82 views

How can i solve this optimization problem effectively?

Recently, i met an optimization problem $$ \arg \min_{\mathbf{x}}\Vert \mathbf {Kx} - \mathbf{y} \Vert^2_2+\frac{\eta \Vert \mathbf{Dx} -\mathbf d \Vert_2^2 }{\Vert \mathbf{Dx} \Vert_2^2} $$ from ...
Leung Joe's user avatar
1 vote
0 answers
89 views

alternating gradient descent on quadratic function

I have $x \in \mathbb{R}^{d\times 1}$ and $y\in \mathbb{R}^{p\times d}$ and I want to minimize the function $f(x,y) = g(x) + x^T y^T y x$ such that $y^T y$ is a positive definite matrix and $g$ is a ...
Ki Chao's user avatar
  • 43
1 vote
0 answers
26 views

Reference request: convergence of the alternating gradient descent

I have an optimization problem with two sets of variables, $x \in \mathbb{R}^d$ and $y \in \mathbb{R}^p$, and you want to minimize the objective function $f(x, y)$. The basic idea of AGD is to update ...
Ki Chao's user avatar
  • 43
1 vote
1 answer
84 views

Check the convexity of the upper bounding function of the subgradient method

I want to proof that the function $$ U(\alpha_1, \ldots, \alpha_k) = \frac{R^2 + M^2 \sum_{i=1}^k \alpha_i^2}{2 \sum_{i=1}^k \alpha_i} $$ is convex, for $R, M \geq 0$ and $\alpha_i > 0$. This ...
Wellington Silva's user avatar
0 votes
1 answer
66 views

What equation would express multiple values of x for only one value of n, within a threshold of requirements?

Simplified Problem My question is a bit complex to be explained within the title, though what I'm truly looking for is an equation that can, as the title mentions, "express multiple values of x ...
Justin Neugebauer's user avatar
0 votes
0 answers
55 views

How to calculate convergence rate of gradient descent

I am researching on gradient descent. I am looking at the convex case with Lipschitz-continous gradients. For that I'm using Nesterov's "Lectures on convex optimitzation". His result for the ...
zoe's user avatar
  • 1

1
2 3 4 5
31