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.

learn more… | top users | synonyms (5)

0
votes
0answers
68 views

Ellipsoidal Decomposition: Finding ellipsoids whose sum contains a given ellipsoid

We have a known ellipsoid $E\left(q,Q\right)$ in a 2D space. $q$ represents the center of the ellipsoid and $Q^{-1}$ is the weight matrix. The general equation of the ellipsoid is given as: ...
0
votes
0answers
10 views

How to make likely-to-be-right-guess in “guess and verify method” in dynamic programming

So, in infinite horizon model with autonomous function, guess and verify method is used to solve the dynamic programming problem. But I can't simply rely on that method. At least I need to make ...
0
votes
0answers
31 views

Kuhn-Tucker constraint qualification, overdetermined?

I have a question about the constraint qualification for KKT. As I've seen the theorem stated if $G(x^*)=(g_1(x^*),\dots,g_n(x^*))$ are the binding constraints at a local max $x^*$ then the jacobian ...
2
votes
0answers
37 views

Moment Generating Function of a Beta random variable.

After getting some excellent help on this problem in the statistics SE, I am reformuluating my question. Let me know if I should just delete it and ask a new one. Let $V$ be a $Beta(\alpha,1)$ ...
0
votes
1answer
21 views

Optimization: KKT conditions statement

I'm currently following this material http://www.math.uh.edu/~rohop/fall_06/Chapter2.pdf And I can't understand why the following statement is true, between the equations (2.9) and (2.10): "The ...
0
votes
0answers
22 views

To minimize surface area of integer cuboid of ​​the known volume

There is a cuboid (a * b * c), (a, b, c ∈ N). S (Surface area of a cuboid) = 2 * (ab + bc + ca). V (Volume of a cuboid) = a * b * c = n. I need to minimize S, provided that I specified the volume ...
0
votes
0answers
22 views

Adjust previous optimal solution to new assignment problem

Suppose I have an assignment problem with $n$ workers and $n$ jobs and its optimal solution. Now another worker and another job comes along and we are given all new costs. Is there an efficient ...
0
votes
1answer
27 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...
2
votes
1answer
303 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
4
votes
1answer
267 views

Derivation of Euler-Lagrange equation

Here is a simple (probably trivial) step in the derivation of the Euler-Lagrange equation. If we denote $Y(x) = y(x) + \epsilon \eta(x) $, I want to know why is $\dfrac{\partial ...
1
vote
0answers
45 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
0
votes
2answers
26 views

Minimum of a function $f(x,y)=\frac{(1+2y)(1+\frac{x}{2})}{(1+y)(1+x)+x}$

what is the minimum of a function \begin{align} f(x,y)&=\frac{(1+2y)(1+\frac{x}{2})}{(1+y)(1+x)+x}\\ \text {s.t. }& 1 \le y \le x \le y(1+y) \end{align} I asked Wolfram and Alfa and it says ...
-1
votes
0answers
31 views

Relaxed optimization [duplicate]

I am facing an optimization problem $\max f(X)$ Can I solve a relaxed optimization problem $g(X)$ $\max g(X)$ if I can prove that $g(X)> f(X)$.
-2
votes
0answers
22 views

Relaxation of optimization problem [duplicate]

Can I solve the following optimization problem, $$f= \max \{h(Y) - h(Y|U)\}$$ by solving an easier upperbound on $f$ for example $g > f$ where $g= \max\{h(Y)-h(Z)\}$. My aim is to prove that ...
0
votes
1answer
24 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
7
votes
1answer
359 views

Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
0
votes
1answer
16 views

multivariate piecewise-linear equality constraint in optimization problem

I have an optimization problem of the type: $\min f(x) \\ s.t. Ax \le b \\ g(x)=0 $ where $g(x)$ is a piecewise-linear function defined as: $g(x) = \begin{cases} c_1^Tx & \text{if $x_1+x_2-x_3 ...
1
vote
0answers
12 views

Minimizing sample variance of $n$ functions

$f_n$, $i=1,\dots, n$ are $n$ functions. I would like to minimize the sample variance of these functions subject to a linear constraint: $$\text{minimize}\quad \frac{1}{N}\sum (f_i(x_i) - ...
3
votes
2answers
96 views

Maximization of $x+y$ when each is greater than $1$ and $xy = 16$.

The product of two numbers $x$ and $y$ is $16$. We know $x\ge 1$ and $y\ge 1$. What is the greatest possible sum of the two numbers?
1
vote
1answer
25 views

Do lagrangian multipliers converge to dual variables in LPs?

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal ...
1
vote
1answer
26 views

How to show that these two versions of Farkas lemma are equal?

One version of Farkas lemma is that Let $A$ be a real $m\times n$ matrix and $b$ an $m$-dimensional real vector. Then, exactly one of the following statements are true. There exists an ...
1
vote
0answers
11 views

Homework-Second derivative of a multivariate function

Let $f(x):\mathbb{R}^n\rightarrow\mathbb{R}$, and let $\theta(\alpha)=f(x+\alpha s)$ where $\alpha\in\mathbb{R}$ and $x,s\in\mathbb{R}^n$, the goal is to find $\theta''(\alpha)$. I guess that the ...
0
votes
0answers
11 views

Stage wise optimization

Are the following two optimization problems equivalent $$ \min_{x\in\{0,1\}} c^T x+ \min_{y\geq 0} \bigg\{q^T y | Ty+Wx\leq h\bigg\}\\ s.t., \\ Ax\leq b$$ and $$ c^T x +q^T y\\ s.t,\\ Ax\leq b\\ ...
0
votes
1answer
24 views

Optimization Problem of Two Variables, One Dependent

I am actually working on a program of sorts. This program takes a user entered value that specifies how many white keys they can span with one hand on a piano. It then computes (based on research) the ...
2
votes
1answer
41 views

min : sum of L2 norm and squared-L2 norm.

Is there a closed-form solution of the following convex problem: $$\min_x \| x - u \| + C \| x - v \|^2$$ where $\| \cdot \|$ is the L2 norm.
0
votes
0answers
18 views

how i could show that $f$ is a constant if it has intermediate value and local extremum properties? [duplicate]

let $ f\colon R\to R $ be a function with intermediate value property . if $f$ has a local extremum at every point $x\in R $ . my question is how i could show that $f$ is constant ? I would be ...
1
vote
1answer
23 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
2
votes
2answers
56 views

Find the smallest $a>1$ such that $\frac{a+\sin x}{a+\sin y} \leq e^{(y-x)}$ for all $x \leq y$

Can anyone please help me with the following question: Find the smallest $a>1$ such that $$\frac{a+\sin x}{a+\sin y} \leq e^{(y-x)}$$ for all $x \leq y$ My attempt: I think we should rearrange ...
2
votes
1answer
23 views

Shared groceries expenses between roommates to be divided as per specific consumption ratio and attendance

My apologies if this question is in the wrong section. Couple of my roommates & I (total 5 people) share the groceries expenses. We record the purchases in an Excel sheet, and also have the ratio ...
0
votes
0answers
11 views

Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
0
votes
0answers
16 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
0
votes
2answers
332 views

How to calculate the hessian of a matrix function

I am estimating a model minimizing the following objective function, $ M(\theta) = (Z'G(\theta))'W(Z'G(\theta))$ $Z$ is an $N \times L$ matrix of data, and $W$ is an $L\times L$ weight matrix, ...
1
vote
2answers
78 views

How do you maximize a polynomial over an integer domain?

I am working on maximizing the polynomial $f:\mathbb{R}^N \rightarrow \mathbb{R}$ $$f(v):=\prod_{i=1}^{N}( v_i+\alpha_i^2)$$ over integer $n$-partitions of $P$, $n\leq N$: $$\left\{v \left|\, v_i \in ...
2
votes
0answers
16 views

How to orthogonalize a set of 2x2 matrices?

I have set of 2D affine transformations of images and I need to modify the transformations such way that they become as close to rotations as possible to minimize distortions of images. Let the ...
2
votes
1answer
19 views

Solving first order constraints; lagrangian function and utility maximisation

I am supposed to find the demand curve if the following is given; $U(x,y) = xy$ price of $x * x$ + price of $y * y = m$ (so a general case, and I will be adding certain prices and income levels ...
0
votes
1answer
47 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
0
votes
1answer
25 views

Why Am i standing in a global minimum?

I`been asked the following in optimization If I am located in a point where all the possible factible directions turn out to be worse for the function, Am I located in a global minimum? The answer is ...
0
votes
0answers
14 views

Optimize the distribution if it is left unsmoothed

I have a question about distribution. Let see my problem The paper said that the distributions p and q are left unsmoothed, so we can ignore Kernel density. But I don't understand what is left ...
2
votes
4answers
98 views

Minimizing $\tan^2 x+\frac{\tan^2 y}{4}+\frac{\tan^2 z}{9}$

Given that $\tan x+2\tan y+3\tan z=40 , \ \ \ x,y,z \in \left(\dfrac{\pi}{2},\dfrac{3\pi}{2}\right),$ We need to find the minimum value of $ \tan^2 x+\dfrac{\tan^2 y}{4}+\dfrac{\tan^2 z}{9}$ ...
-2
votes
0answers
13 views

The projected global optimum of a funtion onto the simplex to obtain the optimum in the simplex? [closed]

One determines the global optimum of a funtion in the space by skipping the constraints. Now by projection the founded optimum into the simplex, which is define in such a way that the initial ...
0
votes
1answer
19 views

minimising total cost

A publishing company sells 75000 books during a year It costs a publishing company 0.6 dollars to store a book for a year. Each time they print additional copies, setting up the printers cost $2500. ...
1
vote
2answers
50 views

minimal value of $x^2+2y^2+5z^2$ with constraint.

$x,y,z>0$, and $xy+yz+zx=1$. I need to find the minimum value of $x^2+2y^2+5z^2$ In general what can we say about the minimal value of $\frac{ax^2+by^2+cz^2}{xy+xz+yz}$, over all positive numbers ...
1
vote
2answers
310 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
3
votes
3answers
40 views

linear solution of curve fitting on multiple linear functions differing by a multiplier

I recently posted this question here but I thought this could be of interest also in mathematics, given I found a partially related question here I am facing the following problem. I know nonlinear ...
1
vote
1answer
34 views

Why don't we go beyond the Hessian in multivariate optimization?

In univariate optimization, we perform the first derivative test to identify stationary points and the second derivative test to classify the stationary points as minima, maxima and inconclusive. When ...
0
votes
0answers
34 views

Vertices of Polyhedral

Suppose there are matrix $A\in\mathbb{R}^{n \times m}$ and vector $b\in\mathbb{R}^n$. Consider a non-empty polyhedron $P = \{Ax \leq b\} $. Then, there exists a vector $\bar{x}\in P $ such that ...
1
vote
1answer
39 views

Constrained Optimization : Minimize sum of dot products

I am working on a problem to minimize sum of dot product. The problem can be stated as following. Given a matrix where each element is either 0 or 1. $$ \ A_{ij} = \{0,1\}; $$ with the constraint ...
1
vote
0answers
19 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.
0
votes
2answers
49 views

Cost per item. Diminishing marginal discount, if you will. (Bigger discount for first few items) Optimal number of units to buy?

The graph above shows price per unit. Say they are cupcakes. When you buy a higher quantity, you get a lower price per unit. Say it levels off like this graph. Obviously, buying 2 nets a nice ...
13
votes
1answer
354 views

Can a dynamic programming problem be transformed into a linear algebra problem?

Here is a simple standard economic problem: Let Robin Crusoe have an endowment $w_0$ of lembas bread. She is immortal and discounts at a rate of $\beta$ per period. Each period (from $t=0$ on) she ...