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)

1
vote
1answer
120 views

Why is Newton's method faster than gradient descent?

Can you provide some intuition as to why Newton's method is faster than gradient descent? Often we are in a scenario where we want to minimize a function f(x) where x is a vector of parameters. To do ...
1
vote
1answer
53 views

dijkstra's algorithm in time O(k|V|+|E|)

Can somebody can help me with this problem: I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the ...
1
vote
0answers
55 views

Efficiently deleting 2s from a random NxM matrix

Edit: There were 2 important logic errors in the code below. They have been fixed! update: I still don't have an answer to this question, but I recently made a massive improvement to my current ...
1
vote
2answers
43 views

Linear systems of inequations

Ok so I have a systems with $6$ inequations and $3$ variables, and a point that may or may not solve this system. To check whether this point solves the inequations is straightforward, my problem is ...
1
vote
1answer
52 views

Maximization of a ratio

Edit: Removed solved in title, because I realize I need someone to check my work. Ok, so the problem is a lot more straight forward than I originally approached it (which was a false statement -- so ...
1
vote
0answers
15 views

Given two non-negative vectors $r,c$, is there always a non-negative matrix A whose marginals are $r$ and $c$?

Let $A$ be an nxm matrix. We can easily determine its row and column marginals $r$ and $c$: $r=A1$ $c=1^TA$. Suppose however, that you are given non-negative marginals $r,c$. Is there always a ...
1
vote
0answers
55 views

Is there any way to transform a non-convex optimization problem into a convex one?

I have an optimization problem which is described as $$\begin{array}{ll} \text{minimize}_x & c^{T}x\\ \text{subject to} & Gx \preceq h\\ & -x^{T}Px - qx - r \leq 0 \end{array} $$ where ...
1
vote
0answers
52 views

Maximum of a convolution

I have a function $f:{\mathbb R}\rightarrow {\mathbb R}_+$ which has a unique maximum at $x=0$. $f$ can be symmetric or asymmetric. I am interested on the mollified-f function ...
1
vote
1answer
37 views

How many samples of $y$ and $x$ given variances?

On a homework problem, I am given two variables, $x$ and $y$, with variances $4$ and $16$, respectively. The question is how many observations should I draw of $y$ in order to estimate the difference ...
1
vote
1answer
37 views

Linear independence of equality constraint gradients in constraint qualifications

I'm, trying to get an intuitive feel for the various constraint qualifications for KKT points. Most of them seem to rely on the linear independence of $\nabla g_i(x^*)$ where $g_i$ are the equality ...
1
vote
2answers
52 views

Intersection of two lines and the minimum of the sum of the two.

We use a formula in my Operations Research class for finding the 'Economic Order Quantity', given the cost function (sum of Holding and Ordering costs) $$C = \frac{Q}{2}H+\frac{D}{Q}S$$ where $Q$ is ...
1
vote
1answer
94 views

Find global and local maxima and minima, given the graph of the function

My attempts were local max: 3,8 - local min: 5 - global max= 3, global min= 5 Module is giving me incorrect. No partial credit. So I can't tell where the problem lies. local max: 6, 4.?? local ...
1
vote
0answers
23 views

Find maximum hyperplane separating two classes by optimizing the Langrangian function.

I am trying to solve the following problem: I am having difficulty starting. I know this is a constrained optimization problem for support vector machines. I am wondering how the training data is ...
1
vote
0answers
31 views

Reduce degree of a high degree unconstrained binary term to quadratic unconstrained binary term

I'm working on a optimization project, in this project I have to convert higher order unconstrained binary polynomial to quadratic unconstrained binary polynomial. Can anyone give me a hint of how to ...
1
vote
0answers
27 views

A sufficient condition for a good to be normal

Context: there are $2$ goods with prices $P_1$ and $P_2$ and the decision maker has the utility function $U(C_1,C_2)$. Denote $U_j=\frac{\partial U(C_1,C_2)}{\partial C_j}$ for $j\in\{1,2\}$. A good ...
1
vote
0answers
25 views

Basic linear optimisation problem

I want to solve the following problem: A company uses cement and three different ways of production $P_1$, $P_2$ and $P_3$ to produce the products P,Q,R and S. For one ton of cement, the ...
1
vote
0answers
43 views

Legendre transform and Minimax Theorems.

Denote the class of lower-semi-continuous convex functions $f:\mathbb{R}^n\to \mathbb{R}\cup\{\pm\infty\}$ by $Lscx(\mathbb{R}^n)$ ( so that only function attaining the value $-\infty$ is the constant ...
1
vote
1answer
40 views

Deleting 0's from a random mod 2 matrix

I am fairly new to optimization problems, so please forgive my lack of knowledge. That said, I'm trying to write a program that takes an NxM matrix randomly filled with 0's and 1's, then reduces this ...
1
vote
0answers
56 views

Mixed-Integer Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using Mixed-Integer Linear Programing ? I would like to get the variable $a$ in this description : $$ i = 1,\ldots,m ...
1
vote
0answers
32 views

Partial concave maximization of subset of variables

Let $f(x_1, \dots, x_N)$ be a concave function in $x_1, \dots, x_N$. For arbitray $n>1$, prove that the (constrained) truncated function defined by $$g(x_1, \dots, x_{n-1}) = \max_{x_n, \dots, x_N ...
1
vote
0answers
104 views

Line search Armijo, Wolfe, Strong Wolfe and Goldstein.

What are the articles (References) who proposed the line search of Armijo, Wolfe, Strong Wolfe, and Goldstein? Articles precursors of unidirectional searches?
1
vote
1answer
41 views

Algorithms: Maximizing $\Pi \, a^{b}$ (NOTE: Homework)

First I would like to say that this is a homework assignment, so I'm not looking for someone to give me a solution. Just a little guidance if what I have is wrong or inefficient: Given two sets $A$ ...
1
vote
0answers
57 views

Least squares with three quadratic constraints (Ellipse fitting based on algebraic distance)

I would like to fit an ellipse to a given set of scattered data in $\mathcal{R}^2$. The fitting problem is in form least squares, minimizing the sum of squared algebraic distances \begin{equation} ...
1
vote
0answers
42 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
1
vote
0answers
22 views

Need guidance on a Queuing problem

I can't really go into specifics, I'm more just looking for terms that I can research to get on the right track. Classes of model/processes etc. A close analogy to my problem: I need to optimally ...
1
vote
0answers
24 views

How to transform equivalent optimization problems

Can somebody either explain how to show the equivalence of the three alternative optimization problems in MPT (or point me to some literature)? I am looking for the necessary "algebraic steps" if at ...
1
vote
0answers
38 views

When result of max of min problem is equal to min of max problem

Let's assume there are two functions $f(x)$ and $g(x)$. I want to know when the optimal $x$ of max of min of $f(x)$ and $g(x)$ is not equal to optimal $x$ of min of max of $\frac{1}{f(x)}$ and ...
1
vote
0answers
30 views

Independent variables in optimization

I'm not sure whether I'm asking very obvious/stupid question, but essentially I'm looking for references. I am looking for the notion of independence in the context of optimization problems (I am ...
1
vote
1answer
75 views

Transversality conditions in optimal control with non-linear final pay-off

I have a doubt regarding transversality condition in the case of a non linear final pay-off. For instance, I need to solve with the Pontryagin maximum principle the following optimization problem ...
1
vote
0answers
143 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
1
vote
0answers
78 views

Find all $(x,y)$ pairs

Find all $x$ , $y$ $\in$ $\mathbb {R^+}$ such that for all $\epsilon>0$, $$x \left(\dfrac{\ln \left(1+\dfrac{1}{x}\right)-2\epsilon}{\ln xy-(1-\epsilon)}\right)\geq \left(\dfrac{\ln ...
1
vote
1answer
76 views

Meal Platters Optimization Problem

Mark has to buy hamburgers, hot dogs, and pig's feet for an event. The restaurant he is purchasing from offers two Platter options. Platter A comes with 4 hamburgers, 3 hot dogs, and 2 pig's feet. ...
1
vote
0answers
17 views

Weierstrass conditions, what does strong mean, and are both conditions required?

I have the Weierstrass condition: In order that the extremal $\bf{C^*}: x = x^*(t)$ give a strong local minimum to $\bf{J[x]}$ it is sufficient that: # ...
1
vote
0answers
31 views

Check my solution for optimization problem

A piece of wire 40 units long is to be cut into two pieces. One piece will be bent to form a circle; the other will be bent to form a square. Find the minimum and maximum values of the area. I found ...
1
vote
0answers
35 views

Is there any standard way to handle fractions of bilinear constraints in optimization?

By fractional bilinear constraints, I mean this form: $$\frac{a_1 + a_2 + a_3 + \cdots}{b_1 + b_2 + b_3 + \cdots} \frac{c_1 + c_2 + c_3 + \cdots}{d_1 + d_2 + d_3 + \cdots}$$ Here, $a,b,c,d$ are ...
1
vote
1answer
95 views

Argument to “linearize” an objective function

I have this optimization problem on the variables $\lambda_\ell^+, \lambda_\ell^-$ such that $ \lambda_\ell^+ \geq \lambda_\ell^-$ with $\ell=1,\ldots,n$ , and fixed $P\in [1/(n+1),1]$ \begin{align} ...
1
vote
0answers
67 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
1
vote
0answers
46 views

Minimizing a function using a direct approach (no Lagrange multipliers).

I want to minimize $g = x^2 + y^2$. My constraint is $h = 2x +y = l$. I know that using Lagrange multipliers is unnecessary here. I solved the constraint to get $y = l - 2x$. I then substituted this ...
1
vote
0answers
76 views

What is a good optimization textbook for the theoretically inclined student looking for a rigorous and concise proof-based book?

I'm looking for an optimization book that is more like a classic pure math textbook without requiring any actual prior pure math courses. A book that puts focus on the theoretical aspects of ...
1
vote
1answer
52 views

Proving a point is a local minimum

I have a rather basic question. I have a function $f:R \rightarrow R$, and I want to show a point, $x^*$, is local minimum, i.e., $f(x^*+\delta) \geq f(x^*), \ \delta \to 0$. I can show that: $f(x^* ...
1
vote
1answer
27 views

Modelling problem

i have this problem and i have to model it in a boolean formula. Assuming that variables can have value 0 or 1 and V is OR and ∧ is AND. I have n boolean variables x1,x2......xn. i want a formula ...
1
vote
1answer
22 views

For single variable, being $x^*$ a local minimzer, suppose $|x-x^*|=\epsilon$. Find bounds on $|f(x)-f(x^*)|$ and $|f'(x)-f'(x^*)|$.

Im studying for a test on unconstrained optimization and completing exercises from a book that doesn't give the solution to all of them. This is one of them, I aren't sure if I am going the right way: ...
1
vote
0answers
33 views

maximum likelihood of a dirichlet prior

Suppose $\theta \sim D(\alpha)$ where $D$ denotes the Dirichlet distribution and $\alpha = (\alpha_1,\ldots,\alpha_K)$ its hyperparameter, in which case: $$p(\theta) = \frac{\Gamma(\sum_k ...
1
vote
1answer
50 views

Integer Optimization

I have an integer optimization problem that I've been pondering for the last several days. Here's an abbreviated version: I have several wav song files with variable sizes (601201 kilobytes for ...
1
vote
0answers
28 views

Approximating the max value of a function containing the half-sum of binomial series

I recently met a problem and I have been finding related materials about it. However it is still hard to handle. Precisely, I want to maximize a function related to $$S_n = \sum_{i=0}^{\lfloor ...
1
vote
0answers
23 views

Condition that multiplied hermitian matrix stays hermitian

Suppose we are given a hermitian matrix $E \in \mathbb{C}^{n\times n}$. I want to find sufficient conditions on the entries of a real symmetric matrix $M$ (depending on the entries of the given ...
1
vote
0answers
91 views

Solving Optimal Control with non linear cost function

I am trying to solve the Kermak Mc-Kendrick SIR model using a non linear cost function, but I am stuck on how to possibly solve it. I need to find an optimal control $u(t)$ in $[0,T]$ that minimize: ...
1
vote
2answers
39 views

Curiosity - maximising a product with a constraint

I have integers greater than 4, for instance $i_1$, $i_2$, $i_3$, ..., $i_n$. We have to change the greatest of these integers (for instance $i_1$ if they are ranked by descending order) by adding to ...
1
vote
1answer
130 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
1
vote
0answers
27 views

Extremal condition for series expansion coefficients

I want to maximize a coefficient in a series expansion, so the situation is the following. $f \in C^{\infty}$ and $f: \mathbb{R} \times \mathbb{R} \times [0,2 \pi] \rightarrow \mathbb{C}$. Now, we ...