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
1 vote
1 answer
42 views

why gradient descent does not always land at the global minimum closest to the starting point?

I am given this function $\boxed{f(x,y)=((x^2+y^2)-1)^2}$. I need to do gradient descent analysis on it. I have studied that it's not trivial to show mathematically "ball reaches to the global ...
user avatar
0 votes
0 answers
25 views

Airfare Ticket Reduction Optimization Problem

I am a little confused as to this basic calculus question. I'll paste it here, it's from my school textbook. The airfare between Vienna and Dubai is approximately €500. An airline has a passenger ...
user avatar
0 votes
0 answers
12 views

Global maximum of symmetric event for binomial distributions

Suppose we're dealing with binomial distributions over $n$ flips of a coin with $n$ even. Call an event $X$ symmetric if $X = \{k, n-k\}$ where WLOG $k<\frac{n}{2}$. When $(\frac{n}{2}-k)^2<\...
user avatar
1 vote
0 answers
11 views

Minimum of a multivariable function

Let $f : \mathbb{R}^n\to \mathbb{R}$ be a continuously differentiable function and $a, b\in\mathbb{R}^n$ such that $a_i \leq b_i$ for each $i\in \{1, 2, \ldots, n\}$. Define $v = \nabla F(a)$. If $v_i ...
user avatar
  • 11
0 votes
0 answers
11 views

Are square configurations the only critical configurations of the energy on the circle?

$\newcommand{\S}{\mathbb{S}^1}$Let$$M=\{(x_1,x_2,x_3,x_4) \in \S\times \S \times \S \times \S\, |\,\, \text{ all the } x_i \, \text{ are distinct}\} $$ Let $E:M \to \mathbb{R}$ be defined by $$E(x_1,...
user avatar
  • 23.1k
0 votes
0 answers
7 views

Algorithms for General Form Consensus

Consider the optimization problem (see Boyd et al. Section 7.2): \begin{align} & \min_{x_1,\dots,x_N,z}\sum_{i\in[N]} f_i(x_i) \\ & \text{subject to } x_i = \tilde{z}_i, \forall i\in[N]. \end{...
user avatar
-5 votes
0 answers
21 views

Optamization problem [closed]

Cube for refrence Information Given: There are 2 ants on a cube with Side=20 centimeters. The first ant is in point E and is Heading towards point F at a rate of 4 cms/sec The second ant is in point ...
user avatar
1 vote
1 answer
37 views

Global minimization Problem for $f(x) = \frac{|| Ax+b||^2}{c^Tx+d}$

I am having trouble proving the following and I would appreciate help with it: Let $A \in \mathbb{R}^{m\times n}$ be of rank $n$, $b \in \mathbb{R}^m, c \in \mathbb{R}^n, d \in \mathbb{R},$ and $\...
user avatar
  • 367
2 votes
0 answers
14 views

Taking multiple optimization steps on the same trajectory not well justified.

I am reading the paper Proximal Policy Optimization Algorithms found at https://arxiv.org/pdf/1707.06347.pdf. In this paper they say "While it is appealing to perform multiple steps of ...
user avatar
  • 21
0 votes
0 answers
11 views

Minimize norm of difference, mapped into several spaces

I'm looking for a non-computational solution, in other words for an explicit formula, for the following problem. Let $Y$ be a vector space and $X$ a subspace of $Y$. Given $y\in Y$, and $n$ morphisms ...
user avatar
0 votes
1 answer
16 views

Why reformulate composite optimization using equality constraints?

On the “Practical Optimization” section in Mosek’s documentation, it recommends reformulating composite functions $f(g(x))$ where $f$ is convex by moving the inner $g(x)$ into a new equality ...
user avatar
  • 167
1 vote
1 answer
36 views

How to solve second order differential optimal control or optimization problem?

From a long time, I meet an optimal control problem, but i don't know how to solve it. Well, to be more specific, Suppose we have following dynamic system and cost function, \begin{cases} \ddot{y}=\...
user avatar
2 votes
2 answers
53 views

A better lower bound for $f(t):=((t-a)^2+b)^2+d(t-c)^2$ on $[0,\infty[$ where $a,b,c,d>0$ and $c>a$

Let $f(t):=((t-a)^2+b)^2+d(t-c)^2$ where $a,b,c,d>0$ and $c>a$, and $t\geq 0$. I am trying to find a better lower bound for $f$ than $b^2$, if it exists. The parabola $t \mapsto (t-a)^2+b$ has ...
user avatar
  • 2,487
0 votes
0 answers
25 views

Recast maximization as minimization

I hope you can help me. I would like to know which are the conditions to transform a maximization problem into a minimization one. I have the following problem $ Q: \max_{x,y} ~ f(y) / g(x) ~~ s.t. ~ (...
user avatar
  • 675
0 votes
0 answers
17 views

Dykstra's projection algorithm

Recently I opened for myself Dykstra's projection algorithm, i.e. the algorithm to find the projection onto intersection of two convex sets. I feel that the algorithm could be useful in non-smooth ...
user avatar
  • 73
0 votes
0 answers
27 views

Interior point method, log of negative number is undefined?

According to this article: https://en.wikipedia.org/wiki/Interior-point_method The logarithmic barrier function associated with a constrained nonlinear optimization problem is: $$f(x) - \mu \sum_i \...
user avatar
  • 539
-2 votes
0 answers
11 views

Utility Maximization Problem [closed]

Describe how (a) the optimal consumption bundle of an agent and (b) the optimal level of utility derived by the agent changes with changes in the underlying parameters of the following utility ...
user avatar
2 votes
1 answer
38 views

Let $B$ be symmetric and positive definite. Show that the range of $B - \frac{Bss^TB}{s^TB} $ is $n-1$.

Let $B\in \mathbb{R}^{n\times n}$ simetric and positive definite and $s\in\mathbb{R}^n-\{0\}$. Let $M := B - \frac{Bss^TB}{s^TBs}$.Show that the range of the matrix $M$ is $n-1$ and find its null ...
user avatar
0 votes
0 answers
43 views

Is this method correct for this transportation problem?

I've attatched a picture of the question I am working on currently, note that this is a past exam paper with no mark scheme. I am only interested in solving part c, can anyone verify that this method ...
user avatar
-1 votes
2 answers
67 views

Show that the absolute maximum of $f(x, y) = \frac{(ax+by+c)^2}{x^2+y^2+1}$ is $a^2 + b^2 + c^2$

I got this question on my exam today: show that the function $f(x, y) = \dfrac{(ax+by+c)^2}{x^2+y^2+1}$ has an absolute maximum whose value is $a^2 + b^2 + c^2$. I tried setting the gradient to the ...
user avatar
  • 21
0 votes
0 answers
12 views

Optimization problem: conditions according to KKT and example of no solution with feasible region not empty

Could you help me with the solution of this problem please? Given the problem: $$min\;\;c^Tx$$ $$s.t.\; Ax{\displaystyle \leq }b$$ $$\;\;\;\;\;\;x{\displaystyle \geq }0$$ Where A a m x n matrix, c a ...
user avatar
1 vote
1 answer
30 views

Can we convert a simplex tableau into a linear program?

Say we have been given a simplex tableau and let us assume that this isn't the first tableau (i.e. simplex has been run once or twice on it at this point). Can we convert this tableau back into the ...
user avatar
2 votes
0 answers
21 views

Is there a rigorous proof that $L_1$ regularization produces sparse results

I'm looking for a rigorous proof that the $L_1$ regularization really produces sparsity, there are multiple intuitive ones like these which I understand but all of these feel like they just explain ...
user avatar
1 vote
1 answer
26 views

Primal-Dual Pair Feasible solution implies optimal solution

Hello I am trying to understand one solution for the following problem: 17.16 Consider the problem $$ \begin{aligned} \operatorname{minimize} \ & \boldsymbol{c}^{\top} \boldsymbol{x}, \quad \...
user avatar
  • 157
2 votes
1 answer
35 views

Let $B$ be simetric and positive definite. Show that $x^T\left(B - \frac{Bss^TB}{s^TBs}\right)x $ is also positive definite

Let $B\in \mathbb{R}^{n\times n}$ simetric and positive definite and $s\in\mathbb{R}^n-\{0\}$ Let $$M := B - \frac{Bss^TB}{s^TBs}$$ Show that $$x^TMx > 0$$ My try: $$x^TMx$$ This is $$x^T\left(B - \...
user avatar
2 votes
0 answers
41 views

Show that for any sequence $\{γ_k\}$ convergent to zero, there exists a sequence $\{x(γ_k)\}$ which tends to $0$

Let $x\in \mathbb{R}$. Consider the following problem $$\text{minimize}\quad x\quad\text{s.t}\quad x^2\geq 0 \quad \text{and}\quad x+1\geq0$$ The optimal solution is $x=-1$ Define the (primal) ...
user avatar
1 vote
0 answers
14 views

Example of local convergence to a global optimum for nonconvex gradient descent

These slides give an overview of some results in nonconvex optimization with gradient descent (GD). They suggest a few types of results that are proven about nonconvex GD: Convergence to a local ...
user avatar
0 votes
0 answers
6 views

Gradient of an objective function containg coupled odes

I have position values of the form $\mathbf{X} = \left[x \; \;y \right]^{T}$. Frenet-Serret model for 2D would consist of following equations: $$ \frac{d{\mathbf{X}}_{model}}{dt} = V(t){\mathbf{T}} $$ ...
user avatar
1 vote
0 answers
64 views

Add some constraints to make $x^TAy \geq 0$ where $A \succ 0$

I am trying to prove the difference of two algorithms' asymptotic mean square error. Eventually, I get an expression like $x^TAy$, where $A$ is a positive definite matrix. I would love to see under ...
user avatar
1 vote
1 answer
58 views

Is my method equivalent to my lecturers?

In lectures we were shown how to 'breakdown' a piece-wise linear function so that it can be used as part of a linear program. Now, my lecturer wrote the function as $a=f(x)=\max(0,55x-11000)$ and in ...
user avatar
0 votes
0 answers
13 views

Regression on Matrix of Vectors [closed]

I was wondering what it means the do a regression on a Matrix of Vectors specifically a LASSO regression. I understand what it means to perform the regression on a standard matrix of scalars but does ...
user avatar
1 vote
2 answers
43 views

Find the value $\hat{\beta}$ which minimizes $\sum_{i=1}^{4}|i||i- \beta|$ for $\beta \in \mathbb{R}$

I am looking for the value $\hat{\beta}$ which satisfies the following condition: for each $\beta \in \mathbb{R}$, $$\sum_{i=1}^{4}|i||i - \hat{\beta}| \leq \sum_{i=1}^{4}|i||i - \beta|\text{.}$$ ...
user avatar
  • 18.1k
0 votes
0 answers
25 views

Optimization problem involving simultaneous solution of $k$ partial derivatives

My Question is how to maximize F in the following setup: $$F(\beta) = \prod_{i \in A}p_{i} \prod_{i \in B} 1-p_{i}$$ $$p_{i} = \frac{1}{1+e^-(x_{i}\beta)}$$ Where $A,B \subset N$ and $A \cap B = 0$. ...
user avatar
0 votes
0 answers
32 views

How do I prove this dynamic programming problem?

Given: $y_i$, $w_i$ - variables at stage $i$, $y_{i} \in \mathbb{R}$, $y_{i} \in \mathbb{R}$; $a\leq w_i \leq b$; $i = 1,\dots,n$ We are also given a function $\phi(\cdot)$ which is continuous. $y_1$ ...
user avatar
0 votes
0 answers
12 views

Let $h:\mathbb{R}^n\to\mathbb{R}$ be proper convex. Prove $\operatorname{argmin}_x M_{\lambda h}(x)=\operatorname{argmin}_x h(x)$

If $h:\mathbb{R} ^n \rightarrow \mathbb{R}\cup {+\infty}$ is proper convex (convex and atleast $1$ finite element in it's range) and differentiable at $\operatorname{prox}_{\lambda h}(x)$ (the argmin ...
user avatar
1 vote
1 answer
21 views

Split Bregman Algorithm for L1 optimization

I know that split bregman algorithm can be used for $L1$ norm optimization problem. In literature I have seen solving the problem of $x =: \underset{x}{\text{argmin }}\frac{1}{2}||y-Ax||^2+||x||_1$ ...
user avatar
3 votes
4 answers
130 views

Minimum possible sum of squares of two numbers with sum $k$?

If the sum of two numbers is k. Find the minimum value of the sum of their squares. This is my calculations so far. ...
user avatar
  • 31
2 votes
1 answer
30 views

Global minimization and least squares

I'm having a bit of trouble proving the following: Let $A \in \mathbb{R}^{m\times n}$ and $b \in \mathbb{R}^{m}$ and define $f: \mathbb{R}^n \to \mathbb{R}$ by $f(x) = ||Ax - b||^2$. How can I show ...
user avatar
  • 367
1 vote
1 answer
40 views

The requirement of compactness for the Strict Separation Theorem

In class I learned about the following theorem: Strict Separation Theorem: Let $A$ and $B$ be two closed convex subsets of $\mathbb{R}^n$ with that $A \cap B = \emptyset$. Furthermore assume that $A$ ...
user avatar
  • 2,474
1 vote
0 answers
18 views

Show that the logaritmic primal barrier $B(x,\rho)$ is not bounded from above (for $x\in \Omega$) for any fixed $\rho>0$

Let $x\in\mathbb{R}$. Consider the problem $$\text{minimize}\quad \frac{1}{1+x^2}\quad\text{s.t}\quad x\geq 1$$ Show that the logaritmic primal barrier $B(x,\rho)$ is not bounded from above (for $x\...
user avatar
1 vote
1 answer
51 views

Why does least-squares need regularization?

If I understand regularization correctly, it helps if a least-squares problem is not well-posed thus... the problem has no solution the problem has multiple solutions a small change in the input ...
user avatar
1 vote
1 answer
23 views

Theorem of Alternatives proof only one of the systems is solvable

Let $ A \in R^{nxm}$, $x \in R^n$, $c,y \in R^m$ show that, either I) $Ax=c$ II) $A^Ty=0, c^Ty=1$ is solvable I'm completely new to the theorem of alternatives, so my attempt is: If I is solvable ...
user avatar
1 vote
1 answer
25 views

A square on the equator of a sphere is a critical point of the electrostatic potential

$\newcommand{\S}{\mathbb{S}^2}$ This is a self-answered question. I learned something from spelling out the details, and I hope this could be interesting to others. I would welcome alternative ...
user avatar
  • 23.1k
0 votes
0 answers
39 views

The effect that slightly increasing a variable has on the optimal solution [closed]

I am going through a past exam paper that doesn't have a mark scheme provided. I am struggling to figure out how you would do part b. Can anyone explain how you would go about getting an answer for ...
user avatar
2 votes
5 answers
115 views

Is it possible to compute $-\log\left({\sqrt{1.8\times 10^{-5}\times 0.1}}\right)$ without a calculator?

The following question is part of a chemistry problem that came in the Dhaka University admission exam 2013-14. What is $-\log\left({\sqrt{1.8\times 10^{-5}\times 0.1}}\right)$? (a) 2.672 (b) 2....
user avatar
1 vote
0 answers
25 views

How is the Wilson-Han-Powell SQP algorithm applied?

Say for example we need to minimize $x_2$ subject to $x_1^2+x_2^2-1=0$ starting at $x_1=x_2=1/2$ and using $B=\nabla^2[x_2+\lambda(x_1^2+x_2^2-1)]$ with $\lambda=1$. Now, the WHP-SQP algorithm goes ...
user avatar
1 vote
1 answer
47 views

Is a planar square on the equator a locally energy minimizing configuration of electrons on $\mathbb{S}^2$?

$\newcommand{\S}{\mathbb{S}^2}$Let$$M=\{(x_1,x_2,x_3,x_4) \in \mathbb{S}^2 \times \mathbb{S}^2 \times \mathbb{S}^2 \times \mathbb{S}^2 \, |\,\, \text{ all the } x_i \, \text{ are distinct}\} $$ Let $...
user avatar
  • 23.1k
0 votes
0 answers
25 views

convergence of maximum value of a function

Suppose $(\Theta^n)_{n\in \mathbb{N}}$ is a monotone sequence of sets in $\mathbb{R}^d$ and $\Theta^{\infty}$ is its limit. Also, let $f:\mathbb{R}^d \to \mathbb{R}$ be a continuous function. I want ...
user avatar
0 votes
1 answer
41 views

Binary matrix multiplication optimization problem

I am looking for pointers to and names of computational approaches to solve a binary matrix optimization problem of: $$ minimize: ||\mathbf{X}\mathbf{Y} - \mathbf{T}||_{L1} $$ where $\mathbf{X}$ and $\...
user avatar
  • 103
1 vote
1 answer
51 views

how can I linearize a constraint of the form sum(min(x(i),y(i))) for a linear optimisation problem?

I have an linear optimisation problem and I'd like to impose a constraint of the following form: $∑_{i=0}^N min⁡(x_i,y_i)≥C$ where x_i,y_i are rational numbers greater or equal to 0. how can I ...
user avatar

1
2 3 4 5
403