Skip to main content

Questions tagged [optimization]

Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

Filter by
Sorted by
Tagged with
2 votes
0 answers
36 views

How to minimize $\| A x - b \|_1$

How can I minimize $\|A x - b\|_1$ where $A$ is not invertible? Here, $x\in\mathbb{R}^N$. I know that I can use the sub-gradient method, but that would be very slow. I also know that I can use the ...
NicNic8's user avatar
  • 7,008
1 vote
1 answer
23 views

What is the largest ellipse of given eccentricity that can be inscribed into square?

If eccentricity of ellipse is known, what is the position of the biggest such ellipse that can be inscribed into square? I could find the answer on the web – the biggest ellipse is positioned with its ...
Vladimir_U's user avatar
1 vote
0 answers
10 views

Proposition 3.2. of Bertsekas' paper about Lagrange multipliers

This is a problem about the proposition 3.2 of Bertsekas' paper below. Bertsekas D P, Ozdaglar A E. Pseudonormality and a Lagrange multiplier theory for constrained optimization[J]. Journal of ...
Mike Dai's user avatar
0 votes
0 answers
10 views

Minimising quadratic function subject to linear equality constraints.

The Problem At a higher level, I am trying to minimise a function that looks a bit like this \begin{equation} (x_2-x_1+c_1)^2 + (x_3-x_2+c_2)^2 + ... \end{equation} Subject to the constraint that $x_1+...
DBruwel's user avatar
-1 votes
0 answers
28 views

Any class $ C^{1} $ function, monotonic and coercive from $ \mathbb{R^{n}}$ into $ \mathbb{R^{n}}$ is bijective [closed]

I am looking for a reference in which I can find the proof of this theorem: Any class $ C^{1} $ function, monotonic and coercive from $ \mathbb{R^{n}}$ into $ \mathbb{R^{n}}$ is bijective
Said Aadi's user avatar
1 vote
0 answers
14 views

A low-rank approximation problem with rank constraints

I am seeking a solution or some ideas to address the following problem: $$ \begin{aligned} &\text { minimize }_{\widehat{A}, \widehat{B}} \quad\|A-\widehat{A}\|_2 + \|B-\widehat{B}\|_2 \\ &\...
zwebrain's user avatar
0 votes
0 answers
17 views

Parameter estimation using L-BFGS

I'm reading through the paper from DeepMind on Training Compute-Optimal Large Language models and have a question on the transformation applied to the objective function. The goal is to estimate $A, B,...
KodeWarrior's user avatar
-1 votes
0 answers
32 views

Why I get two different minimum when using simplex and Newton-cg method?

Given the function $$ f(x_1, x_2) = e^{x_1} (4x_1^2 + 2x_2^2 + 4x_1x_2 + 2x_2 + 1) $$ I have found the minimum at point $[0.5,-1]$. Then working numerically I had to use two different algorithms in ...
Andreas Zachariou's user avatar
0 votes
0 answers
48 views

I encountered a geometry and maximization problem for which I cannot figure out something.

Let $\overline{AB}$ be a diameter of circle $\omega$. Extend $\overline{AB}$ through $A$ to $C$. Point $T$ lies on $\omega$ so that line $CT$ is tangent to $\omega$. Point $P$ is the foot of the ...
Matthew Cronembold's user avatar
-1 votes
1 answer
63 views

Why isn't there a local maximum too (constrained optimisation in $\mathbb{R}^3$)

It's perhaps a stupid question, but I'm dealing with this problem: I have to find max and or min of $f(x, y, z) = 2x^2 + y^2 - z^2$ constrained by $x+2y+z = 1$. Now I solved the problem and I found $x ...
Heidegger's user avatar
  • 3,283
-2 votes
1 answer
21 views

Is squared $\ell_2$ distance to a compact convex subset in $\mathbb{R}^d$ strongly convex outside of the set? [closed]

See question. It is clear that the function is not strongly convex within the set, but what about outside of the set?
milgram's user avatar
0 votes
0 answers
11 views

How to find a linear decision boundary of a linearly separable problem with unlimited class evaluations?

I have a binary classification problem, where my goal is to find a linear decision boundary (which I assume exists). The context of the problem is that I have an iterative optimization process, where ...
oskar0711's user avatar
1 vote
1 answer
56 views

How to prove that this binary optimization problem can be decomposed into two subproblems?

I am an engineer who is currently working with some network placement problem and currently I am running into a strange situation. My original optimization problem has the following form: \begin{array}...
Tuong Nguyen Minh's user avatar
0 votes
0 answers
16 views

Lagrange for f(y,z) with constraint g(x,y,z)

I need to classify extrema of $f=(1+z^2)e^{-y^2}$ on constraint: $x^2+4≤8e^{-y^2-z^2}$ Clearly, a st. pt. for $f$ which is also on and within constraint is $(\pm2,0,0)$ Setting up lagrange: $0=λ(2x)$ $...
Nate's user avatar
  • 13
-1 votes
0 answers
57 views

Solve the question [closed]

Each of the numbers $x_1,\dots,x_{101}$ is $\pm1$. What is the smallest positive value of $$\sum_{1\le i\le j\le101}x_ix_j\ ?$$ Try to sove the question
Prathamesh Laddhad's user avatar
1 vote
2 answers
60 views

Lagrange mutiplier with multivariable function and constraint

As title suggests, I need to optimize a multivariable function with a constraint, specifically; $$f(x,y,z)=z^2e^{xy}, \text{w/ constraint S: } x^2+y^2+z^2≤1$$ clearly one st. pt. will be on the plane $...
Nate's user avatar
  • 13
0 votes
1 answer
39 views

Functional derivative different when constraints are explicitly substituted vs. Lagrange multiplier method

Question (brief) Is the result the same if one 1) takes a functional derivative on a constrained subspace, or 2) takes a functional derivative using the method of Lagrange multipliers to encode ...
Lucas Myers's user avatar
-1 votes
0 answers
20 views

From final tableau to original Linear program

I have this simplex tableau, $$ \begin{align} x_1 &= \frac{5}{2} + \frac{1}{2} x_2 + \frac{1}{6}s_1 - \frac{1}{3} s_2 \\ x_3 &= \frac{5}{2} - \frac{1}{4} x_2 - \frac{1}{2} s_1 \\ z &= \...
Techno's user avatar
  • 1
-1 votes
0 answers
22 views

Formulate the problem as a linear program to increase the overall effectiveness of advertising [closed]

A company can advertise its products on radio and television(TV), or in news- papers. The advertising budget is limited to 10,000$ a month. Each minute of advertising on radio costs 15$ and each ...
user1325912's user avatar
1 vote
1 answer
28 views

Is there any algorithm to calculate this ranking method quickly?

I want to rank the 20 teams in the English Premier League. Say that each team are assigned to the number 1 through 20, defining their ranking, no ties. There would be $20!$ number of permutations for ...
Germaniac's user avatar
3 votes
0 answers
104 views
+50

Show that a function admits at most one maximizer or provide a counter example.

Let $g$ be a strictly concave, increasing, and differentiable function defined on the real line and consider the map $f$ defined on the non-negative reals by $$ f(x) = (x/(1+x))g(a-x) + (1/(1+x))g(-x)...
jmsac's user avatar
  • 333
0 votes
0 answers
15 views

Feasbility of a underdetermined linear inequality system

Let $A \in \mathbb R^{m\times n}$ where $m<n$. Also let $x \in \mathbb R^n$. I assume that I do not know much about $A$ except all its elements are non-zero. Then, is there any lemma that says I ...
Johny's user avatar
  • 21
1 vote
0 answers
37 views

Variational problem with inequality constraint

I am trying to minimize the following functional: $$ \int_0^1 ( f'(t)^2 + g'(t)^2 - 2 \, r f'(t) g'(t) ) \, dt $$ over all pairs $(f, g)$ such that $f(t) \geq f_0(t)$ and $g (t) \geq g_0(t)$ for all $...
tsnao's user avatar
  • 310
0 votes
0 answers
19 views

Quadratic form with Hadamard product, minimization

Let $x,y,a,b$ be the column vectors $(n,1)$ and $D_{1}(n-1,n),D_{2}(n-1,n)$ be the central difference matrices $$ D_{1}=\left[\begin{array}{ccccccc} -0.5 & 0 & 0.5 & \cdots & 0 & 0 ...
justik's user avatar
  • 383
0 votes
0 answers
16 views

Understanding the Role of Eigenvalues in Proving a Strict Local Minimum Using the Hessian Matrix

I have the following theorem: Consider a function $ f : O \subset \mathbb{R}^n \to \mathbb{R} $ that is twice continuously differentiable on an open set $ O $. Also, consider a point $ \bar{x} \in O $ ...
1somorph's user avatar
0 votes
0 answers
32 views

Note on max-min algebra?

I am looking for a note or a text for the rules for max-min algebra. What is a name of course for learning these? I used to see a pdf note online. Let $a,b,c$ be vectors. I am looking to prove ...
dodo's user avatar
  • 776
3 votes
4 answers
143 views

How to Minimize $PC + \frac{1}{2}PA$ for a Point on a Circle Geometrically?

Given the points $ A(1, 0) $, $ B(5, 0) $, and $ C(0, 5) $, a circle is drawn with center at point $ B $ and radius 2. Let $ P $ be a moving point on this circle. I need to find the minimum value of $ ...
Oth S's user avatar
  • 345
0 votes
0 answers
14 views

Equivalent forms of heavy ball method

I am looking at https://pages.cs.wisc.edu/~brecht/cs726docs/HeavyBallLinear.pdf which says one could write $$ \begin{align*} p_{k} & = - \nabla f(x_{k}) + \beta_{k} p_{k-1} \\ x_{k+1} & = x_{k}...
eggplant's user avatar
0 votes
0 answers
36 views

Finding a basis for an unknown-weights-and-balance puzzle?

I have a collection of unknown integer weights $w_1, \ldots, w_n$. I have a balance which I can use to weigh some pile of weights against some other pile to see which is heavier. Suppose I've done $n$...
user326210's user avatar
  • 17.6k
0 votes
0 answers
55 views

Suggest a method to minimize non-linear function

in my program I need to minimize two following separate functions in real-time (initial approximations $(x_0, y_0)_i, i\in\overline{1, n}$ are given, all other letters represent constants which are ...
dimkky's user avatar
  • 1
0 votes
1 answer
35 views

Optimization of Multivariable Functions Using Lagrange Multipliers [closed]

Q.) Given the function $f(x,y,z) = x^2+y^2+z^2$ find its local minima and maxima to the constrain $x+y+z = 1$ How do I properly set up the equations using the method of Lagrange multipliers for this ...
Krishna's user avatar
  • 33
0 votes
0 answers
16 views

How to prove the sum of concave functions no less than a scalars t is equal to entrywise relationship

here is a theorem about optimization. Theorem: Suppose $\phi:=(\phi_1,\phi_2,\cdots\phi_m)$ be concave functions defined on a compact set $\Omega\subset\mathbb{R}^{n}$.For given scalar $t:=(t_1,t_2,\...
王大可's user avatar
0 votes
0 answers
35 views

Is the feasible region for convex combinations of powers of $N$ cosines independent of $N$?

Let $x = \sum_{i=1}^N a_i \cos^2(\theta_i)$ and $y = \sum_{i=1}^N a_i \cos^3(\theta_i)$ be the two convex combinations of powers of cosines, where the variables satisfy the following constraints (1). $...
Luzveraz's user avatar
2 votes
1 answer
65 views

minimizing $| x x^T - A |^2$ for a covariance matrix $A$

For a given covariance matrix $A$ (so $A$ is symmetrical and positive semidefinite), I want to find a vector $x$ such that $| x x^T - A |^2$ is minimized. Here $|M|^2$ just means the sum of squares ...
CuriousMind's user avatar
  • 1,590
4 votes
2 answers
77 views

Why has convexity established itself as the decisive property to assess the difficulty of an optimization problem?

When I read somewhere about the importance of convexity for optimization most of the time it deals with the nice property of convex functions that local and global minima are the same. This is a very ...
Sen90's user avatar
  • 403
0 votes
1 answer
63 views

How do I solve inequalities concerning matrices using linear programming

I would like to solve the inequality, $$Ax≥b⟺Ax=b+z,z≥0⟺x=A^{−1}b+A^{−1}z,z≥0$$ $$ z_i = (Ax)_i - b_i, \, \forall i $$, here $A$ is a matrix and $x$ and $b$ are vectors. Here is a minimal problem that ...
desert_ranger's user avatar
0 votes
0 answers
44 views

Quadratic form minimization: 2 variables

% Preview source code for paragraph 0 Suppose that there is the positive semidefinite (antisymetric) matrix $A\in\mathbb{R}^{n\times n}$ $$ A=\left[\begin{array}{ccccccc} 0 & 1 & -1 & 0 &...
justik's user avatar
  • 383
1 vote
1 answer
29 views

Parameter control problem derived via Dirichlet principle / variational formulation of Poisson equation / Lagrange multipliers

The below is a distilled-down version of a more involved problem I am looking at. Suppose for simplicity that $\Omega = B_R(0) \subset \mathbb{R}^2$ and $R$ is very large. Let us further define $f_s\,\...
Pink and Floyd's user avatar
1 vote
0 answers
19 views

Minimization of smooth objective with conic constraint

I am interested in deriving first-order optimality conditions for \begin{equation} \min_{x\in\mathbb{R}^{n}}f(x)\\ \text{s.t. }x\in\mathcal{K} \end{equation} where $f$ is a smooth function and $\...
Tucker's user avatar
  • 2,100
0 votes
0 answers
26 views

How does McCormick envelope work for inequality constraints?

I have a question regarding the McCormick envelope in mathematical optimization. The McCormick envelope allows to create a convex relaxation for a bilinear term. Given the bilinear constraint $w = x \...
Michael's user avatar
  • 53
0 votes
0 answers
17 views

Berge's Maximum Theorem for Parameters that are Functions

I am given some functions $f_i$ that are $C^1$, $f_i : \mathbb{R}_+ \rightarrow \mathbb{R}_+$ and some budget $z \in \mathbb{R}_+$. I have some constrained optimization problem with a continuous ...
Ator's user avatar
  • 23
0 votes
0 answers
22 views

Minimize function two variables II.

Let $x,y,a,b$ be the column vectors $(n,1)$ , $C(n,n)$ be the matrix, and $$ \phi(x,y)=\left\Vert x-a\right\Vert _{2}^{2}+\left\Vert y-b\right\Vert _{2}^{2}+\left\Vert x^{T}Cy\right\Vert _{2}^{2} $$ ...
justik's user avatar
  • 383
0 votes
0 answers
26 views

Is it possible to convexify the inequality constraint $z \leq x^3 \cdot y$?

Is there a way to convexify the inequality constraint $z \leq x^3 \cdot y$ in a nonlinear optimization problem with $x, y, z$ being nonnegative variables?
Michael's user avatar
  • 53
1 vote
0 answers
22 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
0 votes
0 answers
55 views

Minimize function of two variables

Let $x,y$ be the column vectors $(n,1)$, $A(n,n)$ be the matrix, and $$\Phi(x,y)=\left\Vert x^{T}Ay-y^{T}Ax\right\Vert _{2}^{2},$$ be the minimized function of two variables $x,y$. The function can be ...
justik's user avatar
  • 383
1 vote
2 answers
61 views

Projectile Motion Optimization - Minimum Final Velocity?

I'm doing a project on the physics of basketball and wanted to find the optimal angle of release for a free throw (the basket is 3.05 m tall and 4.572 m away). The optimal angle would be the angle at ...
Jiamu Yue's user avatar
  • 207
2 votes
1 answer
50 views

Shortest path on the surface of a cylinder between given points $A$ and $B$

Suppose you have the cylinder $ x^2 + y^2 = R^2 $ And points $A = (R, 0, 0)$ and $ B = (0, R, h) $. Find the parametric equation of the curve of shortest length connecting $A$ and $B$. My attempt: If ...
c'est pas normale's user avatar
0 votes
1 answer
37 views

Matrix subset selection

We aim to select rows and columns of any matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$. Define a selection matrix $\mathbf{S}\in\mathbb{R}^{m\times n}$ where $S(i,j)=x_i \cdot y_j$, the matrix after ...
Hao WANG's user avatar
0 votes
1 answer
54 views

Optimizing an Objective Function While Minimizing an Argument?

I'd like to preface this by noting I'm not too familiar with optimization techniques, so something may or may not be off. Suppose I have some scalar function $f\left(x_1, x_2\right)$, where $x_1,x_2\...
gettingmathy's user avatar
0 votes
1 answer
29 views

Convex optimization and coercive function(Gausssian graphical lasso)

I want to minimize the following function (with $<A,B> = tr(A^T B)$) $<\Theta, \hat \Sigma> - \log det \Theta + \lambda_n \lVert \Theta \rVert_{1, off}$ over the set of symmetric positive ...
Phil's user avatar
  • 1,666

1
2 3 4 5
454